On the Interaction between Transitive Closure and Data Dependencies

Authors
G. Gottlob, M. Schrefl, M. Stumptner
Paper
Gott89a (1989)
Citation
J. Demetrovics, B. Thalheim (eds.): FMDBS 89, Proceedings of the 2nd Symposium on Mathematical Fundamentals of Database Systems, Visegrad, Hungary, June 1989, Springer Verlag, Lecture Notes in Computer Science, LNCS Vol. 364, ISBN 3-540-51251-9, pp. 187-206, 1989.
Resources
Copy  (In order to obtain the copy please send an email with subject  Gott89a  to dke.win@jku.at)
BibTeX

Abstract

Closure dependencies, of CDs, are introduced to capture formally transitive closure relationships between (sequences of) attributes of a relational scheme, e.g., Part and Subpart. First, CDs are studied alone. The implication problem has a simple complete axiomatization. The interaction of CDs with functional dependencies (FDs) is investigated, leading to the following main results: CDs and FDs considered together imply new CDs, but no new FDs, i.e., no other FDs than those already implied by the given FDs alone. CDs together with FDs imply only longer CDs, i.e., CDs that contain more attributes, but not shorter ones. No k-ary axiomatization can fully describe the interaction between FDs and CDs: Although simple complete axiomatizations for CDs alone and FDs alone exist, there is no complete axiomatization for CDs and FDs taken together, in which every rule is k-ary for some fixed k. Finally, we define a generalized form of CDs and state a list of interesting open problems.