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
5,104 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 5.6946113e-05
5,128 CAPE: Explaining Outliers by Counterbalancing 2019 VLDB 5.6758584e-05
5,191 Going Beyond Provenance: Explaining Query Answers with Pattern-based Counterbalances 2019 SIGMOD 5.6378768e-05
5,209 Explaining Outputs in Modern Data Analytics 2016 VLDB 5.629362e-05
5,222 Enabling SQL-based Training Data Debugging for Federated Learning 2022 VLDB 5.6210545e-05
5,270 Annotated XML: Queries and Provenance 2008 PODS 5.5963545e-05
5,364 A Quest for Beauty and Wealth (or, Business Processes for Database Researchers) 2011 PODS 5.5461492e-05
5,418 High-Level Why-Not Explanations using Ontologies 2015 PODS 5.5178123e-05
5,445 QFix: Diagnosing Errors through Query Histories 2017 SIGMOD 5.5020909e-05
5,487 SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra 2020 VLDB 5.4791501e-05
5,638 Circuit Treewidth, Sentential Decision, and Query Compilation 2017 PODS 5.3965476e-05
5,639 Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins 2021 PODS 5.393897e-05
5,691 Putting Things into Context: Rich Explanations for Query Answers using Join Graphs 2021 SIGMOD 5.3684557e-05
5,708 Lineage-driven Fault Injection 2015 SIGMOD 5.3603939e-05
5,733 Explaining Wrong Queries Using Small Examples 2019 SIGMOD 5.3483446e-05
5,779 Lenses: An On-Demand Approach to ETL 2015 VLDB 5.3307398e-05
5,916 Banzhaf Values for Facts in Query Answering 2024 SIGMOD 5.273953e-05
5,944 DBSP: Automatic Incremental View Maintenance for Rich Query Languages 2023 VLDB 5.2628186e-05
5,992 Evaluating Datalog over Semirings: A Grounding-based Approach 2024 PODS 5.2415551e-05
6,084 Distributed Provenance Compression 2017 SIGMOD 5.2196728e-05
6,156 Optimizing Tensor Programs on Flexible Storage 2023 SIGMOD 5.1802603e-05
6,186 On Provenance Minimization 2011 PODS 5.166082e-05
6,274 Classification of Annotation Semirings over Query Containment 2012 PODS 5.1321227e-05
6,278 Uncertainty Aware Query Execution Time Prediction 2014 VLDB 5.1309442e-05
6,291 Lightweight Inspection of Data Preprocessing in Native Machine Learning Pipelines 2021 CIDR 5.1269764e-05
6,359 Snapshot Semantics for Temporal Multiset Relations 2019 VLDB 5.0963959e-05
6,400 iOLAP: Managing Uncertainty for Efficient Incremental OLAP 2016 SIGMOD 5.0803518e-05
6,409 Fine-Grained Lineage for Safer Notebook Interactions 2021 VLDB 5.0756653e-05
6,415 Queries with Difference on Probabilistic Databases 2011 VLDB 5.0731258e-05
6,534 Automatic Rule Refinement for Information Extraction 2010 VLDB 5.0244622e-05
6,565 Toward Interpretable and Actionable Data Analysis with Explanations and Causality 2022 VLDB 5.0081626e-05
6,643 Query Refinement for Diversity Constraint Satisfaction 2024 VLDB 4.9786132e-05
6,662 Selective Provenance for Datalog Programs Using Top-K Queries 2015 VLDB 4.9704872e-05
6,696 Approximate Summaries for Why and Why-not Provenance 2020 VLDB 4.9581958e-05
6,943 TRAMP: Understanding the Behavior of Schema Mappings through Provenance 2010 VLDB 4.8916728e-05
6,997 Tractable Lineages on Treelike Instances: Limits and Extensions 2016 PODS 4.8676446e-05
7,065 Fast Matrix Multiplication for Query Processing 2024 PODS 4.8447515e-05
7,066 On Multiple Semantics for Declarative Database Repairs 2020 SIGMOD 4.8445108e-05
7,122 Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries 2020 PODS 4.8252188e-05
7,280 I4E: Interactive Investigation of Iterative Information Extraction 2010 SIGMOD 4.778826e-05
7,342 Optimizing Recursive Queries with Program Synthesis 2022 SIGMOD 4.7576316e-05
7,364 ExplainED: Explanations for EDA Notebooks 2020 VLDB 4.7519211e-05
7,482 Provenance-Enabled Explainable AI 2024 SIGMOD 4.7180617e-05
7,491 Saibot: A Differentially Private Data Search Platform 2023 VLDB 4.7180617e-05
7,556 Interactive Query Explanations Using Fine Grained Provenance 2022 SIGMOD 4.7117814e-05
7,720 Provenance: On and Behind the Screens 2016 SIGMOD 4.6684701e-05
7,864 Differentially Private Data Release over Multiple Tables 2023 PODS 4.6327272e-05
7,920 JoinBoost: Grow Trees Over Normalized Data Using Only SQL 2023 VLDB 4.6163888e-05
7,941 Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds 2021 SIGMOD 4.613363e-05
8,125 The Complexity of Why-Provenance for Datalog Queries 2024 PODS 4.5797807e-05
Previous Page 2 / 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