Gestion des documents XML temporels : état de l’art 

Télécharger le fichier pdf d’un mémoire de fin d’études

Le langage XPath

L’interrogation, la transformation et la mise à jour sont de s fonctionnalités qui requièrent de naviguer dans la structure arborescente des documents XML. XPath est le langage permettant d’as-surer cette fonctionnalité. Il a été introduit par le W3C [XPa] pour être utilisé comme sous-langage des langages d’interrogation XQuery [XQu], de transformation XSLT [XSL] ainsi que dans tous les langages manipulant des données XML.
XPath permet de sélectionner les noeuds d’un document XML sur la base de contraintes spéci-fiées par des expressions appeléeschemins. Un chemin est spécifé comme une suite d’étapes notées step et séparées par des « / » [/]step1/step2/ . . . /stepn
Un chemin commence parfois par le symbole « / » indiquant qu’il s’évalue par rapport au noeud du document (document node). Dans ce cas, le chemin est dit absolu. Rappelons ici que, dans notre modèle de données dit simplifié, nous avons fait abstraction du ‘document node’. Donc pour cette présentation, l’évaluation d’un chemin absolu est décalée au niveau de la racine de l’arbre des éléments (data tree). Cela a pour conséquence une écritureégèrementl différente des chemins qui pourra être observée dans nos exemples.
Il est parfois utile qu’un chemin puisse s’évaluer relativement à un noeud du document autre que le document node. Dans ce cas, on parle de chemins relatifs. Dans tous les cas, l’évaluation d’un chemin s’effectue à partir d’un ensemble de noeuds sources (appelé aussi contexte dans la littérature), et produit un ensemble de noeudscibles obtenus en évaluant successivement toutes les étapes composant le chemin.
Comme nous venons de le mentionner, les étapes constituent esl composants de base d’un chemin. Leur forme générale est : step = Axis::T est[cond]
Les deux principaux composants d’une étapestep sont l’axe de navigation Axis qui spécifie la direction de navigation et le filtre T est qui sert à restreindre les noeuds sur la base de leur type (noeuds éléments, noeuds textes, …) ou de leur étiquetteComme. il est parfois utile d’exprimer des conditions sur la valeur ou la structure des noeuds qu’une étape doit sélectionner, XPath permet l’utilisation de prédicats notéscond exprimant ces conditions.
Nous allons maintenant détailler chacun des trois composants d’une étape.
Les axes Comme précédemment évoqué, l’axe spécifie la direction empruntée par la navigation dans le document interrogé. Etant donnée la structure arborescente des documents XML, on peut considérer deux sortes de navigation : en profondeur et en largeur. Les axes permettant une naviga-tion en profondeur sont appelés axesverticaux. Parmi ces axes, certains peuvent naviguer niveau par niveau dans l’arbre tels que l’axe child et l’axe parent ou en traversant plusieurs niveaux tels que l’axe descendant (desc) et l’axe ancestor (ancs). La signification de ces axes est assez simple : l’axe child, respectivement parent sélectionne les noeuds fils, respectivement le noeud parent du noeud source. L’axe desc, respectivement ancs sélectionne les noeuds descendants, respecti-vement les noeuds ancêtres du noeud source. Les axes permettant une navigation en largeur sont appelés axeshorizontaux. Les plus simples sont following-sibling et preceding-sibling qui permettent d’atteindre les noeuds frères à droite (respectivement à gauche) du noeud source. Les autres axes horizontaux preceding et following permettent d’atteindre tous les noeuds « pré-cédents » (respectivement « suivants ») du noeud source suivant le document-order en excluant ses descendants et ses ancêtres. La Figure 2.6 illustre les noeuds sélectionnés par les axespreceding et following pour un noeud source donné.
Les filtres Une fois les noeuds sélectionnés au moyen des axes de navigation, le filtre est utilisé pour spécifier quels noeuds retenir en fonction de leur type ou de leur étiquette. Les filtres utilisés sont :
– node() qui permet de sélectionner à la fois les éléments et les textes,
– text() qui permet de sélectionner uniquement les textes et
– etiq qui spécifie l’étiquette que doivent avoir les noeuds retournés.
Les conditions Les axes et les tests se limitent à sélectionner des noeuds sur la base d’informa-tion structurelle. Il est parfois utile de sélectionner desnoeuds sur la base de leur contenu ce qui nécessite de pouvoir exprimer des conditions au niveau des étapes. Ces conditions peuvent être soit structurelles, auquel cas elles sont exprimées au moyen de chemins, soit faire appel à des fonc-tions pré-définies dans le but de faire un traitement particulier (concaténation des noeuds textes par exemple).
Avant d’entamer la définition de la syntaxe du langage de chemins que nous considérons, il est important de souligner que plusieurs fragments de XPath ont été étudiés dans la littérature [MdR05], [GKPS05] et [BK08]. Ces fragments sont définis sur des critères d’expressivité et de complexité. Le fragment Core XPath proposé par [GKP02] capture les fonctionnalités de base de XPath. Il permet d’exprimer des chemins avec des conditions. Ces conditions se limitent toutefois à des conjonctions et des disjonctions d’expressions. Ce fragment exclut l’utilisation des fonctions pré-définies et la comparaison des textes. Le fragment Conditional XPath proposé par [Mar05] étend le fragment Core XPath en permettant d’exprimer des chemins dits itératifs qui n’existent pas dans le langage XPath tel que défini par le W3C.

