The Possibility Problem for Probabilistic XML

Abstract :

We consider the possibility problem of determining if a document is a possible world of a probabilistic document, in the setting of probabilistic XML. This basic question is a special case of query answering or tree automata evaluation, but it has specific practical uses, such as checking whether an user-provided probabilistic document outcome is possible or sufficiently likely. In this paper, we study the complexity of the possibility problem for probabilistic XML models of varying expressiveness. We show that the decision problem is often tractable in the absence of long-distance dependencies, but that its computation variant is intractable on unordered documents. We also introduce an explicit matches variant to generalize practical situations where node labels are unambiguous; this ensures tractability of the possibility problem, even under long-distance dependencies, provided event conjunctions are disallowed. Our results entirely classify the tractability boundary over all considered problem variants.

Type de document :
Communication dans un congrès
Alberto Mendelzon International Workshop on Foundations of Data Management, Jun 2014, Carthagène des Indes, Colombia. 2014
Liste complète des métadonnées

https://hal-imt.archives-ouvertes.fr/hal-01190712
Contributeur : Admin Télécom Paristech <>
Soumis le : mardi 1 septembre 2015 - 14:35:31
Dernière modification le : jeudi 11 janvier 2018 - 06:23:39

Identifiants

  • HAL Id : hal-01190712, version 1

Citation

Antoine Amarilli. The Possibility Problem for Probabilistic XML. Alberto Mendelzon International Workshop on Foundations of Data Management, Jun 2014, Carthagène des Indes, Colombia. 2014. 〈hal-01190712〉

Partager

Métriques

Consultations de la notice

35