Embedded implicational dependencies and their inference problem

ABSTRACT

It is shown that the general inference problem for embedded implicational dependencies (EIDs) is undecidable. For the more important case of finite inference (i.e., inference for finite data bases), the problem is not even recursively enumerable (r.e.); rather, it is complete in co-r.e. These results hold even for typed EIDs without equality, as well as for (untyped) template dependencies. The case for typed template dependencies remains open. The complexity of the inference problem for full dependencies has also been characterized - it is complete in exponential time for full implicational dependencies, and even for full typed template dependencies.

REFERENCES

• 1: Aho, A. V., C. Beeri, and J. D. Ullman, The theory of joins in relational data bases, 19th FOCS (Oct. 1977), pp. 107-113.
• 2: Beeri, C., On the membership problem for multivalued dependencies in relational databases, Tech. Rep. 229, Dept. EE and CS, Princeton Univ. (1977).
• 3: Beeri, C., On the role of data dependencies in the construction of relational databases, Tech. Rep. 43, Dept. CS, The Hebrew Univ., Jerusalem (1979).
• 4: Philip A. Bernstein, Synthesizing third normal form relations from functional dependencies, ACM Transactions on Database Systems (TODS), v.1 n.4, p.277-298, Dec. 1976 [doi>10.1145/320493.320489]
• 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: Catriel Beeri , Alberto O. Mendelzon , Yehoshua Sagiv , Jeffrey D. Ullman, Equivalence of relational database schemes, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.319-329, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804424]
• 7: Beeri, C. and M. Y. Vardi, On the properties of total join dependencies, Proc. XP1 Workshop on Relational Database Theory, Stony Brook, NY (June 1980). Also, Tech. Rep., Dept. of Comp. Sci., Hebrew Univ., Jerusalem (May 1980).
• 8: Chandra, A. K., D. C. Kozen, and L. J. Stockmeyer, Alternation, J, (to appear). Also, Tech. Rep. RC-7489, IBM Yorktown Heights (Jan 1978).
• 9: Chandra, A. K., H. R. Lewis, and J. A. Makowsky, Embedded implicational dependencies and their inference problem (extended abstract), Proc. XP1 Workshop on Relational Database Theory, Stony Brook, NY (June 1980).
• 10: Claude Delobel, Normalization and hierarchical dependencies in the relational data model, ACM Transactions on Database Systems (TODS), v.3 n.3, p.201-222, Sept. 1978 [doi>10.1145/320263.320271]
• 11: 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]
• 12: Ronald Fagin, Normal forms and relational database operators, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582120]
• 13: 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]
• 14: Galil, Z., An almost linear time algorithm for computing a dependency basis in a relational data base, IBM San Jose Tech. Rep. RJ2656 (Oct 1979).
• 15: Galvin, F., Horn sentences, Ann. Math. Log. 1 (1970) pp. 389-422.
• 16: Grant, J., and B. E. Jacobs, On generalized dependencies, to appear.
• 17: Hagihara, K., M. Ito, K. Taniguchi, and T. Kasami, Decision problems for multivalued dependencies in relational databases, SIAM J. Comp. 8, 2 (May 1979), pp. 247-264.
• 18: Lewis, H. R., Complexity results for classes of quantificational formulas, JCSS (to appear).
• 19: 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]
• 20: Maier, D., A. O. Mendelzon, F. Sadri, J. D. Ullman, Adequacy of decompositions of relational databases, Unpublished.
• 21: 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]
• 22: Paredaens, J., Transitive dependencies in a database scheme, R387 MBLE, Brussels (1979).
• 23: Parker, D. S., and K. Parsaye-Ghomi, Inference involving EMVDs and transitive dependencies, Tech. Rep., UCLA.
• 24: Jorma Rissanen, Independent components of relations, ACM Transactions on Database Systems (TODS), v.2 n.4, p.317-325, Dec. 1977 [doi>10.1145/320576.320580]
• 25: Rissanen, J., Theory of relations for databases - a tutorial survey, Proc. 7th Symp. on Math. Found. of Comp. Sc., Lect. Notes in CS 64, Springer-Verlag (1978), pp. 536-551.
• 26: 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]
• 27: Sagiv, Y., and S. Walecka, Subset dependencies as an alternative to embedded multivalued dependencies, Tech. Rep. UIUCDCS-R-79-980, Dept. of Comp. Sci., Univ. of Illinois (1979).
• 28: Tanaka, K., Y. Kamabayashi, and S. Yajima, Properties of embedded multivalued dependencies in relational databases, Tech. Rep. ER78-03, Dept. of Inf. Sc., Kyoto Univ. (Dec. 1978).
• 29: Tanaka, K., Y. Kambayashi, and S. Yajima, On the representability of decompositional scheme design with multivalued dependencies, Tech. Rep. ER79-01, Dept. of Inf. Sc., Kyoto Univ. (Jan 1979).
• 30: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 31: Yannakakis, M., and C. Papadimitriou, Algebraic dependencies, 21st FOCS, Syracuse, NY (Oct. 1980), pp. 328-332.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Mechanical theorem proving

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

General Terms:
Theory