Database Reference
In-Depth Information
5. INTENSIONAL QUERY EVALUATION
finishes in polynomial time if the query is tractable, i.e., hierarchical, or when its lineage has a
read-once equivalent.
Compilation has applications beyond the computation of marginal probabilities.
Darwiche and Marquis
[
2002
] describe several applications of knowledge compilation for proposi-
tional formulas, including probabilistic inference and model counting. For probabilistic databases,
Koch and Olteanu
[
2008
] introduce compilation-based techniques for
conditioning
probabilistic
databases. The conditioning problem is to transform a probabilistic database of priors into a posterior
probabilistic database which is materialized for subsequent query processing or further refinement.
Here, the new evidence used for conditioning is in the form of database constraints.