Constraint checking with partial information

ABSTRACT

Constraints are a valuable tool for managing information across multiple databases, as well as for general purposes of assuring data integrity. However, efficient implementation of constraint checking is difficult. In this paper we explore techniques for assuring constraint satisfaction without performing a complete evaluation of the constraints. We consider methods that use only constraint definitions, methods that use constraints and updates, and methods that use constraints, updates, and “local” data.

REFERENCES

• 1: José A. Blakeley , Neil Coburn , Per-:1Vke Larson, Updating derived relations: detecting irrelevant and autonomously computable updates, ACM Transactions on Database Systems (TODS), v.14 n.3, p.369-400, Sept. 1989 [doi>10.1145/68012.68015]
• 2: Stefano Ceri , Jennifer Widom, Deriving production rules for constraint maintenance, Proceedings of the sixteenth international conference on Very large databases, p.566-577, September 1990, Brisbane, Australia
• 3: Stefano Ceri , Jennifer Widom, Deriving Production Rules for Incremental View Maintenance, Proceedings of the 17th International Conference on Very Large Data Bases, p.577-589, September 03-06, 1991
• 4: 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]
• 5: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 6: Surajit Chaudhuri , Moshe Y. Vardi, On the equivalence of recursive and nonrecursive datalog programs, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.55-66, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137109]
• 7: Bruno Courcelle, Recursive queries and context-free graph grammars, Theoretical Computer Science, v.78 n.1, p.217-244, Jan. 21, 1991
• 8: Charles Elkan, Independence of logic database queries and update, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.154-160, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298557]
• 9: Gupta, A. {1994}. "Efficient Maintenance of Integrity Constraints and Views in Database Systems," Ph.D. thesis, Dept. of CS, Stanford University.
• 10: Gupta. A. and J. D. Ullman {1992}. "Generalizing conjunctive query containment for view maintenance and integrity constraint verification," Joint Intl. Conf. on Logic Programming, Workshop on Deductive Databases.
• 11: Ashish Gupta , Jennifer Widom, Local verification of global integrity constraints in distributed databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.49-58, May 25-28, 1993, Washington, D.C., United States
• 12: Anthony Klug, On conjunctive queries containing inequalities, Journal of the ACM (JACM), v.35 n.1, p.146-160, Jan. 1988 [doi>10.1145/42267.42273]
• 13: Alon Y. Levy , Yehoshua Sagiv, Queries Independent of Updates, Proceedings of the 19th International Conference on Very Large Data Bases, p.171-181, August 24-27, 1993
• 14: Nicolas, J.-M. {1982}. "Logic for improving integrity checking in relational databases," Acta Informatica 18:3, pp. 227-253.
• 15: Y. Sagiv, Optimizing datalog programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 16: Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980 [doi>10.1145/322217.322221]
• 17: O. Shmueli, Decidability and expressiveness aspects of logic queries, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.237-249, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28685]
• 18: F. W. Tompa , J. A. Blakeley, Maintaining materialized views without accessing base data, Information Systems, v.13 n.4, p.393-406, Oct. 1, 1988 [doi>10.1016/0306-4379(88)90005-1]
• 19: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 20: R. van der Meyden, The complexity of querying indefinite data about linearly ordered domains, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.331-345, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137902]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages
          Nouns: Datalog

General Terms:
Algorithms, Languages, Theory, Verification