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: 1736
Venue: PODS
Year: 2017
Pagerank: 8.4964654e-05
Overall Rank: 2,503 | 82.83%
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 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,798	SMOKE: Fine-grained Lineage at Interactive Speed	2018	VLDB	9.7361937e-05
2,424	Computing the Shapley Value of Facts in Query Answering	2022	SIGMOD	8.6009068e-05
4,128	The Relational Data Borg is Learning	2020	VLDB	6.8850804e-05
4,130	PrIU: A Provenance-Based Approach for Incrementally Updating Regression Models	2020	SIGMOD	6.8839621e-05
5,353	QED: A Powerful Query Equivalence Decider for SQL	2024	VLDB	6.2519268e-05
5,660	Banzhaf Values for Facts in Query Answering	2024	SIGMOD	6.1305635e-05
5,824	ShapGraph: An Holistic View of Explanations through Provenance Graphs and Shapley Values	2022	SIGMOD	6.0750989e-05
8,100	The Complexity of Why-Provenance for Datalog Queries	2024	PODS	5.4872887e-05
8,599	Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries	2024	PODS	5.4049137e-05
8,889	Provenance-based Data Skipping	2022	VLDB	5.3512428e-05
10,557	Database Views as Explanations for Relational Deep Learning	2026	VLDB	5.093636e-05
10,680	Ultraverse: An Efficient What-if Analysis Framework for Software Applications Interacting with Database Systems	2025	SIGMOD	5.093636e-05
11,118	Towards an Objective Metric for Data Value Through Relevance	2024	CIDR	5.093636e-05
11,208	Automating Vectorized Distributed Graph Computation	2024	SIGMOD	5.093636e-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.00059843817
78	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00036571789
382	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00019546431
806	Provenance for Aggregate Queries	2011	PODS	0.00013890398
960	Incremental Query Evaluation in a Ring of Databases	2010	PODS	0.00012945163
1,599	Update Exchange with Mappings and Provenance	2007	VLDB	0.00010241307
1,781	ORCHESTRA: Rapid, Collaborative Sharing of Dynamic Data	2005	CIDR	9.7739542e-05
1,786	Putting Lipstick on Pig: Enabling Database-style Workflow Provenance	2012	VLDB	9.7690421e-05
1,912	Querying Data Provenance	2010	SIGMOD	9.4946756e-05
1,952	Caravan: Provisioning for What-If Analysis	2013	CIDR	9.4233049e-05
2,807	Data Provenance at Internet Scale: Architecture, Experiences, and the Road Ahead	2017	CIDR	8.1009158e-05
3,499	Unicorn: A System for Searching the Social Graph	2013	VLDB	7.362886e-05
5,502	Annotated XML: Queries and Provenance	2008	PODS	6.1961339e-05
6,358	On Provenance Minimization	2011	PODS	5.9020113e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,901	How Can Reasoners Simplify Database Querying (And Why Haven’t They Done It Yet)?	2018	PODS
2	1,829	Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries	2018	VLDB
3	13,101	Deductive Databases in Action	1991	PODS
4	48	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB
5	12,212	A Provenance Framework for Data-Dependent Process Analysis	2014	VLDB
6	4,139	Foundations of Semantic Web Databases	2004	PODS
7	6,358	On Provenance Minimization	2011	PODS
8	806	Provenance for Aggregate Queries	2011	PODS
9	17	Provenance Semirings	2007	PODS
10	1,912	Querying Data Provenance	2010	SIGMOD