DBScholar

Back to papers

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)

Paper ID
hc6c701528f9ee202
Venue
PODS
Year
2020
Pagerank
6.4131333e-05
Overall Rank
4,769 | 68.04%
DOI
10.1145/3375395.3387647

Incoming Non-self Citations Over Time

Authors

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.

Rank Citing Paper Year Venue Pagerank
7,404 Aggregated Deletion Propagation for Counting Conjunctive Query Answers 2021 VLDB 5.5178575e-05
7,443 A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations 2023 SIGMOD 5.5117047e-05
7,724 Consistent Query Answering for Primary Keys on Path Queries 2021 PODS 5.4530482e-05
8,788 Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation 2025 VLDB 5.263678e-05
8,789 Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries 2024 PODS 5.263678e-05
10,469 A Unifying Algorithm for Hierarchical Queries 2026 PODS 4.9605343e-05
11,152 Circuit Bounds for Conjunctive Queries with Self-joins 2025 PODS 4.9605343e-05
11,161 Resilience for Regular Path Queries: Towards a Complexity Classification 2025 PODS 4.9605343e-05
11,165 Smallest Synthetic Witnesses for Conjunctive Queries 2025 PODS 4.9605343e-05
11,527 Consistent Query Answering for Primary Keys on Rooted Tree Queries 2024 PODS 4.9605343e-05
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.

Rank Cited Paper Year Venue Pagerank
17 Provenance Semirings 2007 PODS 0.00059660827
191 Scorpion: Explaining Away Outliers in Aggregate Queries 2013 VLDB 0.0002578784
389 Why Not? 2009 SIGMOD 0.00019254758
581 The Complexity of Causality and Responsibility for Query Answers and non-Answers 2011 VLDB 0.00016042765
593 On Propagation of Deletions and Annotations Through Views 2002 PODS 0.00015833398
620 On the Semantics of Updates in Databases 1983 PODS 0.00015460693
624 On the Provenance of Non-Answers to Queries over Extracted Data 2008 VLDB 0.00015438077
672 A Formal Approach to Finding Explanations for Database Queries 2014 SIGMOD 0.00014903109
790 How to ConQueR Why-Not Questions 2010 SIGMOD 0.00013929166
1,000 Algorithms for Translating View Updates to Database Updates for Views Involving Selections, Projections, and Joins 1985 PODS 0.00012588668
1,093 Updates Of Relational Views 1983 PODS 0.0001204652
1,747 The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints 2015 PODS 9.7180424e-05
2,079 Explaining Missing Answers to SPJUA Queries 2010 VLDB 9.0602682e-05
2,233 Explaining Query Answers with Explanation-Ready Databases 2016 VLDB 8.7844607e-05
2,371 Artemis: A System for Analyzing Missing Answers 2009 VLDB 8.5457987e-05
2,459 Tracing Data Errors with View-Conditioned Causality 2011 SIGMOD 8.4137923e-05
4,085 The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries 2016 VLDB 6.7989526e-05
4,341 Multi-Tuple Deletion Propagation: Approximations and Complexity 2013 VLDB 6.6408734e-05
4,460 Maximizing Conjunctive Views in Deletion Propagation 2011 PODS 6.5757194e-05
5,907 Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms 2018 PODS 5.9344171e-05
6,006 A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies 2012 PODS 5.9002327e-05
7,878 Conjunctive Queries on Probabilistic Graphs: Combined Complexity 2017 PODS 5.4187338e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 7,724 Consistent Query Answering for Primary Keys on Path Queries 2021 PODS
2 1,508 The Complexity of Evaluating Relational Queries 1983 PODS
3 5,907 Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms 2018 PODS
4 4,341 Multi-Tuple Deletion Propagation: Approximations and Complexity 2013 VLDB
5 5,980 A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join 2024 PODS
6 7,404 Aggregated Deletion Propagation for Counting Conjunctive Query Answers 2021 VLDB
7 11,161 Resilience for Regular Path Queries: Towards a Complexity Classification 2025 PODS
8 1,747 The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints 2015 PODS
9 5,989 Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis 2023 PODS
10 4,085 The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries 2016 VLDB