Title:

Modeling and Querying Probabilistic XML


Abstract:

A probabilistic XML document is a probability space over ordinary XML
documents. It is often represented in a compact form (e.g., by
annotating elements with measures of uncertainty). The literature has
a variety of probabilistic XML models that constitute such
representations.  The talk describes a unified framework that captures
previously studied models and gives rise to extensions and
combinations thereof. Following that, the talk surveys a comprehensive
study of the expressive power of the various models (relative to one
another), and discusses the complexity of evaluating tree-pattern
queries (with projection) in two specific models. In the first model,
every query has a tractable data complexity; in the second, every
nontrivial Boolean query is intractable. This draws a complete picture
regarding the complexity of query evaluation, due to the results about
expressiveness. The tractable model subsumes most of those in the
literature, yet it makes an inherent assumption of independence among
probabilistic junctions.  To overcome this limitation, two approaches
are studied. One is to combine the two models, but allow answers to be
approximate. The second is to describe correlations in terms of a
fixed set of constraints. The latter approach is realized by proposing
a rich, efficient query language that has aggregate functions and is
capable of expressing realistic constraints. Finally, the talk
sketches recent results on "running" tree automata over probabilistic
XML, and discusses the implications on query evaluation and on
coupling probabilistic XML with schemata (e.g., DTD).