No icon

On the Complexity of Bounded View Propagation for Conjunctive Queries

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 DV , deletion (insertion) propagation is to find a side effect free update DD on D such that the deletion (insertion) of DD from (into) D will delete (insert) the intentional ones DV 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 DD 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.

 

 

Existing System:

View propagation seeks a deletion or insertion on source data without producing side effect on view. It is believed such a measurement could show the robustness and explain the impact well. However, in this traditional way, a candidate update on the source database is selected aimlessly in advance, so that the updated database may be very distant from the original one even if it is the maximum one. Additionally, this definition suffers from very high computational complexity.

 

Proposed System:

Traditionally, view propagation seeks a deletion or insertion on source data without producing side effect on view. It is believed such a measurement could show the robustness and explain the impact well. However, in this traditional way, a candidate update on the source database is selected aimlessly in advance, so that the updated database may be very distant from the original one even if it is the maximum one. Additionally, this definition suffers from very high computational complexity.

Comment As:

Comment (0)