Aggregate Queries for Discrete and Continuous Probabilistic XML

Serge Abiteboul 1 T-H. Hubert Chan 2 Evgeny Kharlamov 3 Werner Nutt 3 Pierre Senellart 4
1 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : Sources of data uncertainty and imprecision are numerous. A way to handle this uncertainty is to associate probabilistic annotations to data. Many such probabilistic database models have been proposed, both in the relational and in the semi-structured setting. The latter is particularly well adapted to the management of uncertain data coming from a variety of automatic processes. An important problem, in the context of probabilistic XML databases, is that of answering aggregate queries (count, sum, avg, etc.), which has received limited attention so far. In a model unifying the various (discrete) semi-structured probabilistic models studied up to now, we present algorithms to compute the distribution of the aggregation values (exploiting some regularity proper- ties of the aggregate functions) and probabilistic moments (especially, expectation and variance) of this distribution. We also prove the intractability of some of these problems and investigate approximation techniques. We finally extend the discrete model to a continuous one, in order to take into account continuous data values, such as measurements from sensor networks, and present algorithms to compute distribution functions and moments for various classes of continuous distributions of data values.
Type de document :
Communication dans un congrès
International Conference on Database Theory (ICDT), 2010, Lausanne, Switzerland. pp.50-61, 2010
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00537632
Contributeur : Evgeny Kharlamov <>
Soumis le : vendredi 19 novembre 2010 - 10:57:47
Dernière modification le : samedi 3 mars 2018 - 15:12:04
Document(s) archivé(s) le : dimanche 20 février 2011 - 02:40:44

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00537632, version 1

Collections

Citation

Serge Abiteboul, T-H. Hubert Chan, Evgeny Kharlamov, Werner Nutt, Pierre Senellart. Aggregate Queries for Discrete and Continuous Probabilistic XML. International Conference on Database Theory (ICDT), 2010, Lausanne, Switzerland. pp.50-61, 2010. 〈inria-00537632〉

Partager

Métriques

Consultations de la notice

406

Téléchargements de fichiers

167