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.00049520051
Overall Rank: 103 | 99.29%
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
31	Provenance Semirings	2007	PODS	0.00078516827
257	Making Database Systems Usable	2007	SIGMOD	0.00030237174
300	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00028503742
487	Why Not?	2009	SIGMOD	0.00022030123
630	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00018942778
653	On the Provenance of Non-Answers to Queries over Extracted Data	2008	VLDB	0.00018616975
718	Data Integration with Uncertainty	2007	VLDB	0.00017558942
889	Data Integration: The Teenage Years	2006	VLDB	0.00015548507
974	BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models	2008	VLDB	0.00014882804
1,221	A Web of Concepts	2009	PODS	0.00013213428
1,251	Principles of Dataspace Systems	2006	PODS	0.0001302453
1,398	Structured Querying of Web Text: A Technical Challenge	2007	CIDR	0.00012201166
1,625	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB	0.0001109361
1,703	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010820803
1,730	Conditioning Probabilistic Databases	2008	VLDB	0.00010726683
1,863	Approximation Algorithms for Clustering Uncertain Data	2008	PODS	0.00010287379
1,864	Efficient Provenance Storage	2008	SIGMOD	0.00010277171
1,868	Update Exchange with Mappings and Provenance	2007	VLDB	0.0001026365
2,157	MISTIQUE: A System to Store and Query Model Intermediates for Model Diagnosis	2018	SIGMOD	9.4153917e-05
2,182	Querying Data Provenance	2010	SIGMOD	9.3596252e-05
2,259	ProvSQL: Provenance and Probability Management in PostgreSQL	2018	VLDB	9.1790333e-05
2,493	From Complete to Incomplete Information and Back	2007	SIGMOD	8.6470623e-05
2,649	Exploiting Shared Correlations in Probabilistic Databases	2008	VLDB	8.3728762e-05
2,733	Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities	2009	SIGMOD	8.2106718e-05
2,770	The Semiring Framework for Database Provenance	2017	PODS	8.1495762e-05
3,047	Sketching Probabilistic Data Streams	2007	SIGMOD	7.6537004e-05
3,395	Event Queries on Correlated Probabilistic Streams	2008	SIGMOD	7.1402267e-05
3,479	Toward Best-Effort Information Extraction	2008	SIGMOD	7.053581e-05
4,163	Trio-One: Layering Uncertainty and Lineage on a Conventional DBMS	2007	CIDR	6.3861705e-05
4,370	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.2392118e-05
4,384	Hybrid In-Database Inference for Declarative Information Extraction	2011	SIGMOD	6.2251088e-05
4,439	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.1806955e-05
4,501	Rethinking Data Management for Storage-centric Sensor Networks	2007	CIDR	6.1325842e-05
4,510	iTrails: Pay-as-you-go Information Integration in Dataspaces	2007	VLDB	6.1239848e-05
4,722	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.9646931e-05
4,960	Querying Probabilistic Information Extraction	2010	VLDB	5.7992639e-05
5,545	Cleaning Uncertain Data with Quality Guarantees	2008	VLDB	5.447418e-05
5,556	Foundations of Uncertain-Data Integration	2010	VLDB	5.4394558e-05
5,755	A Framework for Clustering Uncertain Data	2015	VLDB	5.3390219e-05
5,771	PODS: A New Model and Processing Algorithms for Uncertain Data Streams	2010	SIGMOD	5.3319881e-05
5,807	Finding Frequent Items in Probabilistic Data	2008	SIGMOD	5.3189104e-05
5,837	Believe It or Not: Adding Belief Annotations to Databases	2009	VLDB	5.3078955e-05
5,991	Sampling Cube: A Framework for Statistical OLAP Over Sampling Data	2008	SIGMOD	5.2385592e-05
6,410	Queries with Difference on Probabilistic Databases	2011	VLDB	5.0682868e-05
6,522	Clustering Uncertain Graphs	2018	VLDB	5.0230003e-05
6,670	Explore or Exploit? Effective Strategies for Disambiguating Large Databases	2010	VLDB	4.9625499e-05
6,707	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD	4.9500448e-05
6,787	FICSR: Feedback-based InConSistency Resolution and Query Processing on Misaligned Data Sources	2007	SIGMOD	4.9207828e-05
6,837	Capturing Data Uncertainty in High-Volume Stream Processing	2009	CIDR	4.9063121e-05
6,958	Supporting OLAP Operations over Imperfectly Integrated Taxonomies	2008	SIGMOD	4.8810116e-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
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057797415
149	Trio: A System for Integrated Management of Data, Accuracy, and Lineage	2005	CIDR	0.00041085859
300	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00028503742
427	Automated Ranking of Database Query Results	2003	CIDR	0.0002350378
453	The Theory Of Probabilistic Databases	1987	VLDB	0.00022801484
561	An Annotation Management System for Relational Databases	2004	VLDB	0.00020099434
593	Lineage Tracing for General Data Warehouse Transformations	2001	VLDB	0.0001952223
655	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00018593536
702	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00017848789
937	Queries Independent of Updates	1993	VLDB	0.00015194231
1,191	The XXL Search Engine: Ranked Retrieval of XML Data using Indexes and Ontologies	2002	SIGMOD	0.00013424353
1,568	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.0001131667
1,695	A Probabilistic Framework for Vague Queries and Imprecise Information in Databases	1990	VLDB	0.00010866183
1,702	U-DBMS: A Database System for Managing Constantly-Evolving Data	2005	VLDB	0.00010821682
1,765	ORCHESTRA: Rapid, Collaborative Sharing of Dynamic Data	2005	CIDR	0.00010614654
1,824	DBNotes: A Post-It System for Relational Databases based on Provenance	2005	SIGMOD	0.00010395269
1,926	Reconciling while Tolerating Disagreement in Collaborative Data Sharing	2006	SIGMOD	0.00010071441
2,352	Horn Tables - An Efficient Tool For Handling Incomplete Information In Databases	1989	PODS	8.9815852e-05
2,593	Answering Queries from Statistics and Probabilistic Views	2005	VLDB	8.4758322e-05
3,503	Dependency Satisfaction in Databases with Incomplete Information	1984	VLDB	7.0332465e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,043	Query-Guided Resolution in Uncertain Databases	2023	SIGMOD	4.3997447e-05
718	Data Integration with Uncertainty	2007	VLDB	0.00017558942
149	Trio: A System for Integrated Management of Data, Accuracy, and Lineage	2005	CIDR	0.00041085859
1,972	Approximate Lineage for Probabilistic Databases	2008	VLDB	9.8937766e-05
4,163	Trio-One: Layering Uncertainty and Lineage on a Conventional DBMS	2007	CIDR	6.3861705e-05
1,698	Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases	2011	SIGMOD	0.00010857033
8,769	New Directions For Uncertainty Reasoning In Deductive Databases	1991	SIGMOD	4.4520434e-05
4,809	Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers	2019	SIGMOD	5.9035874e-05
7,944	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD	4.6089395e-05
300	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00028503742