Aggregated deletion propagation for counting conjunctive query answers

Journal Article (Journal Article)

We investigate the computational complexity of minimizing the source side-effect in order to remove a given number of tuples from the output of a conjunctive query. This is a variant of the well-studied deletion propagation problem, the difference being that we are interested in removing the smallest subset of input tuples to remove a given number of output tuples while deletion propagation focuses on removing a specific output tuple. We call this the Aggregated Deletion Propagation problem. We completely characterize the poly-time solvability of this problem for arbitrary conjunctive queries without self-joins. This includes a poly-time algorithm to decide solvability, as well as an exact structural characterization of NP-hard instances. We also provide a practical algorithm for this problem (a heuristic for NP-hard instances) and evaluate its experimental performance on real and synthetic datasets.

Full Text

Duke Authors

Cited Authors

  • Hu, X; Sun, S; Patwa, S; Panigrahi, D; Roy, S

Published Date

  • January 1, 2020

Published In

Volume / Issue

  • 14 / 2

Start / End Page

  • 228 - 240

Electronic International Standard Serial Number (EISSN)

  • 2150-8097

Digital Object Identifier (DOI)

  • 10.14778/3425879.3425892

Citation Source

  • Scopus