Database Paper Browser

Back to papers

The Complexity of Causality and Responsibility for Query Answers and non-Answers

Summary: Adapts Halpern-Pearl-Chockler causality to define causes and responsibility for answers and non-answers, with ranking. Conjunctive-query causes are PTIME; responsibility has a PTIME/NP-complete dichotomy with max-flow in PTIME and LOGSPACE-hardness. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
10263
Venue
VLDB
Year
2011
Pagerank
0.0001386199
Overall Rank
1,119 | 92.22%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 53 citing papers.

Rank Citing Paper Year Venue Pagerank
942 A Formal Approach to Finding Explanations for Database Queries 2014 SIGMOD 0.00015155714
1,106 Provenance for Aggregate Queries 2011 PODS 0.0001398766
1,449 Causal Relational Learning 2020 SIGMOD 0.0001193267
1,699 Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases 2011 SIGMOD 0.00010858983
2,370 Query-Based Data Pricing 2012 PODS 8.9488834e-05
2,566 Database Repairs and Consistent Query Answering: Origins and Further Developments 2019 PODS 8.5243847e-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,797 Query-Oriented Data Cleaning with Oracles 2015 SIGMOD 8.1108589e-05
2,857 A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies 2012 PODS 8.0037703e-05
2,868 Computing the Shapley Value of Facts in Query Answering 2022 SIGMOD 7.9816425e-05
3,027 The Impact of Negation on the Complexity of the Shapley Value in Conjunctive Queries 2020 PODS 7.6842412e-05
3,051 Partial Results in Database Systems 2014 SIGMOD 7.6512591e-05
3,104 Computing Local Sensitivities of Counting Queries with Joins 2020 SIGMOD 7.5578613e-05
3,105 Data X-Ray: A Diagnostic Tool for Data Errors 2015 SIGMOD 7.5568954e-05
3,218 Reverse Data Management 2011 VLDB 7.3592173e-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,664 Efficient Answering of Historical What-if Queries 2022 SIGMOD 6.0127053e-05
4,937 New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins 2020 PODS 5.8187108e-05
4,971 Maximizing Conjunctive Views in Deletion Propagation 2011 PODS 5.7938195e-05
5,191 Going Beyond Provenance: Explaining Query Answers with Pattern-based Counterbalances 2019 SIGMOD 5.6378768e-05
5,313 XInsight: eXplainable Data Analysis Through The Lens of Causality 2023 SIGMOD 5.573009e-05
5,418 High-Level Why-Not Explanations using Ontologies 2015 PODS 5.5178123e-05
5,826 Why Not Yet: Fixing a Top-k Ranking that Is Not Fair to Individuals 2023 VLDB 5.3124507e-05
5,916 Banzhaf Values for Facts in Query Answering 2024 SIGMOD 5.273953e-05
6,153 On Data-Aware Global Explainability of Graph Neural Networks 2023 VLDB 5.1829258e-05
6,186 On Provenance Minimization 2011 PODS 5.166082e-05
6,262 Fast Shapley Value Computation in Data Assemblage Tasks as Cooperative Simple Games 2024 SIGMOD 5.1349507e-05
6,429 ShapGraph: An Holistic View of Explanations through Provenance Graphs and Shapley Values 2022 SIGMOD 5.0666822e-05
6,475 Explain3D: Explaining Disagreements in Disjoint Datasets 2019 VLDB 5.0497183e-05
6,723 On Shapley Value in Data Assemblage Under Independent Utility 2022 VLDB 4.9490816e-05
7,022 A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations 2023 SIGMOD 4.8576599e-05
7,172 Summarized Causal Explanations For Aggregate Views 2024 SIGMOD 4.8114797e-05
8,665 Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms 2025 VLDB 4.471975e-05
8,721 Aggregated Deletion Propagation for Counting Conjunctive Query Answers 2021 VLDB 4.4608778e-05
9,640 Shapley Revisited: Tractable Responsibility Measures for Query Answers 2025 PODS 4.3109001e-05
9,644 Fair and Actionable Causal Prescription Ruleset 2025 SIGMOD 4.3109001e-05
9,766 DPXPlain: Privately Explaining Aggregate Query Answers 2023 VLDB 4.2856106e-05
10,010 Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries 2026 PODS 4.1945683e-05
10,101 Privacy-preserving and Verifiable Causal Prescriptive Analytics 2026 SIGMOD 4.1945683e-05
10,147 Causal Explanations for Disparate Trends: Where and Why? 2026 SIGMOD 4.1945683e-05
10,269 Database Views as Explanations for Relational Deep Learning 2026 VLDB 4.1945683e-05
10,631 Is Integer Linear Programming All You Need for Deletion Propagation? 2025 VLDB 4.1945683e-05
10,715 What If: Causal Analysis with Graph Databases 2025 VLDB 4.1945683e-05
10,740 Finding Convincing Views to Endorse a Claim 2025 VLDB 4.1945683e-05
10,845 Versatile Property Graph Transformations 2025 VLDB 4.1945683e-05
10,910 Postulates for Provenance: Instance-based provenance for first-order logic 2024 PODS 4.1945683e-05
10,939 Relative Keys: Putting Feature Explanation into Context 2024 SIGMOD 4.1945683e-05
10,954 Counterfactual Explanation at Will, with Zero Privacy Leakage 2024 SIGMOD 4.1945683e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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
487 Why Not? 2009 SIGMOD 0.00022050218
627 Management of Probabilistic Data: Foundations and Challenges 2007 PODS 0.00018959005
652 On the Provenance of Non-Answers to Queries over Extracted Data 2008 VLDB 0.00018634477
1,125 How to ConQueR Why-Not Questions 2010 SIGMOD 0.00013845652
2,728 Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities 2009 SIGMOD 8.2185032e-05
2,790 Artemis: A System for Analyzing Missing Answers 2009 VLDB 8.1239026e-05
3,921 On the Complexity of Deriving Schema Mappings from Database Instances 2008 PODS 6.6301252e-05
Previous Page 1 / 1 Next

Semantically Similar Papers