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: 1413
Venue: PODS
Year: 2007
Pagerank: 0.0007857786
Overall Rank: 31 | 99.79%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 26 of 176 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,954	Counterfactual Explanation at Will, with Zero Privacy Leakage	2024	SIGMOD	4.1945683e-05
10,976	StarfishDB: a Query Execution Engine for Relational Probabilistic Programming	2024	SIGMOD	4.1945683e-05
10,997	Automating Vectorized Distributed Graph Computation	2024	SIGMOD	4.1945683e-05
11,179	Probabilistic Reasoning at Scale: Trigger Graphs to the Rescue	2023	SIGMOD	4.1945683e-05
11,220	Lightweight Materialization for Fast Dashboards Over Joins	2023	SIGMOD	4.1945683e-05
11,294	Erica: Query Refinement for Diversity Constraint Satisfaction	2023	VLDB	4.1945683e-05
11,300	Towards Auto-Generated Data Systems	2023	VLDB	4.1945683e-05
11,399	ActivePDB: Active Probabilistic Databases	2022	VLDB	4.1945683e-05
11,462	INCA: Inconsistency-Aware Data Profiling and Querying	2021	SIGMOD	4.1945683e-05
11,471	On Optimizing the Trade-off between Privacy and Utility in Data Provenance	2021	SIGMOD	4.1945683e-05
11,557	Aggregate Queries on Sparse Databases	2020	PODS	4.1945683e-05
11,616	MuSe: Multiple Deletion Semantics for Data Repair	2020	VLDB	4.1945683e-05
11,647	Ariadne: Online Provenance for Big Graph Analytics	2019	SIGMOD	4.1945683e-05
11,666	RATest: Explaining Wrong Relational Queries Using Small Examples	2019	SIGMOD	4.1945683e-05
11,723	Data Citation: Giving Credit Where Credit is Due	2018	SIGMOD	4.1945683e-05
11,733	Provenance Summaries for Answers and Non-Answers	2018	VLDB	4.1945683e-05
11,735	QuestPro: Queries in SPARQL Through Provenance	2018	VLDB	4.1945683e-05
11,760	A Model for Fine-Grained Data Citation	2017	CIDR	4.1945683e-05
11,766	2017 ACM PODS Alberto O. Mendelzon Test-of-Time Award	2017	PODS	4.1945683e-05
11,767	Data Citation: a Computational Challenge	2017	PODS	4.1945683e-05
11,945	A Demonstration of TripleProv: Tracking and Querying Provenance over Web Data	2015	VLDB	4.1945683e-05
12,014	A Provenance Framework for Data-Dependent Process Analysis	2014	VLDB	4.1945683e-05
12,052	Provenance-based Dictionary Refinement in Information Extraction	2013	SIGMOD	4.1945683e-05
12,094	On Scaling Up Sensitive Data Auditing	2013	VLDB	4.1945683e-05
12,113	Mob Data Sourcing	2012	SIGMOD	4.1945683e-05
12,457	Provenance in Databases (Tutorial Outline)	2007	SIGMOD	4.1945683e-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
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057857292
101	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.0004955674
407	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024004562
445	The Magic of Duplicates and Aggregates	1990	VLDB	0.0002294367
689	Debugging Schema Mappings with Routes	2006	VLDB	0.00018111991

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,099	Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries	2018	VLDB	9.5479391e-05
6,274	Classification of Annotation Semirings over Query Containment	2012	PODS	5.1321227e-05
8,960	Computing How-Provenance for SPARQL Queries via Query Rewriting	2021	VLDB	4.4206222e-05
10,905	Tight Bounds of Circuits for Sum-Product Queries	2024	PODS	4.1945683e-05
2,764	The Semiring Framework for Database Provenance	2017	PODS	8.1574444e-05
5,270	Annotated XML: Queries and Provenance	2008	PODS	5.5963545e-05
6,186	On Provenance Minimization	2011	PODS	5.166082e-05
9,179	Equivalence-Invariant Algebraic Provenance for Hyperplane Update Queries	2020	SIGMOD	4.3820222e-05
2,173	Querying Data Provenance	2010	SIGMOD	9.3676609e-05
1,106	Provenance for Aggregate Queries	2011	PODS	0.0001398766