New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins
Summary: Dichotomy for resilience of single-self-join binary conjunctive queries with exactly two repeated relations; shows triads insufficient and identifies new structural obstructions—chains, confluences, permutations—that yield NP-hard cases. Also gives novel reductions to network flow proving many remaining patterns are in P and relates the results to deletion-propagation with source-side effects. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Cibele Freire (Wellesley College)
- 2. Wolfgang Gatterbauer (Northeastern University)
- 3. Neil Immerman (University of Massachusetts Amherst)
- 4. Alexandra Meliou (University of Massachusetts Amherst)
BibTeX Citation
@inproceedings{freire_pods20,
address = {New York, NY, USA},
series = {{PODS} '20},
title = {{New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins}},
url = {https://dl.acm.org/doi/10.1145/3375395.3387647},
doi = {10.1145/3375395.3387647},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Freire, Cibele and Gatterbauer, Wolfgang and Immerman, Neil and Meliou, Alexandra},
year = {2020}
}Incoming Citations (Sorted by Pagerank)
Showing 10 of 10 citing papers.
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 22 of 22 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Previous
Page 1 / 1
Next