Reference: Levy, A. Y. & Sagiv, Y. Queries Independent of Updates. 1993.
Abstract: 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} focussed 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.
Full paper available as ps.