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: 6889
Venue: SIGMOD
Year: 2024
Pagerank: 5.2688869e-05
Overall Rank: 5,918 | 58.88%
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,960	Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases	2024	PODS	5.251188e-05
8,663	Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms	2025	VLDB	4.4676883e-05
9,639	Shapley Revisited: Tractable Responsibility Measures for Query Answers	2025	PODS	4.3067693e-05
10,010	Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries	2026	PODS	4.1905499e-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.00078516827
487	Why Not?	2009	SIGMOD	0.00022030123
1,119	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.00013851012
2,259	ProvSQL: Provenance and Probability Management in PostgreSQL	2018	VLDB	9.1790333e-05
2,400	Causality and Explanations in Databases	2014	VLDB	8.884178e-05
2,770	The Semiring Framework for Database Provenance	2017	PODS	8.1495762e-05
2,876	Computing the Shapley Value of Facts in Query Answering	2022	SIGMOD	7.9739469e-05
3,030	The Impact of Negation on the Complexity of the Shapley Value in Conjunctive Queries	2020	PODS	7.676832e-05
5,132	CAPE: Explaining Outliers by Counterbalancing	2019	VLDB	5.6704051e-05
5,192	Going Beyond Provenance: Explaining Query Answers with Pattern-based Counterbalances	2019	SIGMOD	5.6324589e-05
6,424	ShapGraph: An Holistic View of Explanations through Provenance Graphs and Shapley Values	2022	SIGMOD	5.0618143e-05
6,700	Approximate Summaries for Why and Why-not Provenance	2020	VLDB	4.9534371e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,148	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	4.5717374e-05
10,000	A Unifying Algorithm for Hierarchical Queries	2026	PODS	4.1905499e-05
8,065	Efficient Computation of Quantiles over Joins	2023	PODS	4.5899218e-05
8,850	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4324268e-05
5,960	Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases	2024	PODS	5.251188e-05
3,702	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8251643e-05
10,007	Query Answering Under Volume-Based Diversity Functions	2026	PODS	4.1905499e-05
10,010	Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries	2026	PODS	4.1905499e-05
2,876	Computing the Shapley Value of Facts in Query Answering	2022	SIGMOD	7.9739469e-05
8,663	Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms	2025	VLDB	4.4676883e-05