The Semiring Framework for Database Provenance

Summary: Retrospective distillation of the semiring framework for database provenance, emphasizing overlooked insights about its algebraic abstraction of provenance via commutative semirings. Not a survey—selectively omits Datalog, collects extensive references, and aims to provoke follow-up research. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1737
Venue: PODS
Year: 2017
Pagerank: 8.1495762e-05
Overall Rank: 2,770 | 80.75%
DOI: 10.1145/3034786.3056125

Incoming Non-self Citations Over Time

Authors

1. Todd J. Green
2. Val Tannen

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,286	SMOKE: Fine-grained Lineage at Interactive Speed	2018	VLDB	9.102574e-05
2,876	Computing the Shapley Value of Facts in Query Answering	2022	SIGMOD	7.9739469e-05
4,423	PrIU: A Provenance-Based Approach for Incrementally Updating Regression Models	2020	SIGMOD	6.1925724e-05
4,787	The Relational Data Borg is Learning	2020	VLDB	5.9168117e-05
5,245	QED: A Powerful Query Equivalence Decider for SQL	2024	VLDB	5.6017846e-05
5,918	Banzhaf Values for Facts in Query Answering	2024	SIGMOD	5.2688869e-05
6,424	ShapGraph: An Holistic View of Explanations through Provenance Graphs and Shapley Values	2022	SIGMOD	5.0618143e-05
8,129	The Complexity of Why-Provenance for Datalog Queries	2024	PODS	4.5753896e-05
8,506	Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries	2024	PODS	4.4909322e-05
8,886	Provenance-based Data Skipping	2022	VLDB	4.4237386e-05
10,269	Database Views as Explanations for Relational Deep Learning	2026	VLDB	4.1905499e-05
10,405	Ultraverse: An Efficient What-if Analysis Framework for Software Applications Interacting with Database Systems	2025	SIGMOD	4.1905499e-05
10,899	Towards an Objective Metric for Data Value Through Relevance	2024	CIDR	4.1905499e-05
11,000	Automating Vectorized Distributed Graph Computation	2024	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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
103	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00049520051
401	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024281448
1,106	Provenance for Aggregate Queries	2011	PODS	0.00013976386
1,231	Incremental Query Evaluation in a Ring of Databases	2010	PODS	0.00013141213
1,646	Caravan: Provisioning for What-If Analysis	2013	CIDR	0.00011026644
1,765	ORCHESTRA: Rapid, Collaborative Sharing of Dynamic Data	2005	CIDR	0.00010614654
1,868	Update Exchange with Mappings and Provenance	2007	VLDB	0.0001026365
2,031	Putting Lipstick on Pig: Enabling Database-style Workflow Provenance	2012	VLDB	9.7341007e-05
2,182	Querying Data Provenance	2010	SIGMOD	9.3596252e-05
2,903	Data Provenance at Internet Scale: Architecture, Experiences, and the Road Ahead	2017	CIDR	7.9403877e-05
3,948	Unicorn: A System for Searching the Social Graph	2013	VLDB	6.5968941e-05
5,275	Annotated XML: Queries and Provenance	2008	PODS	5.5908918e-05
6,187	On Provenance Minimization	2011	PODS	5.1611195e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,931	Semigroup techniques in recursive query optimization	1990	PODS	4.1905499e-05
2,097	Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries	2018	VLDB	9.5439744e-05
12,916	Deductive Databases in Action	1991	PODS	4.1905499e-05
61	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00064281097
12,022	A Provenance Framework for Data-Dependent Process Analysis	2014	VLDB	4.1905499e-05
3,285	Foundations of Semantic Web Databases	2004	PODS	7.2738104e-05
6,187	On Provenance Minimization	2011	PODS	5.1611195e-05
1,106	Provenance for Aggregate Queries	2011	PODS	0.00013976386
31	Provenance Semirings	2007	PODS	0.00078516827
2,182	Querying Data Provenance	2010	SIGMOD	9.3596252e-05