A Formal Context for Symmetric Dependencies
Armstrong and symmetric dependencies are two of the main groups of dependencies in the relational database model, both of them having their own set of axioms. The closure of a set of dependencies is the largest set of dependencies that can be calculated b
- PDF / 477,894 Bytes
- 16 Pages / 430 x 660 pts Page_size
- 68 Downloads / 179 Views
Abstract. Armstrong and symmetric dependencies are two of the main groups of dependencies in the relational database model, both of them having their own set of axioms. The closure of a set of dependencies is the largest set of dependencies that can be calculated by the recursive application of those axioms. There are two problems related to a closure: its calculation and its characterization. Formal concept analysis has dealt with those problems in the case of Armstrong dependencies (that is, functional dependencies and alike). In this paper, we present a formal context for symmetric dependencies that calculates the closure and the lattice characterization of a set of symmetric dependencies.
1 Introduction Dependencies are restrictions that apply over a set of data (we assume that, generally speaking, a set of data is a set of fixed length tuples or records that have a common set of attributes). They usually indicate a relationship between sets of attributes that exist in that set of data, and may be found in different realms, as in database theory, artificial intelligence, propositional logic, knowledge discovery, algebra, etc ([1,5,7,8,22]). Every type of dependency has a (semantical) definition that indicates the conditions that must exist in the set of data for those dependencies to hold. For instance, a func−→ tional dependency X fd Y , where X and Y are sets of attributes, holds in a set of data if the values of the attributes Y can be determined by the values of the attributes X, as Example 1 shows. Example 1. We have the set of data R: Name P.D. James de Pedrolo M. Bukowski C. Durrell L. Gombrowicz W. Plenzdorf U.
Birth Place Birth Year Oxford 1920 L’Arany´o 1918 Berlin 1920 Jalandhar 1912 Małoszyce 1904 Berlin 1934
R. Medina and S. Obiedkov (Eds.): ICFCA 2008, LNAI 4933, pp. 90–105, 2008. c Springer-Verlag Berlin Heidelberg 2008
A Formal Context for Symmetric Dependencies
91
The columns are identified with the attribute names Name, Birth Place, Birth Year and each row represents a record or a tuple. In this case, we have that, given Name, we can deduce Birth Place and Birth Year. For instance, if we are given C. Bukowski, we know that the birth place and birth year are Berlin and 1920. But given Birth Year, we cannot deduce Name, since if we are given the year 1920, the author’s name can be P.D. James or C. Bukowski. Neither do we have that Birth Place determines Name, since if we are given Berlin, the author’s name may be either C. Bukowski or U. Plenzdorf. −→ Therefore, we have that in this set of data, the functional dependency {N ame} fd −→ {Birth Place,Birth Year} holds, but that {Birth Place} fd {Name} and {Birth Year} −→ fd {Name} do not hold. For each set of dependencies Σ we take all sets of data (a possibly infinite number of them) in which all the dependencies in Σ hold: R1 , R2 , . . . . Apart from all the dependencies in Σ, there may be some other dependencies not in Σ that may hold in all Ri as well. These dependencies, together with those in Σ are called the closure of Σ, and are r
Data Loading...
