Independence of logic database queries and update

ABSTRACT

A query is independent of an update if executing the update cannot change the result of evaluating the query. The theorems of this paper give methods for proving independence in concrete cases, taking into account integrity constraints, recursive rules, and arbitrary queries. First we define the notion of independence model-theoretically, and we prove basic properties of the concept. Then we provide proof-theoretic conditions for a conjunctive query to be independent of an update. Finally, we prove correct an induction scheme for showing that a recursive query is independent of an update.

REFERENCES

• Blaauw and Duijvestijn, 1985: G. A. Blaauw and A. J. W. Duijvestijn. View locking. In G. Bucci and G. Valle, editors, Computing 85: A Broad Perspective of Current Developments, pages 157-165. Elsevier Science Publishers B.V. (North-Holland), 1985.
• Blakeley et al., 1986: Jose A. Blakeley , Per-Ake Larson , Frank Wm Tompa, Efficiently updating materialized views, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.61-71, May 28-30, 1986, Washington, D.C., United States
• Blakeley et al., 1987: 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]
• Brodsky and Sagiv, 1989: A. Brodsky , Y. Sagiv, Inference of monotonicity constraints in datalog programs, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.190-199, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73741]
• Chamberlin et al., 1981: Donald D. Chamberlin , Morton M. Astrahan , Michael W. Blasgen , James N. Gray , W. Frank King , Bruce G. Lindsay , Raymond Lorie , James W. Mehl , Thomas G. Price , Franco Putzolu , Patricia Griffiths Selinger , Mario Schkolnick , Donald R. Slutz , Irving L. Traiger , Bradford W. Wade , Robert A. Yost, A history and evaluation of System R, Communications of the ACM, v.24 n.10, p.632-646, Oct. 1981 [doi>10.1145/358769.358784]
• Elkan and McAllester, 1988: Charles Elkan and David McAllester. Automated inductive reasoning about logic programs. In Kenneth Bowen and Robert Kowalsld, editors, Fifth International Conference Symposium on Logic Programming, volume 2, pages 876-892, Seattle, Washington, August 1988. MIT Press.
• Elkan, 1987: Charles P. Elkan, Adaptive Locking, Cornell University, Ithaca, NY, 1987
• Elkan, 1989: C. Elkan, A decision procedure for conjunctive query disjointness, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.134-139, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73735]
• Eswaran et al., 1976: K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
• Jordan et al., 1981: J. R. Jordan , J. Banerjee , R. B. Batman, Precision locks, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582340]
• Klug, 1983: Anthony Klug, Locking Expressions for Increased Database Concurrency, Journal of the ACM (JACM), v.30 n.1, p.36-54, Jan. 1983 [doi>10.1145/322358.322362]
• Naughton and Sagiv, 1987: J. F. Naughton , Y. Sagiv, A decidable class of bounded recursions, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.227-236, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28684]
• Reimer, 1983: Manuel Reimer, Solving the Phantom Problem by Predicative Optimistic Concurrency Control, Proceedings of the 9th International Conference on Very Large Data Bases, p.81-88, October 31-November 02, 1983
• Reiter, 1988: Raymond Reiter, On Integrity Constraints, Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning about Knowledge, p.97-111, March 01, 1988
• Ross, 1989: K. A. Ross, A procedural semantics for well founded negation in logic programs, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.22-33, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73724]
• Sagiv, 1987: Y. Sagiv, Optimizing datalog programs, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.349-362, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28696]
• Shmueli, 1987: 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]
• Subramanian and Genesereth, 1987: Devika Subramanian and Michael R. Genesereth. The relevance of irrelevance. In Proccedings of the Tenth International Joint Conference on Artificial Intelligence, pages 416-422, 1987.
• Ullman, 1988: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• Van Gelder and Topor, 1987: A. Van Gelder , R. Topor, Safety and correct translation of relational calculus formulas, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.313-327, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28693]
• Vardi, 1989: M. Y. Vardi, Invited talk: automata theory for database theoreticians, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.83-92, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73729]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming

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

General Terms:
Design, Management, Performance, Theory, Verification