AI Glossary / Graphs and symbolic AI / Intermediate

Probabilistic database

Definition

A probabilistic database represents uncertainty about database contents using a probability model. In a common possible-worlds interpretation, each possible complete database instance has an associated probability. Queries then propagate that uncertainty to their answers. This is more than storing a confidence column: the system needs semantics for how uncertain records and their dependencies combine during query processing.

What it means

A conventional database typically answers a query against one stored instance. A probabilistic database models several possible instances because some records, attributes, or relationships are uncertain. An answer's probability reflects the worlds in which that answer would be returned, according to the model.
Possible worlds are mathematical database states, not claims about parallel universes. A compact representation usually stands in for a potentially enormous collection of states. Tuple independence is one useful simplifying assumption, but probabilistic databases can also represent mutually exclusive alternatives and correlated facts. Which representation is used affects both meaning and computational cost.

How it works

Define the uncertain events and their probability relationships. Conceptually, evaluate the query on every possible database instance and combine the probabilities of instances producing each result. For a Boolean query, the answer probability is the sum of the probabilities of worlds where the query is true.
Practical systems seek more efficient methods than explicit world enumeration. Query lineage can record the combinations of underlying events that support an answer. Probability evaluation must account for overlap among those combinations; treating every derivation as independent can double-count evidence. Some queries and representations permit efficient exact evaluation, while others require more expensive inference or approximations.

Three practical examples

• A record-linkage workflow can represent uncertainty about whether two imported records refer to the same entity, subject to appropriate consistency constraints.
• A sensor-data application can query uncertain event records without converting every preliminary detection into an unquestioned fact.
• An information-extraction project can preserve uncertainty about extracted relationships and examine how it affects downstream query answers.

Think of it this way

Think of several completed versions of a spreadsheet, each with a weight describing how plausible it is under a model. Ask the same question of each version and combine the weights of matching answers. The analogy is limited because a real probabilistic database usually represents these versions compactly and must preserve dependencies through joins and other operations.

Worked example

Consider an invented database with two uncertain records: event A occurs with probability 0.8 and event B occurs with probability 0.5. Assume their occurrences are independent and no other uncertainty is present.
There are four possible worlds. Both records are present with probability 0.8 × 0.5 = 0.4. Only A is present with probability 0.8 × 0.5 = 0.4. Only B is present with probability 0.2 × 0.5 = 0.1. Neither is present with probability 0.2 × 0.5 = 0.1. The four probabilities sum to 1.
The Boolean query “Does at least one event occur?” is true in the first three worlds, giving probability 0.4 + 0.4 + 0.1 = 0.9. Adding the two record probabilities directly would give 1.3 and double-count the world containing both. The query “Do both occur?” has probability 0.4.
The expected number of present records is 0.8 + 0.5 = 1.3. This value is valid as an expected count, even though 1.3 would be impossible as a probability. If independence is removed, the marginal record probabilities alone do not determine the two Boolean query probabilities.

Illustrative case study

In a fictional archive project, an extraction tool produces two candidate records from different passages. Both passages quote the same original note, so their uncertainties are strongly related. A prototype query treats them as independent confirmations and reports an inflated answer probability.
The team records the shared source event in the model and checks query lineage for repeated dependence on it. It also reviews how extraction scores were converted into probabilities. The case illustrates why data provenance and dependence matter; it does not claim that a probabilistic database can repair inaccurate input probabilities automatically.

Common misconceptions and mistakes

A number between zero and one is not necessarily a calibrated probability. It might be a similarity score, model confidence, or manually assigned weight. Its meaning must be established before probabilistic query rules are applied.
Also distinguish probability from frequency counts and truth labels. An answer probability of 0.9 expresses model uncertainty, not a guarantee of correctness. A NULL value in a conventional table is not automatically a probability distribution. Finally, joins and repeated use of the same uncertain fact can create dependencies even when the original base events were independent.

Business use

Probabilistic databases can help organizations keep uncertainty visible through a chain of information processing. This is useful when a premature yes-or-no decision would hide alternatives that matter to later analysis. Query results can support review priorities or sensitivity analysis when interpreted within a validated model.
Before adopting the approach, identify the uncertain events, dependence assumptions, and origin of probability estimates. Decide whether the required queries need exact probabilities or acceptable approximations. Report approximation uncertainty separately from uncertainty in the data model. Complexity and maintenance costs should be evaluated against a simpler workflow with explicit review states.

People also ask

Is every row required to be independent?

No. Independence is a particular model choice. Other representations can include exclusions and correlations.

Does adding a probability column create a probabilistic database?

Not by itself. Query semantics must specify how those values and dependencies affect results.

Can a query answer have several supporting explanations?

Yes. Their overlap must be accounted for; simply summing explanation probabilities can count the same world more than once.

Check your understanding

In the worked database, what is the probability that exactly one record is present?

Answer: Add the disjoint A-only and B-only worlds: 0.4 + 0.1 = 0.5. This differs from the probability of at least one record, which also includes the both-present world.

Related terms

• Possible world
• Uncertain data
• Probabilistic inference
• Calibration
• Expected value
• Possible worlds
• tuple independence
• query lineage
• database query
• data provenance

Learn next

Next, study Boolean query lineage. Write the worked queries as A OR B, A AND B, and “exactly one of A and B.” Then replace independence with a shared underlying event and explain which calculations must change. Keep the event model separate from the query's logical structure.

More in Graphs and symbolic AI

• Prioritized sweeping - Prioritized sweeping is a model-based reinforcement-learning and planning technique that concentrates value updates on states likely to be affected by...
• Priority queue - A priority queue is a data structure that returns the item with the best priority according to a specified ordering.
• Probabilistic context-free grammar - A probabilistic context-free grammar, or PCFG, is a context-free grammar whose production rules have probabilities.
• Probabilistic Graphical Model - A probabilistic graphical model represents a probability distribution using a graph and associated numerical functions.
• Probabilistic Horn abduction - Probabilistic Horn abduction is a framework that combines logical rules with probabilities assigned to possible hypotheses.
• Probabilistic roadmap - A probabilistic roadmap is a graph built from sampled robot configurations and feasible local paths between them.

Sources

Dalvi, Ré, and Suciu, Queries and Materialized Views on Probabilistic Databases, possible-worlds definitions, query semantics, and lineage discussion: https://homes.cs.washington.edu/~suciu/jcss-probdb.pdf . Relevant original-paper sections were read. The two-event example and archive scenario are original illustrations rather than reported system results.

Previous: Probabilistic context-free grammar Next: Probabilistic forecasting