Unary inclusion dependencies have polynomial time inference problems

ABSTRACT

We study the interaction between unary inclusion dependencies (UIND's) and other known classes of dependencies, in the context of both unrestricted and finite implication. We provide complete axiomatizations for unrestricted and finite implication of UIND's and functional dependencies, and polynomial-time algorithms for the inference problems. The inference problem becomes, however, NP-hard, if we require that some attribute have a bounded domain. We show that for unrestricted implication, the interaction between UIND's and unary functional dependencies completely characterizes the interaction between UIND's and embedded implicational dependencies. Also, for finite implication, the interaction between UIND's and unary functional dependencies completely characterizes the interaction between UIND's and full implicational dependencies (but not UIND's and embedded implicational dependencies).

REFERENCES

• 1: A. V. Aho , C. Beeri , J. D. Ullman, The theory of joins in relational databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.297-314, Sept. 1979 [doi>10.1145/320083.320091]
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: W.W. Armstrong, "Dependency Structures of Database Relationships", Proc. IFIP 74, (1974).
• 4: 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]
• 5: 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]
• 6: F. Bancilhon , N. Spyratos, Update semantics of relational views, ACM Transactions on Database Systems (TODS), v.6 n.4, p.557-575, Dec. 1981 [doi>10.1145/319628.319634]
• 7: C. Beeri, M.Y. Vardi, "A Proof Procedure for Data Dependencies", Technical Report, Department of Computer Science, The Hebrew University of Jerusalem, (December 1980).
• 8: C. Beeri, M.Y. Vardi, "On Acyclic Database Decompositions", to appear.
• 9: C. Beeri, M.Y. Vardi, "Formal Systems for Tuple and Equality Generating Dependencies", Hebrew Univ. of Jerusalem Technical Report (April 1981), to appear in SICOMP.
• 10: 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]
• 11: 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]
• 12: Stavros S. Cosmadakis , Christos H. Papadimitriou, Updaies of relational views, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588096]
• 13: A. Chandra and M.Y. Vardi, Private communication, 1983.
• 14: B. Dreben, W.B. Godfarb, "The Decision Problem - Solvable classes of quantificational formulas", Addison-Wesley, (1979).
• 15: 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]
• 16: 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]
• 17: 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]
• 18: R. Fagin, M.Y. Vardi, "Armstrong Databases for Functional and Inclusion Dependencies", IBM Technical Report RJ3500 (1982), to appear in IPL.
• 19: Zvi Galil, An Almost Linear-Time Algorithm for Computing a Dependency Basis in a Relational Database, Journal of the ACM (JACM), v.29 n.1, p.96-102, Jan. 1982 [doi>10.1145/322290.322296]
• 20: 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
• 21: 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]
• 22: P.C. Kanellakis, "On the Computational Complexity of Cardinality Constraints in Relational Databases", IPL 11,2 (1980).
• 23: J.C. Mitchell, "The Implication Problem for Functional and Inclusion Dependencies", to appear (1983).
• 24: 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]
• 25: 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]
• 26: John Miles Smith , Diane C. P. Smith, Database abstractions: aggregation, Communications of the ACM, v.20 n.6, p.405-413, June 1977 [doi>10.1145/359605.359620]
• 27: M.Y. Vardi, "The Implication Problem for Data Dependencies in Relational Databases", Ph.D. Thesis, The Hebrew University of Jerusalem, (1981).
• 28: M.Y. Vardi, "On decomposition of relational databases", Proc. 23rdFOCS Conference, (1982).
• 29: M. Yannakakis, C.H. Papadimitriou, "Algebraic Dependencies", Proc. 21st IEEE FOCS (1980).

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models; Normal forms

General Terms:
Theory