Horn clauses and database dependencies (Extended Abstract)

ABSTRACT

In the last year or so, a number of generalizations of these dependencies have appeared: Nicolas's mutual dependencies [Ni], which say that a relation is the join of three of its projections; Rissanen's and Aho, Beeri, and Ullman's join dependencies ([Ri], [ABU]), which generalize further to an arbitrary number of projections; Paradaens' transitive dependencies [Pa], which generalize both FDs and MVDs; Sagiv and Walecka's subset dependencies [SW] which generalize embedded MVDs; and Sadri and Ullman's template dependencies [SU], which generalize embedded join dependencies. The purpose of this paper is to help bring order to the chaos by presenting certain mathematical properties shared by all of these dependencies. In Section 2, we introduce the concept of “faithfulness” (with respect to direct product), and show that IDs and EIDs are faithful, whereas slight variations are not necessarily faithful. In Section 3, we discuss “Armstrong relations”, which were known to exist in certain special cases (such as when the only sentences of interest were functional, multivalued, and join dependencies).In Section 4, we discuss finite Armstrong relations.In Section 5, we present some more counterexamples about the existence of Armstrong relations. In Section 6, we discuss projections of classes of relations. Although Zaiddan [Za] showed that projections of FD classes are not necessarily FD classes, it turns out that projections of FD classes (and, even more, of ID classes) are ID classes. In Section 7, we discuss certain extensions of our results.

REFERENCES

• 1: A. V. Aho, C. Beeri, and J. D. Ullman, The theory of joins in relational data bases. Proc. 19th IEEE Symp. on Foundations of Computer Science (Oct. 1977), 107–113.
• 2: W. W. Armstrong, Dependency structures of database relationships. Proc. IFIP 74, North Holland (1974), 580–583.
• 3: W. W. Armstrong , C. Deobel, Decompositions and functional dependencies in relations, ACM Transactions on Database Systems (TODS), v.5 n.4, p.404-430, Dec. 1980 [doi>10.1145/320610.320620]
• 4: C. Beeri, personal communication.
• 5: M. Brooks, Testing, tracing, and debugging recursive programs with simple errors. Ph.D. thesis, Stanford University, to appear.
• 6: E. F. Codd, Further normalization of the data base relational model. Courant Computer Science Symposia 6: Data Base Systems, May 24-25, 1971, Prentice Hall, 65–98.
• 7: H. B. Enderton, A Mathematical Introduction to Logic. Academic Press (1972).
• 8: Ronald Fagin, Multivalued dependencies and a new normal form for relational databases, ACM Transactions on Database Systems (TODS), v.2 n.3, p.262-278, Sept. 1977 [doi>10.1145/320557.320571]
• 9: R. Fagin, A normal form for relational databases that is based on domains and keys. IBM Research Report RJ2520 (May 1979), San Jose, California.
• 10: J. Grant and B. E. Jacobs, On generalized dependencies, to appear.
• 11: A. Heyting, Intuitionism: An Introduction. North Holland Publishing Co. (1956), Amsterdam.
• 12: A. Horn, On sentences which are true of direct unions of algebras. J. Symbolic Logic 16 (1951), 14–21.
• 13: David Maier , Alberto O. Mendelzon , Yehoshua Sagiv, Testing implications of data dependencies, ACM Transactions on Database Systems (TODS), v.4 n.4, p.455-469, Dec. 1979 [doi>10.1145/320107.320115]
• 14: J. M. Nicolas, First order logic formalization for functional, multivalued and mutual dependencies, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509269]
• 15: C. Papadimitriou and M. Yannakakis, Algebraic dependencies, to appear.
• 16: J. Paradaens, Transitive dependencies in a database scheme. R387(1979), MBLE, Brussels.
• 17: J. Rissanen, Theory of relations for databWases - a tutorial survey. Proc. 7th Symp. on Math. Found. of Comp. Science, Lecture notes in Comp. Science, 64, Springer-Verlag, 537–551.
• 18: Y. Sagiv and S. Walecka, Subset dependencies as an alternative to embedded multivalued dependencies. UIUCDCS-R-79-980 (1979), Dept. of Computer Science,Univ. of Illinois.
• 19: Yehoshua Sagiv , Claude Delobel , D. Scott Parker, Jr. , Ronald Fagin, An Equivalence Between Relational Database Dependencies and a Fragment of Propositional Logic, Journal of the ACM (JACM), v.28 n.3, p.435-453, July 1981 [doi>10.1145/322261.322263]
• 20: J. R. Shoenfield, Mathematical Logic. Addison-Wesley(1967).
• 21: A. M. Silva and M. A. Melkanoff, A methodology for inferring the dependencies of a relation, UCLA Technical Report.
• 22: J. R. Slagle and D. Koniver, Finding resolution proofs using duplicate goals in AND/OR trees. Inform. Sci. 4 (1971), 313–342.
• 23: Fereidoon Sadri , Jeffrey D. Ullman, A complete axiomatization for a large class of dependencies in relational datatbases, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.117-122, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804659]
• 24: A. Tarski, Contributions to the theory of Models I. Nederl. Akad. Wetensch. Proc. Ser. A, vol 57 (Indag. Math., vol 16) (1954), 572–588.
• 25: M. Yannakakis, private communication.
• 26: S. Zaiddan, personal communication.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

Additional Classification:
  E. Data
  E.0 GENERAL

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

General Terms:
Management, Theory