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.4673732e-05
Overall Rank: 2,427 | 83.74%
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,722	SMOKE: Fine-grained Lineage at Interactive Speed	2018	VLDB	9.781628e-05
2,234	Computing the Shapley Value of Facts in Query Answering	2022	SIGMOD	8.7839031e-05
4,116	QED: A Powerful Query Equivalence Decider for SQL	2024	VLDB	6.7846764e-05
4,174	The Relational Data Borg is Learning	2020	VLDB	6.750725e-05
4,203	PrIU: A Provenance-Based Approach for Incrementally Updating Regression Models	2020	SIGMOD	6.7255278e-05
5,078	ShapGraph: An Holistic View of Explanations through Provenance Graphs and Shapley Values	2022	SIGMOD	6.2706745e-05
5,809	Banzhaf Values for Facts in Query Answering	2024	SIGMOD	5.9703658e-05
8,296	The Complexity of Why-Provenance for Datalog Queries	2024	PODS	5.3439005e-05
8,505	Provenance-based Data Skipping	2022	VLDB	5.3126038e-05
8,789	Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries	2024	PODS	5.263678e-05
9,192	Automating Vectorized Distributed Graph Computation	2024	SIGMOD	5.1967502e-05
10,810	Database Views as Explanations for Relational Deep Learning	2026	VLDB	4.9605343e-05
10,899	Toward Temporal Attribution Analytics in Dataflows	2026	VLDB	4.9605343e-05
11,189	Ultraverse: An Efficient What-if Analysis Framework for Software Applications Interacting with Database Systems	2025	SIGMOD	4.9605343e-05
11,524	Towards an Objective Metric for Data Value Through Relevance	2024	CIDR	4.9605343e-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.00059660827
85	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00035848027
391	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.0001918714
811	Provenance for Aggregate Queries	2011	PODS	0.00013713646
979	Incremental Query Evaluation in a Ring of Databases	2010	PODS	0.00012697012
1,556	Update Exchange with Mappings and Provenance	2007	VLDB	0.00010232016
1,776	Putting Lipstick on Pig: Enabling Database-style Workflow Provenance	2012	VLDB	9.6661217e-05
1,818	ORCHESTRA: Rapid, Collaborative Sharing of Dynamic Data	2005	CIDR	9.5594619e-05
1,837	Querying Data Provenance	2010	SIGMOD	9.5210079e-05
1,953	Caravan: Provisioning for What-If Analysis	2013	CIDR	9.297314e-05
2,847	Data Provenance at Internet Scale: Architecture, Experiences, and the Road Ahead	2017	CIDR	7.9235089e-05
3,554	Unicorn: A System for Searching the Social Graph	2013	VLDB	7.1879224e-05
5,623	Annotated XML: Queries and Provenance	2008	PODS	6.045738e-05
6,472	On Provenance Minimization	2011	PODS	5.7561073e-05

Semantically Similar Papers

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