DBScholar

Back to papers

Approximate Lineage for Probabilistic Databases

Summary: Introduces approximate lineage for probabilistic databases, retaining only important tuple derivations to avoid massive Boolean provenance formulas. Develops conservative sufficient lineage and Fourier-based polynomial lineage, with computation algorithms, formal error bounds, and empirical validation. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
9906
Venue
VLDB
Year
2008
Pagerank
9.8358116e-05
Overall Rank
1,752 | 87.99%
DOI
10.14778/1453856.1453946

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{re_vldb08,
        title = {{Approximate Lineage for Probabilistic Databases}},
        author = {Ré, Christopher and Suciu, Dan},
        journal = {PVLDB},
        series = {{VLDB} '08},
        volume = {1},
        number = {1},
        pages = {797--808},
        doi = {10.14778/1453856.1453946},
        url = {https://doi.org/10.14778/1453856.1453946},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank Citing Paper Year Venue Pagerank
191 Scorpion: Explaining Away Outliers in Aggregate Queries 2013 VLDB 0.00026096009
1,594 Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases 2011 SIGMOD 0.00010252583
2,663 Partial Results in Database Systems 2014 SIGMOD 8.2818137e-05
4,602 Provenance for Natural Language Queries 2017 VLDB 6.6107638e-05
5,225 Approximate Lifted Inference with Probabilistic Databases 2015 VLDB 6.310093e-05
5,396 Putting Things into Context: Rich Explanations for Query Answers using Join Graphs 2021 SIGMOD 6.2329373e-05
6,712 Capturing Data Uncertainty in High-Volume Stream Processing 2009 CIDR 5.7962014e-05
7,239 I4E: Interactive Investigation of Iterative Information Extraction 2010 SIGMOD 5.6645117e-05
7,907 Provenance-Enabled Explainable AI 2024 SIGMOD 5.5181056e-05
8,032 Lineage Processing over Correlated Probabilistic Databases 2010 SIGMOD 5.5041098e-05
8,476 Anytime Approximation in Probabilistic Databases via Scaled Dissociations 2019 SIGMOD 5.4170414e-05
8,509 Hypothetical Reasoning via Provenance Abstraction 2019 SIGMOD 5.4120069e-05
8,585 Probabilistic Management of OCR Data using an RDBMS 2012 VLDB 5.4075213e-05
8,610 Distributed Time-aware Provenance 2013 VLDB 5.4022415e-05
8,961 Database Optimization for the Cloud: Where Costs, Partial Results, and Consumer Choice Meet 2015 CIDR 5.3438458e-05
10,701 Unified Lineage System: Tracking Data Provenance at Scale 2025 SIGMOD 5.093636e-05
11,385 Probabilistic Reasoning at Scale: Trigger Graphs to the Rescue 2023 SIGMOD 5.093636e-05
11,631 Model Counting meets F0 Estimation 2021 PODS 5.093636e-05
12,366 Schema-As-You-Go: On Probabilistic Tagging and Querying of Wide Tables 2011 SIGMOD 5.093636e-05
12,408 Transducing Markov Sequences 2010 PODS 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
12 C-Store: A Column-oriented DBMS 2005 VLDB 0.00069513174
17 Provenance Semirings 2007 PODS 0.00059843817
50 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB 0.00043596705
58 The Merge/Purge Problem for Large Databases 1995 SIGMOD 0.00040116748
125 Trio: A System for Integrated Management of Data, Accuracy, and Lineage 2005 CIDR 0.00030932014
213 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00024723025
280 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.00022454217
306 Eliminating Fuzzy Duplicates in Data Warehouses 2002 VLDB 0.00021839661
644 The Complexity of Query Reliability 1998 PODS 0.00015367965
683 MYSTIQ: A system for finding more answers by using probabilities 2005 SIGMOD 0.00015005338
2,026 Orchestra: Facilitating Collaborative Data Sharing 2007 SIGMOD 9.287998e-05
2,134 Provenance Management in Curated Databases 2006 SIGMOD 9.1154913e-05
2,611 SPARTAN: A Model-Based Semantic Compression System for Massive Data Tables 2001 SIGMOD 8.34729e-05
2,936 Materialized Views in Probabilistic Databases: For Information Exchange and Query Optimization 2007 VLDB 7.9437689e-05
6,564 bdbms – A Database Management System for Biological Data 2007 CIDR 5.8383221e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,912 Querying Data Provenance 2010 SIGMOD
2 6,358 On Provenance Minimization 2011 PODS
3 78 ULDBs: Databases with Uncertainty and Lineage 2006 VLDB
4 50 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB
5 7,430 Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases 2020 PODS
6 9,009 Efficient Approximations of Conjunctive Queries 2012 PODS
7 7,317 Probabilistic Query Evaluation: The Combined FPRAS Landscape 2023 PODS
8 7,640 Tractable Lineages on Treelike Instances: Limits and Extensions 2016 PODS
9 4,136 Approximating Predicates and Expressive Queries on Probabilistic Databases 2008 PODS
10 8,032 Lineage Processing over Correlated Probabilistic Databases 2010 SIGMOD