PaperlayerView exact revision on arXiv

Source-linked AI summary

Conditioning Probabilistic Databases

Christoph Koch, Dan Olteanu

arXiv:0803.2212v2cs.DBcs.AI

TL;DR

Probabilistic databases often need to incorporate new evidence, but conditioning and exact tuple-confidence computation are NP-hard, and approximation does not address either exact task. The paper develops decomposition-based algorithms for conditioning and exact confidence computation. It evaluates these methods against Monte Carlo approximation and reports that exact approaches can scale to realistic databases and sometimes compete with efficient approximations.

  • Problem

    Conditioning probabilistic databases with new evidence and computing exact tuple confidences are NP-hard tasks that approximation techniques do not solve.

    Source: §1 · p. 1

  • Method

    The paper develops ws-tree decompositions and Davis-Putnam-inspired rules and heuristics for exact confidence computation and database conditioning.

    Source: §1 · pp. 2–3

  • Results

    The paper reports a thorough experimental evaluation and compares its exact confidence techniques with Monte Carlo approximation.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Once a ws-tree decomposition is obtained, both exact confidence computation and conditioning are feasible in linear time.

    Source: §1 · p. 2

    Translation to ws-trees can take exponential time in the input ws-set size, and an equivalent mutex ws-set can also be exponential.

    Source: §6 · p. 9

Abstract

from arXiv · show

Past research on probabilistic databases has studied the problem of answering queries on a static database. Application scenarios of probabilistic databases however often involve the conditioning of a database using additional information in the form of new evidence. The conditioning problem is thus to transform a probabilistic database of priors into a posterior probabilistic database which is materialized for subsequent query processing or further refinement. It turns out that the conditioning problem is closely related to the problem of computing exact tuple confidence values. It is known that exact confidence computation is an NP-hard problem. This has led researchers to consider approximation techniques for confidence computation. However, neither conditioning nor exact confidence computation can be solved using such techniques. In this paper we present efficient techniques for both problems. We study several problem decomposition methods and heuristics that are based on the most successful search techniques from constraint satisfaction, such as the Davis-Putnam algorithm. We complement this with a thorough experimental evaluation of the algorithms proposed. Our experiments show that our exact algorithms scale well to realistic database sizes and can in some scenarios compete with the most efficient previous approximation algorithms.

1. INTRODUCTION

The paper targets conditioning and exact tuple-confidence computation in probabilistic databases, both NP-hard tasks for which approximation is not a substitute in settings where errors can propagate. It develops decomposition-based exact methods and evaluates them experimentally.

1. INTRODUCTION

  • Conditioning removes worlds that violate new evidence and renormalizes the remaining probabilities to produce a posterior database.The paper motivates this as materializing a database of priors after adding constraints or other evidence.Source: §1 · pp. 1–2
  • Exact confidence matters when computed probabilities feed later query operations or updates, because errors can accumulate and affect many subsequent decisions.Data cleaning is one example: transformed data may be materialized once, while incorrect stored probabilities could affect later queries.Source: §1 · p. 2
  • The paper develops efficient algorithms for conditioning probabilistic databases and computing exact tuple confidences, two NP-hard problems.Approximate confidence errors can accumulate in compositional queries and affect later decisions or queries.Source: §1 · p. 2
  • The paper models confidence computation as weighted counting over world-set descriptor structures and introduces a framework generalizing several probabilistic database models.The stated examples include tuple-independence models, ULDBs, product decomposition, and c-table-based models.Source: §1 · p. 2
  • The authors develop ws-trees and a Davis-Putnam-inspired decomposition procedure with variable-elimination and independence rules, plus heuristics for choosing between them.Ws-tree decompositions make conditioning and exact confidence computation linear-time once a tree has been obtained.Source: §1 · pp. 2–3
  • The paper also develops and proves correct a ws-tree-based conditioning algorithm, studies simplification and elimination alternatives, and experimentally compares exact confidence methods with Monte Carlo approximation.The introduction reports a thorough evaluation but gives no specific benchmark outcome in these passages.Source: §1 · p. 3

2. PROBABILISTIC DATABASES

