The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries

Summary: Triads, a structural property of self-join-free CQs, underpin a resilience dichotomy with functional dependencies, yielding tractable deletion propagation and source-side effects. Also revises causal-responsibility dichotomy and extends to FDs and wildcard tuples. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h67b1939a6041ec6a
Venue: VLDB
Year: 2016
Pagerank: 6.8215087e-05
Overall Rank: 4,063 | 72.70%
DOI: 10.14778/2850583.2850588
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Cibele Freire (University of Massachusetts Amherst)
2. Wolfgang Gatterbauer (Carnegie Mellon University)
3. Neil Immerman (University of Massachusetts Amherst)
4. Alexandra Meliou (University of Massachusetts Amherst)

BibTeX Citation

@article{freire_vldb16,
        title = {{The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries}},
        author = {Freire, Cibele and Gatterbauer, Wolfgang and Immerman, Neil and Meliou, Alexandra},
        journal = {PVLDB},
        series = {{VLDB} '16},
        volume = {9},
        number = {3},
        pages = {180--191},
        doi = {10.14778/2850583.2850588},
        url = {https://doi.org/10.14778/2850583.2850588},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,700	Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries	2021	PODS	6.4609577e-05
4,750	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS	6.4344094e-05
6,602	Explain3D: Explaining Disagreements in Disjoint Datasets	2019	VLDB	5.7376131e-05
7,385	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	5.5361635e-05
7,422	A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations	2023	SIGMOD	5.5299903e-05
7,711	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS	5.4711392e-05
8,572	On The Reasonable Effectiveness of Relational Diagrams: Explaining Relational Query Patterns and the Pattern Expressiveness of Relational Languages	2024	SIGMOD	5.3112258e-05
8,769	Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation	2025	VLDB	5.2811408e-05
8,770	Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries	2024	PODS	5.2811408e-05
9,551	SQuID: Semantic Similarity-Aware Query Intent Discovery	2018	SIGMOD	5.1592374e-05
10,403	A Unifying Algorithm for Hierarchical Queries	2026	PODS	4.9769913e-05
10,749	Database Views as Explanations for Relational Deep Learning	2026	VLDB	4.9769913e-05
10,996	GDPView: An Interactive Interface that Unifies Variants of Deletion Propagation (DP)	2026	VLDB	4.9769913e-05
11,100	Resilience for Regular Path Queries: Towards a Complexity Classification	2025	PODS	4.9769913e-05
11,104	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	4.9769913e-05
11,472	Towards an Objective Metric for Data Value Through Relevance	2024	CIDR	4.9769913e-05
11,475	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	4.9769913e-05
12,273	Dichotomies in Ontology-Mediated Querying with the Guarded Fragment	2017	PODS	4.9769913e-05

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.00059813669
190	Scorpion: Explaining Away Outliers in Aggregate Queries	2013	VLDB	0.0002582857
389	Why Not?	2009	SIGMOD	0.00019313101
578	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.00016093679
591	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00015882967
619	On the Semantics of Updates in Databases	1983	PODS	0.00015511647
621	On the Provenance of Non-Answers to Queries over Extracted Data	2008	VLDB	0.0001548582
671	A Formal Approach to Finding Explanations for Database Queries	2014	SIGMOD	0.00014948069
791	How to ConQueR Why-Not Questions	2010	SIGMOD	0.00013970743
996	Algorithms for Translating View Updates to Database Updates for Views Involving Selections, Projections, and Joins	1985	PODS	0.00012629814
1,088	Updates Of Relational Views	1983	PODS	0.00012085975
1,708	PerfXplain: Debugging MapReduce Job Performance	2012	VLDB	9.8184303e-05
1,983	Causality and Explanations in Databases	2014	VLDB	9.2548712e-05
2,069	Explaining Missing Answers to SPJUA Queries	2010	VLDB	9.0884616e-05
2,361	Artemis: A System for Analyzing Missing Answers	2009	VLDB	8.5732984e-05
2,458	Tracing Data Errors with View-Conditioned Causality	2011	SIGMOD	8.4334752e-05
3,150	Explanation-Based Auditing	2012	VLDB	7.5885752e-05
4,323	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB	6.6628189e-05
4,439	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS	6.5969995e-05
5,994	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	5.9198073e-05
6,479	Explainable Security for Relational Databases	2014	SIGMOD	5.770025e-05
6,535	MapRat: Meaningful Explanation, Interactive Exploration and Geo-Visualization of Collaborative Ratings	2012	VLDB	5.7515229e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,994	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS
2	12,695	Resiliency-Aware Data Management	2011	VLDB
3	5,978	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS
4	5,892	Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms	2018	PODS
5	578	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB
6	4,323	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB
7	11,100	Resilience for Regular Path Queries: Towards a Complexity Classification	2025	PODS
8	7,422	A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations	2023	SIGMOD
9	1,737	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
10	4,750	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS