A lattice view of functional dependencies in incomplete relations
Functional Dependencies (or simply FDs) are by far the most common integrity constraint in the real world. When relations are incomplete and thus contain null values the problem of whether satisfaction is additive arises. Additivity is the property of the equivalence of the satisfaction of a set of...
Saved in:
Main Author:  

Format:  Article 
Published: 
1995

Series:  Acta cybernetica
12 No. 2 
Kulcsszavak:  Számítástechnika, Kibernetika 
Subjects:  
Online Access:  http://acta.bibl.uszeged.hu/12555 
Summary:  Functional Dependencies (or simply FDs) are by far the most common integrity constraint in the real world. When relations are incomplete and thus contain null values the problem of whether satisfaction is additive arises. Additivity is the property of the equivalence of the satisfaction of a set of functional dependencies (FDs), F, with the individual satisfaction of each member of F in an incomplete relation. It is well known that, in general, satisfaction of FDs is not additive. Previously we have shown that satisfaction is additive if and only if the set of FDs is monodependent. Thus monodependence of a set of FDs is a desirable property when relations may be incomplete. A set of FDs is monodependent if it satisfies both the intersection property and the splitfreeness property. (The two defining properties of monodependent sets of FDs correspond to the two defining properties of conflictfree sets of multivalued data dependencies.) We investigate the properties of the lattice £(F) of closed sets of a monodependent set of FDs F over a relation schema R. We show an interesting connection between monodependent sets of FDs and exchange and antiexchange lattices. In addition, we give a characterisation of the intersection property in terms of the existence of certain distributive sublattices of £(F). Assume that a set of FDs F satisfies the intersection property. We show that the cardinality of the family .M(F) of meetirreducible closed sets in £(F) is polynomial in the number of attributes associated with R; in general, this number is exponential. Thus an Armstrong relation for F having a polynomial number of tuples in the number of attributes associated with R can be generated. As a corollary we show that the prime attribute problem can be solved in polynomial time in the size of F; in general, the prime attribute problem is NPcomplete. We also show that F satisfies the intersection property if and only if the cardinality of each element in A'i(F) is greater than or equal to the cardinality of the attribute set of R minus two. Using this result we are able to show that the superkey of cardinality k problem is still NPcomplete when F is restricted to satisfy the intersection property. Finally, we show that separatory sets of FDs are monodependent. 

Physical Description:  181207 
ISSN:  0324721X 