Challenges for View-Based Query Answering over Probabilistic XML
Bogdan Cautis, Evgeny Kharlamov · 2011
Abstract. This is the first and preliminary study on answering queries using views in a probabilistic XML setting. We formalize the problem and study it under the two possible semantics for XML query results: with node identifiers and in their absence. Accordingly, we consider rewrite plans that can exploit a single view, by means of compensation, and plans that can use multiple views, by means of intersection. Since in probabilistic settings queries return answers with probabilities, the problem of rewriting goes beyond the classical one of retrieving answers from views. For both semantics of XML queries, we show that, even if the XML answers can be retrieved, the computation of their probabilities might not be possible. We give restrictions that make probabilistic rewriting feasible in polynomial time, and present some initial hardness results for this problem. 1