Optimisation des approximations de probabilité des requêtes en XML probabiliste
Résumé
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 ce travail une solution efficace pour l’évaluation des requêtes tree-pattern avec jointures sur ces documents, ou, plus préciséent, 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 éabli 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.