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
- 1778
- Venue
- PODS
- Year
- 2020
- Pagerank
- 5.8187108e-05
- Overall Rank
- 4,937 | 65.66%
- DOI
-
10.1145/3375395.3387647
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 10 of 10 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 7,022 |
A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations |
2023 |
SIGMOD |
4.8576599e-05 |
| 7,069 |
Consistent Query Answering for Primary Keys on Path Queries |
2021 |
PODS |
4.8438319e-05 |
| 8,508 |
Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries |
2024 |
PODS |
4.4952414e-05 |
| 8,721 |
Aggregated Deletion Propagation for Counting Conjunctive Query Answers |
2021 |
VLDB |
4.4608778e-05 |
| 10,001 |
A Unifying Algorithm for Hierarchical Queries |
2026 |
PODS |
4.1945683e-05 |
| 10,343 |
Circuit Bounds for Conjunctive Queries with Self-joins |
2025 |
PODS |
4.1945683e-05 |
| 10,355 |
Resilience for Regular Path Queries: Towards a Complexity Classification |
2025 |
PODS |
4.1945683e-05 |
| 10,359 |
Smallest Synthetic Witnesses for Conjunctive Queries |
2025 |
PODS |
4.1945683e-05 |
| 10,631 |
Is Integer Linear Programming All You Need for Deletion Propagation? |
2025 |
VLDB |
4.1945683e-05 |
| 10,899 |
Consistent Query Answering for Primary Keys on Rooted Tree Queries |
2024 |
PODS |
4.1945683e-05 |
Outgoing Citations (Sorted by Pagerank)
Showing 21 of 21 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank |
Cited Paper |
Year |
Venue |
Pagerank |
| 31 |
Provenance Semirings |
2007 |
PODS |
0.0007857786 |
| 214 |
Scorpion: Explaining Away Outliers in Aggregate Queries |
2013 |
VLDB |
0.0003363692 |
| 487 |
Why Not? |
2009 |
SIGMOD |
0.00022050218 |
| 556 |
On the Semantics of Updates in Databases |
1983 |
PODS |
0.00020249905 |
| 652 |
On the Provenance of Non-Answers to Queries over Extracted Data |
2008 |
VLDB |
0.00018634477 |
| 655 |
On Propagation of Deletions and Annotations Through Views |
2002 |
PODS |
0.00018608845 |
| 671 |
Algorithms for Translating View Updates to Database Updates for Views Involving Selections, Projections, and Joins |
1985 |
PODS |
0.00018370973 |
| 895 |
Updates Of Relational Views |
1983 |
PODS |
0.00015534879 |
| 942 |
A Formal Approach to Finding Explanations for Database Queries |
2014 |
SIGMOD |
0.00015155714 |
| 1,119 |
The Complexity of Causality and Responsibility for Query Answers and non-Answers |
2011 |
VLDB |
0.0001386199 |
| 1,125 |
How to ConQueR Why-Not Questions |
2010 |
SIGMOD |
0.00013845652 |
| 2,243 |
The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints |
2015 |
PODS |
9.2166927e-05 |
| 2,562 |
Explaining Missing Answers to SPJUA Queries |
2010 |
VLDB |
8.5386194e-05 |
| 2,602 |
Tracing Data Errors with View-Conditioned Causality |
2011 |
SIGMOD |
8.4667197e-05 |
| 2,649 |
Explaining Query Answers with Explanation-Ready Databases |
2016 |
VLDB |
8.3719123e-05 |
| 2,790 |
Artemis: A System for Analyzing Missing Answers |
2009 |
VLDB |
8.1239026e-05 |
| 2,857 |
A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies |
2012 |
PODS |
8.0037703e-05 |
| 4,260 |
Multi-Tuple Deletion Propagation: Approximations and Complexity |
2013 |
VLDB |
6.3124474e-05 |
| 4,361 |
The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries |
2016 |
VLDB |
6.2559141e-05 |
| 4,971 |
Maximizing Conjunctive Views in Deletion Propagation |
2011 |
PODS |
5.7938195e-05 |
| 7,601 |
Conjunctive Queries on Probabilistic Graphs: Combined Complexity |
2017 |
PODS |
4.698961e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 9,707 |
Towards Update-Dependent Analysis of Query Maintenance |
2025 |
PODS |
4.299267e-05 |
| 7,069 |
Consistent Query Answering for Primary Keys on Path Queries |
2021 |
PODS |
4.8438319e-05 |
| 915 |
The Complexity of Evaluating Relational Queries |
1983 |
PODS |
0.0001538509 |
| 4,260 |
Multi-Tuple Deletion Propagation: Approximations and Complexity |
2013 |
VLDB |
6.3124474e-05 |
| 6,112 |
A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join |
2024 |
PODS |
5.2048658e-05 |
| 8,721 |
Aggregated Deletion Propagation for Counting Conjunctive Query Answers |
2021 |
VLDB |
4.4608778e-05 |
| 10,355 |
Resilience for Regular Path Queries: Towards a Complexity Classification |
2025 |
PODS |
4.1945683e-05 |
| 2,243 |
The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints |
2015 |
PODS |
9.2166927e-05 |
| 6,728 |
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis |
2023 |
PODS |
4.9483326e-05 |
| 4,361 |
The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries |
2016 |
VLDB |
6.2559141e-05 |