Banzhaf Values for Facts in Query Answering

Summary: Banzhaf values as a principled explanation metric for fact contributions to query answers; introduces exact, anytime-approximate, and top-k/ranking algorithms via lineage compilation and DP on Boolean functions. Also proves a tractability dichotomy for Banzhaf ranking (hierarchical vs. non-hierarchical queries) and shows large speedups over prior methods. (summarized by gpt-5.4-mini on May 24 2026)

Paper ID: 6888
Venue: SIGMOD
Year: 2024
Pagerank: 5.273953e-05
Overall Rank: 5,916 | 58.85%
DOI: 10.1145/3654926

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,959	Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases	2024	PODS	5.2562342e-05
8,665	Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms	2025	VLDB	4.471975e-05
9,640	Shapley Revisited: Tractable Responsibility Measures for Query Answers	2025	PODS	4.3109001e-05
10,010	Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries	2026	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 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
1,119	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.0001386199
2,256	ProvSQL: Provenance and Probability Management in PostgreSQL	2018	VLDB	9.1879032e-05
2,402	Causality and Explanations in Databases	2014	VLDB	8.8928361e-05
2,764	The Semiring Framework for Database Provenance	2017	PODS	8.1574444e-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
5,128	CAPE: Explaining Outliers by Counterbalancing	2019	VLDB	5.6758584e-05
5,191	Going Beyond Provenance: Explaining Query Answers with Pattern-based Counterbalances	2019	SIGMOD	5.6378768e-05
6,429	ShapGraph: An Holistic View of Explanations through Provenance Graphs and Shapley Values	2022	SIGMOD	5.0666822e-05
6,696	Approximate Summaries for Why and Why-not Provenance	2020	VLDB	4.9581958e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,692	Processing Top-k Join Queries	2010	VLDB	4.6761366e-05
8,145	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	4.5761263e-05
10,001	A Unifying Algorithm for Hierarchical Queries	2026	PODS	4.1945683e-05
8,061	Efficient Computation of Quantiles over Joins	2023	PODS	4.5943269e-05
8,851	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4363908e-05
5,959	Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases	2024	PODS	5.2562342e-05
3,715	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8220943e-05
10,010	Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries	2026	PODS	4.1945683e-05
2,868	Computing the Shapley Value of Facts in Query Answering	2022	SIGMOD	7.9816425e-05
8,665	Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms	2025	VLDB	4.471975e-05