Soutenance mémoire
L’essor du web a révolutionné la façon d’accéder et de traiter les données à de multiples niveaux. Nombreuses sont les applications qui s’appuient sur le web pour l’échange et le partage de données, tant le nombre d’utilisateurs et la complexité de leurs besoins ne cessent de croître. Les données semi-structurées et en particulier le standard XML introduit par le W3C, ont contribué dans une large mesure à cette évolution en offrant un format de données compréhensible par un large panel d’utilisateurs et fournissant une panoplie de mécanismes facilitant l’accès et l’échange de données.
Le développement du standard XML s’est accompagné de la mise en place d’une famille de langages tels que XPath [XPa], XQuery [XQu] et XSLT [XSL] permettant de naviguer, d’interroger et de transformer des documents XML. La communauté scientifique a mené de nombreux travaux autour de ces langages pour en étudier l’expressivité, la complexité, pour proposer des techniques d’optimisation dans des contextes différents : intégration de données, sécurité, …
Le stockage et l’interrogation des données XML sont des aspects importants qui ont suscité le développement de plusieurs systèmes de gestion de données XML. Les premiers systèmes développés reposent sur un stockage en mémoire secondaire et bénéficient des techniques d’optimisation développées pour les SGBD relationnels. L’exemple le plus connu de tels systèmes est sans doute Monet-db [BGvK+06]. L’avantage de ces systèmes est qu’ils permettent un chargement sélectif des données en fonction des besoins des requêtes à évaluer ce qui leur permet de manipuler des documents quasiment sans limite de taille. Toutefois, ces systèmes nécessitent un effort considérable d’administration et de déploiement. Leur utilisation reste réservée à un cadre spécifique tel que l’analyse et le traitement intensifs de données XML.
La plupart des applications manipulant les données XML ne nécessitent pas les fonctionnalités avancées des systèmes précédemment cités. Afin de répondre aux besoins de ces applications, plusieurs systèmes légers connus sous le nom de moteurs mémoire-centrale ont été développés. Ces moteurs sont compatibles avec les principaux standards XML tels que XQuery et XQuery update et permettent le traitement des documents XML directement en mémoire centrale. Intuitivement, ces systèmes sont limités quant à la taille des documents pouvant être traités.
La projection pour l’optimisation des mises à jour XML
La projection XML est une technique d’optimisation proposée dans le but de surmonter les limitations des moteurs mémoire-centrale pour l’interrogation des documents XML. Cette technique repose sur une observation simple selon laquelle les requêtes sont en général sélectives càd qu’elles ciblent seulement une sous partie des documents interrogés. L’idée consiste alors à identifier de manière statique les parties nécessaires à l’évaluation des requêtes et à utiliser cette information pour ne charger en mémoire centrale que les parties du document qui sont accédées par la requête. La projection permet ainsi de traiter des documents volumineux même sous des contraintes de mémoire importantes.
La projection a été utilisée pour la première fois dans [MS03] puis étendue dans [BCCN06] en prenant en compte le schéma du document interrogé. L’utilisation des schémas permet de réduire la taille de la projection en exploitant la possibilité d’inférer de manière précise les données nécessaires à l’évaluation d’une requête. Dans la technique de [BCCN06], l’information inférée consiste en l’ensemble des étiquettes des noeuds nécessaires à l’évaluation des requêtes. Cet ensemble est appelé type-porjecteur.
Bien qu’étudiée de manière approfondie dans le cadre des requêtes XML [MS03, BCL+05, BCCN06], la projection n’a jamais été considérée dans le cadre des mises à jour XML. D’autre part, les techniques développées pour les requêtes ne peuvent pas être réutilisées de manière directe pour les mises à jour.
La technique que nous proposons pour les mises à jour s’appuie sur l’utilisation des schémas pour inférer des projecteurs pour les mises à jour. Le scénario de notre technique introduit une étape supplémentaire permettant de propager les effets des mises à jour sur le document original. Le projecteur inféré pour les mises à jour est conçu dans un souci de précision (réduire le plus possible la taille des documents projetés) et d’efficacité (permettre d’exécuter rapidement la projection d’un document). Outre le fait de permettre le traitement de documents volumineux, cette technique possède deux autres avantages, celui de ne pas avoir à réécrire les mises à jour et celui de pouvoir utiliser les moteurs mémoire-centrale tels quels, sans aucune modification.
Gestion des documents XML temporels
L’objectif du travail réalisé dans cette partie est de proposer deux techniques permettant de construire et de maintenir des documents XML temporels. L’objectif est d’abord de traiter des documents volumineux puisque les documents temporels ont une taille plus importante que la taille les documents statiques. Le deuxième objectif est de générer des documents temporels compacts.
La première technique s’applique dans le cas général pour lequel aucune information n’est utilisée pour construire le document temporel. Cette technique est conçue de sorte à pouvoir être réalisée en streaming en utilisant le parcours SAX [saxa]. Ceci lui permet de traiter des documents volumineux mais l’empêche, dans certains cas, de générer des documents aussi compacts que possible. Ceci s’explique parfaitement par le fait que cette technique n’utilise aucune information sur le changement des données et qu’elle procède en streaming.
La deuxième technique s’applique dans un cas particulier où les changements sont spécifiés par des mises à jour. Dans ce cas les mises à jour sont utilisées pour la construction des documents temporels en utilisant le paradigme de projection. Ceci lui permet de manipuler des documents volumineux et de générer des documents compacts de surcroît. L’avantage de cette technique est qu’elle ne nécessite pas de modifier les moteurs XML pour mettre à jour les documents temporels ni ne requiert de réécrire les mises à jour en des mises à jour temporelles.
La comparaison des documents temporels relativement à leur efficacité de stockage est étudiée. Les expérimentations modestes menées sur les deux techniques permettent de confirmer le fait que sous certaines hypothèses, la deuxième technique produit des documents plus compacts que le première.
|
Table des matières
1 Introduction
1.1 La projection pour l’optimisation des mises à jour XML
1.2 Gestion des documents XML temporels
1.3 Organisation du manuscrit
2 Préliminaires
2.1 XML : Données et schémas
2.2 Modèle de données XML
2.3 Le langage XPath
2.3.1 Syntaxe de XPath
2.3.2 Sémantique
2.4 Le langage de requêtes XQuery
2.4.1 Syntaxe du langage de requêtes
2.4.2 Sémantique
2.5 Le langage de mise à jour XQuery Update
2.5.1 Syntaxe du langage de mises à jour
2.5.2 Sémantique du langage de mises à jour
2.5.3 Autres langages de mises à jour
2.6 Conclusion
Optimisation des mises à jour XML par projection
3 Projection pour les requêtes XML : état de l’art
3.1 Introduction
3.2 Projection basée sur les chemins
3.2.1 L’extraction des chemins à partir des requêtes
3.2.2 Limites d’utilisation
3.3 Projection basée sur les schémas
3.3.1 L’inférence du projecteur pour les chemins
3.3.2 Précision de la projection basées sur les schémas
3.4 Conclusion et Bilan
4 Projection pour les mises à jour XML
4.1 Motivation
4.1.1 Scénario de l’évaluation des mises à jour par projection
4.1.2 Traitement des insertions
4.1.3 Précision du projecteur : discussion
4.1.4 Traitement des noeuds mixed-content
4.1.5 Cas particulier des noeuds textes
4.2 Le tri-projecteur
4.3 Inférence du tri-projecteur associé à une mise à jour
4.3.1 Extraction des chemins pour les mises à jour
4.3.2 Dérivation du tri-projecteur
4.4 Etape de fusion
4.5 Implantation et validation de la technique
4.5.1 Implantation
4.5.2 Expérimentations
4.6 Travaux connexes
4.7 Discussion et perspectives
4.7.1 Extension du tri-projecteur pour la prise en charge du type des mises à jour
4.7.2 Extension du tri-projecteur pour les noeuds texte
5 Conclusion
Télécharger le rapport complet
