Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms

Summary: First practical method to compute Banzhaf and Shapley contributions for aggregate queries (beyond SPJUU). Two optimizations—grouping equal-contribution tuples and using lineage gradients to amortize cost—yield up to 1000× speedups and scale to million-instance tests. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 14019
Venue: VLDB
Year: 2025
Pagerank: 4.471975e-05
Overall Rank: 8,665 | 39.72%
DOI: 10.14778/3749646.3749670

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,010	Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries	2026	PODS	4.1945683e-05
10,140	Analyzing Deviations from Monotonic Trends through Database Repair	2026	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,106	Provenance for Aggregate Queries	2011	PODS	0.0001398766
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,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
4,591	From Shapley Value to Model Counting and Back	2024	PODS	6.0619399e-05
4,706	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB	5.9820914e-05
5,916	Banzhaf Values for Facts in Query Answering	2024	SIGMOD	5.273953e-05
5,959	Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases	2024	PODS	5.2562342e-05
6,262	Fast Shapley Value Computation in Data Assemblage Tasks as Cooperative Simple Games	2024	SIGMOD	5.1349507e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,106	Provenance for Aggregate Queries	2011	PODS	0.0001398766
1,509	Discovering Queries based on Example Tuples	2014	SIGMOD	0.00011612727
5,299	Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints	2003	VLDB	5.5796719e-05
2,544	Aggregation and Relevance in Deductive Databases	1991	VLDB	8.5730083e-05
2,808	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD	8.0870741e-05
2,868	Computing the Shapley Value of Facts in Query Answering	2022	SIGMOD	7.9816425e-05
12,191	Efficient Rank Join with Aggregation Constraints	2011	VLDB	4.1945683e-05
1,259	Aggregation and Ordering in Factorised Databases	2013	VLDB	0.00012995821
10,010	Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries	2026	PODS	4.1945683e-05
5,916	Banzhaf Values for Facts in Query Answering	2024	SIGMOD	5.273953e-05