Querying Probabilitistic Data via Tree Decompositions Supervisor

Probabilistic databases are compact representations of probability distributions over regular databases. A number of models have been proposed for probabilistic data, both relational [7] and XML [4]. Evaluating a Boolean query over such a probabilistic database means computing the probability that the query is true in the probability distribution represented by the database. While query evaluation is usually tractable on regular databases, evaluating queries in this sense on probabilistic databases is often intractable. A number of research works have looked at characteristics of queries that can make them tractable. For instance, queries without self-joins are tractable over tuple-independent databases if and only if they are hierarchical [2], while tree-pattern queries on XML data with a single join are tractable if and only if they are equivalent to a join-free query [3]. By contrast, our recent work [1] has shown that, as long as the data and probabilistic correlations jointly have bounded treewidth [6] in a certai