Interrogation des bases de données XML probabilistes / Asma Souihli ; sous la direction de Pierre Senellart et de Talel Abdessalem

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : anglais / English

Langue / Language : français / French

Catalogue Worldcat

Recherche de l'information

Statistique

Monte-Carlo, Méthode de

Senellart, Pierre (1981-....) (Directeur de thèse / thesis advisor)

Abdessalem, Talel (19..-....) (Directeur de thèse / thesis advisor)

Rigaux, Philippe (1963-....) (Président du jury de soutenance / praeses)

Bonifati, Angela (Rapporteur de la thèse / thesis reporter)

Miklau, Gerome (19..-....) (Rapporteur de la thèse / thesis reporter)

Serhrouchni, Ahmed (Membre du jury / opponent)

Akbarinia, Reza (1977-...) (Membre du jury / opponent)

Télécom Paris (Palaiseau) (Organisme de soutenance / degree-grantor)

École doctorale Informatique, télécommunications et électronique de Paris (Ecole doctorale associée à la thèse / doctoral school)

Résumé / Abstract : XML probabiliste est un modèle probabiliste pour les bases de données incertaines semi-structurées, avec des applications telles que l'intégration incertaine de données, l'extraction d'informations ou le contrôle probabiliste de versions. Nous explorons dans cette thèse une solution efficace pour l'évaluation des requêtes tree-pattern avec jointures sur ces documents, ou, plus précisément, pour l'approximation de la probabilité d'une requête booléenne sur un document probabiliste. L'approche repose sur, d'une part, la production de la provenance probabiliste de la requête posée, et, d'autre part, la recherche d'une stratégie optimale pour estimer la probabilité de cette provenance. Cette deuxième partie s'inspire des approches des optimiseurs de requêtes: l'exploration de différents plans d'évaluation pour différentes parties de la formule et l'estimation du coût de chaque plan, suivant un modèle de coût établi pour les algorithmes de calcul utilisés. Nous démontrons l'efficacité de cette approche sur des jeux de données utilisés dans des travaux précédents sur l'interrogation des bases de données XML probabilistes, ainsi que sur des données synthétiques.

Résumé / Abstract : Probabilistic XML is a probabilistic model for uncertain tree-structured data, with applications to data integration, information extraction, or uncertain version control. We explore in this dissertation efficient algorithms for evaluating tree-pattern queries with joins over probabilistic XML or, more specifically, for approximating the probability of each item of a query result. The approach relies on, first, extracting the query lineage over the probabilistic XML document, and, second, looking for an optimal strategy to approximate the probability of the propositional lineage formula. ProApproX is the probabilistic query manager for probabilistic XML presented in this thesis. The system allows users to query uncertain tree-structured data in the form of probabilistic XML documents. It integrates a query engine that searches for an optimal strategy to evaluate the probability of the query lineage. ProApproX relies on a query-optimizer--like approach: exploring different evaluation plans for different parts of the formula and predicting the cost of each plan, using a cost model for the various evaluation algorithms. We demonstrate the efficiency of this approach on datasets used in a number of most popular previous probabilistic XML querying works, as well as on synthetic data. An early version of the system was demonstrated at the ACM SIGMOD 2011 conference. First steps towards the new query solution were discussed in an EDBT/ICDT PhD Workshop paper (2011). A fully redesigned version that implements the techniques and studies shared in the present thesis, is published as a demonstration at CIKM 2012. Our contributions are also part of an IEEE ICDE