Query rewriting using views : a theoretical and practical perspective

Résumé : Dans ce document, nous adressons le problème de la réécriture de requêtes avec des vues, en adoptant une perspective à la fois théorique et pratique. Dans le premier et principal chapitre, nous approchons le sujet de la recherche de toutes les reformulations minimales (sans atomes relationnels redondants) pour une requête relationnelle conjonctive, sous des contraintes d’intégrité qui incluent la relation entre les schémas source et cible. Nous présentons un nouvel algorithme, correct et complet, le Provenance-Aware Chase & Backchase, qui résout le problème des reformulations avec des performances significatives sur le plan pratique. Nous présentons sa caractérisation théorique détaillée, son implémentation optimisée et son évaluation, montrant des gains de performance jusqu’à deux ordres de grandeur par rapport à un SGBD commercial. Nous généralisons notre algorithme pour trouver directement des reformulations de coût minimum pour les fonctions de coût monotones, et montrons les gains de performance de cette adaptation. Avec notre algorithme, nous introduisons également un nouveau type de chase, la Provenance-Aware Chase, qui comporte son propre intérêt théorique, en tant que moyen de raisonnement sur l’interaction entre la provenance et les contraintes. Dans le deuxième chapitre, nous nous plaçons dans un contexte XML et nous revisitons le travail de Cautis, Deutsch and Onose sur problème de la réécriture de requêtes XPath par un seul niveau d’intersection de plusieurs vues. Nous étendons l’analyse de ce probleme en montrant ses connexions avec les problèmes de l’équivalence DAG-arbre et de la union-freeness d’un DAG. Nous raffinons un algorithme de réécriture proposé par Cautis, Deutsch and Onose pour obtenir une complexité polynomiale et améliorer sa complétude, et présentons un ensemble d’optimisations des procedures de réécriture, necessaires pour atteindre des performances pratiques. Nous fournissons une implementation complète comprenant ces optimizations ainsi que son evaluation experimentale extensive, montrant la performance et l’utilité de la technique polynomiale de réécriture.
Type de document :
Thèse
Databases [cs.DB]. Télécom ParisTech, 2014. English. 〈NNT : 2014ENST0062〉
Liste complète des métadonnées

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

https://pastel.archives-ouvertes.fr/tel-01661323
Contributeur : Abes Star <>
Soumis le : lundi 11 décembre 2017 - 22:53:30
Dernière modification le : jeudi 11 janvier 2018 - 06:23:39

Fichier

TheseIleana2.pdf
Version validée par le jury (STAR)

Identifiants

  • HAL Id : tel-01661323, version 1

Citation

Ioana Ileana. Query rewriting using views : a theoretical and practical perspective. Databases [cs.DB]. Télécom ParisTech, 2014. English. 〈NNT : 2014ENST0062〉. 〈tel-01661323〉

Partager

Métriques

Consultations de la notice

113

Téléchargements de fichiers

61