Notions of dependency satisfaction

ABSTRACT

Two notions of dependency satisfaction, consistency and completeness, are introduced. Consistency is the natural generalization of weak 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 appears unnatural 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. The possibility of formalizing dependency satisfaction without using a universal relation scheme is examined.

REFERENCES

• 1: {ASU} Aho, A.V., Sagiv, Y., Ullman, J.D., "Equivalence Among Relational Expressions," SIAM J. Computing 8,2 (1979), 218-246.
• 2: {BR} Beeri, C., and Rissanen, J., "Faithful Representations of Relational Database Schemes," IBM Research Report RJ2722, 1980.
• 3: {BV1} Beeri, C., and Vardi, M., "A Proof Procedure for Data Dependencies," The Hebrew Univ., Dept. of Computer Science, Dec. 1980.
• 4: 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
• 5: {BV3} Beeri, C., and Vardi, M., "On the Complexity of Testing Implications of Data Dependencies," The Hebrew University, Dept. of Computer Science, Dec. 1980.
• 6: 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]
• 7: Marc Henry Graham, Satisfying database states, 1982
• 8: Herve Gallaire , Jack Minker, Logic and Data Bases, Perseus Publishing, 1978
• 9: Marc H. Graham , Mihalis Yannakakis, Independent database schemas, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588144]
• 10: Peter Honeyman, Functional dependencies and the universal instance property in the relational model of database systems, 1980
• 11: {M} Mendelzon, A.O., "Database States and their Tableaux," Proc. XP2 Workshop on Relational Database Theory, 1981.
• 12: 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]
• 13: {MMSU} Maier, D., Mendelzon, A.O., Sadri, F., and Ullman, J.D., "Adequacy of Decompositions of Relational Databases," J. Comp. and Sys. Sciences 21:3, 1980.
• 14: 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]
• 15: 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]
• 16: Yannis Vassiliou, A formal treatment of imperfect information in database management, 1980