Probabilistic XML via Markov Chains

Michael Benedikt, Dan Olteanu, Evgeny Kharlamov, Pierre Senellart

Abstract

We show how Recursive Markov Chains (RMCs) and their restrictions can define probabilistic distributions over XML documents, and study tractability of querying over such models. We show that RMCs subsume several existing probabilistic XML models. In contrast to the latter, RMC models (i) capture probabilistic versions of XML schema languages such as DTDs, (ii) can be exponentially more succinct, and (iii) do not restrict the domain of probability distributions to be finite. We investigate RMC models for which tractability can be achieved, and identify several tractable fragments that subsume known tractable probabilistic XML models. We then look at the space of models between existing probabilistic XML formalisms and RMCs, giving results on the expressiveness and succinctness of RMC subclasses, both with each other and with prior formalisms. © 2010 VLDB Endowment.
BibTeX
@article{benedikt2010probabilistic,
  author = {Michael Benedikt and Dan Olteanu and Evgeny Kharlamov and Pierre Senellart},
  title = {{Probabilistic XML via Markov Chains}},
  journal = {Proc. VLDB Endow.},
  year = {2010},
  doi = {10.14778/1920841.1920939},
}

Loading related content...

Figure