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}
}
BibTeX

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 ... BibTeX

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 BibTeX

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

Referenced by

  1. Todd D. Millstein, Alon Y. Levy, Marc Friedman: Query Containment for Data Integration Systems. PODS 2000: 67-75
  2. Levent V. Orman: Differential Relational Calculus for Integrity Maintenance. IEEE Trans. Knowl. Data Eng. 10(2): 328-341(1998)
  3. Elena Baralis, Stefano Ceri, Stefano Paraboschi: Compile-Time and Runtime Analysis of Active Behaviors. IEEE Trans. Knowl. Data Eng. 10(3): 353-370(1998)
  4. Shalom Tsur, Jeffrey D. Ullman, Serge Abiteboul, Chris Clifton, Rajeev Motwani, Svetlozar Nestorov, Arnon Rosenthal: Query Flocks: A Generalization of Association-Rule Mining. SIGMOD Conference 1998: 1-12
  5. Daniela Florescu, Alon Y. Levy, Dan Suciu: Query Containment for Conjunctive Queries with Regular Expressions. PODS 1998: 139-148
  6. Dimitri Theodoratos, Timos K. Sellis: Data Warehouse Configuration. VLDB 1997: 126-135
  7. Nam Huyn: Multiple-View Self-Maintenance in Data Warehousing Environments. VLDB 1997: 26-35
  8. Alon Y. Levy, Dan Suciu: Deciding Containment for Queries with Complex Objects. PODS 1997: 20-31
  9. Jeffrey D. Ullman: Information Integration Using Logical Views. ICDT 1997: 19-40
  10. Nam Huyn: Efficient Complete Local Tests for Conjunctive Query Constraints with Negation. ICDT 1997: 82-97
  11. Alon Y. Levy: Obtaining Complete Answers from Incomplete Databases. VLDB 1996: 402-412
  12. Sin Yeung Lee, Tok Wang Ling: Further Improvements on Integrity Constraint Checking for Stratifiable Deductive Databases. VLDB 1996: 495-505
  13. Michael J. Maher, Divesh Srivastava: Chasing Constrained Tuple-Generating Dependencies. PODS 1996: 128-138
  14. Alon Y. Levy, Anand Rajaraman, Jeffrey D. Ullman: Answering Queries Using Limited External Processors. PODS 1996: 227-237
  15. Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995)
  16. Anand Rajaraman, Yehoshua Sagiv, Jeffrey D. Ullman: Answering Queries Using Templates with Binding Patterns. PODS 1995: 105-112
  17. Alon Y. Levy, Yehoshua Sagiv: Semantic Query Optimization in Datalog Programs. PODS 1995: 163-173
  18. Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104
  19. H. V. Jagadish, Inderpal Singh Mumick, Abraham Silberschatz: View Maintenance Issues for the Chronicle Data Model. PODS 1995: 113-124
  20. Venky Harinarayan, Ashish Gupta: Optimization Using Tuple Subsumption. ICDT 1995: 338-352
  21. Jennifer Widom: Research Problems in Data Warehousing. CIKM 1995: 25-30
  22. Elena Baralis, Jennifer Widom: An Algebraic Approach to Rule Analysis in Expert Database Systems. VLDB 1994: 475-486
  23. Ashish Gupta, Yehoshua Sagiv, Jeffrey D. Ullman, Jennifer Widom: Constraint Checking with Partial Information. PODS 1994: 45-55
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
 ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:45:55 2009