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

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb8997 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

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

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)
[El90]: Charles Elkan: Independence of Logic Database Queries and Updates. PODS 1990: 154-160
[GW93]: Ashish Gupta, Jennifer Widom: Local Verification of Global Integrity Constraints in Distributed Databases. SIGMOD Conference 1993: 49-58
[KKR90]: Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. PODS 1990: 299-313
[Kl88]: Anthony C. Klug: On conjunctive queries containing inequalities. J. ACM 35(1): 146-160(1988)
[Levy93]: ...
[LS92]: Alon Y. Levy, Yehoshua Sagiv: Constraints and Redundancy in Datalog. PODS 1992: 67-80
[LMSS93]: Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv, Oded Shmueli: Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions. PODS 1993: 109-122
[Sa88]: Yehoshua Sagiv: Optimizing Datalog Programs. Foundations of Deductive Databases and Logic Programming. 1988: 659-698
[Sh87]: Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249
[Ull88]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents
[vdM93]: Ron van der Meyden: The Complexity of Querying Indefinite Data about Linearly Ordered Domains. PODS 1992: 331-345