ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Queries Independent of Updates.

Alon Y. Levy, Yehoshua Sagiv: Queries Independent of Updates. VLDB 1993: 171-181
@inproceedings{DBLP:conf/vldb/LevyS93,
  author    = {Alon Y. Levy and
               Yehoshua Sagiv},
  editor    = {Rakesh Agrawal and
               Se{\'a}n Baker and
               David A. Bell},
  title     = {Queries Independent of Updates},
  booktitle = {19th International Conference on Very Large Data Bases, August
               24-27, 1993, Dublin, Ireland, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1993},
  isbn      = {1-55860-152-X},
  pages     = {171-181},
  ee        = {db/conf/vldb/LevyS93.html},
  crossref  = {DBLP:conf/vldb/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper considers the problem of detecting independence of a queries expressed by datalog programs from updates. We provide new insight into the independence problem by reducing it to the equivalence problem for datalog programs (both for the case of insertion and deletion updates). Equivalence, as well as independence, is undecidable in general. However, algorithms for detecting subclasses of equivalence provide sufficient (and sometimesalso necessary) conditions for independence. We consider two such subclasses. The first, query-reachability, generalizes previous work on independence[BCL89, E190], which dealt with nonrecursive programs with a single occurrence of the updated predicate. Using recent results on query- reachability [LS92, LMSS93], we generalize theseearlier independence tests to arbitrary recursive datalog queries with dense-order constraints and negated EDB subgoals. The second subclass is uniform equivalence (introduced in [Sa88]). We extend the results of [Sa88] to datalog programs that include dense-order constraints and stratified negation. Based on these extensions, we present new cases in which independence is decidable and give algorithms that are sound for the general case. Aside for their use in detecting independence, the algorithms for detecting uniform equivalence are also important for optimizing datalog programs.

Copyright © 1993 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Rakesh Agrawal, Seán Baker, David A. Bell (Eds.): 19th International Conference on Very Large Data Bases, August 24-27, 1993, Dublin, Ireland, Proceedings. Morgan Kaufmann 1993, ISBN 1-55860-152-X
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[BCL89]
José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. ACM Trans. Database Syst. 14(3): 369-400(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[El90]
Charles Elkan: Independence of Logic Database Queries and Updates. PODS 1990: 154-160 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GW93]
Ashish Gupta, Jennifer Widom: Local Verification of Global Integrity Constraints in Distributed Databases. SIGMOD Conference 1993: 49-58 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KKR90]
Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. PODS 1990: 299-313 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kl88]
Anthony C. Klug: On conjunctive queries containing inequalities. J. ACM 35(1): 146-160(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Levy93]
...
[LS92]
Alon Y. Levy, Yehoshua Sagiv: Constraints and Redundancy in Datalog. PODS 1992: 67-80 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LMSS93]
Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv, Oded Shmueli: Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions. PODS 1993: 109-122 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sa88]
Yehoshua Sagiv: Optimizing Datalog Programs. Foundations of Deductive Databases and Logic Programming. 1988: 659-698 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sh87]
Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ull88]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[vdM93]
Ron van der Meyden: The Complexity of Querying Indefinite Data about Linearly Ordered Domains. PODS 1992: 331-345 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:22:52 2010 by Michael Ley (ley@uni-trier.de)