Local verification of global integrity constraints in distributed databases

ABSTRACT

We present an optimization for integrity constraint verification in distributed databases. The optimization allows a global constraint, i.e. a constraint spanning multiple databases, to be verified by accessing data at a single database, eliminating the cost of accessing remote data. The optimization is based on an algorithm that takes as input a global constraint and data to be inserted into a local database. The algorithm produces a local condition such that if the local data satisfies this condition then, based on the previous satisfaction of the global constraint, the global constraint is still satisfied. If the local data does not satisfy the condition, then a conventional global verification procedure is required.

REFERENCES

• BCL89: 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]
• BBC80: P. A. Bernstein, B. T. Blaustein, and E. M. Clarke. Fast Maintenance of Semantic Integrity Assertions Using Redundant Aggregate Data. In Proceedings of the Sizth conference on Very Large Data Bases, pages 128-138, 1980.
• BB82: Philip A. Bernstein , Barbara T. Blaustein, Fast methods for testing quantified relational calculus assertions, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582361]
• BGM92: Daniel Barbará , Hector Garcia-Molina, The Demarcation Protocol: A Technique for Maintaining Linear Arithmetic Constraints in Distributed Database Systems, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.373-388, March 23-27, 1992
• Bla81: B.T. Blaustein. Enforcing Database Assertions: Techniques and Applications. PhD thesis, Harvard University, Cambridge, Massachusetts, Division of Applied Sciences, 1981.
• BMM92: François Bry , Rainer Manthey , Bern Martens, Integrity Verification in Knowledge Bases, Proceedings of the First Russian Conference on Logic Programming, p.114-139, September 14-18, 1990
• CG92: S. Ceri and F. Garzotto. Specification and Management of Database integrity Constraints through Logic Programming. Technical Report 88-025, Dipartimento Di Elettronica- Politecnico Di Milano, 1992.
• CG85: Stefano Ceri , Georg Gottlob, Translating SQL into relational algebra: optimization, semantics, and equivalence of SQL queries, IEEE Transactions on Software Engineering, v.11 n.4, p.324-345, April 1985 [doi>10.1109/TSE.1985.232223]
• CP84: Stefano Ceri , Giuseppe Pelagatti, Distributed databases principles and systems, McGraw-Hill, Inc., New York, NY, 1984
• C88: Ashok K. Chandra, Theory of database queries, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-9, March 1988, Austin, Texas, United States [doi>10.1145/308386.308396]
• Dav87: Ernest Davis, Constraint propagation with interval labels, Artificial Intelligence, v.32 n.3, p.281-331, July 1987 [doi>10.1016/0004-3702(87)90091-9]
• Elk90: 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]
• F82: 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]
• GU92: A. Gupta and J. D. Ullman. Generalizing Conjunctive Query Containment for View Maintenance and Integrity Constraint Checking. In Workshop on Deductive Databases, JICLSP, 1992.
• GW92: A. Gupta and J. Widom. Local Verification of Global Integrity Constraints in Distributed Databases. Technical Report, Stanford University, 1993.
• KSS87: Robert A. Kowalski , Fariba Sadri , Paul Soper, Integrity Checking in Deductive Databases, Proceedings of the 13th International Conference on Very Large Data Bases, p.61-69, September 01-04, 1987
• Kuc91: V. Kuchenhoff. On the Efficient Computation of the Difference Between Consecutive Database States. in Second international Conference, Deductive and Object.Oriented Databases, LNCS 566, pages 478-502, 1991.
• LST87: J. W. Lloyd , E. A. Sonenberg , R. W. Topor, Integrity constraint checking in stratified databases, Journal of Logic Programming, v.4 n.4, p.331-343, December 1, 1987 [doi>10.1016/0743-1066(87)90009-4]
• Nic82: J.M. Nicolas. Logic for Improving Integrity Checking in Relational Data Bases. Acta
• OV91: M. Tamer Ozsu , P. Valduriez, Principles of distributed database systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• Ull88: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• VT91: Allen Van Gelder , Rodney W. Topor, Safety and translation of relational calculus, ACM Transactions on Database Systems (TODS), v.16 n.2, p.235-278, June 1991 [doi>10.1145/114325.103712]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.3 Languages

          Nouns: SQL; Datalog

General Terms:
Algorithms, Design, Languages, Performance, Verification