Brevet FR2914452A1 — publié le 20081003

La présente invention se rapporte à un procédé et un dispositif d'évaluation d'au moins un prédicat d'une expression, notamment d'une expression de type XPath, sur des éléments d'un document structuré. Elle trouve une application générale dans le traitement de flux de données XML et plus précisément sur des fichiers au format XML. Le langage de balisage XML, acronyme de eXtensible Markup Language , c'est-à-dire un langage à balise extensible, est une syntaxe pour la définition de langages informatiques. Ce langage est standardisé par le comité de standardisation W3C (une description du langage peut être trouvée à l'adresse http://www.w3.org/TR/REC-xml). Le langage XML est une syntaxe permettant de définir de nouveaux langages. Ainsi, il est rendu possible de définir une pluralité de langages XML qui peuvent être traités en utilisant des outils génériques. Le langage XML définit une syntaxe particulière pour mélanger les informations structurelles et les informations de contenu. Le langage XML définit plusieurs types d'items pour décrire les informations structurelles et les informations de contenu. Selon cette syntaxe, chaque élément est défini par une balise ouvrante comportant le nom de l'élément (par exemple: ), une balise fermante comportant elle aussi le nom de l'élément (par exemple: ). Chaque élément peut contenir d'autres éléments ou des données textuelles. Un élément peut aussi être précisé par des attributs. L'attribut est un item localisé dans la balise ouvrante d'un élément et contient, outre le contenu même de l'attribut, un identifiant pour le définir (par exemple : ). La syntaxe XML permet aussi de définir des commentaires (par exemple : ) et des instructions de traitement ( Processing Instruction selon la terminologie anglo-saxonne), qui peuvent 2 préciser à une application informatique quels traitements appliquer au document XML (par exemple: ). L'ensemble des objets décrits par la syntaxe XML, à savoir les éléments, les attributs, les données textuelles, les commentaires et les instructions de traitement, est regroupé sous la désignation de noeud XML. Un document XML peut être décrit en termes d'événements, par exemple dans le cas de parseurs XML travaillant en mode de flux continu ( streaming en terminologie anglo-saxonne), c'est-à-dire représentant un document XML comme un flux de données, tels que les parseurs SAX (acronyme de Simple API for XML , pour Interface de programmation simple pour XML). Ainsi, par exemple, un élément XML sera représenté par un événement de début d'élément, un ensemble d'événements représentant ses attributs, un autre ensemble d'événements représentant son contenu et un événement de fin d'élément. Enfin, la syntaxe XML est textuelle et peut être lue ou écrite aisément par un utilisateur. Plusieurs langages XML différents peuvent contenir des éléments de même nom. Ainsi, pour pouvoir mélanger plusieurs langages XML différents, la syntaxe XML permet de définir des espaces de nommage ( Namespace selon la terminologie anglo-saxonne). De cette manière, deux éléments sont identiques s'ils ont le même nom et se trouvent dans le même espace de nommage. Un espace de nommage est défini par un identifiant uniforme de ressource aussi appelé URI ( Uniform Resource Identifier en terminologie anglo-saxonne), par exemple : http://canon.crf.fr/xml/monlangage . L'utilisation d'un espace de nommage dans un document XML est réalisée par la définition d'un préfixe qui est un raccourci vers l'identifiant uniforme de ressource de cet espace de nommage. Ce préfixe est défini au moyen d'un attribut spécifique. Par exemple, l'expression xmins:ml="http://canon.crf.fr/xml/monlangage" associe le préfixe ml à l'identifiant uniforme de ressource http://canon.crf.fr/xml/monlangage . Ensuite, l'espace de nommage d'un élément ou d'un attribut est précisé en faisant précéder le nom par le préfixe associé à l'espace de nommage suivi de deux-points : tel qu'illustré dans l'exemple suivant : . Le langage XPath (acronyme de XML Path Language ) est issu d'une spécification du consortium W3C appelée Spécification XPath 1.0 , présente à l'adresse www.w3.org/TR/xpath. Ce langage a pour objectif de définir une syntaxe adaptée à adresser des parties d'un document structuré de type XML. Ce langage a été développé initialement pour fournir une base commune à différentes applications, par exemple aux applications XSLT ( eXtensible Stylesheet Language Transformations en terminologie anglo-saxonne) et XQuery, traitant des documents de type XML. La syntaxe de ce langage utilise une syntaxe similaire à celle utilisée dans les expressions relatives à des chemins de localisation dans un système de fichiers, par exemple l'expression relative à un chemin de localisation /librairie/livre . Les chemins de localisation ( LocationPath selon la syntaxe du langage XPath) définissent un ensemble de noeuds XML et les relations entre ces noeuds. Par exemple, le chemin /a/b désigne l'ensemble des éléments b fils d'un élément a racine du document XML. Un chemin de localisation est ainsi constitué d'un ensemble d'étapes de localisation ( Steps en terminologie anglo-saxonne), chaque étape de localisation précisant une filiation, aussi appelé axe selon la syntaxe XPath ( AxisSpecifier en terminologie anglo-saxonne), d'un test de noeud ( NodeTest en terminologie anglo-saxonne) et éventuellement d'un ensemble de prédicats ( Predicate en terminologie anglo-saxonne). La relation de filiation permet de définir la relation entre le noeud sélectionné par l'étape de localisation et le(s) nceud(s) contextuel(s). Pour la première étape de localisation, le noeud contextuel est soit la racine du document, soit le noeud courant. Pour les autres étapes de localisation, les 4 noeuds contextuels sont ceux sélectionnés par l'étape de localisation précédente. Par défaut, si la relation de filiation n'est pas précisée, l'étape de localisation courante concerne les enfants directs des noeuds contextuels. D'autres relations de filiation existent permettant de naviguer facilement dans l'ensemble du document XML. Par exemple, le chemin /a/descendant::b désigne l'ensemble des éléments b descendant, directement ou non, d'un élément a racine du document XML. A l'inverse, le chemin b/ancestor::a désigne l'ensemble des éléments a ancêtre, directement ou non, d'un élément b enfant du noeud courant. Selon un autre exemple, le chemin /descendant::a/following::b désigne l'ensemble des éléments b suivant un élément a situé à une 15 quelconque profondeur dans le document. Une relation de filiation spécifique permet de désigner les attributs d'un élément. Par exemple, le chemin /a/attribute::b retourne l'attribut b de l'élément a racine du document XML. Les relations de filiation comprennent, d'une part, les relations de 20 filiation vers l'avant ou descendante ( forward axis en terminologie anglo-saxonne) qui décrivent des relations dans l'ordre du document, c'est-à-dire des relations qui vont sélectionner des noeuds apparaissant dans le document après le noeud contextuel, et, d'autre part, les relations de filiation vers l'arrière ou ascendante ( reverse axis en terminologie anglo-saxonne) qui décrivent 25 des relations inverses à l'ordre du document, c'est-à-dire des relations qui vont sélectionner des noeuds apparaissant dans le document avant le noeud contextuel. Le test de noeud permet de préciser les caractéristiques des noeuds recherchés. 30 Un exemple de test de noeud est le test sur le nom des noeuds à rechercher. Par exemple, l'expression /descendant::a retourne l'ensemble des éléments a du document. Selon un autre test de noeud, il est permis d'obtenir tous les éléments quel que soit leur nom. Par exemple, l'expression /descendant::* retourne l'ensemble des éléments du document. Selon encore un autre test de noeud, il est permis de retourner les éléments ayant un type défini. Par exemple, l'expression /descendant::comment() retourne tous 10 les noeuds du document de type commentaire. Les prédicats permettent d'imposer une ou plusieurs conditions supplémentaires pour la recherche de noeuds qui sont solutions d'une étape de localisation. Ces conditions peuvent prendre la forme d'une position. 15 Par exemple, l'expression /a/b[2] désigne le deuxième élément b fils de l'élément racine a . Elles peuvent aussi prendre la forme d'un test. Par exemple, l'expression /a/b[c] désigne l'ensemble des éléments b fils de l'élément racine a et ayant un élément fils c . 20 Les conditions peuvent aussi permettre de vérifier le contenu d'un élément ou d'un attribut. Ainsi, par exemple, l'expression /a/b[c="valeur"] désigne l'ensemble des éléments b fils de l'élément racine a ayant un élément fils c dont la valeur textuelle est valeur . De façon similaire, l'expression 25 /a/b[@c="valeur"] désigne l'ensemble des éléments b fils de l'élément racine a ayant un attribut c dont la valeur est valeur . Une étape d'un chemin de localisation peut comporter plusieurs prédicats. Ces prédicats sont appliqués successivement pour sélectionner les éléments désignés par l'étape de localisation. 30 Par exemple, l'expression /a/b[c][2] désigne le deuxième élément b , fils de l'élément racine a et ayant un élément fils c . De manière générale, l'ordre des prédicats est important. 6 Ainsi, par exemple, l'expression /a/b[2][c] est différente de l'expression précédente, et désigne le deuxième élément b , fils de l'élément racine a et vérifie en outre que cet élément a un élément fils c . En plus des chemins de localisation, la syntaxe XPath décrit un ensemble d'expressions algébriques et d'expressions de comparaison, permettant notamment l'expression de conditions dans les prédicats, ainsi qu'un ensemble de fonctions permettant par exemple d'exprimer des prédicats ou de traiter l'ensemble des noeuds désignés par un chemin de localisation. Lors de l'utilisation d'un parseur de type SAX générant des événements décrivant le document XML sur lequel est évalué une expression XPath, les prédicats doivent pouvoir être évalués quelque soient leurs combinaisons. En particulier, l'évaluation peut porter sur une pluralité de prédicats portant sur une même étape de localisation, comme par exemple dans l'expression /livre[auteur/nom="Chateaubriand"][pub>=1800][3] qui retourne le troisième livre, publié après 1800 et dont l'auteur est Chateaubriand. En outre, l'évaluation peut porter sur des prédicats imbriqués, comme par exemple dans l'expression /livre[auteur[naissance=1768][mort=1848]] qui retourne les livres dont l'auteur est né en 1768 et mort en 1848. Pour effectuer l'évaluation d'une expression XPath, en utilisant un parseur de type SAX, plusieurs méthodes ont été proposées. En effet, selon une première méthode décrite dans le document US 2004206082 de Marcus Fontoura et Vanja Josifovsld de la société IBM, il est utilisé pour résoudre des requêtes XQuery un parseur SAX. Le langage XQuery s'appuyant sur la syntaxe XPath, il est ainsi possible d'utiliser cette méthode pour résoudre des expressions XPath en utilisant un parseur de type SAX. Toutefois, cette méthode ne permet pas d'évaluer toutes les combinaisons de prédicats. En particulier, elle ne permet pas d'évaluer des prédicats de position, ni des prédicats contenant des chemins de localisation avec des axes de type suivant ( following en terminologie anglo-saxonne) ou précédent ( preceding en terminologie anglo-saxonne). 7 En outre, selon cette méthode, les prédicats sont évalués sur un élément XML au plus tard lors de l'occurrence de la balise fermante de cet élément. Or, dans certains cas, l'évaluation des prédicats sur un élément XML n'est pas possible lors de l'occurrence de la balise fermante de cet élément. Selon une autre méthode décrite dans le document US 2004068487 de Charles Barton, Philippe Charles, Deepak Goyal et Mukund Raghavachari de la société IBM, dans laquelle une expression XPath est évaluée en utilisant un parseur SAX, l'expression XPath est modifiée de telle manière que celle-ci ne comporte plus que des relations vers l'avant. Ainsi le problème de revenir en arrière dans le document est supprimé. Toutefois, une telle méthode présente plusieurs inconvénients. En effet, selon cette méthode seul un sous-ensemble du langage XPath peut être évalué. En particulier, cette méthode présente l'inconvénient d'être apte à ne traiter que des prédicats contenant des chemins de localisation XPath. Cette méthode ne s'applique donc pas aux tests de position ou de valeur, ni aux expressions arithmétiques ni aux fonctions. Compte tenu de ce qui précède, il serait par conséquent intéressant de pouvoir évaluer des prédicats dans une expression, notamment une expression XPath, en utilisant un parseur de type SAX quelque soit le type et le nombre de prédicats tout en limitant les ressources mémoires nécessaires et en s'affranchissant d'au moins certains des inconvénients mentionnés ci-dessus. La présente invention vise en premier lieu à fournir un procédé d'évaluation d'une pluralité de prédicats associés à une sous-expression d'une expression sur des items d'un document structuré, caractérisé en ce qu'il comprend : - une étape d'association d'au moins un état d'évaluation à au moins un prédicat de ladite pluralité de prédicats, - une étape d'obtention d'un événement décrivant une partie du document structuré, -une étape de mise à jour dudit au moins un état d'évaluation à partir de l'événement obtenu, 8 - une étape d'évaluation de la pluralité de prédicats en fonction dudit au moins un état d'évaluation mis à jour. L'invention prévoit d'évaluer des prédicats dans une expression, notamment une expression XPath, par exemple au moyen d'un parseur SAX. Pour ce faire, il est associé au moins un état d'évaluation aux prédicats, ce dernier est mis à jour en fonction de l'événement obtenu décrivant une partie du document et il est évalué si l'ensemble des prédicats est vérifié pour la sous-expression. Conformément à l'invention, il est permis de traiter des prédicats 10 multiples ou imbriqués et ce procédé est adapté à fonctionner sur des appareils légers. Selon une caractéristique particulière, le procédé comprend : - une étape de création d'au moins un noeud solution représentant au moins un événement décrivant une partie du document structuré, et 15 - une étape d'association dudit au moins un noeud solution à ladite sous-expression. Selon cette caractéristique, les noeuds solutions représentent un événement au sein d'une solution potentielle pour l'expression. Chaque noeud solution représente une valeur vérifiant une partie élémentaire de l'expression. 20 Une solution potentielle regroupe un ensemble de noeuds solutions en respectant la logique de l'expression. Plus particulièrement, l'étape d'association d'au moins un état d'évaluation associe un état d'évaluation à au moins un couple comprenant un prédicat et un noeud solution. 25 Selon un mode de réalisation, le procédé comprend une étape de suppression du noeud solution associé à l'état d'évaluation si cet état d'évaluation indique que le prédicat associé à cet état d'évaluation n'est pas vérifié et ne peut plus être vérifié. Selon ce mode de réalisation, le noeud solution ne pouvant être 30 solution de l'expression, celui-ci est supprimé. Ainsi, la place de stockage prise par les résultats potentiels est réduite. 9 Selon une caractéristique particulière, un prédicat de la pluralité de prédicats étant dépendant de la position du noeud solution, la position du noeud solution est calculée comme la position du noeud solution précédent incrémenté de la valeur 1 si la position du noeud solution précédent est connue et si les prédicats précédent ledit prédicat évalué sont vérifiés pour le noeud solution. Selon une autre caractéristique particulière, le procédé comprend une étape de mise à jour d'au moins un autre état d'évaluation sur la base dudit au moins un état d'évaluation mis à jour. Selon cette caractéristique, il est mis à jour les prédicats interdépendants. C'est le cas par exemple pour les prédicats portant sur la position d'un élément. Selon un mode de réalisation, ledit au moins un état d'évaluation est mémorisé dans un tableau. Selon ce mode de réalisation, un tableau mémorise l'état 15 d'évaluation de chaque prédicat pour chacun des éléments candidats afin de permettre l'évaluation de prédicats. Ainsi, la mise à jour d'un état d'évaluation d'un prédicat peut être réalisée de manière aisée. Selon une caractéristique, le procédé comprend une table de 20 comptage comprenant pour au moins un prédicat, le nombre d'événements vérifiant ledit au moins un prédicat. Selon une caractéristique particulière, le procédé comprend une étape de transmission d'un résultat si l'ensemble des prédicats est vérifié lors de l'étape d'évaluation de la pluralité de prédicats. 25 Selon une autre caractéristique particulière, un prédicat de la pluralité de prédicats étant un chemin de localisation, l'état d'évaluation prend une valeur indiquant que l'évaluation du prédicat est positive si l'événement obtenu permet à l'étape de mise à jour de compléter le chemin de localisation, 30 une valeur indiquant que l'évaluation du prédicat est négative si l'événement obtenu permet à l'étape de mise à jour de déterminer qu'un chemin de localisation ne peut être trouvé, et 10 une valeur indiquant que l'évaluation du prédicat est indéterminée dans les autres cas. Selon encore une autre caractéristique particulière, un prédicat de la pluralité de prédicats étant une expression, l'état d'évaluation prend une valeur correspondant au résultat de l'évaluation de l'expression si l'événement obtenu permet à l'étape de mise à jour de compléter l'évaluation de l'expression, et une valeur indiquant que l'évaluation du prédicat est indéterminée dans les autres cas. Ainsi, l'état d'évaluation est particulièrement bien adapté aux prédicats mis en oeuvre par l'expression traitée. L'invention vise également un dispositif d'évaluation d'une pluralité de prédicats associés à une sous-expression d'une expression sur des items d'un document structuré, caractérisé en ce qu'il comprend : - des moyens d'association d'au moins un état d'évaluation à au moins un prédicat de ladite pluralité de prédicats, - des moyens d'obtention d'un événement décrivant une partie du document structuré, - des moyens de mise à jour dudit au moins un état d'évaluation à partir de l'événement obtenu, - des moyens d'évaluation de la pluralité de prédicats en fonction dudit au moins un état d'évaluation mis à jour. Ce dispositif présente les mêmes avantages que le procédé brièvement décrit ci-dessus et ils ne seront donc pas rappelés ici. La présente invention vise aussi un moyen de stockage d'informations, éventuellement amovible partiellement ou totalement, lisible par un ordinateur ou un microprocesseur conservant des instructions d'un programme d'ordinateur, permettant la mise en oeuvre du procédé tel qu'exposé ci-dessus. La présente invention vise enfin un produit programme d'ordinateur pouvant être chargé dans un appareil programmable, comportant des séquences d'instructions pour mettre en oeuvre le procédé tel qu'exposé ci- 11 dessus, lorsque ce programme est chargé et exécuté par l'appareil programmable. Selon d'autres aspects, l'invention concerne aussi des programmes d'ordinateur pour une mise en oeuvre du procédé de l'invention décrit brièvement ci-dessus. D'autres aspects et avantages de la présente invention apparaîtront plus clairement à la lecture de la description qui va suivre, cette description étant donnée uniquement à titre d'exemple non limitatif et faite en référence aux dessins annexés, dans lesquels : - la Figure 1 représente un exemple d'expression XPath qui est à évaluer conformément à l'invention ; - la Figure 2 illustre l'ensemble des noeuds cibles générés par l'invention à partir de l'expression XPath de la Figure 1 ; - la Figure 3 illustre une représentation logique de l'expression 15 XPath de la Figure 1 conformément à l'invention ; - la Figure 4 illustre un tableau représentant l'état d'évaluation des prédicats conformément à l'invention ; - la Figure 5 illustre un exemple de document XML sur lequel est appliqué l'expression XPath de la Figure 1 ; 20 - la Figure 6 illustre un organigramme général d'évaluation des prédicats d'une expression conformément à l'invention ; - la Figure 7 représente un algorithme de création d'un nouveau noeud solution conformément à l'invention ; - la Figure 8 représente un algorithme de suppression d'un noeud 25 solution conformément à l'invention ; - la Figure 9 représente un algorithme de mise à jour du tableau d'évaluation des prédicats conformément à l'invention ; - la Figure 10 illustre un algorithme de vérification des prédicats pour un noeud solution conformément à l'invention ; 30 - la Figure 11 illustre un algorithme de vérification d'un prédicat p pour un noeud solution ns conformément à l'invention ; et - la Figure 12 illustre une architecture matérielle sur laquelle peut être mis en oeuvre l'invention. L'invention consiste à évaluer des prédicats dans une expression, notamment dans une expression de type XPath en utilisant un parseur, par exemple un parseur de type SAX. Pour ce faire, l'évaluation des prédicats est réalisée en créant un tableau représentant l'état d'évaluation de chaque prédicat pour chacun des éléments candidats. Puis, au fur et à mesure du parcours du document XML, le tableau d'évaluation des prédicats est mis à jour en ajoutant des lignes pour les nouveaux éléments candidats et en modifiant les résultats d'évaluation des prédicats. Le regroupement de l'ensemble des états d'évaluation pour les différents éléments candidats permet d'améliorer leur évaluation si ces évaluations sont interdépendantes, notamment dans le cas de prédicats portant sur la position d'un élément. L'expression 10 en Figure 1 illustre un exemple d'expression XPath apte à être traitée selon l'invention. Selon cette expression, on recherche, parmi les éléments a situés à n'importe quelle profondeur dans le document, les éléments a ayant un élément fils c , et on sélectionne le deuxième élément a ayant un élément fils c . Il est décrit ci-après, le cas où les prédicats s'appliquent à une étape de localisation, comme dans l'exemple de l'expression 10 de la Figure 1. Toutefois, l'invention s'applique tout aussi bien aux autres cas d'utilisation des prédicats, comme les expressions filtrées de la norme XPath ( FilterExpression en terminologie anglo-saxonne). Ainsi l'invention peut s'appliquer à l'expression XPath suivante : (/descendant::a or /descendant::b)[c][2] qui recherche parmi les éléments a ou b situés à n'importe quelle profondeur du document, ceux qui ont un élément fils c , et parmi ces 30 derniers, sélectionne le deuxième. La Figure 2 représente l'ensemble des noeuds cibles générés conformément à l'invention à partir de l'expression XPath 10 de la Figure 1. Les noeuds cibles de la Figure 2 correspondent aux noeuds XML recherchés pour l'évaluation de l'expression XPath. Le noeud cible r (noeud cible 21) correspond à la racine du document XML, et le noeud cible a (noeud cible 22), et le noeud cible c (noeud cible 23) correspondent aux éléments recherchés dans le document XML au moyen de l'expression XPath. Les noeuds cibles sont utilisés pour filtrer les événements reçus par l'entité apte à réaliser l'évaluation d'une expression XPath sur un document XML aussi appelée processeur XPath ( XPath Processor en terminologie anglo-saxonne). Ainsi, les noeuds cibles correspondent aux tests de noeud de l'expression XPath. Pour chaque test de noeud de l'expression XPath, un noeud cible est généré. Cependant, si plusieurs noeuds cibles identiques sont générés, ils sont regroupés en un seul noeud cible. En outre, afin d'optimiser le processus de recherche des noeuds, les noeuds cibles sont organisés en fonction de leurs relations d'ordre d'apparition dans le document et telles qu'elles sont définies par les relations de filiations de l'expression XPath. De cette manière, selon l'exemple illustré en Figures 1 et 2, un élément c est recherché uniquement après avoir trouvé un élément a . Ces relations d'ordre d'apparition sont représentées sur la Figure 2 par des flèches. Le processus de recherche est optimisé davantage par une description précise des relations d'ordre d'apparition exprimées dans l'expression XPath. Ainsi, selon l'exemple illustré en Figures 1 et 2, la relation entre la cible a et la cible c est, notamment, une différence de profondeur 25 d'exactement un . La Figure 3 illustre une représentation logique de l'expression XPath 10 de la Figure 1 conformément à l'invention. Cette représentation logique permet d'évaluer l'expression XPath à partir des noeuds filtrés par les noeuds cibles générés tel que décrit en Figure 2. 30 Selon cette représentation logique, chaque sous-expression élémentaire de l'expression XPath est représentée par un noeud logique. 14 Par exemple, la sous-expression élémentaire descendant::a est représentée par un noeud logique descendant::a . Les liens entre les noeuds logiques décrivent leurs relations au sein de l'expression XPath. Durant l'évaluation d'une expression XPath, cette représentation logique permet en outre de construire les solutions de l'expression XPath. Pour cela, un noeud logique reçoit les événements filtrés par les noeuds cibles et les utilise pour construire des noeuds solutions représentant cet événement au sein d'une solution potentielle pour l'expression XPath. Chaque noeud solution représente une valeur vérifiant une partie élémentaire de l'expression XPath. La partie élémentaire de l'expression XPath vérifiée par le noeud solution correspond au noeud logique associé à ce noeud solution. Une solution potentielle regroupe un ensemble de noeuds solutions en respectant la logique de l'expression XPath. Quand une solution potentielle contient un noeud solution pour chaque noeud logique de l'expression XPath, cette solution potentielle vérifie l'intégralité de l'expression XPath et permet donc de générer une solution pour l'expression XPath. Ainsi, lorsqu'un événement a est reçu, il est détecté par le noeud cible a de la Figure 2 et transmis au noeud logique a de la Figure 3, à savoir le noeud logique descendant::a 300. A partir de cet événement a , le noeud logique 300 met à jour une solution potentielle de l'expression XPath en créant un ou plusieurs noeuds solution représentant cet événement a . En figure 4, il est illustré un exemple de tableau représentant l'état de l'évaluation des prédicats [c] et [2] de l'expression XPath 10 pour les éléments a rencontrés lors du traitement du document structuré, notamment selon le langage XML, illustré en Figure 5. Ce tableau comprend, par exemple trois colonnes, la première identifiant les noeuds solutions correspondant à des éléments a , la seconde, l'évaluation du prédicat [c] et la troisième, l'évaluation du prédicat [2] . Ainsi, pour chaque élément a du document structuré, une nouvelle ligne est ajoutée à ce tableau. Cette ligne est complétée au fur et à mesure du parcours du document XML pour permettre l'évaluation de l'ensemble des prédicats de chaque élément a . II est maintenant décrit en référence à la Figure 5 un exemple de document XML sur lequel peut être appliquée l'expression XPath 10 de la Figure 1. Selon cet exemple, le résultat de l'évaluation de l'expression XPath 10 sur le document XML de la Figure 5 est le deuxième élément a de ce document XML. Lors du traitement du document XML par le parseur SAX, des événements décrivant le document XML sont transmis au processeur XPath Ces événements permettent au processeur XPath de mettre à jour le tableau d'évaluation des prédicats illustré en Figure 4, et ainsi d'évaluer les prédicats pour les différents éléments a du document XML. Il est maintenant décrit les actions du processeur XPath qui ont pour 15 objet l'évaluation de l'expression XPath sur le document XML décrit par ces événements. Sur réception de l'événement Début du document , celui-ci est reçu par le noeud cible r 21. Ce noeud cible crée un noeud solution r pour représenter cet événement. En outre, le noeud cible a 22 est activé, 20 avec un contexte d'activation correspondant à l'ensemble du document XML. En outre, le tableau d'évaluation des prédicats de la figure 4 est créé afin de mémoriser l'état d'évaluation des prédicats pour les différents éléments a du document XML. Ensuite, lors de la réception de l'événement balise ouvrante a 25 correspondant à la balise ouvrante a de la ligne 500, cet événement est reçu par le noeud cible a . Le noeud cible c est activé avec un contexte d'activation correspondant à l'ensemble des noeuds fils de cet élément a . En outre, un noeud solution al est créé pour représenter cet événement et est associé au noeud solution r en tant que fils de ce noeud. 30 D'autre part, le tableau d'évaluation des prédicats de la Figure 4 est modifié par l'ajout d'une ligne (400) afin de mémoriser l'état de l'évaluation des deux prédicats ( [c] et [2] ) pour cet élément a . L'évaluation de ces prédicats n'étant pas réalisable immédiatement, les valeurs des cellules 401 et 402 sont initialisées à la valeur inconnu . Le document XML comprend ensuite une balise ouvrante a 505. L'événement correspondant est traité de manière similaire au précédent. Un noeud solution a2 est créé pour représenter cet événement. En outre, le contexte d'activation du noeud cible c est étendu pour comprendre l'ensemble des noeuds fils de ce deuxième élément a . D'autre part, une deuxième ligne est ajoutée dans le tableau d'évaluation des prédicats de la Figure 4 (ligne 410) afin de mémoriser l'état de l'évaluation des deux prédicats pour ce deuxième élément a . Comme pour l'élément précédent, l'évaluation des prédicats n'étant pas réalisable immédiatement, les valeurs des cellules 411 et 412 sont initialisées à la valeur inconnu . Ensuite, l'événement suivant est l'événement balise ouvrante c correspondant à l'élément vide c 510. Cet événement est reçu par le noeud cible c . Un noeud solution cl est créé pour représenter cet élément c . Ce noeud solution n'est pas relié au noeud solution al représentant le premier élément a (500), car la relation entre cet élément c et le premier élément a ne correspond pas à une relation de type fils . Par contre, ce noeud solution est relié au noeud solution a2 représentant le deuxième élément a (505). Ainsi, il est donc possible d'évaluer le prédicat [c] pour ce deuxième élément a . La valeur de la cellule 411 devient donc vrai . Par contre, il n'est pas encore possible d'évaluer le prédicat [2] pour ce deuxième élément a , car cette évaluation dépend de l'évaluation des prédicats du premier élément a . L'événement suivant est l'événement balise fermante c correspondant à l'élément vide c 510. Cet événement ne provoque aucune modification dans l'évaluation de l'expression XPath. L'événement suivant est l'événement balise fermante correspondant à la balise fermante de l'élément a 515. Cet événement est reçu par le noeud cible a . Etant donné que les prédicats restant à évaluer pour ce deuxième élément a (le prédicat [2] ) ne dépendent pas du contenu de l'élément a , la ligne 410 du tableau d'évaluation des prédicats de la figure 4 est conservée. Cela signifie que l'élément a reste un résultat possible pour l'évaluation de l'expression XPath. Toutefois, si certains prédicats restant à évaluer pour ce deuxième élément a dépendaient du contenu de l'élément a , la ligne 410 du tableau d'évaluation serait supprimée lors de cette étape : en effet, l'élément a ne serait pas un résultat possible pour l'évaluation de l'expression XPath. L'événement suivant est l'événement balise ouvrante correspondant à l'élément vide c 520. Cet événement est reçu par le noeud cible c . Un noeud solution c2 est créé pour représenter cet élément c . Ce noeud solution est relié au noeud solution al représentant le premier élément a (500). Ainsi, il est donc possible d'évaluer le prédicat [c] pour ce premier élément a . La valeur de la cellule 401 devient donc vrai . En outre, il est possible d'évaluer la position de ce premier élément a par rapport à l'ensemble des éléments a ayant un fils c . En effet, la position de ce premier élément a est la première et donc a la valeur 1. Par conséquent, l'évaluation du prédicat [2] pour ce premier élément est négative. La valeur de la cellule 402 est donc faux . Ainsi, l'ensemble des prédicats portant sur ce premier élément a n'est pas vérifié et cet élément a n'est donc pas une solution pour l'expression XPath 10. Cet élément a peut donc être supprimé du tableau d'évaluation des prédicats de la Figure 4. De plus, étant donné que l'évaluation de l'ensemble des prédicats pour le premier élément a est terminée, et qu'en particulier l'évaluation du prédicat [2] pour ce premier élément a est terminée, il est possible d'évaluer le prédicat [2] pour le deuxième élément a . Ce deuxième élément a étant le deuxième élément a du document ayant un fils c , ce prédicat est évalué positivement et la valeur de la cellule 412 est donc vrai . Ainsi, ce deuxième élément a est solution de l'expression XPath. En effet, ce deuxième élément a est bien un deuxième élément a situé selon une profondeur quelconque par rapport à un premier élément a et ayant un élément fils c . Ce deuxième élément a est donc retourné comme solution de l'expression XPath 10. En outre, la ligne 410 est supprimée du tableau d'évaluation des prédicats de la figure 4. L'événement suivant est l'événement balise fermante c correspondant à l'élément vide c 510. Cet événement ne provoque aucune modification dans l'évaluation de l'expression XPath. L'événement suivant est l'événement balise vide a 525. Cet événement est reçu par le noeud cible a . La cible c est alors désactivée. Etant donné qu'il n'y a plus de solution en attente, aucune autre action n'est réalisée. Si l'on considère dans un second exemple de document XML similaire à celui décrit en Figure 5 dans lequel la ligne 520 est absente, la succession d'action permettant de finaliser l'évaluation des prédicats est alors la suivante. L'événement signalant la balise fermante du premier élément a (525) a pour conséquence que le prédicat [c] ne peut être vérifié pour cet élément a . Ce premier élément a est donc supprimé du tableau. Par conséquent, il est devenu possible de finir l'évaluation des prédicats pour le deuxième élément a . En particulier, le prédicat [2] est alors évalué à faux pour cet élément, puisque dans ce cas, le deuxième élément a est le premier élément a du document ayant un fils c . Ce deuxième élément a est donc également supprimé du tableau. Selon cet exemple, aucun résultat n'est retourné, ce qui correspond au résultat escompté de l'évaluation de l'expression XPath. II est maintenant décrit, en référence à la Figure 6, un algorithme général d'évaluation des prédicats pour une étape de localisation XPath conformément à l'invention et adapté pour l'évaluation de prédicats quelque soit l'expression ou la sous-expression XPath. La première étape de cet algorithme (étape 600) consiste en la création d'un tableau apte à mémoriser l'évaluation des prédicats d'une étape de localisation XPath à évaluer. Ce tableau est rattaché au noeud solution représentant le contexte de l'étape de localisation pour lequel il mémorise les résultats des prédicats. Par conséquence, selon un mode de réalisation, ce tableau est créé en même temps que le noeud solution contexte. 19 Plusieurs tableaux peuvent également être créés pour une même étape de localisation. Par exemple, si l'exemple XPath est la suivante : /b/descendant::a[c][2] , un tableau d'évaluation des prédicats est créé pour chaque élément b trouvé à la profondeur 1. Selon un mode de réalisation particulier, outre ce tableau, une autre table est créée afin de mémoriser le nombre de résultats trouvés. Cette table, appelée table de comptage, a un nombre de cellules égal au nombre de prédicats augmenté de 1. En effet, la première cellule mémorise le nombre d'éléments trouvés vérifiant le test de noeud de l'étape de localisation, la deuxième cellule mémorise le nombre d'éléments trouvés vérifiant en outre le premier prédicat et ainsi de suite. Lors de la création de cette table de comptage, ses cellules sont toutes initialisées avec la valeur 0 . L'étape 600 est suivie de l'étape 610 consistant à ajouter un noeud solution pour l'étape de localisation concernée. Cette étape est réalisée à chaque fois qu'un événement correspondant à l'étape de localisation est reçu. Au cours de cette étape, la table de comptage mémorisant le nombre de solutions est également mise à jour. En outre, une nouvelle ligne est insérée dans le tableau d'évaluation des prédicats mémorisant les résultats d'évaluation des prédicats liés à ce noeud solution. Cette ligne du tableau mémorise dans la première colonne le noeud solution. Les autres cellules de la ligne sont remplies en fonction du type du prédicat. Ainsi, pour un prédicat correspondant à un chemin de localisation, la cellule est initialisée à une valeur non-trouvé . Pour un prédicat correspondant à une expression nécessitant la création d'un noeud solution, par exemple un appel de fonction ou une expression arithmétique, ce noeud solution est créé et mémorisé dans la cellule. Enfin, dans les autres cas, la cellule mémorise une valeur non-évalué . Ces autres cas correspondent à des expressions très simples pouvant être évaluées à partir du contexte, c'est notamment le cas des prédicats de position. Enfin, l'algorithme tente d'évaluer les prédicats pour ce nouveau noeud solution. Cette évaluation est possible si, par exemple, un prédicat réfère un élément précédant celui représenté par le noeud solution, ou si un prédicat contient une expression qui peut déjà être calculée. Les étapes suivantes consistent à mettre à jour l'évaluation des prédicats pour un noeud solution mémorisé dans le tableau. La première étape de la mise à jour (étape 620) consiste à recevoir un événement XML décrivant une partie du document XML sur lequel est évaluée l'expression XPath. L'étape suivante (étape 630) consiste à mettre à jour l'un des prédicats associé au noeud solution en fonction de cet événement XML reçu. Cette étape est exécutée notamment lorsque l'événement permet de poursuivre l'évaluation d'un prédicat associé au noeud solution créé précédemment. Dans le cas d'un prédicat correspondant à un chemin de localisation, la mise à jour du tableau d'évaluation des prédicats est réalisée lorsqu'un résultat est trouvé pour ce chemin de localisation. Ce résultat est utilisé ensuite pour mettre à jour la ligne du tableau d'évaluation des prédicats correspondant au noeud solution. La cellule du tableau d'évaluation des prédicats pour le prédicat et le chemin de localisation considéré prend alors la valeur trouvé . S'il n'est plus possible de trouver un résultat pour le chemin de localisation, alors la cellule du tableau pour le prédicat et le chemin de localisation considéré prend la valeur introuvable . Dans le cas d'un prédicat correspondant à une expression nécessitant la création d'un noeud solution, la mise à jour du tableau d'évaluation des prédicats se produit lorsque l'expression est évaluée. Il est à noter que dans ces deux cas, le même événement peut être utilisé pour mettre à jour les prédicats de plusieurs noeuds solutions du tableau. Avantageusement, les étapes de mise à jour peuvent être factorisées pour l'ensemble des noeuds solutions concernés. Ensuite, l'étape 640 consiste à réévaluer l'ensemble des prédicats pour le noeud solution. Cette étape permet de traiter les cas autres que les deux cas de prédicats décrits à l'étape 630. Dans ce dernier cas, la mise à jour du tableau pour le prédicat est la conséquence d'une autre mise à jour du tableau, cette autre mise à jour permettant de disposer des informations nécessaires pour évaluer ledit prédicat. Il est à noter que la mise à jour de l'évaluation d'un prédicat s'accompagne de la mise à jour du nombre de résultats trouvés. En outre, après la mise à jour de l'évaluation des prédicats pour le noeud solution, l'ensemble des prédicats pour l'ensemble des noeuds solutions mémorisés dans le tableau d'évaluation des prédicats est réévalué. Ceci permet en particulier de mettre à jour les prédicats dépendant du résultat d'évaluation d'un autre prédicat. L'étape suivante (étape 650) consiste à supprimer un noeud solution. Cette suppression peut survenir soit lorsque l'ensemble des prédicats du noeud solution sont vérifiés, soit lorsque l'un des prédicats du noeud solution est invalidé. Dans le premier cas, le noeud solution est complètement validé. II peut donc participer à la construction d'un résultat. Dans le cas où le noeud solution correspond à la dernière étape d'un chemin de localisation, c'est-à-dire que le noeud solution représente un résultat, un traitement particulier est mis en oeuvre pour retourner le résultat, notamment dans le bon ordre. Dans le second cas, le noeud solution n'est pas validé, il peut donc 20 être supprimé du tableau. II est à noter que les étapes 610, 620, 630, 640 et 650 sont généralement réalisées plusieurs fois et que l'ordre de ces étapes n'est fixé que dans leur exécution par rapport à un même noeud solution. En outre, les étapes 620, 630 et 640 sont généralement réalisées plusieurs fois pour chaque noeud 25 solution. Il est maintenant décrit, en référence à la figure 7, des traitements à effectuer lors de la création d'un nouveau noeud solution ns. L'algorithme débute à l'étape 700 par la mise à jour de la table de comptage par l'incrémentation de la première cellule de cette table. 30 L'étape suivante (étape 710) consiste à créer une nouvelle ligne dans le tableau pour représenter l'évaluation des prédicats du noeud solution ns. En outre, chacune des cellules de la ligne est initialisée en fonction du type de son prédicat associé. Pour un prédicat correspondant à un chemin de localisation, la cellule est initialisée à une valeur non-trouvé . Toutefois, si le chemin de localisation correspond à un item du document XML situé avant celui représenté par le noeud solution ns et si lors de la création du noeud solution ns, celui-ci a été associé à un ensemble de noeuds solutions constituant un résultat pour le chemin de localisation, alors la cellule est initialisée à la valeur trouvé . Par contre, si le chemin de localisation correspond à un item du document XML situé avant celui représenté par le noeud solution ns, et si aucun ensemble de noeuds solutions constituant un résultat pour ce chemin de localisation n'a été associé au noeud solution ns lors de sa création, alors la cellule est initialisée à la valeur introuvable . Dans le cas d'un prédicat correspondant à une expression nécessitant la création d'un noeud solution, ce noeud est créé (ainsi que tous les noeuds solution associés devant être créés pour évaluer l'expression) et mémorisé dans la cellule. Enfin dans les autres cas, la cellule mémorise la valeur non- évalué . L'étape suivante (étape 720) évalue une première fois les prédicats de ce noeud solution ns. Pour cela, il est fait appel à un algorithme de vérification des prédicats pour le noeud solution ns. Un tel algorithme est décrit ci-après en référence à la figure 10. Enfin (étape 730), si la vérification des prédicats a généré un ou plusieurs résultats, ceux-ci sont retournés. Suivant la position de l'étape de localisation correspondant aux noeuds solutions générés par le tableau, les résultats peuvent être utilisés de plusieurs manières selon que l'étape de localisation est située en fin ou non du chemin de localisation. Si l'étape de localisation n'est pas située en fin de chemin de localisation, un résultat permet de valider le noeud solution correspondant comme entièrement vérifié, c'est-à-dire que le test de noeud et l'ensemble des prédicats ont été vérifiés. Au contraire, si l'étape de localisation est située en fin de chemin de localisation, le résultat constitue un résultat possible pour ce chemin de localisation. Ainsi, si pour un résultat, l'ensemble du chemin est vérifié, c'est-à-dire que pour chaque étape de localisation, il existe un noeud solution entièrement vérifié, alors le résultat peut être retourné comme résultat du chemin de localisation. Dans le cas où le chemin de localisation constitue l'expression principale de l'expression XPath, le résultat de l'évaluation du prédicat est l'un des résultats de l'expression XPath. Dans le cas où le chemin de localisation constitue le contenu d'un prédicat, le résultat permet de valider ce prédicat, alors ce résultat est transmis aux noeuds solutions associés possédant ce prédicat pour mettre à jour leur tableau d'évaluation de prédicats. Dans les autres cas, le résultat est transmis au noeud solution parent du chemin de localisation pour être intégré dans l'évaluation du noeud parent. Il est à noter que pour gérer l'ordre des résultats, la transmission des résultats peut être indirecte. Dans ce but, la transmission peut être filtrée par une structure qui gère l'ensemble des résultats produits par un chemin de localisation pour un contexte donné. Lorsqu'un noeud solution correspondant à la dernière étape de localisation du chemin est créé, ce noeud résultat est ajouté à la liste gérée par la structure. Lorsqu'un noeud solution est supprimé, celui-ci est supprimé de la liste gérée par la structure. Enfin, quand un résultat est généré, le noeud solution correspondant est marqué de façon spéciale dans la structure. Si ce résultat est le premier noeud solution de la liste, il est transmis, sinon il est mis en attente. 24 A chaque fois que le premier noeud solution de la liste est transmis comme résultat ou supprimé de la liste, le noeud solution suivant est vérifié et transmis s'il était en attente. Dans le cas où le chemin de localisation correspond à une sous- expression de l'expression XPath, mais que celui-ci n'a pas de noeud solution parent, alors le résultat est mémorisé pour être utilisé ultérieurement lorsqu'un noeud solution sera associé au chemin de localisation comme parent. Il est maintenant décrit en référence à la figure 8, les traitements à effectuer lors de la suppression d'un noeud solution ns. La suppression d'un noeud solution intervient lorsque plus aucun événement dont ce noeud dépend pour son évaluation complète ne peut survenir. L'algorithme débute à l'étape 800 consistant à déterminer la ligne du tableau d'évaluation des prédicats correspondant au noeud solution ns. L'étape 800 est suivie de l'étape 810 au cours de laquelle il est vérifié si ce noeud solution est pré-validé, c'est-à-dire on vérifie si l'ensemble des événements nécessaires à l'évaluation positive des prédicats a été reçu. En effet, certains prédicats peuvent ne pas encore être aptes à être calculés à cause de l'évaluation non terminée de prédicats d'autres noeuds solutions. Dans l'exemple considéré de la figure 5, c'est notamment le cas pour l'élément a de la ligne 505. Cette vérification dépend, pour chaque prédicat, du type du prédicat. Pour un prédicat correspondant à un chemin de localisation, la cellule doit avoir la valeur trouvé . Pour un prédicat correspondant à une expression nécessitant la création d'un noeud solution, l'ensemble des chemins de localisation descendant de ce noeud solution doit avoir un résultat. En outre, ce prédicat ne doit pas être évalué négativement. Enfin, pour les autres prédicats, ceux-ci ne doivent avoir été évalués négativement. Si, lors de l'étape 810, le test vérifiant si ce noeud solution est pré-validé est négatif, alors l'algorithme se poursuit à l'étape 820 au cours de laquelle le noeud solution est supprimé et la ligne correspondante est détruite. L'étape 820 est suivie de l'étape 830 décrite ci-dessous. Si, au contraire, le test de l'étape 810 est positif, alors le noeud solution est conservé. En effet, ce noeud solution peut générer un résultat lorsque l'ensemble de ses prédicats sera évalué. II est même possible que l'ensemble des prédicats de ce noeud solution ait déjà été vérifié, mais que le résultat correspondant ait été mis en attente afin d'être retourné dans le bon ordre. Cette étape est suivie de l'étape 830. Lors de cette étape (étape 830), le noeud solution mémorisé dans la première ligne du tableau, nO (s'il existe), est vérifié. En effet, la mise à jour du noeud solution ns peut permettre d'avancer l'évaluation d'autres noeuds solutions. C'est en particulier le cas si le noeud solution ns a été supprimé du tableau. Selon une variante de réalisation, pour économiser de la mémoire, 15 l'ensemble des noeuds solutions mémorisés dans le tableau d'évaluation des prédicats peut être vérifié à nouveau. Enfin, l'algorithme se termine à l'étape 840 au cours de laquelle l'algorithme retourne un ou plusieurs résultats, s'ils existent, tel que mentionné également à l'étape 730 de la figure 7. 20 Il est maintenant décrit, en référence à la figure 9, les traitements à effectuer pour mettre à jour le tableau d'évaluation des prédicats. Cet algorithme est mis en oeuvre à chaque fois qu'une information nouvelle peut permettre de poursuivre l'évaluation des prédicats des noeuds solutions contenus dans la première colonne du tableau d'évaluation. Cet algorithme est 25 mis en oeuvre en particulier dans les cas suivants. Cet algorithme est mis en oeuvre, notamment, lors de la production d'un résultat lors de l'évaluation d'un chemin de localisation représentant un prédicat d'un noeud solution mémorisé dans le tableau. Pour ce faire, cet algorithme est appelé, avec comme paramètres, le noeud solution ns et 30 l'identification du prédicat p. D'autre part, cet algorithme est mis en oeuvre lors de la complétion de l'évaluation d'un noeud solution mémorisé dans le tableau d'évaluation des prédicats, ce noeud solution représentant un prédicat constitué par une expression. Pour ce faire, cet algorithme est appelé, avec comme paramètres, le noeud solution ns parent de ce noeud solution complètement évalué et l'identification du prédicat p correspondant. L'algorithme débute à l'étape 900 consistant à déterminer le type du prédicat p. L'étape 910 suit l'étape 900 au cours de laquelle on teste le prédicat afin de déterminer si ce prédicat correspond à un chemin de localisation. Dans le cas négatif, l'algorithme se poursuit à l'étape 930 décrite ci- après. Dans le cas positif, l'algorithme se poursuit à l'étape 920 au cours de laquelle la cellule correspondante du tableau d'évaluation des prédicats est modifiée pour prendre la valeur trouvé . L'étape 920 est suivie de l'étape 930. L'étape 930 consiste à vérifier les prédicats pour le noeud solution ns. Enfin, l'algorithme se termine, à l'étape 940, en retournant un ou plusieurs résultats, s'ils existent, tel que mentionné en référence à l'étape 730 de la figure 7. On décrit maintenant, en référence à la figure 10, les traitements à effectuer pour vérifier l'ensemble de prédicats pour un noeud solution ns. L'algorithme débute à l'étape 1000 consistant à obtenir le premier prédicat p. L'étape 1000 est suivie de l'étape 1005 au cours de laquelle on vérifie si ce prédicat p est bloqué ou non. Un prédicat est dit bloqué pour un noeud solution ns lorsque son évaluation n'est pas encore réalisée pour un noeud solution mémorisé dans une ligne précédente du tableau. En variante de réalisation, un prédicat est aussi considéré comme bloqué si pour l'un quelconque des prédicats précédent, l'étape de vérification 1010 a retourné un résultat indéterminé. Dans cette variante de réalisation, si le prédicat est bloqué, l'algorithme peut se poursuivre directement à l'étape 1090. Selon une autre variante de réalisation, un prédicat est dit bloqué uniquement si son évaluation nécessite l'évaluation de ce même prédicat pour un noeud solution mémorisé dans une ligne précédente du tableau. C'est le cas par exemple pour un prédicat portant sur la position du noeud solution. Si le prédicat est bloqué, l'algorithme se poursuit à l'étape 1020 décrite ci-après. Dans le cas contraire, l'algorithme se poursuit à l'étape 1010 au cours de laquelle on vérifie si le prédicat p est validé pour le noeud solution ns. Cette vérification, décrite ci-après en référence à la figure 11, peut retourner un résultat positif, négatif ou indéterminé. L'étape suivante (étape 1015) consiste à tester la vérification effectuée lors de l'étape 1010. Si la vérification est négative alors l'algorithme se poursuit à l'étape 1070, décrite ci-après. Au contraire, si la vérification est positive ou indéterminée, alors l'algorithme se poursuit à l'étape 1020. Au cours de cette étape (étape 1020), il est vérifié s'il reste d'autres prédicats à traiter. Si tel est le cas, alors l'algorithme se poursuit à l'étape 1030 consistant à sélectionner le prédicat suivant, puis à l'étape 1005 précédemment décrite. Dans le cas contraire, l'algorithme se poursuit à l'étape 1040 au cours de laquelle on vérifie si l'ensemble des prédicats d'un noeud solution ns a été validé, c'est-à-dire si pour chacun des prédicats, la vérification, notamment réalisée selon l'algorithme de la figure 11 décrit ci-après, a retourné un résultat positif. En outre, lors de cette étape 1040, on vérifie également que le noeud solution ns correspond à la première ligne du tableau. Cette vérification permet de retourner les résultats générés dans l'ordre. Si la vérification est négative, alors il est mis fin à l'algorithme à l'étape 1090. Au contraire, si la vérification est positive, l'algorithme se poursuit à l'étape 1045 consistant à supprimer le noeud solution ns du tableau. Ensuite, lors de l'étape suivante (étape 1050), on génère le résultatcorrespondant au noeud solution ns. L'algorithme se poursuit à l'étape 1055 consistant à appeler l'algorithme de la figure 10 récursivement pour vérifier le noeud solution situé dans la nouvelle première ligne du tableau, si ce dernier existe. Ensuite, il est mis fin à l'algorithme lors de l'étape 1090. De retour à l'étape 1015, si la vérification du prédicat p est négative, l'algorithme se poursuit à l'étape 1070 par la suppression du noeud solution ns et, notamment, en supprimant la ligne correspondant du tableau. Ensuite, lors de l'étape 1075, l'algorithme de la figure 10 est appelé récursivement afin de vérifier le noeud solution situé dans la première ligne du tableau, si ce dernier existe. Selon un mode de réalisation, en vue d'optimiser l'algorithme, la vérification de l'étape 1075 n'est réalisée que si le noeud solution supprimé se trouve dans la première ligne du tableau. L'étape 1075 est suivie de l'étape 1090 consistant à mettre fin à l'algorithme. Lors de l'étape 1090, les résultats générés, soit lors de l'étape 1050, soit lors d'un appel récursif à l'algorithme, sont retournés dans l'ordre dans lesquels ils ont été générés. Selon un mode de réalisation particulier, quand le contexte de recherche correspondant aux noeuds solutions mémorisés dans le tableau est terminé, c'est-à-dire quand l'ensemble des événements décrivant le contenu de ce contexte de recherche a été reçu, plus aucun noeud solution ne peut être ajouté au tableau. Dans ce cas, cette information est mémorisée et l'algorithme est appelé avec en paramètre le premier noeud solution contenu dans le tableau. Il est maintenant décrit, en référence à la figure 11, la vérification d'un prédicat p pour un noeud solution ns. L'algorithme débute à l'étape 1100 par la détermination du type du prédicat p. L'étape 1100 est suivie de l'étape 1110, au cours de laquelle on teste si le prédicat p est un chemin de localisation. Si tel est le cas, alors l'algorithme se poursuit à l'étape 1115 au cours de laquelle on vérifie la valeur mémorisée dans le tableau pour ce prédicat p et ce noeud solution ns. Si la valeur est non-trouvé , alors la vérification est indéterminée. Si la valeur est trouvé , alors la vérification est positive. Enfin, si la valeur est introuvable , alors la vérification est négative. L'algorithme se poursuit ensuite à l'étape 1140 décrite ci-après. Dans le cas contraire, c'est-à-dire, si le prédicat p n'est pas un chemin de localisation, alors l'algorithme se poursuit à l'étape 1120 consistant à tester si le prédicat est une expression nécessitant alors la génération d'un noeud solution. Si tel est le cas, l'algorithme se poursuit à l'étape de vérification (étape 1125) au cours de laquelle on évalue le noeud solution. Le résultat de la vérification est donc le résultat de l'évaluation. L'algorithme se poursuit ensuite à l'étape 1140 décrite ci-après. Dans le cas contraire, c'est-à-dire, si le prédicat n'est pas une expression, alors l'algorithme se poursuit à l'étape 1130 au cours de laquelle le prédicat est évalué directement, notamment, à partir des informations disponibles dans le tableau, à savoir, par exemple, le comptage du nombre de solution, la fin du contexte de recherche des noeuds solutions. L'algorithme se poursuit ensuite à l'étape 1140. L'étape 1140 consiste à tester l'état de vérification du prédicat. Si la vérification est indéterminée, alors l'algorithme se poursuit à l'étape 1150 consistant à retourner la valeur indéterminé . Si la vérification est négative, alors l'algorithme se poursuit à l'étape 1160 consistant à retourner la valeur faux . Enfin, si la vérification est positive, alors l'algorithme se poursuit à l'étape 1170 consistant à mettre à jour la table de comptage. Pour cela, l'algorithme détermine la position du prédicat dans la liste des prédicats de l'étape de localisation. Par exemple, dans l'expression XPath 10 de la Figure 1, le prédicat [Cl est en première position. La cellule à modifier pour mettre à jour la table de comptage est celle correspondant à la position du prédicat augmentée de 1. Cette cellule est modifiée en incrémentant sa valeur de 1. L'algorithme se termine alors à l'étape 1175 consistant à retourner la valeur vrai . Afin de mettre en oeuvre le procédé d'évaluation d'au moins un prédicat d'une expression sur des éléments d'un document structuré, un dispositif d'évaluation d'au moins un prédicat d'une expression sur des éléments d'un document structuré comprend notamment des moyens d'association d'au moins un état d'évaluation à au moins un prédicat de ladite pluralité de prédicats, des moyens d'obtention d'un événement décrivant une partie du document structuré, des moyens de mise à jour dudit au moins un état d'évaluation à partir de l'événement obtenu, des moyens d'évaluation de la pluralité de prédicats en fonction dudit au moins un état d'évaluation mis à jour. Ce dispositif d'évaluation d'une expression sur des éléments d'un document structuré peut être incorporé dans un ordinateur 1200 tel qu'illustré à la Figure 12. En particulier, les différents moyens identifiés ci-dessus peuvent être incorporés dans une mémoire morte 1205 ("Read-Only Memory" ou ROM) adaptée à mémoriser un programme d'évaluation d'une expression sur des éléments d'un document structuré conforme à l'invention. La mémoire vive 1210 ("Random Access Memory" ou RAM) est adaptée à mémoriser dans des registres les valeurs modifiées lors de l'exécution du programme d'évaluation d'une expression sur des éléments d'un document structuré. Le microprocesseur 1220 est intégré à un ordinateur 1200 qui peut être connecté à différents périphériques et à d'autres ordinateurs d'un réseau de communication. Cet ordinateur comporte de manière connue une interface de communication 1230 reliée au réseau de communication 1235 pour recevoir ou transmettre des messages. L'ordinateur comporte en outre des moyens de stockage de documents, tel qu'un disque dur 1270, ou est adapté à coopérer au moyen d'un lecteur de disque 1280 (disquettes, disques compacts ou cartes informatiques) avec des moyens de stockage de documents amovibles, tels que des disques 1285. Ces moyens de stockage fixes ou amovibles peuvent comporter le code du procédé d'évaluation d'une expression sur des éléments d'un document structuré conforme à l'invention. Ils sont également adaptés à mémoriser un document électronique contenant des données hiérarchisées tel que défini par la présente invention. A titre de variante, le programme permettant au dispositif d'évaluation d'au moins un prédicat d'une expression de mettre en oeuvre l'invention peut être stocké dans la mémoire morte 1205. En seconde variante, le programme pourra être reçu pour être stocké comme décrit précédemment par l'intermédiaire du réseau de communication 1235. L'ordinateur 1200 possède également un écran 1240 permettant par exemple de servir d'interface avec un opérateur à l'aide du clavier 1250 ou de la souris 1260 ou de tout autre moyen. L'unité centrale 1220 (CPU) exécutera alors les instructions relatives à la mise en oeuvre de l'invention. Lors de la mise sous tension, les programmes et méthodes relatives à l'invention stockés dans une mémoire non volatile, par exemple la mémoire 1205, sont transférés dans la mémoire 1210 qui contiendra alors le code exécutable de l'invention ainsi que les variables nécessaires à la mise en oeuvre de l'invention. Le bus de communication 1290 permet la communication entre les différents sous-éléments de l'ordinateur ou liés à lui. La représentation de ce bus 1290 n'est pas limitative et notamment le microprocesseur 1220 est susceptible de communiquer des instructions à tout 30 sous-élément directement ou par l'intermédiaire d'un autre sous-élément. 32 Bien entendu, de nombreuses modifications peuvent être apportées aux exemples de réalisation décrits précédemment sans sortir du cadre de l'invention. REVENDICATIONS 1. Procédé d'évaluation d'une pluralité de prédicats associés à une sous-expression d'une expression sur des items d'un document structuré, caractérisé en ce qu'il comprend : - une étape d'association d'au moins un état d'évaluation à au moins un prédicat de ladite pluralité de prédicats (600), - une étape d'obtention d'un événement décrivant une partie du document structuré (620), - une étape de mise à jour dudit au moins un état d'évaluation à partir de l'événement obtenu (630), - une étape d'évaluation de la pluralité de prédicats en fonction dudit au moins un état d'évaluation mis à jour (640). 2. Procédé d'évaluation selon la revendication 1, caractérisé en ce qu'il comprend : - une étape de création d'au moins un noeud solution représentant au moins un événement décrivant une partie du document structuré, et - une étape d'association dudit au moins un noeud solution à ladite 20 sous-expression. 3. Procédé d'évaluation selon la revendication 2, caractérisé en ce que l'étape d'association d'au moins un état d'évaluation associe un état d'évaluation à au moins un couple comprenant un prédicat et un noeud solution. 4. Procédé d'évaluation selon la revendication 3, caractérisé en ce qu'il comprend une étape de suppression du noeud solution associé à l'état d'évaluation si cet état d'évaluation indique que le prédicat associé à cet état d'évaluation n'est pas vérifié et ne peut plus être vérifié. 5. Procédé selon l'une quelconque des revendications 2 à 4, caractérisé en ce qu'un prédicat de la pluralité de prédicats étant dépendant de 25 30 la position du noeud solution, la position du noeud solution est calculée comme la position du noeud solution précédent incrémenté de la valeur 1 si la position du noeud solution précédent est connue et si les prédicats précédent ledit prédicat évalué sont vérifiés pour le noeud solution. 6. Procédé d'évaluation selon l'une quelconque des revendications précédentes, caractérisé en ce qu'il comprend une étape de mise à jour d'au moins un autre état d'évaluation sur la base dudit au moins un état d'évaluation mis à jour. 7. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que ledit au moins un état d'évaluation est mémorisé dans un tableau. 15 8. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'il comprend une table de comptage comprenant pour au moins un prédicat, le nombre d'événements vérifiant ledit au moins un prédicat. 9. Procédé selon l'une quelconque des revendications précédentes, 20 caractérisé en ce qu'il comprend une étape de transmission d'un résultat si l'ensemble des prédicats est vérifié lors de l'étape d'évaluation de la pluralité de prédicats. 10. Procédé selon l'une quelconque des revendications précédentes, 25 caractérisé en ce qu'un prédicat de la pluralité de prédicats étant un chemin de localisation, l'état d'évaluation prend une valeur indiquant que l'évaluation du prédicat est positive si l'événement obtenu permet à l'étape de mise à jour de compléter le chemin de localisation, 30 une valeur indiquant que l'évaluation du prédicat est négative si l'événement obtenu permet à l'étape de mise à jour de déterminer qu'un chemin de localisation ne peut être trouvé, et 10 une valeur indiquant que l'évaluation du prédicat est indéterminée dans les autres cas. 11. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'un prédicat de la pluralité de prédicats étant une expression, l'état d'évaluation prend une valeur correspondant au résultat de l'évaluation de l'expression si l'événement obtenu permet à l'étape de mise à jour de compléter l'évaluation de l'expression, et une valeur indiquant que l'évaluation du prédicat est indéterminée dans les autres cas. 12. Dispositif d'évaluation d'une pluralité de prédicats associés à une sous-expression d'une expression sur des items d'un document structuré, caractérisé en ce qu'il comprend : - des moyens d'association d'au moins un état d'évaluation à au moins un prédicat de ladite pluralité de prédicats, - des moyens d'obtention d'un événement décrivant une partie du document structuré, - des moyens de mise à jour dudit au moins un état d'évaluation à partir de l'événement obtenu, - des moyens d'évaluation de la pluralité de prédicats en fonction dudit au moins un état d'évaluation mis à jour. 13. Dispositif d'évaluation selon la revendication 12, caractérisé en ce qu'il comprend : - des moyens de création d'au moins un noeud solution représentant au moins un événement décrivant une partie du document structuré, et - des moyens d'association dudit au moins un noeud solution à ladite sous-expression. 14. Dispositif d'évaluation selon la revendication 13, caractérisé en ce que les moyens d'association d'au moins un état d'évaluation sont aptes à associer un état d'évaluation à au moins un couple comprenant un prédicat et un noeud solution. 15. Dispositif d'évaluation selon la revendication 14, caractérisé en ce qu'il comprend des moyens de suppression du noeud solution associé à l'état d'évaluation si cet état d'évaluation indique que le prédicat associé à cet état d'évaluation n'est pas vérifié et ne peut plus être vérifié. 10 16. Dispositif selon l'une quelconque des revendications 13 à 15, caractérisé en ce qu'un prédicat de la pluralité de prédicats étant dépendant de la position du noeud solution, le dispositif comprend des moyens de calcul aptes à calculer la position du noeud solution comme la position du noeud solution 15 précédent incrémenté de la valeur 1 si la position du noeud solution précédent est connue et si les prédicats précédent ledit prédicat évalué sont vérifiés pour le noeud solution. 17. Dispositif d'évaluation selon l'une quelconque des revendications 20 12 à 16, caractérisé en ce qu'il comprend des moyens de mise à jour d'au moins un autre état d'évaluation sur la base dudit au moins un état d'évaluation mis à jour. 18. Dispositif selon l'une quelconque des revendications 12 à 17, 25 caractérisé en ce qu'il comprend des moyens de mémorisation aptes à mémoriser ledit au moins un état d'évaluation dans un tableau. 19. Dispositif selon l'une quelconque des revendications 12 à 18, caractérisé en ce qu'il comprend une table de comptage comprenant pour au 30 moins un prédicat, le nombre d'événements vérifiant ledit au moins un prédicat.5 20. Dispositif selon l'une quelconque des revendications 12 à 19, caractérisé en ce qu'il comprend des moyens de transmission aptes à transmettre un résultat si l'ensemble des prédicats est vérifié lors de l'étape d'évaluation de la pluralité de prédicats. 21. Dispositif selon l'une quelconque des revendications 12 à 20, caractérisé en ce qu'un prédicat de la pluralité de prédicats étant un chemin de localisation, le dispositif comprend des moyens de détermination de l'état d'évaluation tels que l'état d'évaluation prend une valeur indiquant que l'évaluation du prédicat est positive si l'événement obtenu permet à l'étape de mise à jour de compléter le chemin de localisation, une valeur indiquant que l'évaluation du prédicat est négative si l'événement obtenu permet à l'étape de mise à jour de déterminer qu'un chemin 15 de localisation ne peut être trouvé, et une valeur indiquant que l'évaluation du prédicat est indéterminée dans les autres cas. 22. Dispositif selon l'une quelconque des revendications 12 à 21, 20 caractérisé en ce qu'un prédicat de la pluralité de prédicats étant une expression, le dispositif comprend des moyens de détermination de l'état d'évaluation tels que l'état d'évaluation prend une valeur correspondant au résultat de l'évaluation de l'expression si l'événement obtenu permet à l'étape de mise à jour de compléter l'évaluation 25 de l'expression, et une valeur indiquant que l'évaluation du prédicat est indéterminée dans les autres cas. 23. Produit programme ordinateur pouvant être chargé dans un 30 appareil programmable, caractérisé en ce qu'il comporte des séquences d'instructions pour mettre en oeuvre un procédé d'évaluation d'une pluralité de prédicats associés à une sous-expression d'une expression sur des items d'un document structuré selon l'une quelconque des revendications 1 à 11, lorsque ce programme est chargé et exécuté par l'appareil programmable. 24. Moyen de stockage d'informations, lisible par un ordinateur ou un microprocesseur conservant des instructions d'un programme d'ordinateur, caractérisé en ce qu'il permet la mise en oeuvre d'un procédé d'évaluation d'une pluralité de prédicats associés à une sous-expression d'une expression sur des items d'un document structuré selon l'une quelconque des revendications 1 à 11.10