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
h630ecb11e65c90a3
Venue
VLDB
Year
2008
Pagerank
9.6438009e-05
Overall Rank
1,785 | 88.01%
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
190 Scorpion: Explaining Away Outliers in Aggregate Queries 2013 VLDB 0.0002582857
1,615 Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases 2011 SIGMOD 0.00010062545
2,719 Partial Results in Database Systems 2014 SIGMOD 8.0942034e-05
4,684 Provenance for Natural Language Queries 2017 VLDB 6.4692258e-05
5,342 Approximate Lifted Inference with Probabilistic Databases 2015 VLDB 6.171876e-05
5,533 Putting Things into Context: Rich Explanations for Query Answers using Join Graphs 2021 SIGMOD 6.0906707e-05
6,850 Capturing Data Uncertainty in High-Volume Stream Processing 2009 CIDR 5.6635511e-05
7,235 Hypothetical Reasoning via Provenance Abstraction 2019 SIGMOD 5.5765963e-05
7,370 I4E: Interactive Investigation of Iterative Information Extraction 2010 SIGMOD 5.5389537e-05
8,083 Provenance-Enabled Explainable AI 2024 SIGMOD 5.3917406e-05
8,198 Lineage Processing over Correlated Probabilistic Databases 2010 SIGMOD 5.3785339e-05
8,277 Distributed Time-aware Provenance 2013 VLDB 5.3618022e-05
8,650 Anytime Approximation in Probabilistic Databases via Scaled Dissociations 2019 SIGMOD 5.2929907e-05
8,755 Probabilistic Management of OCR Data using an RDBMS 2012 VLDB 5.2841044e-05
9,135 Database Optimization for the Cloud: Where Costs, Partial Results, and Consumer Choice Meet 2015 CIDR 5.2215089e-05
11,144 Unified Lineage System: Tracking Data Provenance at Scale 2025 SIGMOD 4.9769913e-05
11,706 Probabilistic Reasoning at Scale: Trigger Graphs to the Rescue 2023 SIGMOD 4.9769913e-05
11,944 Model Counting meets F0 Estimation 2021 PODS 4.9769913e-05
12,663 Schema-As-You-Go: On Probabilistic Tagging and Querying of Wide Tables 2011 SIGMOD 4.9769913e-05
12,705 Transducing Markov Sequences 2010 PODS 4.9769913e-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.0006897844
17 Provenance Semirings 2007 PODS 0.00059813669
51 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB 0.00042926566
60 The Merge/Purge Problem for Large Databases 1995 SIGMOD 0.00039440583
126 Trio: A System for Integrated Management of Data, Accuracy, and Lineage 2005 CIDR 0.00030430114
222 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00024210103
286 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.00022112534
307 Eliminating Fuzzy Duplicates in Data Warehouses 2002 VLDB 0.00021489374
660 The Complexity of Query Reliability 1998 PODS 0.00015045167
696 MYSTIQ: A system for finding more answers by using probabilities 2005 SIGMOD 0.00014691377
2,006 Orchestra: Facilitating Collaborative Data Sharing 2007 SIGMOD 9.2046844e-05
2,172 Provenance Management in Curated Databases 2006 SIGMOD 8.9202679e-05
2,657 SPARTAN: A Model-Based Semantic Compression System for Massive Data Tables 2001 SIGMOD 8.162525e-05
2,985 Materialized Views in Probabilistic Databases: For Information Exchange and Query Optimization 2007 VLDB 7.7794901e-05
6,690 bdbms – A Database Management System for Biological Data 2007 CIDR 5.7058148e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,827 Querying Data Provenance 2010 SIGMOD
2 6,459 On Provenance Minimization 2011 PODS
3 84 ULDBs: Databases with Uncertainty and Lineage 2006 VLDB
4 51 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB
5 7,575 Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases 2020 PODS
6 9,177 Efficient Approximations of Conjunctive Queries 2012 PODS
7 7,470 Probabilistic Query Evaluation: The Combined FPRAS Landscape 2023 PODS
8 7,801 Tractable Lineages on Treelike Instances: Limits and Extensions 2016 PODS
9 4,215 Approximating Predicates and Expressive Queries on Probabilistic Databases 2008 PODS
10 8,198 Lineage Processing over Correlated Probabilistic Databases 2010 SIGMOD