On the Complexity of Managing Probabilistic XML Data

Pierre Senellart 1 Serge Abiteboul 1
1 GEMO - Integration of data and knowledge distributed over the web
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : In [3], we introduced a framework for querying and updating probabilistic information over unordered labeled trees, the probabilistic tree model. The data model is based on trees where nodes are annotated with conjunctions of probabilistic event variables. We briefly described an implementation and scenarios of usage. We develop here a mathematical foundation for this model. In particular, we present complexity results. We identify a very large class of queries for which simple variations of querying and updating algorithms from [3] compute the correct answer. A main contribution is a full complexity analysis of queries and updates. We also exhibit a decision procedure for the equivalence of probabilistic trees and prove it is in co-RP. Furthermore, we study the issue of removing less probable possible worlds, and that of validating a probabilistic tree against a DTD. We show that these two problems are intractable in the most general case.
Type de document :
Communication dans un congrès
Principles Of Database Systems, Jun 2007, Beijing/China, 2007
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00137138
Contributeur : Pierre Senellart <>
Soumis le : mercredi 21 mars 2007 - 20:54:23
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : mardi 21 septembre 2010 - 12:16:19

Fichier

pods102-senellart.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00137138, version 2

Collections

Citation

Pierre Senellart, Serge Abiteboul. On the Complexity of Managing Probabilistic XML Data. Principles Of Database Systems, Jun 2007, Beijing/China, 2007. 〈inria-00137138v2〉

Partager

Métriques

Consultations de la notice

194

Téléchargements de fichiers

64