The paper represents probabilistic databases using independent variables, a relational world-table, and tuple-associated world-set descriptors. This representation connects valuations of variables to the databases present in each possible world.

2. PROBABILISTIC DATABASES

  • A world-table W stores each variable, its domain value, and the probability assigned to that value.The variables are independent, and the probabilities for assignments of each variable sum to one.Source: §2 · p. 3
  • A world-set descriptor is a partial assignment that denotes every total valuation extending it; a total assignment identifies one possible world.An empty descriptor denotes all possible worlds.Source: §2 · p. 3
  • A ws-set combines descriptors by taking the union of the world-sets they represent.The paper defines its semantics by extending the descriptor-to-world-set function to sets of descriptors.Source: §2 · p. 3
  • A U-relation associates each tuple with a ws-descriptor, and a probabilistic database represents one ordinary database for each possible world defined by W.A tuple appears in a world when that world's total valuation extends the tuple's descriptor.Source: §2 · p. 3
  • U-relations generalize probabilistic database models including tuple-independence, ULDB, product-decomposition, and c-table-based models.The paper notes that U-relations are a complete representation system for probabilistic databases over nonempty finite world sets.Source: §2 · p. 3

3. PROPERTIES OF WS-DESCRIPTORS

The paper develops symbolic properties and operations on world-set descriptors so that world-set manipulations need not enumerate potentially enormous collections of worlds. It applies these properties to confidence computation, tuple possibility, and conditioning.

3. PROPERTIES OF WS-DESCRIPTORS

  • Symbolic ws-descriptor operations support tasks such as tuple possibility, confidence computation, and conditioning without enumerating potentially huge world sets.The paper cites prior experiments reporting 10^106 worlds in such sets.Source: §3 · p. 4, §3.2 · p. 4

3.1 Mutex, Independence, and Containment

  • After eliminating singleton-domain variables, mutex descriptors have conflicting assignments, independent descriptors share no variables, and containment is tested by extension.For ws-sets, the paper defines mutex and independence pairwise across descriptors and equivalence as representing the same world-set.Source: §3.1 · p. 4

3.2 Set Operations on ws-sets

  • The paper defines union, intersection, and difference on ws-sets to perform symbolic world-set manipulation.The operations are correct, and descriptors produced by difference are pairwise mutex.Source: §3.2 · p. 4

4. WORLD-SET TREES

Ws-sets can overlap, complicating probability manipulation; ws-trees make independence and exclusivity explicit to support exact probability computation and conditioning. Their construction uses decomposition and variable-choice heuristics, and ordering can substantially affect tree size.

4. WORLD-SET TREES

  • Ws-sets can overlap, making probability manipulation costly; ws-trees expose structure through independent ⊗ children and mutually exclusive ⊕ branches.The structure supports exact probability computation and conditioning.Source: §4 · pp. 4–5

4.1 Constructing world-set trees

  • ComputeTree recursively partitions independent subsets into ⊗ nodes or branches on variable assignments into ⊕ nodes, preserving the represented world-set.A nullary descriptor ends recursion at a ∅ leaf.Source: §4.1 · pp. 5–6
  • Variable ordering strongly affects tree size: eliminating y creates highly overlapping intermediates and a larger tree than R, and redundancy removal still leaves it larger.The translation can yield exponential-size ws-trees, so ordering and independent partitioning matter in practice.Source: §4.1 · p. 6

4.2 Heuristics

  • Minlog and minmax are variable-choice heuristics; minmax minimizes the largest resulting ws-set, while independent partitioning reduces cost when available.Both heuristics take time linear in the variable-domain sizes plus the ws-set size; minlog additionally uses log and exp operations.Source: §4.2 · p. 6

4.3 Probability computation

  • Exact probability is evaluated bottom-up: multiply independent ⊗ children, sum assignment-weighted mutually exclusive ⊕ branches, and assign 1 or 0 to universal or empty leaves.The probability traversal can be composed with translation so the ws-tree need not be precomputed.Source: §4.3 · pp. 6–7

5. CONDITIONING

Conditioning removes worlds that fail a Boolean condition and renormalizes the remaining database. The algorithm uses ws-tree recursion to preserve a succinct representation while computing the condition’s confidence.

