Notions of dependency satisfaction

ABSTRACT

Two notions of dependency satisfaction, consistency and completeness, are introduced. Consistency is the natural generalization of weak-instance satisfaction and seems appropriate when only equality-generating dependencies are given, but disagrees with the standard notion in the presence of tuple-generating dependencies. Completeness is based on the intuitive semantics of tuple-generating dependencies but differs from the standard notion for equality-generating dependencies. It is argued that neither approach is the correct one, but rather that they correspond to different policies on constraint enforcement, and each one is appropriate in different circumstances. Consistency and completeness of a state are characterized in terms of the tableau associated with the state and in terms of logical properties of a set of first-order sentences associated with the state. A close relation between the problems of testing for consistency and completeness and of testing implication of dependencies is established, leading to lower and upper bounds for the complexity of consistency and completeness. The possibility of formalizing dependency satisfaction without using a universal relation scheme is examined.

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: AHO, A. V., SAGIV, Y., AND ULLMAN, J.D. Equivalence among relational expressions. SIAM J. Comput. 8, (2) (1979), 218-246.
• 3: BEERI, C., AND RISSANEN, J. Faithful representations of relational database schemes. Res. Rep. RJ 2722, IBM, 1980.
• 4: BEERI, C., AND VARDI, M.Y. On the complexity of testing implications of data dependencies. Dept. Comput. Sci., The Hebrew Univ., Jerusalem, Israel, 1980.
• 5: 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
• 6: 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]
• 7: Edward P. F. Chan , Alberto O. Mendelzon, Independent and separable database schemes, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588091]
• 8: 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]
• 9: CODD, E. F. Further normalization of the data base relational model. In Data Base Systems, R. Rustin, Ed. Prentice-Hall, N. J., 1972, pp. 33-64.
• 10: 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]
• 11: Herve Gallaire , Jack Minker, Logic and Data Bases, Perseus Publishing, 1978
• 12: GAREV, M. R., AND JOHNSON, D.S. Computers and Intractability. Freeman, San Francisco, 1979.
• 13: GRAHAM, M.H. Satisfying database states. Rep. CSRG-137, Univ. of Toronto, Toronto, Ont., Canada, Dec. 1981.
• 14: Marc H. Graham , Moshe Y. Vardi, On the complexity and axiomatizability of consistent database states, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588052]
• 15: GRAHAM, M. H., AND YANNAKAKIS, i. Independent database schemas. Jr. Comput. Syst. Sci. 28 (1984), 121-141.
• 16: 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]
• 17: Peter Honeyman, Testing satisfaction of functional dependencies, Journal of the ACM (JACM), v.29 n.3, p.668-677, July 1982 [doi>10.1145/322326.322330]
• 18: MAIER, D., MENDELZON, A. O., SADRI, F., AND ULLMAN, J. D. Adequacy of decompositions of relational databases. In Advances in Database Theory, H. Gallaire, J. Minker, and J. M. Nicolas, Eds. Plenum Press, New York, 198 l, pp. l0 l- l 14.
• 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: David Maier , Yehoshua Sagiv , Mihalis Yannakakis, On the Complexity of Testing Implications of Functional and Join Dependencies, Journal of the ACM (JACM), v.28 n.4, p.680-695, Oct. 1981 [doi>10.1145/322276.322280]
• 21: MCKINSEY, J. C.C. The decision problem for some classes of sentences without quantifiers. J. Symb. Logic 8 ( 1943), 61-76.
• 22: Alberto O. Mendelzon, Database states and their tableaux, ACM Transactions on Database Systems (TODS), v.9 n.2, p.264-282, June 1984 [doi>10.1145/329.318579]
• 23: 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]
• 24: RISSANEN, J. Theory of relations for databases--A tutorial survey. In Proceedings of the 7th Symposium on Mathematical Foundations of Computer Science (Poland, 1978). Lecture Notes in Computer Science, vol. 64. Springer-Vedag, New York, 1978, pp. 537-551.
• 25: Yehoshua Sagiv, Can we use the universal instance assumption without using nulls?, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582336]
• 26: VARDI, M. The implication problem for data dependencies in relational databases. Ph.D. Dissertation (in Hebrew). The Hebrew University in Jerusalem, Jerusalem, Israel, 1981.
• 27: VARDI, M.Y. Global decision problems for relational databases. In Proceedings of the 22nd IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1981, pp. 198-202.
• 28: VARDI, M.Y. The implication and finite implication problems for typed template dependencies. J. Comput. Syst. Sci. 28 (1984), 3-28.
• 29: Yannis Vassiliou, A formal treatment of imperfect information in database management, 1980
• 30: YANNAKAKIS, M. Algorithms for acyclic database schemes. In Proceedings of the 7th Conference on Very Large Databases (Cannes, France, Sept. 9-11 ). ACM, New York, 198 l, 82-94.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Complexity of proof procedures

General Terms:
Algorithms, Languages, Management, Measurement, Performance, Theory, Verification