Inference rules for functional and inclusion dependencies

ABSTRACT

A set Σ of functional dependencies and inclusion dependencies implies a single dependency σ if all databases (finite and infinite) which satisfy Σ also satisfy σ. This paper presents complete inference rules for deducing implications of inclusion and functional dependencies. The results of [5] suggest that the implication problem for functional and inclusion dependencies together has no simple axiomatization satisfying a natural set of conditions. Out of necessity, the inference rules presented here do not satisfy the conditions assumed in [5].

REFERENCES

• 1: Armstrong, W W Dependency Structures of Database Relationships Proc IFIP '74, 1974, pp 580-583
• 2: Catriel Beeri , Philip A. Bernstein, Computational problems related to the design of normal form relational schemas, ACM Transactions on Database Systems (TODS), v.4 n.1, p.30-59, March 1979 [doi>10.1145/320064.320066]
• 3: Catriel Beeri , Ronald Fagin , John H. Howard, A complete axiomatization for functional and multivalued dependencies in database relations, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada [doi>10.1145/509404.509414]
• 4: Catriel Beeri , Henry F. Korth, Compatible attributes in a universal relation, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588121]
• 5: Marco A. Casanova , Ronald Fagin , Christos H. Papadimitriou, Inclusion dependencies and their interaction with functional dependencies, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588141]
• 6: Peter Pin-Shan Chen, The entity-relationship model—toward a unified view of data, ACM Transactions on Database Systems (TODS), v.1 n.1, p.9-36, March 1976 [doi>10.1145/320434.320440]
• 7: Codd, E F Relational Completeness of Database Sublanguages In R Rustin, Ed, Data Base Systems, Prentice-Hall, New Jersey, 1972
• 8: E. F. Codd, Extending the database relational model to capture more meaning, ACM Transactions on Database Systems (TODS), v.4 n.4, p.397-434, Dec. 1979 [doi>10.1145/320107.320109]
• 9: Ronald Fagin, A normal form for relational databases that is based on domains and keys, ACM Transactions on Database Systems (TODS), v.6 n.3, p.387-415, Sept. 1981 [doi>10.1145/319587.319592]
• 10: Ronald Fagin, Horn clauses and database dependencies (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.123-134, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804660]
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: D. S. Johnson , A. Klug, Testing containment of conjunctive queries under functional and inclusion dependencies, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588138]
• 13: Paris C. Kanellakis , Stavros S. Cosmadakis , Moshe Y. Vardi, Unary inclusion dependencies have polynomial time inference problems, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.264-277, December 1983 [doi>10.1145/800061.808756]
• 14: Moshe Y. Varde, The implication and finite implication problems for typed template dependencies, Stanford University, Stanford, CA, 1982
• 15: Yannakakis, M and C H Papadimitriou Algebraic Dependencies Proc 21-st IEEE Symp on Found of Comp Sci, 1980, pp 328-332