Syntaxe de XPath

Nous présentons à présent la syntaxe du langage de chemins. Comme notre étude s’appuie sur la technique de projection développée dans [BCCN06], nous utilisons un langage de chemins équivalent à celui défini dans [BCCN06]. La particularité dece langage est qu’il ne permet pas d’exprimer de conditions imbriquées. Ceci requiert d’avoir une syntaxe à deux niveaux :
– un niveau pour définir les chemins simples utilisés par les conditions et dans lesquels il est interdit d’imbriquer des conditions, et
– un autre niveau pour définir les chemins avec conditions.
La syntaxe du langage de chemins que nous considérons est donnée en Figure 2.7.
Les chemins (avec condition) sont générés par le non-terminal P . Il est composé d’un nombre arbitraire d’étapesST EP pouvant contenir une condition cond. Une condition cond est construite soit par conjonction (∧) soit par disjonction (∨) de conditions. Elle peut être aussi une expression de comparaison Exp construite à partir d’expressions de comparaison en utilis ant les opérateurs de comparaison = = ou d’expressions arithmétiques Arit elles mêmes construites à partir d’un litéralst qui consiste en une constante de type String, d’un chemin simple p (qui peut être absolu) ou d’une fonction f ayant pour argument une ou plusieurs expressions de comparaisons. Il existe plusieurs sortes de fonctions dans XPath. Les plus utilisée restent les fonctions d’agrégat telles que count(exp) ou sum(exp) et les fonctions de positions first() last() et position(). Notons que dans XPath l’opérateur de négation est exprimée à l’aided’une fonction not(exp).
Les chemins simples sont générés avec le non-terminalp et peuvent contenir un nombre arbi-traire d’étapes. Une étape est générée par le non-terminalstep, elle est composée d’un axeAxis et d’un test Test. Noter que cette syntaxe permet de générer des chemins simples relatifs et absolus à la fois. Ceci répond au besoin d’exprimer dans les conditions les deux types de chemins.
Dans la suite de manuscrit, nous ne considérons pas les fonctions sauf la négation.
Exemple 7. Considérons les chemins suivants :
– P1 = self :: Solar child :: planet,
– P2 = self :: Solar desc :: name,
– P3 = self :: Solar child :: planet[child :: note], et
– P4 = self :: Solar child :: planet[child :: name = ”Uranus”] satellite.
Les chemins P1 et P2 ne contiennent pas de conditions : ce sont des chemins simples. L’évalua-tion du chemin P1 (à partir du noeud racine du document) retourne simplement l es noeuds planet qui sont fils du noeud Solar. Avec la même convention, le cheminP2 retourne les noeuds name qui sont descendants du noeud Solar. Les chemins P3 et P4 sont des chemins avec conditions. Le chemin P3 a pour préfixe P1 et sélectionne parmi les noeuds retournés parP1 ceux qui pos-sèdent un noeud fils étiqueténote. Cette condition est simplement exprimée par le chemin relatif child :: note. Le chemin P4 sélectionne d’abord les noeudsplanet dont le noeud fils name a pour valeur ”Uranus” puis retourne leurs noeuds fils satellite.
Dans la suite de ce manuscrit, nous utilisons les abbréviations suivantes :
– T est pour child :: T est, et
–Test pour desc-or-self :: node() child :: T est.

Sémantique

