Polynomial-time implication problems for unary inclusion dependencies

ABSTRACT

Unary inclusion dependencies are database constraints expressing subset relationships. The decidability of implication for these dependencies together with embedded implicational dependencies, such as functional dependencies, are investigated. As shown by Casanova et al., the unrestricted and finite implication problems are different for the class of functional and unary inclusion dependencies; also, for this class and for any fixed k, finite implication has no k-ary complete axiomatization. For both of these problems, complete axiomatizations and polynomial-time decision procedures are provided: linear time for unrestricted implication and cubic time for finite implication. It follows that functional and unary inclusion dependencies form a semantically natural class of first-order sentences with equality, which although not finitely controllable, is efficiently solvable and docile. Generalizing from these results, it is shown that the interaction between functional and inclusion dependencies characterizes: (1) unrestricted implication of unary inclusion and all embedded implicational dependencies; (2) finite implication of unary inclusion and all full implicational dependencies; (3) finite implication of unary inclusion and all embedded tuple-generating dependencies. As a direct consequence of this analysis, most of the applications of dependency implication are extended, within polynomial-time, to database design problems involving unary inclusion dependencies. Such examples are tests for lossless joins and tests for complementarity of projective views. Finally, if one additionally requires that

REFERENCES

• 1: AANDERAA, S., AND LEWIS, H.R. Prefix classes of Krom formulas. J. Symb. Logic 38, 4 (1973), 628-642.
• 2: 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]
• 3: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 4: ARMSTRONG, W. W. Dependency structure of database relationships. In Proceedings IFIP 74. North-Holland, Amsterdam, 1974, pp. 580-583.
• 5: 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]
• 6: 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]
• 7: 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]
• 8: Catriel Beeri , Moshe Y. Vardi, The Implication Problem for Data Dependencies, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.73-85, July 13-17, 1981
• 9: BEERI, C., AND VARDI, M.Y. Formal systems for tuple and equality generating dependencies. SIAMJ. Comput. 13, 1 (1984), 76-98.
• 10: BEERI, C., AND VARDI, M.Y. On acyclic database decompositions. Inf. Control 61, 2 (I984), 75- 84.
• 11: Catriel Beeri , Moshe Y. Vardi, A Proof Procedure for Data Dependencies, Journal of the ACM (JACM), v.31 n.4, p.718-741, Oct. 1984 [doi>10.1145/1634.1636]
• 12: CASANOVA, M. A., FAGIN, R., AND PAPADIMITRIOU, C. H. Inclusion dependencies and their interaction with functional dependencies. Jr. Comput. Syst. Sci. 28, 1 (1984), 29-59.
• 13: M. A. Casanova , V. M. P. Vidal, Towards a sound view integration methodology, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588065]
• 14: Ashok K. Chandra , Harry R. Lewis , Johann A. Makowsky, Embedded implicational dependencies and their inference problem, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.342-354, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802488]
• 15: CHANDRA, A. K., AND VARDI, M. Y. The implication problem for functional and inclusion dependencies is undecidable. SIAM J. Comput. 14, 3 (1985), 671-677.
• 16: CODD, E. F. Further normalization of the database relational model. In Database Systems, R. Rustin, ed. Prentice-Hall, New York, 1972, pp. 33-64.
• 17: 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]
• 18: COSMADAKIS, S. S. Equational Theories and Database Constraints. Ph.D. dissertation. Massachusetts Institute of Technology, Cambridge, Mass., 1985.
• 19: S S Cosmadakis , P C Kanellakis, Equational theories and database constraints, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.273-284, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22176]
• 20: Stavros S. Cosmadakis , Paris C. Kanellakis, Two applications of equational theories to database theory, Proc. of the first international conference on Rewriting techniques and applications, p.107-123, December 1985, Dijon, France
• 21: COSMADAKIS, S. S., AND KANELLAKIS, P.C. Functional and inclusion dependencies: A graph theoretic approach. In Advances in Computing Research, vol. 3: The Theory of Databases. P. C. Kanellakis and F. Preparata, eds. JAI Press, Greenwich, Conn., 1986, pp. 164-185.
• 22: Stavros S Cosmadakis , Paris C Kanellakis , Nicolas Spyratos, Partition semantics for relations, Journal of Computer and System Sciences, v.33 n.2, p.203-233, Oct. 1986 [doi>10.1016/0022-0000(86)90019-X]
• 23: Stavros S. Cosmadakis , Christos H. Papadimitriou, Updates of Relational Views, Journal of the ACM (JACM), v.31 n.4, p.742-760, Oct. 1984 [doi>10.1145/1634.1887]
• 24: DATE, C. Referential integrity. In Proceedings of the 7th VLDB Conference, Morgan-Kaufmann, San Mateo, Calif., 198 l, pp. 2-12.
• 25: Peter J. Downey , Ravi Sethi , Robert Endre Tarjan, Variations on the Common Subexpression Problem, Journal of the ACM (JACM), v.27 n.4, p.758-771, Oct. 1980 [doi>10.1145/322217.322228]
• 26: DREBEN, B., AND GOLDFARB, W.B. The Decision ProblemmSolvable Classes of Quantificational Formulas. Addison-Wesley, Reading, Mass., 1979.
• 27: 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]
• 28: 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]
• 29: Ronald Fagin, Horn clauses and database dependencies, Journal of the ACM (JACM), v.29 n.4, p.952-985, Oct. 1982 [doi>10.1145/322344.322347]
• 30: FAGIN, R., AND VARDI, M.Y. Armstrong databases for functional and inclusion dependencies. Inf. Proc. Lett. 16, l (1983), 13-19.
• 31: FAGIN, R., AND VARDI, M.Y. The theory of data dependencies: A survey. In Mathematics of Information Processing, M. Anshel and W. Gewirtz, eds., Symposia in Applied Mathematics, vol. 34. Morgan-Kaufmann, San Mateo, Calif., 1986, pp. 19-72.
• 32: 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]
• 33: 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
• 34: Yuri Gurevich , Harry R. Lewis, The inference problem for template 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.588148]
• 35: JOHNSON, D. S., AND KLUG, A. Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Sci. 28, 1 (1984), 167-189.
• 36: KANELLAKIS, P. C. On the computational complexity of cardinality constraints in relational databases. Inf. Proc. Lett. 11, 2 (1980), 98-101.
• 37: 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]
• 38: Kent Laver , Alberto O. Mendelzon , Marc H. Graham, Functional dependencies on cyclic database schemes, Proceedings of the 1983 ACM SIGMOD international conference on Management of data, May 23-26, 1983, San Jose, California
• 39: 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]
• 40: John C. Mitchell, The implication problem for functional and inclusion dependencies, Information and Control, v.56 n.3, p.154-173, March 1983 [doi>10.1016/S0019-9958(83)80002-3]
• 41: PAREDAENS, J., AND JANSSENS, D. DecompoSitions of relations: A comprehensive approach. In Advances in Database TheorymVol. 1, H. Gallaire, J. Minker, and J-M. Nicolas, eds. Plenum Press, New York, 198 l, pp. 73-100.
• 42: RISSANEN, J. Theory of relations for databasesmA tutorial survey. In Proceedings of 7th Mathematical Foundations of Computer Science. Lecture Notes on Computer Science, Vol. 64. Springer-Verlag, New York, 1978, pp. 537-551.
• 43: Fereidoon Sadri , Jeffrey D. Ullman, Template Dependencies: A Large Class of Dependencies in Relational Databases and Its Complete Axiomatization, Journal of the ACM (JACM), v.29 n.2, p.363-372, April 1982 [doi>10.1145/322307.322312]
• 44: 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]
• 45: Edward Sciore, A Complete Axiomatization of Full Join Dependencies, Journal of the ACM (JACM), v.29 n.2, p.373-393, April 1982 [doi>10.1145/322307.322313]
• 46: SOORE, E. Comparing the universal instance and relational data models. In Advances in Computing Research, vol. 3: The Theory of Databases, P. C. Kanellakis, and F. Preparata, eds. JAI Press, Greenwich, Conn., 1986, pp. 139-163.
• 47: 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]
• 48: VARDI, M. Y. The implication problem for data dependencies in relational databases. Ph.D. dissertation. The Hebrew University, Jerusalem, Israel, 198 I.
• 49: VARDI, M.Y. On decompositions of relational databases. In Proceedings 23rd IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1982, pp. 176-187.
• 50: VARDI, M.Y. The implication and finite implication problems for typed template dependencies. J. Comput. Syst. Sci. 28, 1 (I984), 3-28.
• 51: YANNAKAKIS, M., AND PAPADIMITRIOU, C.H. Algebraic dependencies. J. Comput. Syst. Sci. 21, l (1982), 2-41.
• 52: Carlo Antonio Zaniolo, Analysis and design of relational schemata for database systems., 1976

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Normal forms

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Model theory

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General
          Subjects: Security, integrity, and protection**
      H.2.1 Logical Design
          Subjects: Schema and subschema

General Terms:
Algorithms, Design, Theory