DBScholar

Back to papers

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.8247395e-05
Overall Rank
4,062 | 72.70%
DOI
10.14778/2850583.2850588

Incoming Non-self Citations Over Time

Authors

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,698 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS 6.4640177e-05
4,747 New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins 2020 PODS 6.4374568e-05
6,600 Explain3D: Explaining Disagreements in Disjoint Datasets 2019 VLDB 5.7403306e-05
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,565 On The Reasonable Effectiveness of Relational Diagrams: Explaining Relational Query Patterns and the Pattern Expressiveness of Relational Languages 2024 SIGMOD 5.3137413e-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
9,550 SQuID: Semantic Similarity-Aware Query Intent Discovery 2018 SIGMOD 5.1594571e-05
10,391 A Unifying Algorithm for Hierarchical Queries 2026 PODS 4.9793485e-05
10,739 Database Views as Explanations for Relational Deep Learning 2026 VLDB 4.9793485e-05
10,987 GDPView: An Interactive Interface that Unifies Variants of Deletion Propagation (DP) 2026 VLDB 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,466 Towards an Objective Metric for Data Value Through Relevance 2024 CIDR 4.9793485e-05
11,469 Consistent Query Answering for Primary Keys on Rooted Tree Queries 2024 PODS 4.9793485e-05
12,267 Dichotomies in Ontology-Mediated Querying with the Guarded Fragment 2017 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,708 PerfXplain: Debugging MapReduce Job Performance 2012 VLDB 9.8224587e-05
1,981 Causality and Explanations in Databases 2014 VLDB 9.2586863e-05
2,067 Explaining Missing Answers to SPJUA Queries 2010 VLDB 9.0924963e-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
3,149 Explanation-Based Auditing 2012 VLDB 7.5920152e-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,994 A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies 2012 PODS 5.922611e-05
6,477 Explainable Security for Relational Databases 2014 SIGMOD 5.7726401e-05
6,533 MapRat: Meaningful Explanation, Interactive Exploration and Geo-Visualization of Collaborative Ratings 2012 VLDB 5.7542451e-05
Previous Page 1 / 1 Next

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,689 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,091 Resilience for Regular Path Queries: Towards a Complexity Classification 2025 PODS
8 7,419 A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations 2023 SIGMOD
9 1,735 The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints 2015 PODS
10 4,747 New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins 2020 PODS