Output details

Answering queries using views over probabilistic XML: Complexity and tractability

<15>

This paper studies an important optimisation problem for query processing over probabilistic XML and provides promising solutions applicable in practice. It investigates whether and how one can answer a query over such a database using only views. The paper proves that this may be computationally infeasible even when the problem can be efficiently solved for deterministic XML, and presents algorithms to detect these infeasible cases. For feasible cases, the paper studies different answer semantics, and presents efficient algorithms (modulo the complexity of the feasibility check) to compute query answers.