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
11499
Venue
VLDB
Year
2016
Pagerank
6.9695922e-05
Overall Rank
3,991 | 72.62%
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 17 of 17 citing papers.

Rank Citing Paper Year Venue Pagerank
4,670 New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins 2020 PODS 6.5734205e-05
4,781 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS 6.5116536e-05
6,461 Explain3D: Explaining Disagreements in Disjoint Datasets 2019 VLDB 5.8718966e-05
7,269 A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations 2023 SIGMOD 5.6595955e-05
7,558 Consistent Query Answering for Primary Keys on Path Queries 2021 PODS 5.5993651e-05
8,407 On The Reasonable Effectiveness of Relational Diagrams: Explaining Relational Query Patterns and the Pattern Expressiveness of Relational Languages 2024 SIGMOD 5.4312823e-05
8,598 Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation 2025 VLDB 5.4049137e-05
8,599 Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries 2024 PODS 5.4049137e-05
8,700 Aggregated Deletion Propagation for Counting Conjunctive Query Answers 2021 VLDB 5.3829336e-05
9,368 SQuID: Semantic Similarity-Aware Query Intent Discovery 2018 SIGMOD 5.2778771e-05
10,174 A Unifying Algorithm for Hierarchical Queries 2026 PODS 5.093636e-05
10,557 Database Views as Explanations for Relational Deep Learning 2026 VLDB 5.093636e-05
10,648 Resilience for Regular Path Queries: Towards a Complexity Classification 2025 PODS 5.093636e-05
10,652 Smallest Synthetic Witnesses for Conjunctive Queries 2025 PODS 5.093636e-05
11,118 Towards an Objective Metric for Data Value Through Relevance 2024 CIDR 5.093636e-05
11,121 Consistent Query Answering for Primary Keys on Rooted Tree Queries 2024 PODS 5.093636e-05
11,969 Dichotomies in Ontology-Mediated Querying with the Guarded Fragment 2017 PODS 5.093636e-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.00059843817
191 Scorpion: Explaining Away Outliers in Aggregate Queries 2013 VLDB 0.00026096009
385 Why Not? 2009 SIGMOD 0.00019455743
602 On the Semantics of Updates in Databases 1983 PODS 0.00015856828
605 The Complexity of Causality and Responsibility for Query Answers and non-Answers 2011 VLDB 0.00015839628
620 On Propagation of Deletions and Annotations Through Views 2002 PODS 0.00015703409
628 On the Provenance of Non-Answers to Queries over Extracted Data 2008 VLDB 0.00015630285
663 A Formal Approach to Finding Explanations for Database Queries 2014 SIGMOD 0.00015174751
856 How to ConQueR Why-Not Questions 2010 SIGMOD 0.00013573466
979 Algorithms for Translating View Updates to Database Updates for Views Involving Selections, Projections, and Joins 1985 PODS 0.00012850156
1,075 Updates Of Relational Views 1983 PODS 0.00012294896
1,694 PerfXplain: Debugging MapReduce Job Performance 2012 VLDB 9.9953156e-05
1,943 Causality and Explanations in Databases 2014 VLDB 9.440636e-05
2,032 Explaining Missing Answers to SPJUA Queries 2010 VLDB 9.2828822e-05
2,358 Artemis: A System for Analyzing Missing Answers 2009 VLDB 8.6996414e-05
2,432 Tracing Data Errors with View-Conditioned Causality 2011 SIGMOD 8.5870067e-05
3,105 Explanation-Based Auditing 2012 VLDB 7.7528586e-05
4,248 Multi-Tuple Deletion Propagation: Approximations and Complexity 2013 VLDB 6.8052749e-05
4,901 Maximizing Conjunctive Views in Deletion Propagation 2011 PODS 6.4528526e-05
5,905 A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies 2012 PODS 6.0461963e-05
6,365 Explainable Security for Relational Databases 2014 SIGMOD 5.8985919e-05
6,425 MapRat: Meaningful Explanation, Interactive Exploration and Geo-Visualization of Collaborative Ratings 2012 VLDB 5.8810029e-05
Previous Page 1 / 1 Next

Semantically Similar Papers