Institute of Information Science, Academia Sinica

In the database community there has been intense research activity both in XML data management and management of uncertain data. At the intersection of these two topics there has been interest in probabilistic variants of XML -- XML documents where content (e.g. elements or attributes) is uncertain. We will review the most well-studied existing models of probabilistic XML, and show that one can see them as subclasses of a formalism from verification of probabilistic procedural functions, Recursive Markov Chains (RMCs). In RMCs one recursively generates a nested set of call and return pairs of functions; in our variation, we use the same specification as a generator of random trees, by means of their nested-word serializations. We show that even quite powerful tree query formalisms can be effectively evaluated on these models. We then analyze the complexity for common XML query languages, such as XPath. In some cases, the algorithms and results are adaptations of those from Recursive State Machines and RMCs. In other cases, we find phenomena here that do not emerge in either the world of probabilistic model-checking or in classical XML querying -- for example, some query languages are complete for #EXPTIME.