5. CONDITIONING

  • The algorithm recursively conditions on a ws-tree and renormalizes branch weights by introducing variables whose assignments reflect the new weights.It returns both the condition’s confidence in the input database and a modified database in which that confidence is 1.Source: §5 · pp. 7–8
  • During recursion, eliminated variables are replaced by new variables with normalized assignments, and the associated ws-descriptors are updated.The algorithm extends descriptors for each alternative of an eliminated variable.Source: §5 · p. 8
  • Theorem 5.3 establishes that conditioning on a nonempty subset of worlds produces a database whose world probabilities sum to 1.The algorithm also preserves a representation of the conditioned database.Source: §5 · p. 8
  • The implementation can simplify the world table and output descriptors by dropping unused or single-valued variables and merging equivalent variables created in separate branches.Source: §5 · pp. 8–9
  • Assert-operations commute with other asserts and with positive relational algebra operations, a property the paper identifies as useful for query optimization.Source: §5 · p. 9

6. WS-DESCRIPTOR ELIMINATION

Ws-descriptor elimination computes a ws-set’s probability by incrementally removing descriptors and using differences to split the remaining probability calculation into mutex parts.

6. WS-DESCRIPTOR ELIMINATION

  • For a descriptor d1 in S, the method computes S without d1 and the difference {d1} − (S without d1), then sums their probabilities because the resulting ws-sets are mutex.The difference operation preserves mutex and world-set monotonicity.Source: §6 · p. 9
  • Theorem 6.3 states that Pw computes the probability of any ws-set S.The proof follows from the difference operation’s world-set properties.Source: §6 · p. 9
  • The method can take exponential time in the input ws-set size, and its equivalent mutex ws-set can also be exponential.However, probabilities of mutex ws-sets can be computed in linear time, and difference descriptors can be summed and discarded as they are generated.Source: §6 · p. 9

7. EXPERIMENTS

The experiments evaluate exact confidence computation across TPC-H-derived and synthetic ws-sets, comparing variable-elimination methods, ws-descriptor elimination, and Monte Carlo approximation.

7. EXPERIMENTS

  • The synthetic workloads span 50–100K variables, 5–60K descriptors, descriptor lengths of 2 or 4, and 2 or 4 alternatives per variable.They include TPC-H-derived tuple-independent databases and ws-sets modeled on nonhierarchical conjunctive joins.Source: §7 · pp. 9–10
  • The study compares INDVE with minlog and minmax heuristics against VE, ws-descriptor elimination, and Monte Carlo confidence estimation.The exact implementations compute confidence and the modified world table; materializing the conditioned U-relations adds only small overhead in practice.Source: §7 · p. 10
  • INDVE(minlog) runs within hundreds of seconds on TPC-H queries over databases with more than 700K variables and 60K ws-descriptors.The workload includes an equi-join and a selection-projection query; the latter’s descriptors are pairwise independent, making its confidence computation more efficient for INDVE.Source: Figure 10 · p. 10, §7 · p. 11

2. The numbers of variables and of ws-descriptors

The relative numbers of variables and ws-descriptors shape the difficulty of exact confidence computation, with independence partitioning and variable-elimination heuristics affecting performance.

The numbers of variables and of ws-descriptors

  • Within a second, VE handles 100 variables, domain size 4, descriptor length 4, and more than 1.2K ws-descriptors; VE also outperforms INDVE in this many-descriptor regime.VE and INDVE with minlog remain stable when descriptors greatly outnumber variables.Source: §2 · p. 11
  • INDVE(minlog) runs within seconds on 100K variables and 100–6K length-2 ws-descriptors with domain size 4, while VE performs much worse.The passage also reports two length-4 outliers among 25 runs that exceed 600 seconds.Source: §2 · p. 11
  • When variable and descriptor counts become close, INDVE(minlog) shows an easy-hard-easy pattern, with computation remaining hard until descriptors exceed variables by an order of magnitude.Ws-descriptor elimination follows the easy-hard transition but does not return to the easy regime within the reported range.Source: §2 · p. 11
  • When counts differ by orders of magnitude, INDVE(minlog) and VE(minlog) are competitive with KL; near-equal counts let KL with ε = 0.001 outperform INDVE(minlog) only in hard cases.Source: §2 · p. 11
  • Minlog costs more to compute than minmax but generally chooses better variables, leaving INDVE less sensitive to data correlations.The figure compares the two heuristics.Source: §2 · p. 11, Figure 13 · p. 11

