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.4374568e-05
Overall Rank
4,747 | 68.09%
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,383 Aggregated Deletion Propagation for Counting Conjunctive Query Answers 2021 VLDB 5.5387855e-05
7,419 A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations 2023 SIGMOD 5.5326094e-05
7,705 Consistent Query Answering for Primary Keys on Path Queries 2021 PODS 5.4737304e-05
8,761 Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation 2025 VLDB 5.283642e-05
8,762 Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries 2024 PODS 5.283642e-05
10,391 A Unifying Algorithm for Hierarchical Queries 2026 PODS 4.9793485e-05
11,082 Circuit Bounds for Conjunctive Queries with Self-joins 2025 PODS 4.9793485e-05
11,091 Resilience for Regular Path Queries: Towards a Complexity Classification 2025 PODS 4.9793485e-05
11,095 Smallest Synthetic Witnesses for Conjunctive Queries 2025 PODS 4.9793485e-05
11,469 Consistent Query Answering for Primary Keys on Rooted Tree Queries 2024 PODS 4.9793485e-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.00059752575
189 Scorpion: Explaining Away Outliers in Aggregate Queries 2013 VLDB 0.00025840026
391 Why Not? 2009 SIGMOD 0.00019238698
578 The Complexity of Causality and Responsibility for Query Answers and non-Answers 2011 VLDB 0.00016096504
590 On Propagation of Deletions and Annotations Through Views 2002 PODS 0.00015890019
619 On the Semantics of Updates in Databases 1983 PODS 0.00015518944
622 On the Provenance of Non-Answers to Queries over Extracted Data 2008 VLDB 0.00015484312
670 A Formal Approach to Finding Explanations for Database Queries 2014 SIGMOD 0.00014954494
791 How to ConQueR Why-Not Questions 2010 SIGMOD 0.00013976192
995 Algorithms for Translating View Updates to Database Updates for Views Involving Selections, Projections, and Joins 1985 PODS 0.00012635689
1,088 Updates Of Relational Views 1983 PODS 0.00012091631
1,735 The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints 2015 PODS 9.7545681e-05
2,067 Explaining Missing Answers to SPJUA Queries 2010 VLDB 9.0924963e-05
2,222 Explaining Query Answers with Explanation-Ready Databases 2016 VLDB 8.8109051e-05
2,360 Artemis: A System for Analyzing Missing Answers 2009 VLDB 8.5770202e-05
2,458 Tracing Data Errors with View-Conditioned Causality 2011 SIGMOD 8.4371456e-05
4,062 The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries 2016 VLDB 6.8247395e-05
4,323 Multi-Tuple Deletion Propagation: Approximations and Complexity 2013 VLDB 6.6658586e-05
4,437 Maximizing Conjunctive Views in Deletion Propagation 2011 PODS 6.6001218e-05
5,892 Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms 2018 PODS 5.956925e-05
5,994 A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies 2012 PODS 5.922611e-05
7,858 Conjunctive Queries on Probabilistic Graphs: Combined Complexity 2017 PODS 5.4392859e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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