Deletion Propagation Revisited for Multiple Key Preserving Views

Deletion propagation is widely studied for single view but rarely for multiple views. We study the deletion propagation problem for multiple views called
Mdp
. We investigate the complexity and algorithms of
Mdp
in depth for key-preserving conjunctive queries. We characterize the structure of the set of queries to derive new results. On aspect of combined complexity, for two key-preserving views, it is NP-hard to find an approximation within a constant ratio for
Mdp
. This implies, if the number of queries and the dimension of every query are unbounded, it is hard to find a good approximation for
Mdp
even under the key preservation condition. On aspect of data complexity, for two key-preserving views, it is NP-hard to approximate
Mdp
within a ratio
$k-2-\epsilon$
for any
$\epsilon >0$
and
$k>4$
, if the dimension of each individual query is at most
$k$
. On aspect of upper bound, we design a linear programming based approximation algorithm. This implies that, under the key preservation condition,
Mdp
can be approximated within a ratio
$d$
if each query has a dimension at most
$d$
and the set of input queries is tree-like. In addition, we show that the approximation ratio can be improved as
$2\sqrt{n}$
when
$n$
the size of
$I$
is smaller than
$d^2$
. At last, a dynamic programming based algorithm is proposed to solve the strict star-like case in polynomial time. The strict star-like case is more restrictive than tree-like case under the key preservation condition.