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: 14207
Venue: VLDB
Year: 2025
Pagerank: 5.3847009e-05
Overall Rank: 8,688 | 40.40%
DOI: 10.14778/3749646.3749670

Incoming Non-self Citations Over Time

Authors

1. Omer Abramovich (Tel Aviv University)
2. Daniel Deutch (Tel Aviv University)
3. Nave Frost (eBay)
4. Ahmet Kara (Ostbayerische Technische Hochschule Regensburg)
5. Dan Olteanu (University of Zurich)

BibTeX Citation

@article{abramovich_vldb25,
        title = {{Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms}},
        author = {Abramovich, Omer and Deutch, Daniel and Frost, Nave and Kara, Ahmet and Olteanu, Dan},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {11},
        pages = {3996--4008},
        doi = {10.14778/3749646.3749670},
        url = {https://doi.org/10.14778/3749646.3749670},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,183	Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries	2026	PODS	5.093636e-05
10,429	Analyzing Deviations from Monotonic Trends through Database Repair	2026	SIGMOD	5.093636e-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
605	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.00015839628
806	Provenance for Aggregate Queries	2011	PODS	0.00013890398
1,943	Causality and Explanations in Databases	2014	VLDB	9.440636e-05
1,965	ProvSQL: Provenance and Probability Management in PostgreSQL	2018	VLDB	9.3852716e-05
2,424	Computing the Shapley Value of Facts in Query Answering	2022	SIGMOD	8.6009068e-05
2,670	The Impact of Negation on the Complexity of the Shapley Value in Conjunctive Queries	2020	PODS	8.2737143e-05
3,918	From Shapley Value to Model Counting and Back	2024	PODS	7.0181891e-05
4,098	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB	6.9035475e-05
5,382	Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases	2024	PODS	6.237788e-05
5,441	Fast Shapley Value Computation in Data Assemblage Tasks as Cooperative Simple Games	2024	SIGMOD	6.2184806e-05
5,660	Banzhaf Values for Facts in Query Answering	2024	SIGMOD	6.1305635e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,262	Discovering Queries based on Example Tuples	2014	SIGMOD
2	10,180	Query Answering Under Volume-Based Diversity Functions	2026	PODS
3	5,164	Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints	2003	VLDB
4	2,511	Aggregation and Relevance in Deductive Databases	1991	VLDB
5	2,424	Computing the Shapley Value of Facts in Query Answering	2022	SIGMOD
6	2,608	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD
7	12,386	Efficient Rank Join with Aggregation Constraints	2011	VLDB
8	860	Aggregation and Ordering in Factorised Databases	2013	VLDB
9	10,183	Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries	2026	PODS
10	5,660	Banzhaf Values for Facts in Query Answering	2024	SIGMOD