DBLP:conf/vldb/LevyS93 +, KSL-93-03 + redirect page
Research Problems in Data Warehousing +,
An Algebraic Approach to Rule Analysis in Expert Database Systems +,
Data Warehouse Configuration + Has citation
Queries Independent of Updates + Has identifier
Queries Independent of Updates + Ksl tr id
Queries Independent of Updates + Number
| Queries Independent of Updates |
Bibtype
techreport
Has publishing details
1993
Has title
Queries Independent of Updates
Has where published
KSL-93-03
Has year
1993
Title
Queries Independent of Updates
Year
1993
Abstract
We consider the problem of detecting indep … We consider the problem of detecting independence of queries from updates in datalog programs. Detecting independence is important for several reasons. It can be used in view maintenance to identify that some views are independent of certain updates. In transaction scheduling, we can provide greater flexibility by identifying that one transaction is independent of updates made by another. Finally, we can use independence in query optimization by ignoring parts of the database for which updates do not affect a specific query.Earlier work by Blakeley et al.~\cite{Bl89} and Elkan~\cite{Elkan90} focused on cases for which independence is the same as query reachability. Essentially, these are the cases where the update predicate has a single occurrence in the query. Blakeley et al.~\cite{Bl89} considered only conjunctive queries. Elkan~\cite{Elkan90} considered a more general framework, but gave an algorithm only for nonrecursive rules without negation; that algorithm is complete only for the case of a single occurrence of the query predicate. Elkan also gave a proof method for recursive rules, but its power is limited. In this paper, we provide new insight into the independence problem by reducing it to the equivalence problem for datalog programs. Equivalence, as well as independence, is undecidable in general. However, algorithms for equivalence provide sufficient (and sometimes also necessary) conditions for independence.We give new decidable cases of independence; for example, if the update is an insertion, and both the query and the update are given by datalog program with no recursion or negation, then independence is decidable (note that the updated predicate may have multiple occurrences). Other decidable cases are described in Section~\ref{sec:prop}.We also give new sufficient conditions for independence. One condition is in terms of query reachability, which has recently been shown decidable even for recursive datalog programs with dense-order constraints and negated EDB subgoals~\cite{LS92,LMSS92}. Another condition is in terms of new algorithms for uniform equivalence that extend the one of~\cite{Sa88} to datalog programs with built-in predicates and negation. In particular, note that uniform equivalence is identical to equivalence when bodies of rules have only built-in and EDB predicates, and this entails some new decidable cases of independence. Finally, we also characterize new cases for which independence of insertions is the same as independence of deletions. Since the former is, in many cases, easier to detect, these characterizations are of practical importance. acterizations are of practical importance.
Author
Alon Y. Halevy and Yehoshua Sagiv +
Has author
Alon Y. Halevy and Yehoshua Sagiv +
Has identifier
Queries Independent of Updates +
Institution
Knowledge Systems, AI Laboratory +
Ksl tr id
Queries Independent of Updates +
Number
Queries Independent of Updates +
Process note
YES +
Categories KSL Technical Report +, Publication +, Technical Report +
|
