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.8131196e-05
- Overall Rank
- 4,940 | 65.67%
- 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,024 |
A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations |
2023 |
SIGMOD |
4.8530001e-05 |
| 7,064 |
Consistent Query Answering for Primary Keys on Path Queries |
2021 |
PODS |
4.8391823e-05 |
| 8,506 |
Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries |
2024 |
PODS |
4.4909322e-05 |
| 8,718 |
Aggregated Deletion Propagation for Counting Conjunctive Query Answers |
2021 |
VLDB |
4.4566012e-05 |
| 10,000 |
A Unifying Algorithm for Hierarchical Queries |
2026 |
PODS |
4.1905499e-05 |
| 10,355 |
Circuit Bounds for Conjunctive Queries with Self-joins |
2025 |
PODS |
4.1905499e-05 |
| 10,367 |
Resilience for Regular Path Queries: Towards a Complexity Classification |
2025 |
PODS |
4.1905499e-05 |
| 10,371 |
Smallest Synthetic Witnesses for Conjunctive Queries |
2025 |
PODS |
4.1905499e-05 |
| 10,639 |
Is Integer Linear Programming All You Need for Deletion Propagation? |
2025 |
VLDB |
4.1905499e-05 |
| 10,903 |
Consistent Query Answering for Primary Keys on Rooted Tree Queries |
2024 |
PODS |
4.1905499e-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.00078516827 |
| 213 |
Scorpion: Explaining Away Outliers in Aggregate Queries |
2013 |
VLDB |
0.0003371037 |
| 487 |
Why Not? |
2009 |
SIGMOD |
0.00022030123 |
| 555 |
On the Semantics of Updates in Databases |
1983 |
PODS |
0.00020229919 |
| 653 |
On the Provenance of Non-Answers to Queries over Extracted Data |
2008 |
VLDB |
0.00018616975 |
| 655 |
On Propagation of Deletions and Annotations Through Views |
2002 |
PODS |
0.00018593536 |
| 672 |
Algorithms for Translating View Updates to Database Updates for Views Involving Selections, Projections, and Joins |
1985 |
PODS |
0.00018353514 |
| 893 |
Updates Of Relational Views |
1983 |
PODS |
0.00015519479 |
| 943 |
A Formal Approach to Finding Explanations for Database Queries |
2014 |
SIGMOD |
0.00015140995 |
| 1,119 |
The Complexity of Causality and Responsibility for Query Answers and non-Answers |
2011 |
VLDB |
0.00013851012 |
| 1,124 |
How to ConQueR Why-Not Questions |
2010 |
SIGMOD |
0.00013832959 |
| 2,246 |
The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints |
2015 |
PODS |
9.2039096e-05 |
| 2,565 |
Explaining Missing Answers to SPJUA Queries |
2010 |
VLDB |
8.5307653e-05 |
| 2,600 |
Tracing Data Errors with View-Conditioned Causality |
2011 |
SIGMOD |
8.4652308e-05 |
| 2,655 |
Explaining Query Answers with Explanation-Ready Databases |
2016 |
VLDB |
8.3638668e-05 |
| 2,794 |
Artemis: A System for Analyzing Missing Answers |
2009 |
VLDB |
8.1164685e-05 |
| 2,864 |
A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies |
2012 |
PODS |
7.9964194e-05 |
| 4,256 |
Multi-Tuple Deletion Propagation: Approximations and Complexity |
2013 |
VLDB |
6.3063725e-05 |
| 4,358 |
The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries |
2016 |
VLDB |
6.2499e-05 |
| 4,973 |
Maximizing Conjunctive Views in Deletion Propagation |
2011 |
PODS |
5.7882537e-05 |
| 7,604 |
Conjunctive Queries on Probabilistic Graphs: Combined Complexity |
2017 |
PODS |
4.6944524e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 9,706 |
Towards Update-Dependent Analysis of Query Maintenance |
2025 |
PODS |
4.2951473e-05 |
| 7,064 |
Consistent Query Answering for Primary Keys on Path Queries |
2021 |
PODS |
4.8391823e-05 |
| 912 |
The Complexity of Evaluating Relational Queries |
1983 |
PODS |
0.00015374685 |
| 6,114 |
A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join |
2024 |
PODS |
5.1998701e-05 |
| 4,256 |
Multi-Tuple Deletion Propagation: Approximations and Complexity |
2013 |
VLDB |
6.3063725e-05 |
| 8,718 |
Aggregated Deletion Propagation for Counting Conjunctive Query Answers |
2021 |
VLDB |
4.4566012e-05 |
| 10,367 |
Resilience for Regular Path Queries: Towards a Complexity Classification |
2025 |
PODS |
4.1905499e-05 |
| 2,246 |
The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints |
2015 |
PODS |
9.2039096e-05 |
| 6,732 |
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis |
2023 |
PODS |
4.9435849e-05 |
| 4,358 |
The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries |
2016 |
VLDB |
6.2499e-05 |