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)

Előnézet

Cikk, tanulmány, mű cybernetica_012_numb_002_181-207.pdf Letöltés (1MB) | Előnézet

Absztrakt (kivonat)

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.

Mű típusa:	Cikk, tanulmány, mű
Befoglaló folyóirat/kiadvány címe:	Acta cybernetica
Dátum:	1995
Kötet:	12
Szám:	2
ISSN:	0324-721X
Oldalak:	pp. 181-207
Nyelv:	angol
Kiadás helye:	Szeged
Befoglaló mű URL:	http://acta.bibl.u-szeged.hu/38500/
Kulcsszavak:	Számítástechnika, Kibernetika
Megjegyzések:	Bibliogr.: p. 205-207. ; összefoglalás angol nyelven
Szakterület:	01. Természettudományok 01. Természettudományok > 01.02. Számítás- és információtudomány
Feltöltés dátuma:	2016. okt. 15. 12:26
Utolsó módosítás:	2022. jún. 13. 13:25
URI:	http://acta.bibl.u-szeged.hu/id/eprint/12555

Bővebben:

Tétel nézet