SEF view deletion under bounded condition

Deletion propagation problem has been an important role in data lineage, is a classic problem in the database research on data provenance and quality. As a more restricted version of classic view update problem in relational databases, it is defined on a given database D, a monotonic relational algebraic query Q and its materialized view V of D, deletion propagation aims to find a tuple set ΔD whose deletion from D guarantees that the result of Q is exactly the view V minus an intended deletion ΔV, i.e., ΔD will not produce side-effect on view. Such ΔD is side-effect-free if no side effect produced by deleting it from D. We study the complexity of finding side-effect-free deletion in this paper. We also consider the functional dependency restricted version deletion propagation problem ‘b-dp ’ which generalizes the computational issues involved in data lineage, it is to find the ΔD not only view side-effect free but also without introducing inconsistency with respect to the predefined functional dependencies. Both data and combined complexity of b-dp are studied under both single and group deletion. Plenty of analysis are provided on this problem with respect to queries in different classes on either complexity aspect.