Structurally Tractable Uncertain Data

Abstract :

Many data management applications must deal with data which is uncertain, incomplete, or noisy. However, on existing uncertain data representations, we cannot tractably perform the important query evaluation tasks of determining query possibility, certainty, or probability: these problems are hard on arbitrary uncertain input instances. We thus ask whether we could restrict the structure of uncertain data so as to guarantee the tractability of exact query evaluation. We present our tractability results for tree and tree-like uncertain data, and a vision for probabilistic rule reasoning. We also study uncertainty about order, proposing a suitable representation, and study uncertain data conditioned by additional observations.

Type de document :
Communication dans un congrès
SIGMOD/PODS Ph.D. Symposium, Jun 2015, Melbourne, Australia. pp.39-44, 2015
Liste complète des métadonnées

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

Identifiants

  • HAL Id : hal-01190610, version 1

Citation

Antoine Amarilli. Structurally Tractable Uncertain Data. SIGMOD/PODS Ph.D. Symposium, Jun 2015, Melbourne, Australia. pp.39-44, 2015. 〈hal-01190610〉

Partager

Métriques

Consultations de la notice

54