{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:24:10Z","timestamp":1756992250905},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:p>\n            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\n            <jats:italic>deletion propagation<\/jats:italic>\n            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\n            <jats:italic>Aggregated Deletion Propagation<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.14778\/3425879.3425892","type":"journal-article","created":{"date-parts":[[2020,11,25]],"date-time":"2020-11-25T02:45:23Z","timestamp":1606272323000},"page":"228-240","source":"Crossref","is-referenced-by-count":5,"title":["Aggregated deletion propagation for counting conjunctive query answers"],"prefix":"10.14778","volume":"14","author":[{"given":"Xiao","family":"Hu","sequence":"first","affiliation":[{"name":"Duke University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shouzhuo","family":"Sun","sequence":"additional","affiliation":[{"name":"Duke University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shweta","family":"Patwa","sequence":"additional","affiliation":[{"name":"Duke University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Debmalya","family":"Panigrahi","sequence":"additional","affiliation":[{"name":"Duke University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sudeepa","family":"Roy","sequence":"additional","affiliation":[{"name":"Duke University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,11,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/120884857"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/319628.319634"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543633"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1054328"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1096402"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039742"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183614.1183705"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395119"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/319732.319740"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850592"},{"key":"e_1_2_1_11_1","volume-title":"New results for the complexity of resilience for binary conjunctive queries with self-joins. arXiv preprint arXiv:1907.01129","author":"Freire C.","year":"2019","unstructured":"C. Freire , W. Gatterbauer , N. Immerman , and A. Meliou . New results for the complexity of resilience for binary conjunctive queries with self-joins. arXiv preprint arXiv:1907.01129 , 2019 . C. Freire, W. Gatterbauer, N. Immerman, and A. Meliou. New results for the complexity of resilience for binary conjunctive queries with self-joins. arXiv preprint arXiv:1907.01129, 2019."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.04.002"},{"key":"e_1_2_1_13_1","volume-title":"Aggregated deletion propagation for counting conjunctive query answers. https:\/\/arxiv.org\/pdf\/2010.08694.pdf","author":"Hu X.","year":"2020","unstructured":"X. Hu , S. Patwa , S. Sun , D. Panigrahi , and S. Roy . Aggregated deletion propagation for counting conjunctive query answers. https:\/\/arxiv.org\/pdf\/2010.08694.pdf , 2020 . X. Hu, S. Patwa, S. Sun, D. Panigrahi, and S. Roy. Aggregated deletion propagation for counting conjunctive query answers. https:\/\/arxiv.org\/pdf\/2010.08694.pdf, 2020."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213584"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989308"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536267"},{"key":"e_1_2_1_17_1","volume-title":"June","author":"Leskovec J.","year":"2014","unstructured":"J. Leskovec and A. Krevl . Snap datasets: Stanford large network dataset collection. http\/\/snap.stanford.edu\/data\/ , June 2014 . J. Leskovec and A. Krevl. Snap datasets: Stanford large network dataset collection. http\/\/snap.stanford.edu\/data\/, June 2014."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2999134.2999195"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196980"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/1880172.1880176"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402755.3402803"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213875"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856329"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588578"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536354.2536356"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3425879.3425892","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:07:44Z","timestamp":1672225664000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3425879.3425892"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["10.14778\/3425879.3425892"],"URL":"https:\/\/doi.org\/10.14778\/3425879.3425892","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,10]]}}}