A lattice view of functional dependencies in incomplete relations

Levene Mark: A lattice view of functional dependencies in incomplete relations. In: Acta cybernetica, (12) 2. pp. 181-207. (1995)

[thumbnail of cybernetica_012_numb_002_181-207.pdf]
Cikk, tanulmány, mű

Download (1MB) | Preview


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 split-freeness property. (The two defining properties of monodependent sets of FDs correspond to the two defining properties of conflict-free 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 meet-irreducible 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 NP-complete. 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 NP-complete when F is restricted to satisfy the intersection property. Finally, we show that separatory sets of FDs are monodependent.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 1995
Volume: 12
Number: 2
ISSN: 0324-721X
Page Range: pp. 181-207
Language: English
Place of Publication: Szeged
Related URLs: http://acta.bibl.u-szeged.hu/38500/
Uncontrolled Keywords: Számítástechnika, Kibernetika
Additional Information: Bibliogr.: p. 205-207. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:26
Last Modified: 2022. Jun. 13. 13:25
URI: http://acta.bibl.u-szeged.hu/id/eprint/12555

Actions (login required)

View Item View Item