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)
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 32 of 182 citing papers.
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.00042936299 |
| 84 | ULDBs: Databases with Uncertainty and Lineage | 2006 | VLDB | 0.00035963861 |
| 390 | Conjunctive-Query Containment and Constraint Satisfaction | 1998 | PODS | 0.00019248147 |
| 531 | The Magic of Duplicates and Aggregates | 1990 | VLDB | 0.00016847212 |
| 845 | Debugging Schema Mappings with Routes | 2006 | VLDB | 0.00013526977 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 1,680 | Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries | 2018 | VLDB |
| 2 | 6,299 | Classification of Annotation Semirings over Query Containment | 2012 | PODS |
| 3 | 8,330 | Computing How-Provenance for SPARQL Queries via Query Rewriting | 2021 | VLDB |
| 4 | 8,073 | Tight Bounds of Circuits for Sum-Product Queries | 2024 | PODS |
| 5 | 2,418 | The Semiring Framework for Database Provenance | 2017 | PODS |
| 6 | 5,611 | Annotated XML: Queries and Provenance | 2008 | PODS |
| 7 | 6,457 | On Provenance Minimization | 2011 | PODS |
| 8 | 9,596 | Equivalence-Invariant Algebraic Provenance for Hyperplane Update Queries | 2020 | SIGMOD |
| 9 | 1,827 | Querying Data Provenance | 2010 | SIGMOD |
| 10 | 819 | Provenance for Aggregate Queries | 2011 | PODS |