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: h154cd7a09bc74de2
Venue: PODS
Year: 2017
Pagerank: 8.4928222e-05
Overall Rank: 2,418 | 83.75%
DOI: 10.1145/3034786.3056125

Incoming Non-self Citations Over Time

Authors

1. Todd J. Green (LogicBlox Inc.)
2. Val Tannen (University of Pennsylvania)

BibTeX Citation

@inproceedings{green_pods17,
        address = {New York, NY, USA},
        series = {{PODS} '17},
        title = {{The Semiring Framework for Database Provenance}},
        url = {https://dl.acm.org/doi/10.1145/3034786.3056125},
        doi = {10.1145/3034786.3056125},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Green, Todd J. and Tannen, Val},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,746	SMOKE: Fine-grained Lineage at Interactive Speed	2018	VLDB	9.7341914e-05
2,217	Computing the Shapley Value of Facts in Query Answering	2022	SIGMOD	8.8172185e-05
4,102	QED: A Powerful Query Equivalence Decider for SQL	2024	VLDB	6.8070264e-05
4,161	The Relational Data Borg is Learning	2020	VLDB	6.7700593e-05
4,195	PrIU: A Provenance-Based Approach for Incrementally Updating Regression Models	2020	SIGMOD	6.7422305e-05
5,055	ShapGraph: An Holistic View of Explanations through Provenance Graphs and Shapley Values	2022	SIGMOD	6.2944577e-05
5,793	Banzhaf Values for Facts in Query Answering	2024	SIGMOD	5.9930101e-05
8,275	The Complexity of Why-Provenance for Datalog Queries	2024	PODS	5.3641687e-05
8,495	Provenance-based Data Skipping	2022	VLDB	5.3304338e-05
8,762	Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries	2024	PODS	5.283642e-05
10,262	Automating Vectorized Distributed Graph Computation	2024	SIGMOD	5.050482e-05
10,739	Database Views as Explanations for Relational Deep Learning	2026	VLDB	4.9793485e-05
10,828	Toward Temporal Attribution Analytics in Dataflows	2026	VLDB	4.9793485e-05
11,120	Ultraverse: An Efficient What-if Analysis Framework for Software Applications Interacting with Database Systems	2025	SIGMOD	4.9793485e-05
11,466	Towards an Objective Metric for Data Value Through Relevance	2024	CIDR	4.9793485e-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
17	Provenance Semirings	2007	PODS	0.00059752575
84	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00035963861
390	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00019248147
819	Provenance for Aggregate Queries	2011	PODS	0.00013666629
978	Incremental Query Evaluation in a Ring of Databases	2010	PODS	0.00012731074
1,555	Update Exchange with Mappings and Provenance	2007	VLDB	0.00010269848
1,765	Putting Lipstick on Pig: Enabling Database-style Workflow Provenance	2012	VLDB	9.6955585e-05
1,809	ORCHESTRA: Rapid, Collaborative Sharing of Dynamic Data	2005	CIDR	9.5935116e-05
1,827	Querying Data Provenance	2010	SIGMOD	9.5545888e-05
1,944	Caravan: Provisioning for What-If Analysis	2013	CIDR	9.3281326e-05
2,843	Data Provenance at Internet Scale: Architecture, Experiences, and the Road Ahead	2017	CIDR	7.9491056e-05
3,544	Unicorn: A System for Searching the Social Graph	2013	VLDB	7.2136759e-05
5,611	Annotated XML: Queries and Provenance	2008	PODS	6.0684862e-05
6,457	On Provenance Minimization	2011	PODS	5.7779266e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,406	Semigroup techniques in recursive query optimization	1990	PODS
2	1,680	Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries	2018	VLDB
3	13,391	Deductive Databases in Action	1991	PODS
4	50	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB
5	12,503	A Provenance Framework for Data-Dependent Process Analysis	2014	VLDB
6	4,222	Foundations of Semantic Web Databases	2004	PODS
7	6,457	On Provenance Minimization	2011	PODS
8	819	Provenance for Aggregate Queries	2011	PODS
9	17	Provenance Semirings	2007	PODS
10	1,827	Querying Data Provenance	2010	SIGMOD