Conditioning probabilistic databases
Past research on probabilistic databases has studied the problem of answering queries on a static database. Ap-plication scenarios of probabilistic databases however often involve the conditioning of a database using additional in-formation in the form of new evidence. The conditioning problem is th...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2008
|
| Summary: | Past research on probabilistic databases has studied the problem of answering queries on a static database. Ap-plication scenarios of probabilistic databases however often involve the conditioning of a database using additional in-formation in the form of new evidence. The conditioning problem is thus to transform a probabilistic database of pri-ors into a posterior probabilistic database which is material-ized 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 approx-imation techniques for confidence computation. However, neither conditioning nor exact confidence computation can be solved using such techniques. In this paper we present ef-ficient techniques for both problems. We study several prob-lem decomposition methods and heuristics that are based on the most successful search techniques from constraint satis-faction, such as the Davis-Putnam algorithm. We comple-ment this with a thorough experimental evaluation of the algorithms proposed. Our experiments show that our ex-act algorithms scale well to realistic database sizes and can in some scenarios compete with the most efficient previous approximation algorithms. © 2008 VLDB Endowment. |
|---|