DBScholar

Back to papers

ULDBs: Databases with Uncertainty and Lineage

Summary: Introduces ULDBs, a relational representation unifying uncertain data with lineage, enabling correlated uncertainty propagation and efficient query processing. Establishes completeness, minimization notions, subset extraction under interconnected uncertainty, and probabilistic-database execution. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h24ebe19d37d2c122
Venue
VLDB
Year
2006
Pagerank
0.00035963861
Overall Rank
84 | 99.44%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{benjelloun_vldb06,
        title = {{ULDBs: Databases with Uncertainty and Lineage}},
        author = {Benjelloun, Omar and Sarma, Anish Das and Halevy, Alon and Widom, Jennifer},
        journal = {PVLDB},
        series = {{VLDB} '06},
        pages = {953},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 28 of 78 citing papers.

Rank Citing Paper Year Venue Pagerank
7,545 Supporting OLAP Operations over Imperfectly Integrated Taxonomies 2008 SIGMOD 5.4983387e-05
7,702 UPI: A Primary Index for Uncertain Databases 2010 VLDB 5.4748399e-05
7,819 You Say ‘What’, I Hear ‘Where’ and ‘Why’ — (Mis-)Interpreting SQL to Derive Fine-Grained Provenance 2018 VLDB 5.4466474e-05
7,863 Optimizing Probabilistic Query Processing on Continuous Uncertain Data 2011 VLDB 5.4367962e-05
7,998 Set Similarity Join on Probabilistic Data 2010 VLDB 5.4104124e-05
8,425 Tuple-Independent Representations of Infinite Probabilistic Databases 2021 PODS 5.3350162e-05
8,514 URank: Formulation and Efficient Evaluation of Top-k Queries in Uncertain Databases 2007 SIGMOD 5.3252399e-05
8,760 Beta Probabilistic Databases: A Scalable Approach to Belief Updating and Parameter Learning 2017 SIGMOD 5.283642e-05
8,862 Counting Problems over Incomplete Databases 2020 PODS 5.2627214e-05
8,892 FaDE: More Than a Million What-ifs Per Second 2025 VLDB 5.2559789e-05
9,097 Efficient Query Answering in Probabilistic RDF Graphs 2011 SIGMOD 5.2283159e-05
9,214 Threshold Query Optimization for Uncertain Data 2010 SIGMOD 5.2058816e-05
9,264 Zoom*UserViews: Querying Relevant Provenance in Workflow Systems 2007 VLDB 5.2056825e-05
9,502 Computing All Skyline Probabilities for Uncertain Data 2009 PODS 5.1708619e-05
10,117 A*-tree: A Structure for Storage and Modeling of Uncertain Multidimensional Arrays 2010 VLDB 5.0789354e-05
10,803 Efficient Query Repair for Aggregate Constraints 2026 VLDB 4.9793485e-05
11,100 A Rank-Based Approach to Recommender System’s Top-K Queries with Uncertain Scores 2025 SIGMOD 4.9793485e-05
12,108 CONCIERGE: Improving Constrained Search Results by Data Melioration 2020 VLDB 4.9793485e-05
12,397 Supporting Data Uncertainty in Array Databases 2015 SIGMOD 4.9793485e-05
12,442 Beyond Itemsets: Mining Frequent Featuresets over Structured Items 2015 VLDB 4.9793485e-05
12,758 Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations 2010 VLDB 4.9793485e-05
12,839 Query Evaluation with Soft-Key Constraints 2008 PODS 4.9793485e-05
12,858 UQBE: Uncertain Query By Example for Web Service Mashup 2008 SIGMOD 4.9793485e-05
12,861 Query Answering Techniques on Uncertain and Probabilistic Data 2008 SIGMOD 4.9793485e-05
12,910 QUIC: Handling Query Imprecision & Data Incompleteness in Autonomous Databases 2007 CIDR 4.9793485e-05
12,920 K-Relevance: A Spectrum of Relevance for Data Sources Impacting a Query 2007 SIGMOD 4.9793485e-05
12,940 Integrating and Querying Taxonomies with QUEST in the Presence of Conflicts 2007 SIGMOD 4.9793485e-05
12,941 Provenance in Databases (Tutorial Outline) 2007 SIGMOD 4.9793485e-05
Previous Page 2 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 cited papers.

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

Rank Cited Paper Year Venue Pagerank
51 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB 0.00042936299
126 Trio: A System for Integrated Management of Data, Accuracy, and Lineage 2005 CIDR 0.00030439683
337 Trio: A System for Data, Uncertainty, and Lineage 2006 VLDB 0.00020621631
474 Automated Ranking of Database Query Results 2003 CIDR 0.00017672562
525 An Annotation Management System for Relational Databases 2004 VLDB 0.00016890994
571 The Theory of Probabilistic Databases 1987 VLDB 0.00016210743
590 On Propagation of Deletions and Annotations Through Views 2002 PODS 0.00015890019
591 Lineage Tracing for General Data Warehouse Transformations 2001 VLDB 0.00015888097
696 MYSTIQ: A system for finding more answers by using probabilities 2005 SIGMOD 0.00014697176
875 Queries Independent of Updates 1993 VLDB 0.00013316445
1,518 Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions 2005 VLDB 0.00010396565
1,543 The XXL Search Engine: Ranked Retrieval of XML Data using Indexes and Ontologies 2002 SIGMOD 0.00010306756
1,588 DBNotes: A Post-It System for Relational Databases based on Provenance 2005 SIGMOD 0.00010140362
1,657 U-DBMS: A Database System for Managing Constantly-Evolving Data 2005 VLDB 9.967084e-05
1,761 Reconciling while Tolerating Disagreement in Collaborative Data Sharing 2006 SIGMOD 9.7093946e-05
1,809 ORCHESTRA: Rapid, Collaborative Sharing of Dynamic Data 2005 CIDR 9.5935116e-05
1,865 A Probabilistic Framework for Vague Queries and Imprecise Information in Databases 1990 VLDB 9.4818521e-05
2,718 Answering Queries from Statistics and Probabilistic Views 2005 VLDB 8.0978764e-05
2,965 Horn Tables - An Efficient Tool For Handling Incomplete Information In Databases 1989 PODS 7.8051404e-05
3,807 Dependency Satisfaction in Databases with Incomplete Information 1984 VLDB 7.0097907e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 8,190 Lineage Processing over Correlated Probabilistic Databases 2010 SIGMOD
2 715 Data Integration with Uncertainty 2007 VLDB
3 126 Trio: A System for Integrated Management of Data, Accuracy, and Lineage 2005 CIDR
4 1,785 Approximate Lineage for Probabilistic Databases 2008 VLDB
5 4,216 Trio-One: Layering Uncertainty and Lineage on a Conventional DBMS 2007 CIDR
6 1,615 Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases 2011 SIGMOD
7 9,105 New Directions For Uncertainty Reasoning In Deductive Databases 1991 SIGMOD
8 4,868 Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers 2019 SIGMOD
9 8,426 Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds 2021 SIGMOD
10 337 Trio: A System for Data, Uncertainty, and Lineage 2006 VLDB