Database Paper Browser

Back to papers

Approximate Lineage for Probabilistic Databases

Summary: Approximate lineage for probabilistic databases replaces full Boolean lineage with compact, query-guided derivations. Two variants: sufficient lineage (conservative) and polynomial lineage (Fourier-based) with definitions, algorithms, and validation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
9715
Venue
VLDB
Year
2008
Pagerank
9.896375e-05
Overall Rank
1,970 | 86.30%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank Citing Paper Year Venue Pagerank
214 Scorpion: Explaining Away Outliers in Aggregate Queries 2013 VLDB 0.0003363692
1,699 Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases 2011 SIGMOD 0.00010858983
3,051 Partial Results in Database Systems 2014 SIGMOD 7.6512591e-05
4,851 Provenance for Natural Language Queries 2017 VLDB 5.8768322e-05
5,691 Putting Things into Context: Rich Explanations for Query Answers using Join Graphs 2021 SIGMOD 5.3684557e-05
6,169 Approximate Lifted Inference with Probabilistic Databases 2015 VLDB 5.1716068e-05
6,838 Capturing Data Uncertainty in High-Volume Stream Processing 2009 CIDR 4.9109732e-05
7,280 I4E: Interactive Investigation of Iterative Information Extraction 2010 SIGMOD 4.778826e-05
7,482 Provenance-Enabled Explainable AI 2024 SIGMOD 4.7180617e-05
7,754 Lineage Processing over Correlated Probabilistic Databases 2010 SIGMOD 4.6600967e-05
8,378 Probabilistic Management of OCR Data using an RDBMS 2012 VLDB 4.5320288e-05
8,394 Hypothetical Reasoning via Provenance Abstraction 2019 SIGMOD 4.527807e-05
8,504 Distributed Time-aware Provenance 2013 VLDB 4.496125e-05
8,581 Anytime Approximation in Probabilistic Databases via Scaled Dissociations 2019 SIGMOD 4.492241e-05
8,792 Database Optimization for the Cloud: Where Costs, Partial Results, and Consumer Choice Meet 2015 CIDR 4.4506724e-05
10,419 Unified Lineage System: Tracking Data Provenance at Scale 2025 SIGMOD 4.1945683e-05
11,179 Probabilistic Reasoning at Scale: Trigger Graphs to the Rescue 2023 SIGMOD 4.1945683e-05
11,433 Model Counting meets F0 Estimation 2021 PODS 4.1945683e-05
12,170 Schema-As-You-Go: On Probabilistic Tagging and Querying of Wide Tables 2011 SIGMOD 4.1945683e-05
12,213 Transducing Markov Sequences 2010 PODS 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank Cited Paper Year Venue Pagerank
21 C-Store: A Column-oriented DBMS 2005 VLDB 0.00086087497
31 Provenance Semirings 2007 PODS 0.0007857786
67 The Merge/Purge Problem for Large Databases 1995 SIGMOD 0.00061348205
74 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB 0.00057857292
149 Trio: A System for Integrated Management of Data, Accuracy, and Lineage 2005 CIDR 0.00041101118
273 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00029390945
280 Eliminating Fuzzy Duplicates in Data Warehouses 2002 VLDB 0.00029113044
372 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.00025354779
571 The Complexity of Query Reliability 1998 PODS 0.00019910719
706 MYSTIQ: A system for finding more answers by using probabilities 2005 SIGMOD 0.00017845469
2,068 Orchestra: Facilitating Collaborative Data Sharing 2007 SIGMOD 9.6377415e-05
2,524 Provenance Management in Curated Databases 2006 SIGMOD 8.6017899e-05
2,908 SPARTAN: A Model-Based Semantic Compression System for Massive Data Tables 2001 SIGMOD 7.9306333e-05
6,610 bdbms – A Database Management System for Biological Data 2007 CIDR 4.995269e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,173 Querying Data Provenance 2010 SIGMOD 9.3676609e-05
6,186 On Provenance Minimization 2011 PODS 5.166082e-05
101 ULDBs: Databases with Uncertainty and Lineage 2006 VLDB 0.0004955674
74 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB 0.00057857292
7,149 Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases 2020 PODS 4.8173876e-05
8,851 Efficient Approximations of Conjunctive Queries 2012 PODS 4.4363908e-05
7,163 Probabilistic Query Evaluation: The Combined FPRAS Landscape 2023 PODS 4.8132033e-05
6,997 Tractable Lineages on Treelike Instances: Limits and Extensions 2016 PODS 4.8676446e-05
4,442 Approximating Predicates and Expressive Queries on Probabilistic Databases 2008 PODS 6.186154e-05
7,754 Lineage Processing over Correlated Probabilistic Databases 2010 SIGMOD 4.6600967e-05