ULDBs: Databases with Uncertainty and Lineage

Summary: ULDBs extend relational databases with constructs for representing and manipulating uncertainty and lineage. They enable joint processing where lineage ties to input uncertainty, and define data- and lineage-minimality with subset-extraction algorithms for interconnected uncertainty—foundational for Trio. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9508
Venue: VLDB
Year: 2006
Pagerank: 0.00037068234
Overall Rank: 78 | 99.46%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 78 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
17	Provenance Semirings	2007	PODS	0.00059742957
306	Making Database Systems Usable	2007	SIGMOD	0.00021823454
316	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00021468682
381	Why Not?	2009	SIGMOD	0.0001962695
557	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00016599507
632	On the Provenance of Non-Answers to Queries over Extracted Data	2008	VLDB	0.00015670341
684	Data Integration with Uncertainty	2007	VLDB	0.00015113784
802	BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models	2008	VLDB	0.0001396623
897	Data Integration: The Teenage Years	2006	VLDB	0.00013392568
1,148	Principles of Dataspace Systems	2006	PODS	0.00012051136
1,313	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB	0.00011294367
1,340	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00011196212
1,482	Conditioning Probabilistic Databases	2008	VLDB	0.00010696881
1,570	Update Exchange with Mappings and Provenance	2007	VLDB	0.00010390225
1,591	Efficient Provenance Storage	2008	SIGMOD	0.00010347331
1,649	MISTIQUE: A System to Store and Query Model Intermediates for Model Diagnosis	2018	SIGMOD	0.00010189983
1,708	Structured Querying of Web Text: A Technical Challenge	2007	CIDR	0.00010041923
1,843	A Web of Concepts	2009	PODS	9.7180374e-05
1,862	Querying Data Provenance	2010	SIGMOD	9.684721e-05
2,061	ProvSQL: Provenance and Probability Management in PostgreSQL	2018	VLDB	9.3066629e-05
2,410	The Semiring Framework for Database Provenance	2017	PODS	8.6978651e-05
2,441	Exploiting Shared Correlations in Probabilistic Databases	2008	VLDB	8.6376718e-05
2,456	From Complete to Incomplete Information and Back	2007	SIGMOD	8.6275489e-05
2,758	Approximation Algorithms for Clustering Uncertain Data	2008	PODS	8.2228285e-05
2,839	Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities	2009	SIGMOD	8.1117137e-05
2,963	Sketching Probabilistic Data Streams	2007	SIGMOD	7.9682307e-05
2,986	Event Queries on Correlated Probabilistic Streams	2008	SIGMOD	7.9400023e-05
3,219	Toward Best-Effort Information Extraction	2008	SIGMOD	7.6992459e-05
4,049	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	7.00091e-05
4,072	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.9861328e-05
4,090	Trio-One: Layering Uncertainty and Lineage on a Conventional DBMS	2007	CIDR	6.97209e-05
4,118	Hybrid In-Database Inference for Declarative Information Extraction	2011	SIGMOD	6.9535811e-05
4,273	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	6.8587835e-05
4,670	Rethinking Data Management for Storage-centric Sensor Networks	2007	CIDR	6.6354395e-05
4,938	iTrails: Pay-as-you-go Information Integration in Dataspaces	2007	VLDB	6.5011792e-05
4,955	Querying Probabilistic Information Extraction	2010	VLDB	6.4953597e-05
5,252	Cleaning Uncertain Data with Quality Guarantees	2008	VLDB	6.3675581e-05
5,303	Foundations of Uncertain-Data Integration	2010	VLDB	6.3437328e-05
5,515	Believe It or Not: Adding Belief Annotations to Databases	2009	VLDB	6.2552512e-05
5,577	Sampling Cube: A Framework for Statistical OLAP Over Sampling Data	2008	SIGMOD	6.2286797e-05
5,755	A Framework for Clustering Uncertain Data	2015	VLDB	6.1624394e-05
5,968	PODS: A New Model and Processing Algorithms for Uncertain Data Streams	2010	SIGMOD	6.0868533e-05
6,030	Finding Frequent Items in Probabilistic Data	2008	SIGMOD	6.0614112e-05
6,266	Clustering Uncertain Graphs	2018	VLDB	5.9974199e-05
6,436	Queries with Difference on Probabilistic Databases	2011	VLDB	5.9412426e-05
6,601	Capturing Data Uncertainty in High-Volume Stream Processing	2009	CIDR	5.8860028e-05
6,606	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD	5.8853432e-05
6,749	Explore or Exploit? Effective Strategies for Disambiguating Large Databases	2010	VLDB	5.8429601e-05
6,752	FICSR: Feedback-based InConSistency Resolution and Query Processing on Misaligned Data Sources	2007	SIGMOD	5.8414303e-05
7,273	I4E: Interactive Investigation of Iterative Information Extraction	2010	SIGMOD	5.7119592e-05

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
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043653232
125	Trio: A System for Integrated Management of Data, Accuracy, and Lineage	2005	CIDR	0.0003120745
316	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00021468682
455	Automated Ranking of Database Query Results	2003	CIDR	0.00018236909
512	An Annotation Management System for Relational Databases	2004	VLDB	0.00017315632
547	The Theory Of Probabilistic Databases	1987	VLDB	0.00016787108
580	Lineage Tracing for General Data Warehouse Transformations	2001	VLDB	0.00016231832
591	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00016070218
669	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00015281707
827	Queries Independent of Updates	1993	VLDB	0.00013831135
1,458	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00010797276
1,501	The XXL Search Engine: Ranked Retrieval of XML Data using Indexes and Ontologies	2002	SIGMOD	0.00010651442
1,543	DBNotes: A Post-It System for Relational Databases based on Provenance	2005	SIGMOD	0.00010479282
1,565	U-DBMS: A Database System for Managing Constantly-Evolving Data	2005	VLDB	0.00010398531
1,707	Reconciling while Tolerating Disagreement in Collaborative Data Sharing	2006	SIGMOD	0.0001004571
1,748	ORCHESTRA: Rapid, Collaborative Sharing of Dynamic Data	2005	CIDR	9.9260926e-05
1,793	A Probabilistic Framework for Vague Queries and Imprecise Information in Databases	1990	VLDB	9.8280602e-05
2,624	Answering Queries from Statistics and Probabilistic Views	2005	VLDB	8.3970315e-05
2,838	Horn Tables - An Efficient Tool For Handling Incomplete Information In Databases	1989	PODS	8.1129346e-05
3,687	Dependency Satisfaction in Databases with Incomplete Information	1984	VLDB	7.262891e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,057	Query-Guided Resolution in Uncertain Databases	2023	SIGMOD	5.3880466e-05
684	Data Integration with Uncertainty	2007	VLDB	0.00015113784
125	Trio: A System for Integrated Management of Data, Accuracy, and Lineage	2005	CIDR	0.0003120745
1,728	Approximate Lineage for Probabilistic Databases	2008	VLDB	9.9864985e-05
4,090	Trio-One: Layering Uncertainty and Lineage on a Conventional DBMS	2007	CIDR	6.97209e-05
1,563	Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases	2011	SIGMOD	0.00010402446
8,812	New Directions For Uncertainty Reasoning In Deductive Databases	1991	SIGMOD	5.4311509e-05
4,748	Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers	2019	SIGMOD	6.5987185e-05
8,125	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD	5.5419908e-05
316	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00021468682