La sémantique de XPath a été définie par le W3C dans [XS] et dansplusieurs travaux de recherche tels que [GKP02] et [BK08]. La définition que nous avons choisie pour la sémantique s’inspire fortement de celle définie par [BK08].
La sémantique des chemins, utilise le jugement principal suivant :
step
σ S|=P ⇒ R (Jug−Path)
Ce jugement entend spécifier qu’étant donné un storeσ, l’évaluation d’un cheminP , à partir d’un id-set source S, retourne un id-set cible R contenant les réponses de l’évaluation deP sur σ.
Afin de traiter les conditions exprimées dans les chemins, la spécification du jugement Jug-Path utilise le jugement intermédiaire ci-dessous :
cond ′
σ S|=cond ⇒ S (Jug − Cond)
Ce jugement entend spécifier qu’étant donné un storeσ, l’évaluation de la conditioncond, à partir d’un id-set source S, retourne un id-set cible S′ correspondant aux noeuds de S qui satisfont la condition cond.
Nous sommes maintenant prêts pour présenter les règles d’inférence spécifiant les jugements Jug-Path et Jug-Cond. Ces règles sont données dans la Figure 2.8. Elles sont bien videmmenté regroupées en suivant la définition syntaxique des chemins.Chaque groupe de règles est commenté en ne ciblant que les aspects spécifiques.
Les trois premières règles constituent le point d’entrée. Les règles restantes spécifient l’évalua-tion des conditions structurelles, les seules à pouvoir être exprimées par notre fragment.
La règle (Path) spécifie que l’évaluation d’un chemin passe par l’évaluation successive de cha-cune de ses étapes. Cette règle s’applique aussi bien aux chemins simples (générés par le symbole p de notre syntaxe) qu’aux chemins pouvant exprimer des conditions (ceux qui sont générés par le symbole P ).
La règle (Step:simple) spécifie l’évaluation d’une étape simple ne contenant pas decondition. Cette évaluation consiste à pré-sélectionner les noeuds qui sont atteints à partir des noeuds de l’ensemble source S suivant l’axe Axis puis à filtrer ces noeuds en utilisant T est.
La règle (Step:cond) spécifie l’évaluation d’une étape composée. Cette évaluation consiste à pré-sélectionner les noeuds accédés parstep puis à vérifier pour chacun d’eux la condition cond.
Les règles spécifiant l’évaluation des conditions sont présentées dans le deuxième encadré de la Figure 2.8. Cette évaluation s’effectue à partir d’un id-set source S et retourne un sous-ensemble de noeuds de S qui vérifient cond.
La règle (Cond:conj) spécifie l’évaluation d’une conjonction de conditions. Cete évaluation est triviale : l’une des deux conditions est évaluée puis la seconde condition est utilisée pour restreindre le résultat de la première.
La règle (Cond:disj) spécifie l’évaluation d’une disjonction de conditions. Dans ce cas, les ré-ponses sont les noeuds qui vérifient l’une des deux conditions.
Le règle (Cond:Neg) capture l’évaluation de la négation d’une condition. Cetteévaluation est triviale, elle retourne les noeuds de S qui ne satisfont pas cond.
La règle(Cond:Exp) capture l’évaluation d’une condition spécifiée par une expression comparai-son. Le résultat de cette évaluation est l’id-setS restreint aux noeuds pour lesquels la comparaison est vérifiée. L’évaluation des expressions est assurée para lfonction Eval() que nous ne spécifions pas ici.
La règle (Cond:rel−path) spécifie l’évaluation d’une condition réduite à un chemin relatif p. Le résultat de cette évaluation est la restriction deS aux noeuds à partir desquels l’évaluation de p est non vide.
Exemple 8. Soit t le document de la Figure 2.3.
Soit le chemin P5 = self :: Solar planet node()[bold] qui retourne les noeuds fils de planet ayant un fils bold.
L’évaluation deP5 sur t retourne {i8} puisque :
− PEval(t self :: Solar planet node()) = {i6 i7 i8}, et
− PEval{i6 }(t bold)=PEval{i7 }(t bold) = ∅ alors que PEval{i8 }(t bold) = {i12}.
Les règles (Cond:abs−path) et (Cond:abs−path−empty) spécifient l’évaluation d’une condition réduite à un chemin absolu p . Cette évaluation est triviale : l’id-setS est retourné si l’évaluation de p à partir de la racine de σ est non vide. Dans le cas contraire, l’évaluation de la condition retourne l’ensemble vide.

Le langage de requêtes XQuery

Le langage de chemins que nous venons d’introduire est insuffisant pour assurer les fonctio-nalités d’interrogation des documents XML. Il se limite à sélectionner des noeuds sur la base de conditions relativement simples alors que l’interrogation requiert de spécifier des conditions com-plexes et de pouvoir éventuellement construire de nouveauxéléments. C’est la raison pour laquelle l’interrogation des documents XML est assurée par le langage XQuery proposé par le W3C [XQu]. XQuery est un langage fonctionnel qui s’appuie sur XPath pour naviguer dans le document interrogé et sur des expressions pré-définies pour spécifierdes traitements complexes. Les expres-sions FLWOR (For, Let, Where, Order by et Return) sont les plus utiliséesdans XQuery. La forme générale des requêtes XQuery est donnée ci-dessous.

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
I 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
II Mises à jour de documents XML temporels 
5 Gestion des documents XML temporels : état de l’art 
5.1 Données relationnelles temporelles
5.2 Données semi-structurées temporelles
5.3 Données XML temporelles
5.3.1 Approches basées sur les deltas
5.3.2 Approches basées sur les documents estampillés
5.4 Conclusion
6 Gestion des documents XML temporels 
6.1 Modèles XML temporels
6.1.1 Ordre de compacité
6.2 Construction d’encodages compacts
6.2.1 Encodage de documents abstraits : cas général
6.2.2 Encodage d’un historique
6.3 Implantation et validation expérimentale
6.3.1 Implantation
6.4 Conclusion et perspectives
A Extraction des paths pour les requêtes
B Correction de l’inférence des paths
B.1 Preuve du Lemme 4
B.1.1 Démonstration du Lemme 4-bis
B.2 Preuve du Théorème 3
C Correction du tri-projecteur
Bibliographie

Télécharger le rapport complet