8. RELATED WORK

Prior work studied confidence computation and uncertain-data representations, but this paper is the first to study conditioning for probabilistic databases. The authors relate their approach to graphical models, model counting, and decision-diagram representations.

8. RELATED WORK

  • The paper is the first to study conditioning for probabilistic databases.The authors state this as a contribution to the literature on probabilistic databases and knowledge compilation.Source: §8 · p. 11
  • U-relations capture several uncertain-data formalisms, including MystiQ, Trio, and MayBMS [3], for which applications in data cleaning and other areas have been described.These formalisms are associated with natural applications in data cleaning and other areas.Source: §8 · pp. 11–12
  • Graphical-model methods can be inefficient for queried tuple-independent data because the resulting models tend to be flat but have high tree-width.Although graphical models are more succinct than U-relations, their succinctness does not benefit currently known query-evaluation techniques.Source: §8 · p. 12
  • Confidence computation on DNF-like possible-world representations generalizes DNF model counting and is #P-complete, while Monte Carlo methods provide an approximation approach.The passage places the approach in prior work on query reliability and the MystiQ project.Source: §8 · p. 12
  • The variable-elimination approach combines the Davis-Putnam procedure with independent partitioning to address exact confidence computation and conditioning.The authors contrast their database-context experiments with prior model-counting work on CNF formulas with up to 50 variables and 200 clauses.Source: §8 · p. 12
  • ws-trees and OBDDs both expose formula structure for manipulation, but differ in variable types, ordering constraints, and explicit representation of independence.Different variable orderings on different paths can make BDDs exponentially more succinct, while binary encoding of multistate variables adds a logarithmic number of variables.Source: §8 · p. 12

APPENDIX Proof of Theorem 4.4

The proof establishes that ComputeTree preserves the world-set represented by a ws-set. It uses induction over ws-tree structure, handling independent partitions and variable-based decomposition.

APPENDIX Proof of Theorem 4.4

  • ComputeTree(S) and S represent the same world-set for any ws-set S.The proof establishes the correctness of the translation from ws-sets to ws-trees.Source: APPENDIX Proof of Theorem 4.4 · p. 13
  • The induction maps the empty world-set to ⊥ and the universal ws-descriptor to ∅, then treats the two inner-node types.For the pairwise-independent case, the proof uses the corresponding computed trees for the partitioned ws-sets.Source: APPENDIX Proof of Theorem 4.4 · p. 13
  • For a variable x, the proof splits ws-descriptors by assignments to x and separates descriptors containing another assignment from those consistent with the selected assignment.Removing inconsistent descriptors preserves equivalence, yielding the decomposition into Sx→i and T.Source: APPENDIX Proof of Theorem 4.4 · p. 13

Proof of Theorem 5.3

The proof shows that conditioning a nonempty subset of worlds yields a probabilistic-database representation whose probabilities sum to one. It establishes correctness by induction over the input ws-tree and its recursive conditioning steps.

Proof of Theorem 5.3

  • The conditioning algorithm returns a representation of the selected nonempty world subset with probabilities summing to 1.The algorithm computes node probabilities using the probability-computation algorithm before proving renormalization correct by induction.Source: Proof of Theorem 5.3 · p. 13
  • At the base case, the ws-tree ∅ represents the whole world-set, so conditioning returns U unchanged.No conditioning is performed in this case.Source: Proof of Theorem 5.3 · p. 13
  • Recursive calls condition the subsets of U consistent with each child; the resulting tuples are those whose ws-descriptors match a child descriptor.The proof distinguishes independent-partitioning and variable-elimination nodes in the recursive construction.Source: Proof of Theorem 5.3 · p. 13
Loading 0803.2212v2…