Database Paper Browser

Back to papers

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 50 of 176 citing papers.

Rank Citing Paper Year Venue Pagerank
8,145 Evaluating Top-k Queries with Inconsistency Degrees 2020 VLDB 4.5761263e-05
8,163 Capturing and Querying Fine-grained Provenance of Preprocessing Pipelines in Data Science 2021 VLDB 4.5723431e-05
8,212 I-Rex: An Interactive Relational Query Explainer for SQL 2020 VLDB 4.5580125e-05
8,230 You Say 'What', I Hear 'Where' and 'Why' - (Mis-)Interpreting SQL to Derive Fine-Grained Provenance 2018 VLDB 4.5541444e-05
8,340 Beta Probabilistic Databases: A Scalable Approach to Belief Updating and Parameter Learning 2017 SIGMOD 4.5433598e-05
8,345 SlabCity: Whole-Query Optimization using Program Synthesis 2023 VLDB 4.5426916e-05
8,369 Expressive Power of Linear Algebra Query Languages 2021 PODS 4.534839e-05
8,388 FEDEX: An Explainability Framework for Data Exploration Steps 2022 VLDB 4.5297787e-05
8,394 Hypothetical Reasoning via Provenance Abstraction 2019 SIGMOD 4.527807e-05
8,508 Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries 2024 PODS 4.4952414e-05
8,589 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 4.4897014e-05
8,853 Complaint-Driven Training Data Debugging at Interactive Speeds 2022 SIGMOD 4.4350727e-05
8,886 Provenance-based Data Skipping 2022 VLDB 4.4279829e-05
8,954 Understanding Queries by Conditional Instances 2022 SIGMOD 4.4221863e-05
8,960 Computing How-Provenance for SPARQL Queries via Query Rewriting 2021 VLDB 4.4206222e-05
8,966 Output-sensitive Conjunctive Query Evaluation 2024 PODS 4.4193184e-05
9,043 Query-Guided Resolution in Uncertain Databases 2023 SIGMOD 4.4039656e-05
9,044 Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data 2023 VLDB 4.4039656e-05
9,088 Collaborative Access Control in WebdamLog 2015 SIGMOD 4.3992936e-05
9,130 Enabling Personal Consent in Databases 2022 VLDB 4.3900952e-05
9,179 Equivalence-Invariant Algebraic Provenance for Hyperplane Update Queries 2020 SIGMOD 4.3820222e-05
9,202 Compact, Tamper-Resistant Archival of Fine-Grained Provenance 2021 VLDB 4.3742967e-05
9,551 Data Integration and Data Exchange: It’s Really About Time 2013 CIDR 4.3255102e-05
9,622 NLProv: Natural Language Provenance 2016 VLDB 4.3163112e-05
9,766 DPXPlain: Privately Explaining Aggregate Query Answers 2023 VLDB 4.2856106e-05
9,813 Datalog with First-Class Facts 2025 VLDB 4.2783272e-05
9,907 PROPOLIS: Provisioned Analysis of Data-Centric Processes 2013 VLDB 4.2577164e-05
9,921 ProvCite: Provenance-based Data Citation 2019 VLDB 4.2549509e-05
9,968 Please Don't Kill My Vibe: Empowering Agents with Data Flow Control 2026 CIDR 4.1945683e-05
10,004 Codd's Theorem for Databases over Semirings 2026 PODS 4.1945683e-05
10,049 Approximate Query Processing under Updates 2026 SIGMOD 4.1945683e-05
10,284 FlowLog: Efficient and Extensible Datalog via Incrementality 2026 VLDB 4.1945683e-05
10,343 Circuit Bounds for Conjunctive Queries with Self-joins 2025 PODS 4.1945683e-05
10,344 Circuits and Formulas for Datalog over Semirings 2025 PODS 4.1945683e-05
10,357 Rewriting Consistent Answers on Annotated Data 2025 PODS 4.1945683e-05
10,359 Smallest Synthetic Witnesses for Conjunctive Queries 2025 PODS 4.1945683e-05
10,377 FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds 2025 SIGMOD 4.1945683e-05
10,393 SHARQ: Explainability Framework for Association Rules on Relational Data 2025 SIGMOD 4.1945683e-05
10,546 Evaluating Continuous Queries with Inconsistency Annotations 2025 VLDB 4.1945683e-05
10,551 Avoiding Materialisation for Guarded Aggregate Queries 2025 VLDB 4.1945683e-05
10,676 Meaningful Data Erasure in the Presence of Dependencies 2025 VLDB 4.1945683e-05
10,725 Suna: Scalable Causal Confounder Discovery over Relational Data 2025 VLDB 4.1945683e-05
10,762 ParSEval: Plan-aware Test Database Generation for SQL Equivalence Evaluation 2025 VLDB 4.1945683e-05
10,886 FaDE: More Than a Million What-ifs Per Second 2025 VLDB 4.1945683e-05
10,905 Tight Bounds of Circuits for Sum-Product Queries 2024 PODS 4.1945683e-05
10,910 Postulates for Provenance: Instance-based provenance for first-order logic 2024 PODS 4.1945683e-05
10,915 Consistency of Relations over Monoids 2024 PODS 4.1945683e-05
10,922 Below and Above Why-Provenance for Datalog Queries 2024 PODS 4.1945683e-05
10,929 Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs 2024 PODS 4.1945683e-05
10,939 Relative Keys: Putting Feature Explanation into Context 2024 SIGMOD 4.1945683e-05
Previous Page 3 / 4 Next

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
Previous Page 1 / 1 Next

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