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
342 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00026795977
652 On the Provenance of Non-Answers to Queries over Extracted Data 2008 VLDB 0.00018634477
809 Curated Databases 2008 PODS 0.00016430384
1,057 Cosette: An Automated Prover for SQL 2017 CIDR 0.0001439886
1,106 Provenance for Aggregate Queries 2011 PODS 0.0001398766
1,119 The Complexity of Causality and Responsibility for Query Answers and non-Answers 2011 VLDB 0.0001386199
1,177 Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins 2013 SIGMOD 0.00013470212
1,238 Incremental Query Evaluation in a Ring of Databases 2010 PODS 0.00013114581
1,371 Tiresias: The Database Oracle for How-To Queries 2012 SIGMOD 0.00012323502
1,609 A Unified Approach to Ranking in Probabilistic Databases 2009 VLDB 0.00011150935
1,646 Caravan: Provisioning for What-If Analysis 2013 CIDR 0.00011036992
1,660 Data Markets in the Cloud: An Opportunity for the Database Community 2011 VLDB 0.00010979534
1,699 Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases 2011 SIGMOD 0.00010858983
1,866 Update Exchange with Mappings and Provenance 2007 VLDB 0.00010272139
1,970 Approximate Lineage for Probabilistic Databases 2008 VLDB 9.896375e-05
2,028 Putting Lipstick on Pig: Enabling Database-style Workflow Provenance 2012 VLDB 9.7433981e-05
2,068 Orchestra: Facilitating Collaborative Data Sharing 2007 SIGMOD 9.6377415e-05
2,099 Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries 2018 VLDB 9.5479391e-05
2,169 AJAR: Aggregations and Joins over Annotated Relations 2016 PODS 9.3845975e-05
2,173 Querying Data Provenance 2010 SIGMOD 9.3676609e-05
2,256 ProvSQL: Provenance and Probability Management in PostgreSQL 2018 VLDB 9.1879032e-05
2,359 Data Market Platforms: Trading Data Assets to Solve Data Problems 2020 VLDB 8.9607667e-05
2,596 WeTune: Automatic Discovery and Verification of Query Rewrite Rules 2022 SIGMOD 8.4729982e-05
2,602 Tracing Data Errors with View-Conditioned Causality 2011 SIGMOD 8.4667197e-05
2,753 Complaint-driven Training Data Debugging for Query 2.0 2020 SIGMOD 8.1724339e-05
2,764 The Semiring Framework for Database Provenance 2017 PODS 8.1574444e-05
2,797 Query-Oriented Data Cleaning with Oracles 2015 SIGMOD 8.1108589e-05
2,868 Computing the Shapley Value of Facts in Query Answering 2022 SIGMOD 7.9816425e-05
2,907 Convergence of Datalog over (Pre-) Semirings 2022 PODS 7.933806e-05
3,015 Chorus: Foundation Models for Unified Data Discovery and Exploration 2024 VLDB 7.7092391e-05
3,082 FDB: A Query Engine for Factorised Relational Databases 2012 VLDB 7.6014248e-05
3,105 Data X-Ray: A Diagnostic Tool for Data Errors 2015 SIGMOD 7.5568954e-05
3,110 Learning to Create Data-Integrating Queries 2008 VLDB 7.5475982e-05
3,218 Reverse Data Management 2011 VLDB 7.3592173e-05
3,432 Demonstration of the Cosette Automated SQL Prover 2017 SIGMOD 7.1008151e-05
3,505 Consensus Answers for Queries over Probabilistic Databases 2009 PODS 7.0337815e-05
3,509 Complete Yet Practical Search for Minimal Query Reformulations Under Constraints 2014 SIGMOD 7.0263584e-05
3,584 Efficient Querying and Maintenance of Network Provenance at Internet-Scale 2010 SIGMOD 6.9460423e-05
3,995 How Large Language Models Will Disrupt Data Management 2023 VLDB 6.5513237e-05
4,197 Incremental View Maintenance with Triple Lock Factorization Benefits 2018 SIGMOD 6.367895e-05
4,361 The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries 2016 VLDB 6.2559141e-05
4,424 PrIU: A Provenance-Based Approach for Incrementally Updating Regression Models 2020 SIGMOD 6.198474e-05
4,591 From Shapley Value to Model Counting and Back 2024 PODS 6.0619399e-05
4,664 Efficient Answering of Historical What-if Queries 2022 SIGMOD 6.0127053e-05
4,706 Aggregation in Probabilistic Databases via Knowledge Compilation 2012 VLDB 5.9820914e-05
4,708 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 5.980172e-05
4,774 LIMA: Fine-grained Lineage Tracing and Reuse in Machine Learning Systems 2021 SIGMOD 5.9316087e-05
4,806 Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers 2019 SIGMOD 5.9092698e-05
4,851 Provenance for Natural Language Queries 2017 VLDB 5.8768322e-05
4,937 New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins 2020 PODS 5.8187108e-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.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