Uncertain Database¶
A database representation whose semantics admit multiple possible ordinary instances and define query answers across them.
Core Idea¶
An uncertain database represents more than one possible ordinary database instance. It stores alternatives compactly, gives rules for interpreting those alternatives as complete instances, and defines how a query works across them. A ULDB can retain alternative results and their lineage; a probabilistic database can attach weights to worlds and return answer probabilities. Probability and lineage are model-specific, not universal requirements.[ref-318179fbd4d8][ref-4f92a41cf6a3]
Scope of Application¶
Benjelloun and colleagues' ULDB formalism uses alternative and optional tuples in a simplified witness-observation relation. Dalvi and Suciu use uncertain movie-query matches to create probabilistic director and film candidate tables. These are different kinds of uncertainty in relational data, both with a mapping from stored marks to possible instances and query results.[ref-318179fbd4d8][ref-4f92a41cf6a3]
The cited cases are authors' worked examples. SQL NULL or fuzzy grades do not automatically share the same world and query semantics; they require their own specified models.
Clarity¶
Separate what is stored, which ordinary instances it represents, and what the query returns. “Amy saw Mazda or Toyota” in an x-tuple does not assert both sightings. A tuple-presence probability is not necessarily the probability of a derived join answer when derivations share input tuples.[ref-318179fbd4d8][ref-4f92a41cf6a3]
Manages Complexity¶
Dalvi and Suciu's three independent input tuples generate eight possible worlds. Storing three probabilities is much shorter than listing all worlds, but correct evaluation must still respect dependencies created by query operations. Their worked query returns 0.54; a naive independence calculation on joined rows gives 0.636.[^ref-4f92a41cf6a3]
Abstract Reasoning¶
Identify the model's alternatives, determine which ordinary instances they permit, apply the query under that model, and then use its result rule. Keep alternative outputs and lineage where the model does, or calculate a weighted answer under a probabilistic model. Never add a numeric confidence to a model that supplies no world weights.[ref-318179fbd4d8][ref-4f92a41cf6a3]
Knowledge Transfer¶
The representation-to-worlds-to-query discipline transfers from ULDB alternatives to probabilistic relations. Their encodings and answer rules differ. The broader Representation Prime carries the medium-to-target mapping beyond databases; this entry still requires database instances and query semantics.[ref-318179fbd4d8][ref-4f92a41cf6a3]
Example¶
Alternative witness observations: Benjelloun and colleagues' Saw(witness, car) example allows different ordinary relations from alternative and optional tuples. Mapped roles: alternatives → three possible Saw instances; representation → x-tuples; interpretation → consistent selection; query → alternative results with lineage in the ULDB model. Confidence is an optional extension.[^ref-318179fbd4d8]
Uncertain movie matches: Dalvi and Suciu turn approximate director-name, film-title and year matches into probabilistic candidate tables and rank joined film results. Mapped roles: alternatives → candidate row presences; representation → probabilistic tables; interpretation → weighted possible worlds; query → ranked answer probabilities. Their separate formal example shows how a shared input event affects a 0.54 answer probability.[^ref-4f92a41cf6a3]
Relationships to Other Abstractions¶
Current abstraction Uncertain Database Domain-specific
Parents (1) — more general patterns this builds on
-
Uncertain Database is a kind of Representation Prime
An uncertain database is a representation mapped to possible ordinary database instances.
Hierarchy path (1) — routes to 1 parentless root
- Uncertain Database → Representation → Abstraction
Neighborhood in Abstraction Space¶
Uncertain Database sits in a sparse region of the domain-specific corpus (97th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2551 abstractions)
Nearest neighbors
- Nonelementary Problem — 0.79
- Boolean Conjunctive Query — 0.78
- Exportation (logic) — 0.76
- NTIME — 0.76
- Rational Choice Model — 0.76
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
A single fully determined instance, bare NULL notation without declared semantics, or probability attached to a query result without an underlying possible-world account. The proposed strict parent is Representation: every uncertain database maps stored data to alternative instances, while most representations are not databases.[ref-318179fbd4d8][ref-4f92a41cf6a3]
References¶
[^ref-318179fbd4d8]: Omar Benjelloun, Anish Das Sarma, Alon Halevy and Jennifer Widom, ULDBs, Databases with Uncertainty and Lineage, VLDB 2006 original full paper (source title uses a colon after “ULDBs”), §§2.2–3, especially Example 2.5 and Definition 3.1; §5, pp. 7–8 discusses added confidence treatment. [^ref-4f92a41cf6a3]: Nilesh Dalvi and Dan Suciu, Efficient Query Evaluation on Probabilistic Databases, VLDB 2004 original author PDF, §2, Figs. 1–4, and “Queries with uncertain matches” on printed p. 3. The movie query and 0.54 calculation are separate illustrative examples.