Provenance Semirings

Summary: Comm. semirings unify provenance: bag, probabilistic, incomplete DBs and why‑provenance are instances and positive relational-algebra semantics factor through semiring homomorphisms. Proposes polynomial/formal‑power‑series provenance, extends to Datalog via fixed‑point semirings and gives algorithms to decide/compute finite series and monomial coefficients. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h5dd3a15a7e2c5fe0
Venue: PODS
Year: 2007
Pagerank: 0.00059660827
Overall Rank: 17 | 99.89%
DOI: 10.1145/1265530.1265535

Incoming Non-self Citations Over Time

Authors

1. Todd J. Green (University of Pennsylvania)
2. Grigoris Karvounarakis (University of Pennsylvania)
3. Val Tannen (University of Pennsylvania)

BibTeX Citation

@inproceedings{green_pods07,
        address = {New York, NY, USA},
        series = {{PODS} '07},
        title = {{Provenance Semirings}},
        url = {https://dl.acm.org/doi/10.1145/1265530.1265535},
        doi = {10.1145/1265530.1265535},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Green, Todd J. and Karvounarakis, Grigoris and Tannen, Val},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 183 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
208	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024929198
581	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.00016042765
624	On the Provenance of Non-Answers to Queries over Extracted Data	2008	VLDB	0.00015438077
787	Cosette: An Automated Prover for SQL	2017	CIDR	0.00013959502
811	Provenance for Aggregate Queries	2011	PODS	0.00013713646
858	Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins	2013	SIGMOD	0.00013391977
979	Incremental Query Evaluation in a Ring of Databases	2010	PODS	0.00012697012
1,055	Tiresias: The Database Oracle for How-To Queries	2012	SIGMOD	0.0001225364
1,079	Curated Databases	2008	PODS	0.00012117197
1,367	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00010878876
1,556	Update Exchange with Mappings and Provenance	2007	VLDB	0.00010232016
1,568	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.00010178045
1,597	Data Markets in the Cloud: An Opportunity for the Database Community	2011	VLDB	0.00010096805
1,619	Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases	2011	SIGMOD	0.00010044303
1,678	Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries	2018	VLDB	9.8966017e-05
1,776	Putting Lipstick on Pig: Enabling Database-style Workflow Provenance	2012	VLDB	9.6661217e-05
1,795	Approximate Lineage for Probabilistic Databases	2008	VLDB	9.6147575e-05
1,822	ProvSQL: Provenance and Probability Management in PostgreSQL	2018	VLDB	9.5464187e-05
1,837	Querying Data Provenance	2010	SIGMOD	9.5210079e-05
1,838	CHORUS: Foundation Models for Unified Data Discovery and Exploration	2024	VLDB	9.5195856e-05
1,858	Data Market Platforms: Trading Data Assets to Solve Data Problems	2020	VLDB	9.4779185e-05
1,888	WeTune: Automatic Discovery and Verification of Query Rewrite Rules	2022	SIGMOD	9.4148912e-05
1,953	Caravan: Provisioning for What-If Analysis	2013	CIDR	9.297314e-05
2,015	Orchestra: Facilitating Collaborative Data Sharing	2007	SIGMOD	9.1743528e-05
2,234	Computing the Shapley Value of Facts in Query Answering	2022	SIGMOD	8.7839031e-05
2,298	FDB: A Query Engine for Factorised Relational Databases	2012	VLDB	8.6645337e-05
2,427	The Semiring Framework for Database Provenance	2017	PODS	8.4673732e-05
2,459	Tracing Data Errors with View-Conditioned Causality	2011	SIGMOD	8.4137923e-05
2,473	Complaint-driven Training Data Debugging for Query 2.0	2020	SIGMOD	8.3984284e-05
2,492	Query-Oriented Data Cleaning with Oracles	2015	SIGMOD	8.3722864e-05
2,638	Convergence of Datalog over (Pre-) Semirings	2022	PODS	8.1763678e-05
2,685	Data X-Ray: A Diagnostic Tool for Data Errors	2015	SIGMOD	8.116387e-05
2,962	Reverse Data Management	2011	VLDB	7.7949147e-05
3,100	Learning to Create Data-Integrating Queries	2008	VLDB	7.6312005e-05
3,122	Incremental View Maintenance with Triple Lock Factorization Benefits	2018	SIGMOD	7.6091671e-05
3,194	Demonstration of the Cosette Automated SQL Prover	2017	SIGMOD	7.5310063e-05
3,223	How Large Language Models Will Disrupt Data Management	2023	VLDB	7.5043163e-05
3,373	Efficient Querying and Maintenance of Network Provenance at Internet-Scale	2010	SIGMOD	7.348575e-05
3,444	Complete Yet Practical Search for Minimal Query Reformulations Under Constraints	2014	SIGMOD	7.277762e-05
3,553	Consensus Answers for Queries over Probabilistic Databases	2009	PODS	7.188315e-05
3,684	DBSP: Automatic Incremental View Maintenance for Rich Query Languages	2023	VLDB	7.0834345e-05
4,011	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	6.842581e-05
4,020	From Shapley Value to Model Counting and Back	2024	PODS	6.8347969e-05
4,085	The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries	2016	VLDB	6.7989526e-05
4,196	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB	6.7317801e-05
4,203	PrIU: A Provenance-Based Approach for Incrementally Updating Regression Models	2020	SIGMOD	6.7255278e-05
4,347	Query Refinement for Diversity Constraint Satisfaction	2024	VLDB	6.6380671e-05
4,354	LIMA: Fine-grained Lineage Tracing and Reuse in Machine Learning Systems	2021	SIGMOD	6.6318545e-05
4,487	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	6.5628751e-05
4,505	SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra	2020	VLDB	6.5561966e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00042804864
85	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00035848027
391	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.0001918714
533	The Magic of Duplicates and Aggregates	1990	VLDB	0.00016794756
846	Debugging Schema Mappings with Routes	2006	VLDB	0.00013486084

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,678	Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries	2018	VLDB
2	6,313	Classification of Annotation Semirings over Query Containment	2012	PODS
3	8,338	Computing How-Provenance for SPARQL Queries via Query Rewriting	2021	VLDB
4	8,099	Tight Bounds of Circuits for Sum-Product Queries	2024	PODS
5	2,427	The Semiring Framework for Database Provenance	2017	PODS
6	5,623	Annotated XML: Queries and Provenance	2008	PODS
7	6,472	On Provenance Minimization	2011	PODS
8	9,630	Equivalence-Invariant Algebraic Provenance for Hyperplane Update Queries	2020	SIGMOD
9	1,837	Querying Data Provenance	2010	SIGMOD
10	811	Provenance for Aggregate Queries	2011	PODS