Extensional Query Evaluation - Probabilistic Databases - page 89

infinite probability distributions, and can be exponentially more succinct than the PrXML exp model,
while still preserving tractability for Monadic Second-Order Logic. In particular, it is shown that the
so-called hierarchical Markov chains are tractable under fixed-cost arithmetic, and so-called tree-
like Markov chains are tractable in the usual bit-cost arithmetic. The yardstick particularly useful
to differentiate among these models is the ability to represent succinctly trees of arbitrary width or
depth, and probability spaces with worlds that have probabilities double-exponentially close to 1.
Deutch et al. [ 2010a ] discuss the query evaluation problem for datalog with a stochastic extension
that determines the execution of a datalog program to be a Markov Chain. They show that the query
evaluation problem is hard in general and describe approximation algorithms for special cases.