Abstract Queries Independent of Updates

This paper considers the problem of detecting indepen-dence 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 dat-alog programs (both for the case of insertion and deletion updates). Equivalence, as well as independence, is unde-cidable in general. However, algorithms for detecting sub-classes of equivalence provide sufficient (and sometimes also necessary) conditions for independence. We consider two such subclasses. The first, query-reachability, general-izes 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 these earlier independence tests to arbitrary recursive datalog queries with dense-order constraints and negated EDB subgoals. The second subclass is uniform equivalence (introduced in [S&S]). We extend the results of [SaSSI to datalog programs that include dense-order constraints and strati-fied negation. Based on these extensions, we present new cases in which independence is decidable and give algo-rithms that are sound for the general case. Aside for their use in detecting independence, the algorithms for detect-ing uniform equivalence are also important for optimizing datalog programs