On the Complexity of Bounded View Propagation for Conjunctive Queries

Abstract

The view propagation problem is a class of view update problem in relational databases [7] , involving deletion and insertion propagations. Given source database $D$ , conjunctive query $Q$ , view $V$ generated by query $Q(D)$ and a deletion (insertion) on view $\Delta V$ , deletion (insertion) propagation is to find a side effect free update $\Delta D$ on $D$ such that the deletion (insertion) of $\Delta D$ from (into) $D$ will delete (insert) the intentional ones $\Delta V$ without resulting in the deletion (insertion) of additional tuples from (into) the view. Generally, such a deletion (insertion) is side effect free. The related data management applications include query result explanation, data debugging, and anonymizing datasets, which rely on understanding how interventions in a database affect the output of a query. View propagation is a natural and typical way to define such interventions, which seems to be well-studied. However, in general, the candidate update on a source database is picked up aimlessly in advance, making the updated database to be very distant from the original one no matter whether it is the maximum one. In this paper, we formally define the bounded view propagation problem, where candidate update $\Delta D$ is bounded as a subset of potential $C$ which is a fixed small tuple set of $D$ . We study the complexity of this problem for conjunctive queries, and make contributions to the previous results of the problems of side-effect free deletion propagation. Specifically, our bounded view propagation problem decreases computational complexity regardless of conjunctive query structure. We show the fixed potential is actually a dichotomy for both deletion and insertion propagations, and figure out the results on combined complexity which is neglected previously. Based on our results, for view propagation, we map out a complete picture of the computational complexity hierarchy for conjunctive queries on both data and combined complexities. Moreover, this bounded version is an update forbidden case of view propagation, and our results can be applied to it.