DBScholar

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
10454
Venue
VLDB
Year
2011
Pagerank
0.00015839628
Overall Rank
605 | 95.86%
DOI
10.14778/1880172.1880176

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{meliou_vldb11,
        title = {{The Complexity of Causality and Responsibility for Query Answers and non-Answers}},
        author = {Meliou, Alexandra and Gatterbauer, Wolfgang and Moore, Katherine F. and Suciu, Dan},
        journal = {PVLDB},
        series = {{VLDB} '11},
        volume = {4},
        number = {1},
        pages = {34--45},
        doi = {10.14778/1880172.1880176},
        url = {https://doi.org/10.14778/1880172.1880176},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 53 citing papers.

Rank Citing Paper Year Venue Pagerank
11,329 PD-Explain: A Unified Python-native Framework for Query Explanations Over DataFrames 2024 VLDB 5.093636e-05
11,938 Provenance Summaries for Answers and Non-Answers 2018 VLDB 5.093636e-05
12,092 Looking at Everything in Context 2015 CIDR 5.093636e-05
Previous Page 2 / 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
17 Provenance Semirings 2007 PODS 0.00059843817
385 Why Not? 2009 SIGMOD 0.00019455743
574 Management of Probabilistic Data: Foundations and Challenges 2007 PODS 0.00016278855
628 On the Provenance of Non-Answers to Queries over Extracted Data 2008 VLDB 0.00015630285
856 How to ConQueR Why-Not Questions 2010 SIGMOD 0.00013573466
2,358 Artemis: A System for Analyzing Missing Answers 2009 VLDB 8.6996414e-05
2,831 Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities 2009 SIGMOD 8.0788784e-05
3,942 On the Complexity of Deriving Schema Mappings from Database Instances 2008 PODS 7.0063604e-05
Previous Page 1 / 1 Next

Semantically Similar Papers