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
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
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
Copyright © Fri Mar 12 17:22:52 2010
by Michael Ley (ley@uni-trier.de)