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.00078516827
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
341 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00026850764
653 On the Provenance of Non-Answers to Queries over Extracted Data 2008 VLDB 0.00018616975
807 Curated Databases 2008 PODS 0.00016415752
1,056 Cosette: An Automated Prover for SQL 2017 CIDR 0.00014391317
1,106 Provenance for Aggregate Queries 2011 PODS 0.00013976386
1,119 The Complexity of Causality and Responsibility for Query Answers and non-Answers 2011 VLDB 0.00013851012
1,177 Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins 2013 SIGMOD 0.00013465351
1,231 Incremental Query Evaluation in a Ring of Databases 2010 PODS 0.00013141213
1,376 Tiresias: The Database Oracle for How-To Queries 2012 SIGMOD 0.00012315734
1,612 A Unified Approach to Ranking in Probabilistic Databases 2009 VLDB 0.00011142757
1,646 Caravan: Provisioning for What-If Analysis 2013 CIDR 0.00011026644
1,660 Data Markets in the Cloud: An Opportunity for the Database Community 2011 VLDB 0.00010968969
1,698 Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases 2011 SIGMOD 0.00010857033
1,868 Update Exchange with Mappings and Provenance 2007 VLDB 0.0001026365
1,972 Approximate Lineage for Probabilistic Databases 2008 VLDB 9.8937766e-05
2,031 Putting Lipstick on Pig: Enabling Database-style Workflow Provenance 2012 VLDB 9.7341007e-05
2,073 Orchestra: Facilitating Collaborative Data Sharing 2007 SIGMOD 9.6287026e-05
2,097 Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries 2018 VLDB 9.5439744e-05
2,173 AJAR: Aggregations and Joins over Annotated Relations 2016 PODS 9.3767985e-05
2,182 Querying Data Provenance 2010 SIGMOD 9.3596252e-05
2,259 ProvSQL: Provenance and Probability Management in PostgreSQL 2018 VLDB 9.1790333e-05
2,366 Data Market Platforms: Trading Data Assets to Solve Data Problems 2020 VLDB 8.9521259e-05
2,595 WeTune: Automatic Discovery and Verification of Query Rewrite Rules 2022 SIGMOD 8.4725961e-05
2,600 Tracing Data Errors with View-Conditioned Causality 2011 SIGMOD 8.4652308e-05
2,759 Complaint-driven Training Data Debugging for Query 2.0 2020 SIGMOD 8.1646193e-05
2,770 The Semiring Framework for Database Provenance 2017 PODS 8.1495762e-05
2,805 Query-Oriented Data Cleaning with Oracles 2015 SIGMOD 8.103731e-05
2,876 Computing the Shapley Value of Facts in Query Answering 2022 SIGMOD 7.9739469e-05
2,912 Convergence of Datalog over (Pre-) Semirings 2022 PODS 7.9261665e-05
3,003 Chorus: Foundation Models for Unified Data Discovery and Exploration 2024 VLDB 7.7358219e-05
3,088 FDB: A Query Engine for Factorised Relational Databases 2012 VLDB 7.5940302e-05
3,107 Data X-Ray: A Diagnostic Tool for Data Errors 2015 SIGMOD 7.5549177e-05
3,116 Learning to Create Data-Integrating Queries 2008 VLDB 7.5404022e-05
3,224 Reverse Data Management 2011 VLDB 7.3523336e-05
3,430 Demonstration of the Cosette Automated SQL Prover 2017 SIGMOD 7.0985442e-05
3,509 Consensus Answers for Queries over Probabilistic Databases 2009 PODS 7.0283775e-05
3,514 Complete Yet Practical Search for Minimal Query Reformulations Under Constraints 2014 SIGMOD 7.0192177e-05
3,587 Efficient Querying and Maintenance of Network Provenance at Internet-Scale 2010 SIGMOD 6.9394966e-05
3,982 How Large Language Models Will Disrupt Data Management 2023 VLDB 6.5595332e-05
4,200 Incremental View Maintenance with Triple Lock Factorization Benefits 2018 SIGMOD 6.3618329e-05
4,358 The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries 2016 VLDB 6.2499e-05
4,423 PrIU: A Provenance-Based Approach for Incrementally Updating Regression Models 2020 SIGMOD 6.1925724e-05
4,591 From Shapley Value to Model Counting and Back 2024 PODS 6.056109e-05
4,661 Efficient Answering of Historical What-if Queries 2022 SIGMOD 6.0069281e-05
4,708 Aggregation in Probabilistic Databases via Knowledge Compilation 2012 VLDB 5.9763416e-05
4,709 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 5.9744219e-05
4,779 LIMA: Fine-grained Lineage Tracing and Reuse in Machine Learning Systems 2021 SIGMOD 5.9259373e-05
4,809 Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers 2019 SIGMOD 5.9035874e-05
4,853 Provenance for Natural Language Queries 2017 VLDB 5.8711821e-05
4,940 New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins 2020 PODS 5.8131196e-05
Previous Page 1 / 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.00057797415
103 ULDBs: Databases with Uncertainty and Lineage 2006 VLDB 0.00049520051
401 Conjunctive-Query Containment and Constraint Satisfaction 1998 PODS 0.00024281448
448 The Magic of Duplicates and Aggregates 1990 VLDB 0.00022922417
688 Debugging Schema Mappings with Routes 2006 VLDB 0.00018095639
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,097 Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries 2018 VLDB 9.5439744e-05
6,272 Classification of Annotation Semirings over Query Containment 2012 PODS 5.1271971e-05
8,965 Computing How-Provenance for SPARQL Queries via Query Rewriting 2021 VLDB 4.4163852e-05
10,909 Tight Bounds of Circuits for Sum-Product Queries 2024 PODS 4.1905499e-05
2,770 The Semiring Framework for Database Provenance 2017 PODS 8.1495762e-05
5,275 Annotated XML: Queries and Provenance 2008 PODS 5.5908918e-05
6,187 On Provenance Minimization 2011 PODS 5.1611195e-05
9,183 Equivalence-Invariant Algebraic Provenance for Hyperplane Update Queries 2020 SIGMOD 4.3778211e-05
2,182 Querying Data Provenance 2010 SIGMOD 9.3596252e-05
1,106 Provenance for Aggregate Queries 2011 PODS 0.00013976386