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: 9507
Venue: VLDB
Year: 2006
Pagerank: 0.0004955674
Overall Rank: 101 | 99.30%
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.0007857786
257	Making Database Systems Usable	2007	SIGMOD	0.00030223397
299	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00028525071
487	Why Not?	2009	SIGMOD	0.00022050218
627	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00018959005
652	On the Provenance of Non-Answers to Queries over Extracted Data	2008	VLDB	0.00018634477
721	Data Integration with Uncertainty	2007	VLDB	0.00017570539
893	Data Integration: The Teenage Years	2006	VLDB	0.00015558352
980	BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models	2008	VLDB	0.00014879747
1,221	A Web of Concepts	2009	PODS	0.00013219242
1,252	Principles of Dataspace Systems	2006	PODS	0.00013033186
1,395	Structured Querying of Web Text: A Technical Challenge	2007	CIDR	0.00012207039
1,624	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB	0.00011099222
1,707	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010816111
1,730	Conditioning Probabilistic Databases	2008	VLDB	0.00010736755
1,860	Approximation Algorithms for Clustering Uncertain Data	2008	PODS	0.0001028857
1,861	Efficient Provenance Storage	2008	SIGMOD	0.00010287053
1,866	Update Exchange with Mappings and Provenance	2007	VLDB	0.00010272139
2,152	MISTIQUE: A System to Store and Query Model Intermediates for Model Diagnosis	2018	SIGMOD	9.4239787e-05
2,173	Querying Data Provenance	2010	SIGMOD	9.3676609e-05
2,256	ProvSQL: Provenance and Probability Management in PostgreSQL	2018	VLDB	9.1879032e-05
2,491	From Complete to Incomplete Information and Back	2007	SIGMOD	8.655056e-05
2,656	Exploiting Shared Correlations in Probabilistic Databases	2008	VLDB	8.3620622e-05
2,728	Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities	2009	SIGMOD	8.2185032e-05
2,764	The Semiring Framework for Database Provenance	2017	PODS	8.1574444e-05
3,041	Sketching Probabilistic Data Streams	2007	SIGMOD	7.6697078e-05
3,398	Event Queries on Correlated Probabilistic Streams	2008	SIGMOD	7.141911e-05
3,477	Toward Best-Effort Information Extraction	2008	SIGMOD	7.0583481e-05
4,163	Trio-One: Layering Uncertainty and Lineage on a Conventional DBMS	2007	CIDR	6.3923196e-05
4,373	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.2443809e-05
4,387	Hybrid In-Database Inference for Declarative Information Extraction	2011	SIGMOD	6.2320072e-05
4,442	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.186154e-05
4,500	Rethinking Data Management for Storage-centric Sensor Networks	2007	CIDR	6.1381791e-05
4,508	iTrails: Pay-as-you-go Information Integration in Dataspaces	2007	VLDB	6.1298098e-05
4,720	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.973811e-05
4,983	Querying Probabilistic Information Extraction	2010	VLDB	5.7870787e-05
5,537	Cleaning Uncertain Data with Quality Guarantees	2008	VLDB	5.4522327e-05
5,548	Foundations of Uncertain-Data Integration	2010	VLDB	5.4446854e-05
5,755	A Framework for Clustering Uncertain Data	2015	VLDB	5.3402052e-05
5,764	PODS: A New Model and Processing Algorithms for Uncertain Data Streams	2010	SIGMOD	5.3369195e-05
5,796	Finding Frequent Items in Probabilistic Data	2008	SIGMOD	5.3240234e-05
5,823	Believe It or Not: Adding Belief Annotations to Databases	2009	VLDB	5.3129967e-05
5,987	Sampling Cube: A Framework for Statistical OLAP Over Sampling Data	2008	SIGMOD	5.2432535e-05
6,415	Queries with Difference on Probabilistic Databases	2011	VLDB	5.0731258e-05
6,545	Clustering Uncertain Graphs	2018	VLDB	5.0193115e-05
6,670	Explore or Exploit? Effective Strategies for Disambiguating Large Databases	2010	VLDB	4.9672601e-05
6,705	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD	4.9549359e-05
6,787	FICSR: Feedback-based InConSistency Resolution and Query Processing on Misaligned Data Sources	2007	SIGMOD	4.92548e-05
6,838	Capturing Data Uncertainty in High-Volume Stream Processing	2009	CIDR	4.9109732e-05
6,959	Supporting OLAP Operations over Imperfectly Integrated Taxonomies	2008	SIGMOD	4.8857059e-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.00057857292
149	Trio: A System for Integrated Management of Data, Accuracy, and Lineage	2005	CIDR	0.00041101118
299	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00028525071
427	Automated Ranking of Database Query Results	2003	CIDR	0.0002352637
450	The Theory Of Probabilistic Databases	1987	VLDB	0.00022822073
561	An Annotation Management System for Relational Databases	2004	VLDB	0.00020115419
611	Lineage Tracing for General Data Warehouse Transformations	2001	VLDB	0.00019231115
655	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00018608845
706	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00017845469
938	Queries Independent of Updates	1993	VLDB	0.00015197786
1,192	The XXL Search Engine: Ranked Retrieval of XML Data using Indexes and Ontologies	2002	SIGMOD	0.00013432765
1,586	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00011250856
1,697	A Probabilistic Framework for Vague Queries and Imprecise Information in Databases	1990	VLDB	0.00010873473
1,705	U-DBMS: A Database System for Managing Constantly-Evolving Data	2005	VLDB	0.00010829958
1,767	ORCHESTRA: Rapid, Collaborative Sharing of Dynamic Data	2005	CIDR	0.00010623574
1,824	DBNotes: A Post-It System for Relational Databases based on Provenance	2005	SIGMOD	0.00010405194
1,923	Reconciling while Tolerating Disagreement in Collaborative Data Sharing	2006	SIGMOD	0.00010080761
2,347	Horn Tables - An Efficient Tool For Handling Incomplete Information In Databases	1989	PODS	8.9890664e-05
2,590	Answering Queries from Statistics and Probabilistic Views	2005	VLDB	8.483194e-05
3,496	Dependency Satisfaction in Databases with Incomplete Information	1984	VLDB	7.0397186e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,754	Lineage Processing over Correlated Probabilistic Databases	2010	SIGMOD	4.6600967e-05
721	Data Integration with Uncertainty	2007	VLDB	0.00017570539
149	Trio: A System for Integrated Management of Data, Accuracy, and Lineage	2005	CIDR	0.00041101118
1,970	Approximate Lineage for Probabilistic Databases	2008	VLDB	9.896375e-05
4,163	Trio-One: Layering Uncertainty and Lineage on a Conventional DBMS	2007	CIDR	6.3923196e-05
1,699	Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases	2011	SIGMOD	0.00010858983
8,772	New Directions For Uncertainty Reasoning In Deductive Databases	1991	SIGMOD	4.456315e-05
4,806	Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers	2019	SIGMOD	5.9092698e-05
7,941	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD	4.613363e-05
299	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00028525071