FR2914451A1

FR2914451A1 - Item expression evaluating method for XML document, involves generating target nodes and logical representation, and evaluating expression on items of structured document from all generated target nodes and logical representation

Info

Publication number: FR2914451A1
Application number: FR0754071A
Authority: FR
Inventors: Herve Ruellan
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 2007-03-27
Filing date: 2007-03-27
Publication date: 2008-10-03
Anticipated expiration: 2027-03-27
Also published as: FR2914451B1

Abstract

The method involves generating a set of target nodes corresponding to items to be sought in a structured document from an expression. A logical representation of the expression is generated, where the logical representation comprises a set of nodes representing an elementary sub-expression of the expression, and linked according to relationships between the elementary sub-expressions. The expression on items of the structured document is evaluated from all the generated target nodes and the logical representation. The items of the document are filtered from the target nodes. Independent claims are also included for the following: (1) a device for evaluating an expression on items of a structured document (2) an information storage unit for implementing a method for evaluating an expression on items of a structured document (3) a computer program product having a set of instructions for evaluating an expression on items of a structured document.

Description

La présente invention se rapporte à un procédé et un dispositifThe present invention relates to a method and a device

d'évaluation 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. evaluating an expression, in particular an XPath type expression, on elements of a structured document. It finds a general application in the processing of XML data streams and more specifically on files in XML format.

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: <balise>), une balise fermante comportant elle aussi le nom de l'élément (par exemple: </balise>). Chaque élément peut contenir d'autres éléments ou des données textuelles. The XML markup language, which stands for eXtensible Markup Language, is an extensible tag language and is a syntax for defining computer languages. This language is standardized by the W3C standardization committee (a description of the language can be found at http://www.w3.org/TR/REC-xml). XML is a syntax for defining new languages. Thus, it is possible to define a plurality of XML languages that can be processed using generic tools. XML defines a particular syntax for mixing structural information and content information. XML defines several types of items to describe structural information and content information. According to this syntax, each element is defined by an opening tag containing the name of the element (for example: <tag>), a closing tag that also includes the name of the element (for example: </ tag>). Each element can contain other elements or textual data.

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 : <balise attribut="valeur">). La syntaxe XML permet aussi de définir des commentaires (par exemple : <l-- Commentaire--> ) et des instructions de traitement ( Processing Instruction selon la terminologie anglo-saxonne), qui peuvent préciser à une application informatique quels traitements appliquer au document XML (par exemple: <?montraitement?> ). 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. 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. An element can also be specified by attributes. The attribute is an item located in the opening tag of an element and contains, in addition to the very content of the attribute, an identifier to define it (for example: <attribute tag = "value">). The XML syntax also makes it possible to define comments (for example: <l-- Comment ->) and processing instructions (Processing Instruction according to the English terminology), which can specify to a computer application which processes to apply to the document XML (for example, <? Myprocessing?>). The set of objects described by the XML syntax, namely the elements, the attributes, the textual data, the comments and the processing instructions, is grouped under the designation of XML node. Finally, the XML syntax is textual and can be easily read or written by a user. Several different XML languages may contain elements of the same name. Thus, to be able to mix several different XML languages, the XML syntax makes it possible to define namespace (namespace according to the English terminology). In this way, two elements are identical if they have the same name and are in the same namespace. A namespace is defined by a uniform resource identifier also called URI (Uniform Resource Identifier), for example: http://canon.crf.fr/xml/monlangage. The use of a namespace in an XML document is achieved by defining a prefix that is a shortcut to the uniform resource identifier of that namespace.

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 : <ml:balise ml:attribut="valeur"> . 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. This prefix is defined by means of a specific attribute. For example, the expression xmins: ml = "http://canon.crf.fr/xml/monlanguage" associates the prefix ml with the uniform resource identifier http://canon.crf.fr/xml/monlangage. Then, the namespace of an element or attribute is specified by prefixing the name with the prefix associated with the namespace followed by a colon: as shown in the following example: < ml: ml tag: attribute = "value">. XPath (acronym for XML Path Language) is derived from a W3C consortium specification called XPath Specification 1.0, available at www.w3.org/TR/xpath. The purpose of this language is to define a syntax suitable for addressing parts of a structured document of the XML type.

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. This language was initially developed to provide a common basis for different applications, for example XSLT (eXtensible Stylesheet Language Transformations) applications and XQuery, dealing with documents of the XML type.

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), un test de noeud ( NodeTest en terminologie anglo-saxonne) et éventuellement 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) noeud(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 noeuds contextuels sont ceux sélectionnés par l'étape de localisation précédente. The syntax of this language uses a syntax similar to that used in expressions relating to location paths in a file system, for example the expression relating to a location path / library / book. LocationPaths (LocationPath according to XPath syntax) define a set of XML nodes and the relationships between these nodes. For example, the path / a / b designates the set of elements b that are the children of a root element of the XML document. A location path thus consists of a set of location steps (Steps in English terminology), each location step specifying a parentage, also called axis according to the XPath syntax (AxisSpecifier in English terminology), a node test (NodeTest in English terminology) and possibly a set of predicates (Predicate in English terminology). The relation of filiation makes it possible to define the relation between the node selected by the location step and the contextual node (s). For the first location step, the context node is either the root of the document or the current node. For the other localization steps, the contextual nodes are those selected by the preceding location step.

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 30 éléments b descendant, directement ou non, d'un élément a racine du document XML. By default, if the relation of parentage is not specified, the current location step concerns the direct children of the contextual nodes. Other filiation relationships exist to easily navigate the entire XML document. For example, the path / a / descendant :: b designates all 30 elements b descending, directly or indirectly, from a root element of the XML document.

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 5 désigne l'ensemble des éléments b suivant un élément a situé à une 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. 10 Les relations de filiation comprennent, d'une part, les relations de 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 15 ou ascendante ( reverse axis en terminologie anglo-saxonne) qui décrivent 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 20 recherchés. 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. 25 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 30 éléments ayant un type défini. Par exemple, l'expression /descendant::comment() retourne tous les noeuds du document de type commentaire. Conversely, the path b / ancestor :: a designates the set of ancestor elements, directly or otherwise, of a child element b of the current node. In another example, the path / descendant :: a / following :: b 5 designates the set of elements b following an element a located at any depth in the document. A specific relation of parentage makes it possible to designate the attributes of an element. For example, the path / a / attribute :: b returns the attribute b of the root element of the XML document. Parenting relationships include, on the one hand, forward or backward relationships (forward axis) which describe relationships in the document order, i.e. relations which will select nodes appearing in the document after the contextual node, and, on the other hand, backward or upward (reverse-axis) relationship relations which describe inverse relations to the document order, that is, relationships that will select nodes appearing in the document before the context node. The node test makes it possible to specify the characteristics of the nodes 20 sought. An example of a node test is the test on the name of the nodes to be searched. For example, the / descendant :: a expression returns all the elements of the document. According to another node test, it is permissible to obtain all elements regardless of their name. For example, the expression / descendant :: * returns all the elements of the document. According to yet another node test, it is allowed to return the 30 elements having a defined type. For example, the expression / descendant :: comment () returns all the nodes of the comment type document.

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. Predicates make it possible to impose one or more additional conditions for searching for nodes that are solutions of a location step. These conditions can take the form of a position.

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 . For example, the expression / a / b [2] designates the second child element b of the root element a. They can also take the form of a test. For example, the expression / a / b [c] designates the set of elements b son of the root element a and having a son element c.

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 /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. Conditions can also be used to check the content of an element or attribute. Thus, for example, the expression / a / b [c = "value"] designates the set of elements b son of the root element a having a son element c whose textual value is value. Similarly, the expression / a / b [@ c = "value"] denotes the set of b elements son of the root element a having an attribute c whose value is value. A step in a location path can have multiple predicates. These predicates are applied successively to select the elements designated by the location step.

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. 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. For example, the expression / a / b [c] [2] designates the second element b, son of the root element a and having a child element c. In general, the order of predicates is important. Thus, for example, the expression / a / b [2] [c] is different from the previous expression, and designates the second element b, son of the root element a and furthermore verifies that this element has an element son c. In addition to localization paths, the XPath syntax describes a set of algebraic expressions and comparison expressions, including the expression of conditions in predicates, as well as a set of functions that make it possible, for example, to express predicates. or to treat all the nodes designated by a location path.

Pour effectuer l'évaluation d'une expression XPath selon une première méthode, on divise un chemin de localisation en un ensemble d'étapes de localisation et on traite chaque étape successivement. Par exemple, lors de l'évaluation de l'expression /a/b[2] , il est, dans un premier temps, recherché l'ensemble des éléments a qui sont des éléments racines du document XML, puis ensuite, pour chacun de ces éléments, il est recherché l'ensemble des éléments fils b . Enfin, parmi cet ensemble, il est sélectionné le deuxième élément. II est à noter que si le document XML est correctement écrit, celui-ci comprend un unique élément racine. Une telle méthode est décrite dans le document US 2004060007 de Georg Gottlob, Christopher Koch et Reinhard Pichler. Cette méthode d'évaluation d'une expression XPath est basée sur la décomposition de l'expression en un ensemble de sous-expressions élémentaires, et sur l'évaluation de chaque sous-expression élémentaire séparément. Le résultat de l'évaluation d'une sous-expression élémentaire est mémorisé dans une table appelée table de contexte-valeur, le contexte correspondant au contexte d'évaluation de la sous-expression élémentaire et la valeur correspondant au résultat de l'évaluation de la sous-expression élémentaire. To evaluate an XPath expression according to a first method, a location path is divided into a set of location steps and each step is processed successively. For example, when evaluating the expression / a / b [2], it is, first of all, searched for the set of elements a which are root elements of the XML document, then for each of them. these elements, it is searched for all the elements son b. Finally, from this set, the second element is selected. It should be noted that if the XML document is correctly written, it includes a single root element. Such a method is described in US 2004060007 by Georg Gottlob, Christopher Koch and Reinhard Pichler. This method of evaluating an XPath expression is based on the decomposition of the expression into a set of elementary sub-expressions, and on the evaluation of each elementary subexpression separately. The result of the evaluation of an elementary subexpression is stored in a table called context-value table, the context corresponding to the evaluation context of the elementary sub-expression and the value corresponding to the result of the evaluation of the sub-expression. the elementary subexpression.

Les résultats des différentes sous-expressions élémentaires sont ensuite combinés pour générer un résultat global. La mémorisation des résultats obtenus permet d'éviter de réaliser le calcul d'une même expression une pluralité de fois dans le même contexte et ainsi d'optimiser le temps de calcul pour certaines expressions. The results of the different elementary sub-expressions are then combined to generate a global result. The memorization of the results obtained makes it possible to avoid calculating the same expression a plurality of times in the same context and thus to optimize the calculation time for certain expressions.

Selon une première application de cette méthode, l'évaluation débute par l'évaluation des sous-expressions élémentaires. Ensuite, les résultats sont combinés pour réaliser l'évaluation des expressions complexes. L'évaluation de chaque sous-expression élémentaire est mémorisée dans une table de contexte-valeur. Selon cette méthode, cette table peut être de taille très importante. En outre, selon cette méthode, de nombreux résultats intermédiaires inutiles sont calculés lors de l'évaluation du résultat. According to a first application of this method, the evaluation starts with the evaluation of the elementary sub-expressions. Then, the results are combined to perform the evaluation of complex expressions. The evaluation of each elementary subexpression is stored in a context-value table. According to this method, this table can be very large. In addition, according to this method, many unnecessary intermediate results are calculated during the evaluation of the result.

Selon une seconde application de cette méthode, l'évaluation des sous-expressions élémentaires est effectuée dans un ordre correspondant à la sémantique de l'expression XPath. Ainsi, lors de l'évaluation d'une sous-expression élémentaire, 5 l'ensemble des contextes d'évaluation est connu évitant de la sorte le calcul des résultats intermédiaires inutiles. Une application spécifique de cette méthode peut être réalisée en modifiant une mise en oeuvre d'un processeur XPath afin d'éviter que ce processeur n'évalue plusieurs fois une même sous-expression élémentaire pour 10 un même contexte. Cette modification consiste à mémoriser le résultat de chaque évaluation dans une table de contexte-valeur. Toutefois, une telle méthode présente plusieurs inconvénients. En effet, selon cette méthode, l'ensemble du document doit être présent en mémoire afin de réaliser l'évaluation d'une expression XPath. En effet, pour des 15 appareils ayant des capacités mémoire limitées, par exemple pour une caméra vidéo, cette méthode ne permet pas d'évaluer une expression XPath sur un document XML de taille importante. Dans le cas d'appareil de faibles capacités mémoire, le traitement d'un document XML est en général réalisé à l'aide d'un parseur de type SAX 20 ( Simple API for XML en terminologie anglo-saxonne). Le parseur de type SAX est apte à traiter séquentiellement les noeuds du document XML, c'est-à-dire les éléments, les commentaires et les valeurs textuelles. Cependant, l'utilisation d'un parseur SAX lors de l'évaluation d'une 25 expression XPath ne permet pas de revenir en arrière dans le document XML. Par conséquence, il n'est pas possible de réaliser directement l'évaluation d'expressions comprenant une relation de filiation vers l'arrière. Néanmoins, il est possible de construire des méthodes permettant d'évaluer une expression XPath sur un document XML à l'aide d'un parseur de 30 type SAX ou équivalent. According to a second application of this method, the evaluation of the elementary sub-expressions is performed in an order corresponding to the semantics of the XPath expression. Thus, when evaluating an elementary sub-expression, the set of evaluation contexts is known thus avoiding the calculation of unnecessary intermediate results. A specific application of this method can be realized by modifying an implementation of an XPath processor in order to prevent this processor from evaluating several times the same elementary sub-expression for the same context. This modification consists in memorizing the result of each evaluation in a context-value table. However, such a method has several disadvantages. Indeed, according to this method, the entire document must be present in memory in order to perform the evaluation of an XPath expression. Indeed, for devices with limited memory capacity, for example for a video camera, this method does not evaluate an XPath expression on a large XML document. In the case of apparatus of low memory capacity, the processing of an XML document is generally carried out using a parser SAX type 20 (Simple API for XML in English terminology). The SAX parser is able to process sequentially the nodes of the XML document, that is to say the elements, the comments and the textual values. However, using a SAX parser when evaluating an XPath expression does not allow going back into the XML document. Consequently, it is not possible to directly evaluate expressions comprising a backward relationship. Nevertheless, it is possible to construct methods for evaluating an XPath expression on an XML document using a parser of the SAX type or equivalent.

Ainsi, selon une méthode connue du document US 2004068487 de Charles Barton, Philippe Charles, Deepak Goyal et Mukund Raghavachari, une expression XPath est évaluée en utilisant un parseur SAX. Pour ce faire, une représentation de l'expression XPath ne comportant que des relations vers l'avant est créée. De cette manière, il n'est plus nécessaire de revenir en arrière dans le document. Cependant, selon cette méthode, l'évaluation ne peut être réalisée que sur une expression XPath utilisant une sous-partie du langage XPath. En particulier, cette méthode ne permet de traiter que les prédicats contenant des chemins XPath. Elle ne s'applique donc pas aux tests de position ou de valeur, 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 une expression, notamment des expressions XPath, en utilisant un parseur de type SAX quelque soit l'expression 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 expression sur des items d'un document structuré, une expression comprenant un ensemble de sous-expressions élémentaires, caractérisé en ce qu'il comprend les étapes préalables suivantes : -génération, à partir de l'expression, d'un ensemble des noeuds cibles correspondant à des items à rechercher dans le document structuré ; -génération d'une représentation logique de l'expression, une représentation logique comprenant un ensemble de noeuds, représentant les sous-expressions élémentaires de l'expression, reliés en fonction des relations entre ces sous-expressions élémentaires ; et une étape de -évaluation de l'expression sur des items du document structuré à partir de l'ensemble des noeuds cibles généré et de la représentation logique 30 générée. Thus, according to a known method of US 2004068487 by Charles Barton, Philip Charles, Deepak Goyal and Mukund Raghavachari, an XPath expression is evaluated using a SAX parser. To do this, a representation of the XPath expression with only forward relationships is created. In this way, it is no longer necessary to go back in the document. However, according to this method, the evaluation can only be performed on an XPath expression using a subpart of the XPath language. In particular, this method only processes predicates containing XPath paths. It does not apply to position or value tests, arithmetic expressions or functions. Given the above, it would therefore be interesting to be able to evaluate an expression, including XPath expressions, using a SAX type parser regardless of the expression by limiting the required memory resources and by avoiding at least some of the disadvantages mentioned above. The present invention aims first of all at providing a method of evaluating an expression on items of a structured document, an expression comprising a set of elementary sub-expressions, characterized in that it comprises the following preliminary steps: -generating, from the expression, a set of target nodes corresponding to items to be searched in the structured document; generating a logical representation of the expression, a logical representation comprising a set of nodes, representing the elementary sub-expressions of the expression, related as a function of the relationships between these elementary sub-expressions; and a step of evaluating the expression on items of the structured document from the set of target nodes generated and the generated logical representation.

L'invention prévoit de trouver parmi les items d'un document structuré, les items répondant à l'évaluation d'une expression, notamment d'une expression XPath. Les items d'un document structuré sont, notamment, décrits dans un langage de balisage structurant les données, par exemple, en utilisant le langage XML. Pour permettre cette évaluation, le procédé selon l'invention prévoit de générer, d'une part, un ensemble de noeuds cibles correspondant à des items à rechercher, et d'autre part, une représentation logique de l'expression. The invention provides to find among the items of a structured document, the items responding to the evaluation of an expression, including an XPath expression. The items of a structured document are, in particular, described in a markup language structuring the data, for example, using the XML language. To allow this evaluation, the method according to the invention provides for generating, on the one hand, a set of target nodes corresponding to items to be searched, and on the other hand, a logical representation of the expression.

A partir de l'ensemble de noeuds cibles générés et de la représentation logique, l'évaluation de l'expression peut être réalisée. Selon l'invention, il est donc évité de calculer de nombreux résultats intermédiaires inutiles dans l'évaluation du résultat. De plus, l'évaluation d'une expression est rendue possible sur des 15 appareils ayant de faibles capacités mémoires. Selon un mode de réalisation particulier, l'étape de génération d'un ensemble des noeuds cibles comprend, en outre, la génération d'une représentation des relations entre les noeuds cibles. Selon cette caractéristique, les noeuds cibles sont organisés selon 20 leurs relations. En effet, il peut être utile de rechercher un second élément seulement si un premier élément a été trouvé. Selon une caractéristique particulière, l'étape d'évaluation de l'expression comprend : - une étape de filtrage des items du document à partir de l'ensemble 25 des noeuds cibles ; et - une étape d'évaluation des items filtrés à partir de la représentation logique. Selon ces caractéristiques, les items sont filtrés de sorte à ne conserver que les événements utiles à l'évaluation de l'expression. 30 Selon une autre caractéristique particulière, l'étape de filtrage des items du document à partir de l'ensemble des noeuds cibles comprend une étape d'identification des items du document correspondant à des noeuds cibles de l'ensemble des noeuds cibles. Selon une autre caractéristique particulière, l'étape d'évaluation des items filtrés comprend une étape de création d'un noeud solution associé à un noeud de la représentation logique, ce noeud solution représentant un résultat d'évaluation pour le noeud de la représentation logique. Selon un mode de réalisation, l'étape de création d'un noeud solution associé à un noeud de la représentation logique comprend une étape d'association d'un item filtré avec ce noeud solution. From the set of generated target nodes and the logical representation, evaluation of the expression can be performed. According to the invention, it is therefore avoided to calculate many unnecessary intermediate results in the evaluation of the result. In addition, evaluation of an expression is made possible on devices having low memory capabilities. According to a particular embodiment, the step of generating a set of target nodes further comprises generating a representation of the relationships between the target nodes. According to this feature, the target nodes are organized according to their relationships. Indeed, it can be useful to search for a second element only if a first element has been found. According to a particular characteristic, the evaluation step of the expression comprises: a step of filtering the items of the document from the set of target nodes; and a step of evaluating the filtered items from the logical representation. According to these characteristics, the items are filtered so that only the events that are useful for evaluating the expression are kept. According to another particular characteristic, the step of filtering the items of the document from the set of target nodes comprises a step of identifying the items of the document corresponding to target nodes of the set of target nodes. According to another particular characteristic, the step of evaluating the filtered items comprises a step of creating a solution node associated with a node of the logical representation, this solution node representing an evaluation result for the node of the logical representation. . According to one embodiment, the step of creating a solution node associated with a node of the logical representation comprises a step of associating a filtered item with this solution node.

Selon une caractéristique particulière, l'étape d'évaluation des items filtrés comprend en outre une étape de création d'une relation entre un premier noeud solution associé à un premier noeud de la représentation logique et au moins un deuxième noeud solution associé à un deuxième noeud de la représentation logique conformément à la relation entre le premier noeud de la représentation logique et le deuxième noeud de la représentation logique. Selon une caractéristique particulière, l'étape d'évaluation de l'expression comprend en outre une étape de vérification de la complétude d'une solution comprenant les sous-étapes suivantes : -vérification de l'existence pour chaque noeud de la représentation logique d'au moins un noeud solution associé ; - sélection pour chaque noeud de la représentation logique d'un noeud solution associé, l'ensemble des noeuds solutions sélectionnés formant une solution ; - pour chaque relation entre deux noeuds de la représentation logique, vérification qu'une relation similaire existe entre les noeuds solutions associés sélectionnés. Selon une caractéristique, l'étape d'évaluation de l'expression comprend, si l'étape de vérification de la complétude d'une solution est positive, une étape de génération d'un résultat à partir de la solution. According to a particular characteristic, the step of evaluating the filtered items further comprises a step of creating a relationship between a first solution node associated with a first node of the logical representation and at least a second solution node associated with a second node. node of the logical representation according to the relationship between the first node of the logical representation and the second node of the logical representation. According to one particular characteristic, the evaluation step of the expression further comprises a step of verifying the completeness of a solution comprising the following substeps: verification of the existence for each node of the logical representation of at least one associated solution node; selecting for each node the logical representation of an associated solution node, the set of selected solution nodes forming a solution; for each relationship between two nodes of the logical representation, checking that a similar relationship exists between the selected associated solution nodes. According to one characteristic, the step of evaluating the expression comprises, if the step of verifying the completeness of a solution is positive, a step of generating a result from the solution.

Selon une caractéristique particulière, un contexte de recherche est associé à un item filtré correspondant à un noeud de la représentation logique et à un noeud de la représentation logique descendant du noeud correspondant à l'item filtré. Selon cette caractéristique, le contexte de recherche permet de déterminer si la recherche de solutions pour des items est terminée. According to a particular characteristic, a search context is associated with a filtered item corresponding to a node of the logical representation and a node of the descending logical representation of the node corresponding to the filtered item. According to this characteristic, the search context makes it possible to determine if the search for solutions for items is finished.

Selon une autre caractéristique particulière, un contexte de recherche comprend une information d'identification d'une partie du document dans laquelle est recherché un item correspondant au noeud descendant. Selon une autre caractéristique particulière, il comprend une étape de transmission d'un résultat dès la fin de l'évaluation de l'expression. According to another particular characteristic, a search context includes identification information of a part of the document in which an item corresponding to the descending node is searched. According to another particular characteristic, it comprises a step of transmitting a result as soon as the evaluation of the expression is finished.

Selon une caractéristique, le procédé comprend une étape de suppression d'un noeud solution, la suppression d'un noeud solution étant réalisée en fonction d'un critère de validité du noeud solution. Selon une autre caractéristique particulière, le critère de validité d'un noeud solution dépend des relations existant entre ce noeud solution et d'autres noeuds solutions et des contextes de recherches associés au noeud de la représentation logique associé à ce noeud solution. L'invention vise également un dispositif d'évaluation d'une expression sur des items d'un document structuré, une expression comprenant un ensemble de sous-expressions élémentaires, caractérisé en ce qu'il comprend : - des moyens de génération, à partir de l'expression, d'un ensemble des noeuds cibles correspondant à des items à rechercher dans le document structuré ; - des moyens de génération d'une représentation logique de 25 l'expression, une représentation logique comprenant un ensemble de noeuds, représentant les sous-expressions élémentaires de l'expression, reliés en fonction des relations entre ces sous-expressions élémentaires ; et - des moyens d'évaluation de l'expression sur des items du document structuré à partir de l'ensemble des noeuds cibles généré et de la 30 représentation logique générée. 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. According to one characteristic, the method comprises a step of deleting a solution node, the deletion of a solution node being performed according to a validity criterion of the solution node. According to another particular characteristic, the criterion of validity of a solution node depends on the relations existing between this solution node and other solution nodes and search contexts associated with the node of the logical representation associated with this solution node. The invention also relates to a device for evaluating an expression on items of a structured document, an expression comprising a set of elementary sub-expressions, characterized in that it comprises: generation means, starting from the expression, a set of target nodes corresponding to items to be searched in the structured document; means for generating a logical representation of the expression, a logical representation comprising a set of nodes, representing the elementary sub-expressions of the expression, related as a function of the relationships between these elementary sub-expressions; and means for evaluating the expression on items of the structured document from the set of target nodes generated and the generated logical representation. This device has the same advantages as the method briefly described above and they will not be recalled here.

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-dessus, lorsque ce programme est chargé et exécuté par l'appareil programmable. 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 20 XPath de la Figure 1 conformément à l'invention ; - la Figure 4 illustre un exemple de document XML sur lequel est appliqué l'expression XPath de la Figure 1 ; - la Figure 5 illustre les noeuds solutions créés après le traitement de l'événement correspondant à la balise vide a référencée en 435 sur la 25 Figure 4 ; - la Figure 6 représente le contexte nommé ctx-b dans la Figure 5; - la Figure 7 représente le contexte nommé ctx-c dans la Figure 5 ; 30 - la Figure 8 représente un organigramme général d'évaluation d'une expression conformément à l'invention ; - la Figure 9 représente les différentes étapes de traitement d'une expression XPath pour générer les noeuds cibles et la représentation logique correspondant à cette expression conformément à l'invention ; - la Figure 10 illustre un algorithme d'évaluation d'une expression 5 XPath sur un document XML conformément à l'invention ; - la Figure 11 illustre un algorithme de construction des résultats à partir des événements filtrés par les cibles conformément à l'invention ; et - la Figure 12 illustre une architecture matérielle sur laquelle peut être mise en oeuvre l'invention. 10 L'invention consiste à décomposer l'évaluation d'une expression, notamment d'une expression XPath, en deux parties. La première partie consiste à filtrer les événements reçus du parseur SAX pour ne conserver que les événements utiles à l'évaluation de l'expression. Les événements filtrés 15 représentent un ensemble de noeuds cibles recherchés pour l'évaluation de l'expression XPath. La deuxième partie consiste à combiner les événements filtrés pour réaliser l'évaluation proprement dite de l'expression. Cette combinaison consiste à créer des solutions potentielles contenant l'état d'évaluation des différents candidats pouvant être résultats de l'expression 20 XPath. L'expression 10 en Figure 1 illustre un exemple d'expression XPath apte à être traitée selon l'invention. Selon cette expression, des éléments a fils d'un élément a situé à n'importe quelle profondeur dans le document et ayant au moins deux 25 enfants directs b et un ancêtre c sont recherchés. 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. L'élément r (noeud cible 30 21) correspond à la racine du document XML, et l'élément c (noeud cible 22), l'élément a (noeud cible 23) et l'élément b (noeud cible 24) correspondent aux noeuds 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. The present invention also aims at a means of storing information, possibly partially or totally removable, readable by a computer or a microprocessor retaining instructions of a computer program, allowing the implementation of the method as explained hereinabove. above. Finally, the present invention relates to a computer program product that can be loaded into a programmable device, comprising sequences of instructions for implementing the method as explained above, when this program is loaded and executed by the device. programmable. Other aspects and advantages of the present invention will emerge more clearly on reading the following description, this description being given solely by way of nonlimiting example and with reference to the appended drawings, in which: FIG. 1 represents an example XPath expression that is to be evaluated according to the invention; FIG. 2 illustrates the set of target nodes generated by the invention from the XPath expression of FIG. 1; Figure 3 illustrates a logical representation of the XPath expression of Figure 1 according to the invention; FIG. 4 illustrates an exemplary XML document to which the XPath expression of FIG. 1 is applied; FIG. 5 illustrates the solution nodes created after the treatment of the event corresponding to the empty tag referenced at 435 in FIG. 4; Figure 6 shows the context named ctx-b in Figure 5; Figure 7 shows the context named ctx-c in Figure 5; Figure 8 shows a general flowchart for evaluating an expression according to the invention; FIG. 9 represents the different steps of processing an XPath expression to generate the target nodes and the logical representation corresponding to this expression according to the invention; Figure 10 illustrates an algorithm for evaluating an XPath expression on an XML document according to the invention; FIG. 11 illustrates an algorithm for constructing the results from the events filtered by the targets according to the invention; and FIG. 12 illustrates a hardware architecture on which the invention can be implemented. The invention consists in decomposing the evaluation of an expression, in particular of an XPath expression, in two parts. The first part consists in filtering the events received from the SAX parser to keep only the events useful for the evaluation of the expression. The filtered events represent a set of target nodes sought for evaluation of the XPath expression. The second part consists in combining the filtered events to carry out the actual evaluation of the expression. This combination consists in creating potential solutions containing the evaluation status of the different candidates that can be results of the XPath expression. The expression 10 in FIG. 1 illustrates an exemplary XPath expression that can be processed according to the invention. According to this expression, son elements of an element at any depth in the document and having at least two direct children b and one ancestor c are searched. Figure 2 shows the set of target nodes generated in accordance with the invention from the XPath expression of Figure 1. The target nodes of Figure 2 correspond to the searched XML nodes for evaluating the XPath expression. . The element r (target node 21) corresponds to the root of the XML document, and the element c (target node 22), the element a (target node 23) and the element b (target node 24) correspond to the Nodes searched in the XML document using the XPath expression. The target nodes are used to filter the events received by the entity able to perform the evaluation of an XPath expression on an XML document also called XPath processor (XPath Processor in English terminology). Thus, the target nodes correspond to the node tests of the XPath expression. For each node test of the XPath expression, a target node is generated. However, if several identical target nodes are generated, they are grouped into a single target node.

Conformément à l'invention, un noeud cible généré permet de filtrer tous les noeuds XML correspondant à ce noeud cible. Par exemple, selon l'expression 10 de la Figure 1, un seul noeud cible est généré pour l'ensemble des éléments a . En effet, un noeud cible ayant pour rôle de filtrer les noeuds du document XML, un seul noeud cible suffit pour réaliser ce filtrage. According to the invention, a generated target node makes it possible to filter all the XML nodes corresponding to this target node. For example, according to the expression 10 of Figure 1, a single target node is generated for all elements a. Indeed, a target node having the role of filtering the nodes of the XML document, a single target node is sufficient to perform this filtering.

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 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 b est recherché uniquement après avoir trouvé un élément a . De la même manière, un élément a est recherché uniquement après avoir trouvé un élément c . 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 c et la cible a est, notamment, une différence de profondeur d'au moins un . In addition, in order to optimize the search process of the nodes, the target nodes are organized according to their order of appearance relationships in the document as defined by the filiation relationships of the XPath expression. In this way, according to the example illustrated in FIGS. 1 and 2, an element b is searched only after finding an element a. In the same way, an element a is searched only after finding an element c. These order of appearance relationships are shown in Figure 2 by arrows. The search process is further optimized by a precise description of the appearance order relationships expressed in the XPath expression. Thus, according to the example illustrated in FIGS. 1 and 2, the relationship between the target c and the target a is, in particular, a difference in depth of at least one.

De même, il est possible de décrire précisément une relation de filiation de type noeud frère suivant ( following-sibling selon la spécification XPath) comme enfant du même élément, avec un numéro d'ordre supérieur . Cette précision dans la description des relations d'ordre d'apparition est à l'origine de la flèche partant du noeud cible a et allant sur lui-même. En effet, de cette manière, il est indiqué qu'après avoir trouvé un élément a , on poursuit la recherche d'un élément a fils de cepremier élément a . 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. Selon cette représentation logique, chaque sous-expression élémentaire de l'expression XPath est représentée par un noeud logique. Par exemple, la sous-expression élémentaire descendant::a est représentée par un noeud logique descendant::a . Similarly, it is possible to precisely describe a sister sibling relationship (following-sibling according to the XPath specification) as a child of the same element, with a higher order number. This precision in the description of the order of appearance relationships is at the origin of the arrow starting from the target node a and going on itself. Indeed, in this way, it is indicated that after finding an element a, we continue the search for a son element of thisfirst element a. Figure 3 illustrates a logical representation of the XPath expression of Figure 1 according to the invention. This logical representation makes it possible to evaluate the XPath expression from the nodes filtered by the generated target nodes as described in FIG. 2. According to this logical representation, each elementary subexpression of the XPath expression is represented by a logical node. For example, the descendant elementary subexpression :: a is represented by a descending logical node :: 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. The links between the logical nodes describe their relationships within the XPath expression. During the evaluation of an XPath expression, this logical representation also makes it possible to build the solutions of the XPath expression. For this, a logical node receives the events filtered by the target nodes and uses them to build solution nodes representing this event within a potential solution for the XPath expression. Each solution node represents a value that checks an elementary part of the XPath expression. The elementary part of the XPath expression checked by the solution node corresponds to the logical node associated with this solution node. A potential solution groups together a set of solution nodes according to the logic of the XPath expression. When a potential solution contains a solution node for each logical node of the XPath expression, this potential solution checks the completeness of the XPath expression and thus generates a solution for the XPath expression.

Ainsi, lorsqu'un événement a est reçu, il est détecté par le noeud cible a de la Figure 2 et transmis aux deux noeuds logiques a de la Figure 3, à savoir le noeud logique descendant::a 300 et le noeud logique child::a 310. A partir de l'événement a , les noeuds logiques 300 et 310 mettent à jour les solutions potentielles de l'expression XPath en créant un ou plusieurs 5 noeuds solution représentant cet événement a . II est maintenant décrit en référence à la Figure 4 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 10 sur le document XML de la Figure 4 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. II 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 c 22 est activé, 20 avec un contexte d'activation correspondant à l'ensemble du document XML. Ensuite, lors de la réception de l'événement balise ouvrante m 400, celui-ci n'est reçu par aucune cible, il est donc ignoré. L'événement suivant est l'événement balise ouvrante c 405. Cet événement est reçu par le noeud cible c . Le noeud cible a est activé 25 avec un contexte d'activation correspondant à l'ensemble des noeuds descendant de cet élément c . En outre, un noeud solution et est créé pour représenter cet événement et est associé au noeud solution r en tant que fils de ce noeud. Le document XML comprend ensuite une balise vide b 410. 30 L'événement associé n'est reçu par aucun noeud cible. En effet, le noeud cible b n'a pas été activé. Thus, when an event a is received, it is detected by the target node a of FIG. 2 and transmitted to the two logical nodes a of FIG. 3, namely the descending logic node :: a 300 and the logical node child: : a 310. From the event a, the logical nodes 300 and 310 update the potential solutions of the XPath expression by creating one or more solution nodes representing this event a. A sample XML document to which the XPath expression of FIG. 1 can be applied is now described with reference to FIG. 4. According to this example, the result of the evaluation of the XPath expression 10 on the document XML in Figure 4 is the second element of this XML document. When processing the XML document by the SAX parser, events describing the XML document are passed to the XPath processor. It is now described the XPath processor actions which are for evaluating the XPath expression on the XML document described by these events. On receipt of the event Start of the document, it is received by the target node r 21. This target node creates a solution node r to represent this event. In addition, the target node c 22 is activated, with an activation context corresponding to the entire XML document. Then, upon receipt of the event tag opening m 400, it is not received by any target, it is ignored. The next event is the opening tag event c 405. This event is received by the target node c. The target node a is activated with an activation context corresponding to the set of nodes descending from this element c. In addition, a solution node is created to represent this event and is associated with the solution node r as the child of this node. The XML document then comprises an empty tag b 410. The associated event is not received by any target node. Indeed, the target node b has not been activated.

Ensuite, l'événement suivant est l'événement balise fermante c 415. Cet événement est reçu par le noeud cible c . Cet événement marque la fin du contexte d'activation du noeud cible a . Ce noeud cible est donc désactivé. Then, the next event is the closing tag event c 415. This event is received by the target node c. This event marks the end of the activation context of the target node a. This target node is therefore disabled.

De plus, le noeud solution et est supprimé. En effet, il n'y a pas d'élément a dont l'élément c qu'il représente est l'ancêtre et comme le contexte d'activation du noeud cible a est terminé, il n'est plus possible de trouver un tel élément a . L'événement suivant est l'événement balise ouvrante c 420. Cet événement est reçu par le noeud cible c et le noeud cible a est activé avec un contexte d'activation correspondant à l'ensemble des noeuds descendant de cet élément c . En outre, un noeud solution c2 est créé et associé au noeud solution r en tant que fils de ce noeud. In addition, the solution node and is deleted. Indeed, there is no element a whose element c which it represents is the ancestor and as the context of activation of the target node a is finished, it is not any more possible to find such a element a. The next event is the opening tag event c 420. This event is received by the target node c and the target node a is activated with an activation context corresponding to the set of nodes descending from this element c. In addition, a solution node c2 is created and associated with the solution node r as the child of this node.

Ensuite, l'événement suivant est l'événement balise ouvrante a 425. Cet événement est reçu par le noeud cible a . Le noeud cible b est activé avec un contexte d'activation correspondant à l'ensemble des noeuds enfant de cet élément a . En outre, le contexte d'activation du noeud cible a est augmenté par l'ensemble des noeuds enfant de cet élément a . Then, the next event is the opening tag event at 425. This event is received by the target node a. The target node b is activated with an activation context corresponding to all the child nodes of this element a. In addition, the activation context of the target node a is increased by the set of child nodes of this element a.

L'événement a est transmis aux deux noeuds logiques a 300 et 310 de la Figure 3. Le premier noeud logique a 300 utilise cet événement pour créer un noeud solution al . En outre, un noeud solution and1 est créé en tant que fils du noeud solution al et le noeud solution c2 est associé au noeud solution and1 en tant que fils de ce noeud. Event a is passed to both logical nodes at 300 and 310 in Figure 3. The first logical node at 300 uses this event to create a solution node al. In addition, a solution node and1 is created as the son of the solution node al and the solution node c2 is associated with the solution node and1 as the child of this node.

Comme le noeud solution c2 forme un résultat pour le chemin de localisation qu'il constitue, ce résultat est transmis au noeud solution and1 . Toutefois, le noeud solution and1 n'ayant la connaissance que de la valeur d'un seul de ses opérandes, il ne peut être évalué. Le deuxième noeud logique a 310 ignore cet événement, puisqu'il 30 ne correspond pas à un élément a fils d'un autre élément a pour lequel un noeud solution existe. Since the solution node c2 forms a result for the location path that it constitutes, this result is transmitted to the solution node and1. However, since the solution node has only the knowledge of the value of one of its operands, it can not be evaluated. The second logical node 310 ignores this event since it does not correspond to a child element of another element a for which a solution node exists.

L'événement suivant est l'événement balise vide b 430. Cet événement est reçu par le noeud cible b . Un noeud solution b1 est créé, fils du noeud solution and1 pour représenter cet élément b . Un autre noeud solution 2-1 est créé fils de ce noeud b1 , représentant le prédicat [2] et correspondant au noeud logique 2 340. Etant donné que le prédicat du noeud solution b1 est évalué à faux, ces deux noeuds nouvellement créés, à savoir b1 et 2-1 , ne peuvent participer à une solution de l'expression XPath et sont donc supprimés. L'événement suivant est l'événement balise vide a 435. Cet événement est reçu par le noeud cible a et l'événement a est transmis aux deux noeuds logiques a 300 et 310. Le premier noeud logique, le noeud 300 de la Figure 3, utilise cet événement pour créer un noeud solution a2 , avec son noeud solution fils and2 . Le noeud solution c2 est associé à and2 en tant que fils de ce noeud. The next event is the empty tag event b 430. This event is received by the target node b. A solution node b1 is created, son of the solution node and1 to represent this element b. Another solution node 2-1 is created son of this node b1, representing the predicate [2] and corresponding to the logical node 2340. Since the predicate of the solution node b1 is evaluated to false, these two newly created nodes, know b1 and 2-1, can not participate in a solution of the expression XPath and are therefore deleted. The next event is the empty tag event at 435. This event is received by the target node a and the event a is transmitted to the two logical nodes at 300 and 310. The first logical node, the node 300 of Figure 3 , uses this event to create a solution node a2, with its solution node son and2. The solution node c2 is associated with and2 as the child of this node.

Toutefois, comme l'élément a est vide et qu'il ne peut donc avoir de sous-élément fils b , ces deux noeuds solutions sont immédiatement supprimés. Le deuxième noeud logique a , à savoir le noeud 310 de la Figure 3 crée un noeud solution a3 , fils du noeud solution a1 . Ce noeud solution 20 a3 est un résultat possible pour l'expression XPath. Toutefois, étant donné que l'ensemble des prédicats de al n'est pas encore vérifié, le noeud solution a3 ne peut être retourné comme résultat à ce moment de l'évaluation. La Figure 5 représente les noeuds solutions créés après le traitement 25 de l'événement correspondant à la balise vide a 435. Il est à noter que pour chaque noeud solution créé, l'algorithme mémorise les contextes de recherche de noeuds solutions fils représentant des éléments du document XML. La Figure 6 représente le contexte nommé ctx-b dans la Figure 5 30 correspondant au contexte de recherche pour des noeuds solutions correspondant à des éléments b fils de l'élément a présent en référence 425 de la Figure 4. Il s'agit, en fait, des éléments permettant de vérifier la partie de prédicat b[2] de l'expression XPath 10 de la Figure 1. La Figure 7 représente le contexte nommé ctx-c dans la Figure 5 correspondant au contexte de recherche pour des noeuds solutions correspondant à des éléments c ancêtre de l'élément a présent en référence 425 de la Figure 4. II s'agit, en fait, des éléments permettant de vérifier la partie du prédicat ancestor::c de l'expression XPath 10 de la Figure 1. De retour à la Figure 4, l'événement suivant l'événement 435 est l'événement balise vide b 440. Cet événement est reçu par le noeud cible b et un noeud solution b2 est créé, fils du noeud solution and1 . Un autre noeud solution 2-2 est créé fils de ce noeud b2 . Etant donné que le prédicat du noeud solution b2 est vérifié, un résultat est généré pour le chemin de localisation qu'il représente. However, since element a is empty and therefore can not have child sub-element b, these two solution nodes are immediately deleted. The second logical node, that is, the node 310 of Figure 3 creates a solution node a3, the son of the solution node a1. This solution node a3 is a possible result for the XPath expression. However, since the set of predicates of al is not yet verified, the solution node a3 can not be returned as a result at this time of the evaluation. FIG. 5 represents the solution nodes created after the processing of the event corresponding to the empty tag a 435. It should be noted that for each node created solution, the algorithm stores the search contexts of nodes solutions son representing elements the XML document. FIG. 6 represents the context named ctx-b in FIG. 5 corresponding to the search context for solution nodes corresponding to b elements son of the element present at reference 425 of FIG. 4. fact, elements to check the predicate part b [2] of the XPath expression 10 of Figure 1. Figure 7 represents the context named ctx-c in Figure 5 corresponding to the search context for corresponding solution nodes to elements c ancestor of the element present at reference 425 of FIG. 4. These are, in fact, elements making it possible to verify the part of the ancestor :: c predicate of the XPath expression of FIG. Returning to Figure 4, the event following event 435 is the empty beacon event b 440. This event is received by the target node b and a solution node b2 is created, sons of the solution node and1. Another solution node 2-2 is created son of this node b2. Since the predicate of the solution node b2 is verified, a result is generated for the location path that it represents.

Ce résultat est transmis au noeud solution and1 , qui peut être entièrement évalué à vrai . Ce résultat d'évaluation est transmis au noeud solution al . L'ensemble des prédicats du chemin constitué par les noeuds solutions al et a3 étant vérifié, le résultat représenté par a3 peut 20 maintenant être retourné. En outre, le noeud solution a3 est supprimé. En effet, le résultat représenté par ce noeud a été retransmis, il n'est donc plus nécessaire de le conserver. D'autre part, les noeuds solutions and1 et b2 sont supprimés, ces derniers ayant été complètement évalués et ne pouvant servir à d'autres 25 évaluations. Par contre, le noeud solution c2 est conservé. En effet, il peut prendre part à d'éventuelles autres solutions, notamment s'il y a d'autres éléments a dans la suite du document XML. L'ensemble des événements suivants est traité de manière similaire, 30 servant principalement à supprimer les noeuds solutions restants. II est maintenant décrit, en référence à la Figure 8, l'organigramme général d'évaluation d'une expression conformément à l'invention. This result is passed to the solution node and1, which can be fully evaluated to true. This evaluation result is transmitted to the solution node al. Since all the predicates of the path constituted by the solution nodes al and a3 are verified, the result represented by a3 can now be returned. In addition, the solution node a3 is deleted. Indeed, the result represented by this node has been retransmitted, it is therefore no longer necessary to keep it. On the other hand, the solution nodes and1 and b2 are deleted, the latter having been fully evaluated and not suitable for other evaluations. On the other hand, the solution node c2 is preserved. Indeed, it can take part in possible other solutions, especially if there are other elements in the following XML document. The following set of events is treated in a similar manner, mainly serving to delete the remaining solution nodes. The general flowchart for evaluating an expression according to the invention is now described with reference to FIG.

Tel que décrit précédemment, un fichier XML 800 est traité par un parseur SAX afin de générer des événements décrivant les données contenues dans le fichier XML. Ces événements sont filtrés par un filtre d'événements 810 à partir des noeuds cibles générés à partir de l'expression XPath. Les événements ayant passé le filtre d'événements 810 sont ensuite utilisés par l'évaluateur de solutions 820 pour créer des solutions potentielles à l'expression XPath, notamment à l'aide de la représentation logique de l'expression XPath. Enfin, les solutions potentielles entièrement vérifiées génèrent des résultats 830. Il est à noter que ces différents processus peuvent être exécutés simultanément. Ainsi, dès qu'une solution potentielle est entièrement vérifiée, le résultat correspondant peut être généré immédiatement. Il est maintenant décrit, en référence à la figure 9, les différentes 15 étapes de traitement d'une expression XPath pour générer les noeuds cibles et la représentation logique correspondant à cette expression. L'algorithme débute à l'étape 900 par l'obtention de l'expression XPath. Selon un mode de réalisation, l'expression XPath est obtenue sous 20 une forme textuelle. L'étape suivante (étape 910) consiste à analyser cette expression préalablement à son traitement. Lors de cette analyse, une représentation interne de l'expression XPath à traiter est générée. Selon un mode de réalisation, cette analyse est réalisée de manière classique à l'aide d'un 25 analyseur lexical et d'un analyseur syntaxique. L'algorithme se poursuit à l'étape 920 au cours de laquelle, à partir de cette représentation interne, les noeuds cibles correspondant à l'expression XPath sont générés. Pour ce faire, l'expression XPath est analysée. 30 Ainsi, pour chaque unité lexicale de type étape de localisation ( location step en terminologie anglo-saxonne), un noeud cible est créé. As previously described, an XML file 800 is processed by a SAX parser to generate events describing the data contained in the XML file. These events are filtered by an event filter 810 from the target nodes generated from the XPath expression. The events that passed the event filter 810 are then used by the solution evaluator 820 to create potential solutions to the XPath expression, including using the logical representation of the XPath expression. Finally, the fully verified potential solutions generate results 830. It should be noted that these different processes can be executed simultaneously. Thus, as soon as a potential solution is fully verified, the corresponding result can be generated immediately. It is now described, with reference to FIG. 9, the different steps of processing an XPath expression to generate the target nodes and the logical representation corresponding to this expression. The algorithm starts at step 900 by obtaining the XPath expression. According to one embodiment, the XPath expression is obtained in a textual form. The next step (step 910) consists in analyzing this expression before it is processed. During this analysis, an internal representation of the XPath expression to be processed is generated. According to one embodiment, this analysis is performed in a conventional manner using a lexical analyzer and a parser. The algorithm continues in step 920 in which, from this internal representation, the target nodes corresponding to the XPath expression are generated. To do this, the XPath expression is analyzed. Thus, for each lexical unit of the location step type (location step in English terminology), a target node is created.

Un noeud cible correspond au test de noeud contenu dans l'étape de localisation. En outre, un noeud cible est créé pour représenter la racine de la recherche. Selon le type d'expression XPath, la racine de la recherche est soit 5 la racine du document XML, soit l'élément courant du document XML. Si deux noeuds cibles identiques sont créés, alors ils sont regroupés en un unique élément. Les relations entre les différentes étapes de localisation sont analysées et mémorisées dans des liens entre les différents noeuds cibles. 10 Pour deux étapes de localisation successives d'un même chemin de localisation, la relation correspond à la relation de filiation vers la deuxième étape de localisation. Dans les autres cas, la relation dépend de la relation de filiation de l'une des étapes de localisation et de la sémantique de la sous-expression 15 élémentaire XPath reliant les deux étapes de localisation. Ainsi, pour une étape de localisation présente dans un prédicat d'une autre étape de localisation, la relation entre ces deux étapes correspond à la relation de filiation de l'étape de localisation située dans le prédicat. Les liens entre les différents noeuds cibles sont créés dans un ordre 20 correspondant à l'ordre du document XML. De cette manière, si un noeud cible c est un ancêtre d'un noeud cible a , un lien est créé du noeud cible c vers le noeud cible a . D'autre part, si un noeud cible n'a aucun lien incident, alors un lien entre le noeud cible représentant la racine et ce noeud cible est créé. 25 L'algorithme se poursuit à l'étape 930 consistant à générer une représentation logique correspondant à l'expression XPath à partir de la représentation interne préalablement générée. Pour ce faire, l'expression XPath est analysée. Chaque unité lexicale de l'expression est représentée par un noeud 30 logique dans un arbre, les liens entre les noeuds logiques correspondant aux relations sémantiques entre les unités lexicales. Ainsi, l'ensemble de l'arbre représente l'expression XPath dans son ensemble. A target node corresponds to the node test contained in the location step. In addition, a target node is created to represent the root of the search. Depending on the type of XPath expression, the root of the search is either the root of the XML document or the current element of the XML document. If two identical target nodes are created, then they are grouped into a single element. The relationships between the different location steps are analyzed and stored in links between the different target nodes. For two successive location steps of the same location path, the relation corresponds to the relationship of descent to the second location step. In other cases, the relationship depends on the parentage relationship of one of the location steps and the semantics of the XPath elementary subexpression connecting the two location steps. Thus, for a locating step present in a predicate of another locating step, the relationship between these two steps corresponds to the parentage relation of the locating step located in the predicate. The links between the different target nodes are created in an order corresponding to the order of the XML document. In this way, if a target node c is an ancestor of a target node a, a link is created from the target node c to the target node a. On the other hand, if a target node has no incident link, then a link between the target node representing the root and this target node is created. The algorithm continues in step 930 of generating a logical representation corresponding to the XPath expression from the previously generated internal representation. To do this, the XPath expression is analyzed. Each lexical unit of the expression is represented by a logical node in a tree, the links between the logical nodes corresponding to the semantic relations between the lexical units. Thus, the whole tree represents the XPath expression as a whole.

En outre, chaque noeud logique représentant une unité lexicale de type étape de localisation est relié au noeud cible correspondant. De cette manière, un noeud cible transmet les événements qu'il filtre aux noeuds logiques qui vont à leur tour traiter cette information pour évaluer l'expression XPath. In addition, each logical node representing a locating step type lexical unit is connected to the corresponding target node. In this way, a target node transmits the events it filters to the logical nodes that in turn process that information to evaluate the XPath expression.

II est maintenant décrit, en référence à la Figure 10, un algorithme d'évaluation d'une expression XPath sur un document XML conformément à l'invention. Cet algorithme est précédé par l'exécution de l'algorithme décrit en référence à la Figure 9 afin de créer les différentes structures nécessaires à l'évaluation de l'expression XPath. Toutefois, une seule exécution de l'algorithme décrit en référence à la Figure 9 est nécessaire pour ensuite évaluer une pluralité de fois une même expression XPath. L'algorithme de la Figure 10 débute par l'étape 1000 au cours de 15 laquelle un document XML est obtenu. Le document XML peut être lu depuis un fichier, reçu à partir d'un réseau de télécommunications ou fourni de toute autre manière à l'algorithme. Pour traiter le document XML, un parseur génère des événements aptes à représenter le document XML. 20 Des parseurs connus sont par exemple un parseur de type SAX ou un parseur de type pull. Toutefois, un parseur de type DOM peut être utilisé par itération sur les noeuds XML créés par ce parseur pour générer les événements XML. Les différentes étapes de l'algorithme traitent successivement 25 l'ensemble des événements décrivant le document XML. Ainsi, l'étape 1000 est suivie de l'étape 1010 au cours de laquelle un premier événement XML e est obtenu. Lors de cette étape 1010, le contexte courant est aussi mis à jour. Le contexte courant représente la position courante du parseur XML dans le 30 document XML. Il correspond donc à la position de l'événement e au sein du document XML. It is now described, with reference to FIG. 10, an algorithm for evaluating an XPath expression on an XML document according to the invention. This algorithm is preceded by the execution of the algorithm described with reference to FIG. 9 in order to create the different structures necessary for evaluating the XPath expression. However, a single run of the algorithm described with reference to Figure 9 is necessary to then evaluate a plurality of times the same XPath expression. The algorithm of Figure 10 begins with step 1000 during which an XML document is obtained. The XML document can be read from a file, received from a telecommunications network, or otherwise provided to the algorithm. To process the XML document, a parser generates events that can represent the XML document. Known parsers are, for example, a SAX type parser or a pull type parser. However, a DOM parser can be used by iteration on the XML nodes created by this parser to generate the XML events. The different steps of the algorithm successively process all the events describing the XML document. Thus, step 1000 is followed by step 1010 in which a first XML event e is obtained. During this step 1010, the current context is also updated. The current context represents the current position of the XML parser in the XML document. It therefore corresponds to the position of the event e within the XML document.

Ensuite, l'algorithme se poursuit à l'étape 1020 consistant à rechercher un noeud cible c correspondant à cet événement e . Pour ce faire, l'ensemble des noeuds cibles de l'expression XPath est parcouru et l'événement e reçu est comparé au test de noeud représenté par le noeud cible. Si l'événement e vérifie le test de noeud, alors le noeud cible correspond à cet événement e . II est à noter que dans le cas d'un élément correspondant à un noeud cible, alors l'événement représentant la balise ouvrante de cet élément et 10 l'événement représentant la balise fermante de cet élément correspondent à cette cible. L'événement représentant la balise ouvrante est nécessaire pour décrire l'existence de l'élément correspondant. De plus, l'événement représentant la balise fermante est nécessaire 15 pour décrire la fin de l'élément et permettre, d'une part, l'évaluation de certaines fonctions, par exemple le comptage du nombre d'enfants de cet élément, et d'autre part, la mise à jour de certaines solutions potentielles. Par exemple, un prédicat portant sur les enfants d'un élément est entièrement évalué lorsque l'événement représentant la balise fermante de l'élément est reçu. Ainsi, lors de 20 la réception de cet événement, le résultat de l'évaluation peut être propagé vers le reste de la solution potentielle. A titre de variante, si un noeud cible c correspondant à cet événement e est trouvé et si cet événement e correspond à une balise ouvrante d'élément, alors les noeuds cibles liés au noeud cible c par un lien 25 incident voient leurs contextes d'activation mis à jour. Pour réaliser cette mise à jour, pour chacun de ces noeuds cibles, un nouveau contexte d'activation est créé, à partir du contexte courant et en fonction du lien de filiation entre le noeud cible c et le noeud cible traité. L'algorithme se poursuit à l'étape 1030 au cours de laquelle on teste 30 si un noeud cible c correspondant à l'événement e existe. A titre de variante, l'étape 1030 teste, en plus de l'existence d'un noeud cible c correspondant à l'événement e , Si ce noeud cible c est actif. Un noeud cible c est actif si l'un des contextes d'activation du noeud cible c contient le contexte courant. Si tel est le cas, alors l'algorithme se poursuit à l'étape 1040 consistant à transmettre l'événement e aux noeuds associés au noeud cible c . Cette étape est décrite en détail ci-après en référence à la Figure 11. L'étape 1040 est suivie de l'étape 1050. De même, si le test de l'étape 1030 est négatif, alors l'étape 1030 est suivie de l'étape 1050. Au cours de l'étape 1050, on vérifie les contextes de recherche 10 associés aux différents noeuds solutions existant. Ainsi, si le contexte courant n'appartient plus à un contexte de recherche et ne peut plus y appartenir, alors l'évaluation du noeud solution concerné est mise à jour et le résultat de cette évaluation est propagé tel que décrit ci-après en référence à l'étape 1120 de la Figure 11. 15 A titre de variante, l'étape 1050 met aussi à jour les contextes d'activation des noeuds cibles. Pour chaque noeud cible et pour chacun de ses contextes d'activation, l'étape 1050 vérifie que le contexte courant est situé avant la fin de ce contexte d'activation (c'est-à-dire que soit le contexte courant est contenu dans le contexte d'activation, soit le contexte courant pourra être 20 contenu dans le contexte d'activation). Si ce n'est pas le cas, ce contexte d'activation est supprimé. Lors de l'étape suivante (étape 1060), on vérifie s'il reste d'autres événements décrivant le document XML à traiter. Si tel est le cas, alors l'algorithme se poursuit à l'étape 1010 25 précédemment décrite consistant à obtenir l'événement suivant. Dans le cas contraire, il est mis fin à l'algorithme à l'étape 1070. II est maintenant décrit, en référence à la Figure 11, un algorithme de construction des résultats à partir des événements filtrés par les cibles conformément à l'invention. 30 Cet algorithme débute par le traitement effectué sur les événements correspondant à un début d'item XML ou à une fin d'item XML. Then, the algorithm continues at step 1020 of searching for a target node c corresponding to this event e. To do this, the set of target nodes of the XPath expression is traversed and the event e received is compared to the node test represented by the target node. If the event e checks the node test, then the target node corresponds to this event e. It should be noted that in the case of an element corresponding to a target node, then the event representing the opening tag of this element and the event representing the closing tag of this element correspond to this target. The event representing the opening tag is necessary to describe the existence of the corresponding element. In addition, the event representing the closing tag is necessary to describe the end of the element and allow, on the one hand, the evaluation of certain functions, for example the counting of the number of children of this element, and on the other hand, the updating of some potential solutions. For example, a predicate on the children of an element is fully evaluated when the event representing the closing tag of the element is received. Thus, upon receipt of this event, the result of the evaluation may be propagated to the rest of the potential solution. Alternatively, if a target node c corresponding to this event e is found and if this event e corresponds to an element start tag, then the target nodes linked to the target node c by an incident link see their contexts. activation updated. To carry out this update, for each of these target nodes, a new activation context is created, based on the current context and according to the filiation link between the target node c and the target node processed. The algorithm continues in step 1030 in which one tests 30 if a target node c corresponding to the event e exists. As a variant, the step 1030 tests, in addition to the existence of a target node c corresponding to the event e, that this target node c is active. A target node c is active if one of the activation contexts of the target node c contains the current context. If so, then the algorithm proceeds to step 1040 of transmitting the event e to the nodes associated with the target node c. This step is described in detail hereinafter with reference to FIG. 11. Step 1040 is followed by step 1050. Similarly, if the test of step 1030 is negative, then step 1030 is followed by step 1050. In step 1050, the search contexts associated with the different existing solution nodes are checked. Thus, if the current context no longer belongs to a search context and can no longer belong to it, then the evaluation of the solution node concerned is updated and the result of this evaluation is propagated as described below with reference in step 1120 of Figure 11. Alternatively, step 1050 also updates the activation contexts of the target nodes. For each target node and for each of its activation contexts, step 1050 verifies that the current context is located before the end of this activation context (i.e., the current context is contained in the activation context, the current context may be contained in the activation context). If this is not the case, this activation context is deleted. In the next step (step 1060), it is checked whether there are other events describing the XML document to be processed. If so, then the algorithm proceeds to the previously described step 1010 of obtaining the next event. In the opposite case, the algorithm is terminated at step 1070. It is now described, with reference to FIG. 11, an algorithm for constructing the results from the events filtered by the targets according to the invention. . This algorithm starts with the processing performed on the events corresponding to an XML item start or an XML item end.

Il s'applique donc, en particulier, aux événements générés à partir du document XML représentant une balise ouvrante ou une balise fermante. Concernant les autres événements, par exemple un contenu textuel ou un commentaire, l'algorithme est exécuté deux fois de manière consécutive, la première pour signifier le début de l'item, la seconde pour signifier sa fin. Selon un mode de réalisation particulier, pour l'ensemble des événements représentant un item XML complet, les deux parties de cet algorithme correspondant au traitement du début de l'item et de la fin de l'item sont combinées en un algorithme réalisant l'ensemble des étapes contenues dans ces deux parties. Lors de la mise en oeuvre de l'algorithme décrit en référence à la Figure 11, l'événement e à traiter a été sélectionné au moyen d'un noeud cible c lors des étapes 1020 et 1030 de la Figure 10 et est associé à un noeud logique r lors de l'étape 1040 de la Figure 10. It therefore applies, in particular, to events generated from the XML document representing an opening tag or a closing tag. For other events, for example a textual content or a comment, the algorithm is executed twice consecutively, the first to signify the beginning of the item, the second to signify its end. According to a particular embodiment, for the set of events representing a complete XML item, the two parts of this algorithm corresponding to the processing of the beginning of the item and the end of the item are combined into an algorithm realizing the set of steps contained in these two parts. When implementing the algorithm described with reference to FIG. 11, the event e to be treated was selected by means of a target node c during the steps 1020 and 1030 of FIG. 10 and is associated with a logical node r in step 1040 of Figure 10.

En outre, si le noeud cible c est associé à plusieurs noeuds logiques, alors cet algorithme est mis en oeuvre pour chacun de ces noeuds logiques. L'algorithme débute à l'étape 1100 consistant à tester si l'événement e traité est un événement de début d'item ou un événement de fin d'item. In addition, if the target node c is associated with several logical nodes, then this algorithm is implemented for each of these logical nodes. The algorithm starts at step 1100 of testing whether the processed event e is an item start event or an item end event.

Si l'événement est un événement de début d'item, alors l'algorithme se poursuit à l'étape 1105 de création d'un noeud solution n pour représenter l'item. Ce noeud solution mémorise l'item représenté et sa position dans le document XML. If the event is an item start event, then the algorithm proceeds to step 1105 of creating a solution node n to represent the item. This solution node stores the item represented and its position in the XML document.

En outre, si le noeud logique r est relié à d'autres noeuds logiques descendant de ce noeud logique r dans la représentation logique et représentant des fonctions ou des opérateurs, alors un noeud solution est créé pour chacun de ces noeuds logiques. Ces noeuds solutions nouvellement créés sont reliés au noeud solution n . In addition, if the logical node r is connected to other logical nodes descending from this logical node r in the logical representation and representing functions or operators, then a solution node is created for each of these logical nodes. These newly created solution nodes are connected to the solution node n.

De plus, pour chacun des chemins de localisation qui est fils de l'un des noeuds solutions créés, le contexte de recherche pour ce chemin de localisation est mémorisé. Ce contexte de recherche est notamment fonction du noeud solution n et de la relation de filiation reliant le noeud solution au chemin de localisation. Ce contexte de recherche permet, par exemple, de déterminer la fin de la recherche de solutions pour le chemin de localisation considéré. In addition, for each of the location paths that is the child of one of the created solution nodes, the search context for this location path is stored. This search context is in particular a function of the solution node n and the filiation relation connecting the solution node to the location path. This search context makes it possible, for example, to determine the end of the search for solutions for the location path considered.

Ainsi, dans l'exemple illustré en Figures 1 à 7, lorsqu'un événement correspondant à un élément a associé au noeud logique 300 est traité, un noeud solution est créé pour représenter cet élément a et un autre noeud solution est créé pour représenter l'opérateur and décrit par le noeud logique 320. Par contre, lorsqu'un événement correspondant à un élément c associé au noeud logique 350 est traité, alors seul le noeud solution représentant l'élément c est créé. En outre, lorsque cet élément a est créé, un contexte de recherche est créé pour les noeuds solutions associés au noeud logique 310, ctx-a . Ce contexte de recherche est associé au noeud solution représentant cet élément a . Deux autres contextes de recherche sont créés pour le noeud solution représentant l'opérateur and , le premier contexte correspondant aux noeuds solutions associés au noeud logique ctx-b référencé 330 en Figure 3, le second contexte correspondant aux noeuds solutions associés au noeud logique ctx-c référencé 340 en Figure 3. Le contexte de recherche ctx-c a été entièrement exploré, ainsi aucun noeud solution c pouvant être relié au noeud solution a ne peut plus être trouvé. S'il n'existe pas encore de noeud solution c pouvant être relié au noeud solution a , le noeud solution a ne peut être intégré à une solution de l'expression XPath, il peut donc être détruit immédiatement. L'algorithme se poursuit par la recherche de noeuds solutions liés à l'un de ces noeuds solutions nouvellement créés. On considère que deux noeuds solutions sont liés s'ils vérifient deux conditions : d'une part, ils doivent correspondre à des noeuds logiques de l'expression reliés entre eux et, d'autre part, la relation entre ces deux noeuds solutions doit correspondre à la relation sémantique entre les noeuds logiques. Thus, in the example illustrated in FIGS. 1 to 7, when an event corresponding to an element associated with the logical node 300 is processed, a solution node is created to represent this element a and another solution node is created to represent the However, when an event corresponding to an element c associated with the logic node 350 is processed, then only the solution node representing the element c is created. In addition, when this element is created, a search context is created for the solution nodes associated with the logical node 310, ctx-a. This search context is associated with the solution node representing this element a. Two other search contexts are created for the solution node representing the operator and, the first context corresponding to the solution nodes associated with the logical node ctx-b referenced 330 in Figure 3, the second context corresponding to the solution nodes associated with the logical node ctx- c referenced 340 in Figure 3. The search context ctx-c has been fully explored, so no solution node c can be connected to the solution node a can no longer be found. If there is not yet a solution node c that can be connected to the solution node a, the solution node a can not be integrated into a solution of the XPath expression, it can be destroyed immediately. The algorithm continues by searching for solution nodes linked to one of these newly created solution nodes. We consider that two solution nodes are linked if they satisfy two conditions: on the one hand, they must correspond to logical nodes of the expression connected to each other and, on the other hand, the relation between these two solution nodes must correspond to the semantic relation between the logical nodes.

Ainsi, dans l'exemple considéré en Figures 1 à 7, lorsque l'événement correspondant à l'élément b illustré en référence 430 de la Figure 4, associé au noeud logique 330 de la Figure 3, est traité, le noeud solution représentant cet événement est lié au noeud solution représentant le noeud logique 320 de la Figure 3 associé au noeud solution représentant l'élément a référencé en 425 de la Figure 4 associé au noeud logique 300 de la Figure 3. En effet, les noeuds logiques 300 et 330 de la Figure 3 sont reliés par une relation de filiation de type enfant ( child selon la spécification XPath), ce qui correspond effectivement à la relation entre les deux éléments b (430) et a (425). Par contre, le noeud solution représentant cet élément b (430) associé au noeud logique 330 de la Figure 3 n'est pas lié au noeud solution représentant l'élément a référencé en 435 de la Figure 4 associé au noeud logique 300 de la Figure 3. En effet, l'élément b (430) n'est pas le fils de l'élément a (435). L'étape 1105 décrite précédemment est suivie de l'étape 1110 consistant à tester s'il existe un noeud solution I lié à un noeud solution m parmi les nouveaux noeuds solutions créés lors de l'étape 1105. Thus, in the example considered in FIGS. 1 to 7, when the event corresponding to the element b illustrated with reference 430 of FIG. 4, associated with the logical node 330 of FIG. 3, is processed, the solution node representing this event is linked to the solution node representing the logical node 320 of Figure 3 associated with the solution node representing the element a referenced at 425 of Figure 4 associated with the logical node 300 of Figure 3. In fact, the logical nodes 300 and 330 of Figure 3 are related by a child-type relationship (child according to the XPath specification), which effectively corresponds to the relationship between the two elements b (430) and a (425). On the other hand, the solution node representing this element b (430) associated with the logical node 330 of FIG. 3 is not linked to the solution node representing the element a referenced at 435 of FIG. 4 associated with the logical node 300 of FIG. 3. Indeed, the element b (430) is not the son of the element a (435). Step 1105 described above is followed by step 1110 of testing whether there is a solution node I linked to a solution node m among the new solution nodes created in step 1105.

Dans la négative, il est mis fin à l'algorithme à l'étape 1190. Dans le cas contraire, l'algorithme se poursuit à l'étape 1115 consistant à relier le noeud solution I au noeud solution m . L'étape 1115 est suivie de l'étape 1120 consistant à propager l'évaluation. If not, the algorithm is terminated at step 1190. Otherwise, the algorithm proceeds to step 1115 of connecting the solution node I to the solution node m. Step 1115 is followed by step 1120 of propagating the evaluation.

La propagation de l'évaluation consiste à vérifier si l'événement reçu permet d'avancer dans l'évaluation de l'expression XPath. Plusieurs cas se présentent pour la propagation de l'évaluation, en fonction du type du noeud logique correspondant au noeud solution m . Dans un premier cas, le noeud logique correspondant au noeud solution m est une étape de localisation. Dans un deuxième cas, le noeud logique correspondant au noeud solution m ne représente pas une étape de localisation. 28 The propagation of the evaluation consists of checking whether the received event makes it possible to advance in the evaluation of the XPath expression. Several cases arise for the propagation of the evaluation, depending on the type of the logical node corresponding to the solution node m. In a first case, the logical node corresponding to the solution node m is a location step. In a second case, the logical node corresponding to the solution node m does not represent a location step. 28

Si le noeud logique correspondant au noeud solution m représente une étape de localisation, alors l'algorithme vérifie s'il existe une solution complète pour ce chemin de localisation. Pour ce faire, on vérifie s'il existe un ensemble de noeuds solutions 5 liés entre eux et correspondant aux différentes étapes du chemin de localisation. A chaque étape du chemin de localisation doit correspondre un et un seul noeud solution dans l'ensemble de noeuds solutions. Toutefois, plusieurs ensembles de noeuds solutions peuvent être testés pour couvrir l'ensemble des 10 noeuds solutions correspondant à chaque étape du chemin de localisation. En outre, pour chaque noeud solution de cet ensemble, il est vérifié que l'ensemble des prédicats associés à ce noeud solution sont évalués positivement. Pour chaque solution complète ainsi trouvée, il est généré un résultat 15 pour le chemin de localisation. Lors de la génération des résultats, il est vérifié que les résultats ne sont générés qu'une seule fois et qu'ils sont générés dans l'ordre approprié. Il est à noter qu'un résultat peut être généré par deux ensembles de noeuds solutions différents. 20 Ainsi, après la création du noeud solution associé au noeud logique 310 de la figure 3 représentant l'élément a référencé en 435 dans la Figure 4, il est vérifié s'il existe un noeud solution associé au noeud logique 300 lié à ce premier noeud solution. Dans l'exemple considéré, il existe un tel noeud solution, c'est le 25 noeud solutionreprésentant l'élément a référencé en 425 de la Figure 4. Ainsi, pour chacune des étapes du chemin de localisation, il existe un noeud solution correspondant à cette étape. En outre, il est vérifié si le prédicat de ce deuxième noeud solution est vérifié. Dans l'exemple considéré, un seul élément b fils de l'élément 30 a référencé en 425 de la Figure 4 a été trouvé à ce moment là, le prédicat n'est donc pas vérifié. Par conséquence, dans l'exemple considéré, il n'existe pas de solution complète pour le chemin de localisation. Aucun résultat pour ce chemin de localisation ne peut donc être retourné. Dans le cas où le résultat généré pour un chemin de localisation ne correspond pas à l'expression principale de l'expression XPath évaluée, alors ce résultat est propagé vers les noeuds solutions parents de la solution complète ayant généré le résultat. Il s'agit des noeuds solutions parent du noeud solution de la première étape du chemin de localisation appartenant à la solution complète. En outre, ce résultat est mémorisé au niveau de la première étape du chemin de localisation appartenant à la solution complète pour pouvoir être utilisé ultérieurement par de nouveaux noeuds solutions reliés à ce chemin de localisation. Chaque noeud solution parent est alors réévalué en prenant en compte ce nouveau résultat. Deux cas peuvent se présenter. Selon un premier cas, l'évaluation du noeud solution parent est 15 terminée. Le résultat de cette évaluation est alors retransmis de la même façon aux noeuds solutions parents de ce noeud solution parent. Selon un second cas, l'évaluation du noeud solution parent n'est pas terminée et aucune autre action n'est effectuée au niveau de ce noeud solution parent. 20 L'évaluation d'un noeud solution après la réception d'un résultat dépend du type d'élément de l'expression XPath représenté par ce noeud solution. S'il s'agit d'une étape de localisation, l'algorithme vérifie s'il existe une solution complète pour ce chemin de localisation comme décrit précédemment. Dans un tel cas, le résultat correspond à l'évaluation d'un prédicat de cette 25 étape de localisation et peut donc permettre de trouver une solution complète pour le chemin de localisation auquel appartient cette étape de localisation. S'il s'agit d'une fonction, l'algorithme tente d'évaluer la fonction. Pour ce faire, il est vérifié si l'ensemble des données nécessaires à l'évaluation de la fonction a été reçu. Dans ce but, le contexte de recherche lié à ce noeud 30 solution est utilisé pour déterminer si l'ensemble des données constituant les arguments de la fonction est connu ou non. II est à noter que certaines fonctions peuvent être évaluées même si certains de leurs arguments ne sont pas encore entièrement connus. Si l'ensemble des données nécessaires à l'évaluation de la fonction a été reçu, la fonction est évaluée. Dans le cas contraire, le résultat ou une partie du résultat est mémorisé afin de pouvoir évaluer ultérieurement la fonction. If the logical node corresponding to the solution node m represents a location step, then the algorithm checks whether there is a complete solution for this location path. To do this, it is checked whether there exists a set of solution nodes 5 linked together and corresponding to the different steps of the location path. At each step of the location path must correspond one and only one solution node in the set of solution nodes. However, several sets of solution nodes can be tested to cover all 10 solution nodes corresponding to each step of the location path. In addition, for each solution node of this set, it is verified that all the predicates associated with this solution node are evaluated positively. For each complete solution thus found, a result is generated for the location path. When generating the results, it is verified that the results are generated only once and that they are generated in the appropriate order. It should be noted that a result can be generated by two sets of different solution nodes. Thus, after the creation of the solution node associated with the logical node 310 of FIG. 3 representing the element a referenced at 435 in FIG. 4, it is checked whether there exists a solution node associated with the logical node 300 linked to this first node. node solution. In the example considered, there exists such a solution node, it is the solution node representing the element referenced at 425 of FIG. 4. Thus, for each of the steps of the location path, there exists a solution node corresponding to this step. In addition, it is checked whether the predicate of this second solution node is checked. In the example considered, a single element b son of the element 30 referenced at 425 of Figure 4 was found at that time, the predicate is not verified. Consequently, in the example considered, there is no complete solution for the location path. No result for this location path can be returned. In the case where the result generated for a location path does not match the primary expression of the evaluated XPath expression, then this result is propagated to the parent solution nodes of the complete solution that generated the result. These are the parent solution nodes of the solution node of the first stage of the location path belonging to the complete solution. In addition, this result is stored at the first step of the location path belonging to the complete solution to be used later by new solution nodes connected to this location path. Each parent solution node is then reevaluated taking into account this new result. Two cases may arise. In a first case, the evaluation of the parent solution node is complete. The result of this evaluation is then retransmitted in the same way to the parent solution nodes of this parent solution node. In a second case, the evaluation of the parent solution node is not completed and no other action is performed at this parent solution node. The evaluation of a solution node after receipt of a result depends on the type of element of the XPath expression represented by this solution node. If it is a location step, the algorithm checks whether there is a complete solution for this location path as previously described. In such a case, the result corresponds to the evaluation of a predicate of this location step and can therefore find a complete solution for the location path to which this location step belongs. If it is a function, the algorithm attempts to evaluate the function. To do this, it is checked whether all the data necessary for the evaluation of the function has been received. For this purpose, the search context related to this solution node is used to determine whether the set of data constituting the arguments of the function is known or not. It should be noted that certain functions can be evaluated even if some of their arguments are not yet fully known. If all the data needed to evaluate the function has been received, the function is evaluated. Otherwise, the result or part of the result is saved so that the function can be evaluated later.

S'il s'agit d'un opérateur, l'algorithme tente d'évaluer l'opérateur. Cette évaluation est réalisée de manière similaire à l'évaluation d'une fonction. Dans ces deux derniers cas, si la fonction ou l'opérateur peut être évalué, le résultat de cette évaluation est transmis aux noeuds solutions parents du noeud solution correspondant à la fonction ou à l'opérateur. Ces noeuds solutions parents sont à leur tour évalués comme décrit précédemment. En outre, le résultat de l'évaluation est mémorisé au niveau du noeud solution correspondant à la fonction ou à l'opérateur pour pouvoir être utilisé ultérieurement. Le deuxième cas pour la propagation de l'évaluation est celui où le noeud logique correspondant au noeud solution m ne représente pas une étape de localisation. Le noeud logique peut ainsi représenter une fonction, ou bien un opérateur. Dans ce cas, l'algorithme tente d'évaluer la fonction ou l'opérateur, comme décrit précédemment. En outre, si la fonction ou l'opérateur peut être évalué, le résultat de cette évaluation est transmis à ses noeuds solutions parents pour propager l'évaluation. L'étape 1120 est suivie de l'étape 1125 consistant à tester si certains résultats générés au cours de l'étape 1120 correspondent à l'expression principale de l'expression XPath évaluée. If it is an operator, the algorithm attempts to evaluate the operator. This evaluation is performed in a similar way to the evaluation of a function. In the latter two cases, if the function or the operator can be evaluated, the result of this evaluation is transmitted to the parent solution nodes of the solution node corresponding to the function or the operator. These parent solution nodes are in turn evaluated as described above. In addition, the evaluation result is stored at the solution node corresponding to the function or the operator for later use. The second case for propagation of the evaluation is that where the logical node corresponding to the solution node m does not represent a location step. The logical node can thus represent a function, or an operator. In this case, the algorithm attempts to evaluate the function or the operator, as previously described. In addition, if the function or operator can be evaluated, the result of this evaluation is transmitted to its parent solution nodes to propagate the evaluation. Step 1120 is followed by step 1125 of testing whether certain results generated in step 1120 correspond to the primary expression of the evaluated XPath expression.

Si tel est le cas, alors l'algorithme se poursuit à l'étape 1130 consistant à retourner ces résultats. L'étape suivante est l'étape 1135. Lors de l'étape 1125, si le test est négatif, alors l'étape suivante est l'étape 1135. Cette étape (étape 1135) consiste à réaliser une mise à jour des noeuds solutions. Pour ce faire, l'algorithme commence par considérer un ensemble de noeuds solutions. Cet ensemble de noeuds solutions comprend les noeuds solutions correspondant à une étape de localisation dont un prédicat a été évalué à faux et les noeuds solutions correspondant à la dernière étape du chemin de localisation du résultat et représentant un événement correspondant à un résultat généré lors de l'étape 1120. If this is the case, then the algorithm proceeds to step 1130 of returning these results. The next step is step 1135. In step 1125, if the test is negative, then the next step is step 1135. This step (step 1135) consists of updating the solution nodes . To do this, the algorithm starts by considering a set of solution nodes. This set of solution nodes comprises the solution nodes corresponding to a location step of which a predicate has been evaluated to false and the solution nodes corresponding to the last step of the location path of the result and representing an event corresponding to a result generated during the first step. step 1120.

L'ensemble des noeuds solutions considérés est ensuite supprimé. Ensuite, sont également supprimés les noeuds solutions ne représentant pas une étape de localisation et descendant de l'un de ces noeuds solutions supprimés, soit directement, soit indirectement par l'intermédiaire d'autres noeuds solutions ne représentant pas une étape de localisation. The set of solution nodes considered is then deleted. Next, the solution nodes that do not represent a step of locating and going down from one of these deleted solution nodes, either directly or indirectly via other solution nodes that do not represent a location step, are also deleted.

Enfin, les descendants de l'un des noeuds solutions précédemment supprimés correspondant à des étapes de localisation sont examinés. Pour chacun de ces noeuds, deux critères sont vérifiés. D'une part, le noeud solution ne doit pas être enfant d'un autre noeud solution existant. D'autre part, le noeud solution ne doit pas pouvoir être enfant d'un futur noeud solution non encore créé. Ce second critère est vérifié, notamment en analysant la relation du noeud logique correspondant au noeud solution avec ses noeuds logique parents. Si ces deux critères sont vérifiés pour un noeud solution, alors ce noeud solution est supprimé et ses éventuels descendants sont à leur tour examinés de la même manière. Finally, the descendants of one of the previously deleted solution nodes corresponding to location steps are examined. For each of these nodes, two criteria are checked. On the one hand, the solution node must not be a child of another existing solution node. On the other hand, the solution node must not be able to be a child of a future solution node not yet created. This second criterion is verified, in particular by analyzing the relationship of the logical node corresponding to the solution node with its parent logical nodes. If these two criteria are checked for a solution node, then this solution node is deleted and any descendants in turn are examined in the same way.

L'algorithme se poursuit ensuite à l'étape 1140 afin de vérifier s'il reste d'autres noeuds liés aux noeuds précédemment créés. Si tel est le cas, alors l'algorithme se poursuit à l'étape 1115 précédemment décrite. Dans le cas contraire, il est mis fin à l'algorithme à l'étape 1190. The algorithm then continues at step 1140 to check if there are other nodes linked to previously created nodes. If this is the case, then the algorithm continues in step 1115 previously described. In the opposite case, the algorithm is terminated at step 1190.

De retour à l'étape 1100, dans le cas où l'événement e correspond à la fin d'un item XML, par exemple à une balise fermante pour un élément XML, l'algorithme se poursuit à l'étape 1150 au cours de laquelle il est recherché s'il existe un noeud solution n correspondant à l'événement e et au noeud logique r . Returning to step 1100, in the case where the event e corresponds to the end of an XML item, for example to a closing tag for an XML element, the algorithm continues at step 1150 during which is searched if there is a solution node n corresponding to the event e and the logical node r.

Si tel n'est pas le cas, alors l'algorithme se termine à l'étape 1190. Si, au contraire, un noeud solution n est trouvé, alors l'algorithme se poursuit à l'étape 1155 consistant à propager l'événement de fin d'item. If this is not the case, then the algorithm ends at step 1190. If, on the contrary, a solution node n is found, then the algorithm proceeds to step 1155 of propagating the event end of item.

La propagation de l'événement de fin d'item consiste à terminer toutes les évaluations qui ne pouvaient l'être avant la fin de cet item. Pour ce faire, l'ensemble des noeuds solutions descendant du noeud solution n est parcouru, et pour chacun de ces noeuds solutions, il est vérifié si l'événement de fin d'item est utile pour l'évaluation de ce noeud solution. Durant cette vérification, le contexte de recherche correspondant à un noeud solution est utilisé pour vérifier si l'événement de fin d'item indique la fin du contexte de recherche et donc la fin de l'évaluation du noeud solution. Si tel est le cas alors l'évaluation est réalisée. Si cette évaluation est terminée, alors elle est propagée comme décrit précédemment. Par exemple, dans le cas d'une expression de type a/b[position() = last()] , l'événement de fin d'élément a permet de calculer la valeur de last() pour cet événement. L'étape 1155 est suivie de l'étape 1160 permettant de tester si des résultats on été générés par la propagation de fin d'item. Cette étape est similaire à l'étape 1125. Si tel est le cas, alors l'algorithme se poursuit à l'étape 1165 au cours de laquelle ces résultats sont retournés. Cette étape est similaire à l'étape 1130. L'étape suivante est l'étape 1170. The propagation of the end-of-item event consists in completing all the evaluations that could not be done before the end of this item. To do this, the set of solution nodes descending from the solution node n is traversed, and for each of these solution nodes, it is checked whether the end of item event is useful for the evaluation of this solution node. During this check, the search context corresponding to a solution node is used to check whether the end of item event indicates the end of the search context and therefore the end of the evaluation of the solution node. If this is the case then the evaluation is carried out. If this evaluation is complete, then it is propagated as previously described. For example, in the case of an expression of type a / b [position () = last ()], the event of end of element a makes it possible to calculate the value of last () for this event. Step 1155 is followed by step 1160 to test whether results have been generated by the end-of-item propagation. This step is similar to step 1125. If so, then the algorithm proceeds to step 1165 in which these results are returned. This step is similar to step 1130. The next step is step 1170.

Si le test de l'étape 1160 est négatif, alors l'algorithme se poursuit à l'étape 1170 de mise à jour des solutions. L'étape 1170 est similaire à l'étape 1135. Toutefois, elle en diffère par l'ensemble de noeuds solutions considérés. En effet, en plus des noeuds solutions correspondant à une étape de localisation dont un prédicat a été évalué à faux et des noeuds solutions correspondant à un résultat généré, dans certains cas le noeud solution n est ajouté à cet ensemble de noeuds solutions. Le noeud solution n est effectivement ajouté à cet ensemble de noeuds solutions s'il existe un noeud logique rp représentant une étape de localisation liée directement au noeud logique r ou indirectement par l'intermédiaire de noeuds logiques ne représentant pas une étape de localisation et vérifiant deux conditions. D'une part, aucun noeud solution correspondant à ce noeud logique rp n'a été associé au noeud solution n . D'autre part, il n'est plus possible de trouver un noeud solution correspondant à ce noeud logique rp et pouvant être associé au noeud solution n . Pour un noeud logique rp descendant du noeud logique r associé au noeud solution n , cette deuxième condition peut être évaluée à l'aide du contexte de recherche pour rp associé au noeud solution n . Ainsi dans le cas de l'expression /a/b , lors du traitement de l'événement représentant la balise fermante d'un élément a , Si aucun noeud solution représentant un élément b fils de cet élément a n'a été trouvé, alors le noeud solution représentant a est supprimé. La même situation se produit aussi lors de l'évaluation de l'expression /a[b] . L'étape 1170 est suivie de l'étape 1190 mettant fin à l'algorithme. Afin de mettre en oeuvre le procédé d'évaluation d'une expression sur des éléments d'un document structuré, un dispositif d'évaluation d'une expression sur des éléments d'un document structuré comprend notamment des moyens de génération, à partir de l'expression, d'un ensemble des noeuds cibles correspondant à des items à rechercher dans le document structuré ; des moyens de génération d'une représentation logique de l'expression, une représentation logique comprenant un ensemble de noeuds, représentant les sous-expressions élémentaires de l'expression, reliés en fonction des relations entre ces sous-expressions élémentaires ; et des moyens d'évaluation de l'expression sur des items du document structuré à partir de l'ensemble des noeuds cibles généré et de la représentation logique générée. If the test of step 1160 is negative, then the algorithm proceeds to step 1170 of updating the solutions. Step 1170 is similar to step 1135. However, it differs by the set of solution nodes considered. Indeed, in addition to the solution nodes corresponding to a location step of which a predicate has been evaluated to false and solution nodes corresponding to a result generated, in some cases the solution node is added to this set of solution nodes. The solution node n is effectively added to this set of solution nodes if there exists a logical node rp representing a location step directly linked to the logical node r or indirectly via logical nodes not representing a location step and verifying two conditions. On the one hand, no solution node corresponding to this logical node rp has been associated with the solution node n. On the other hand, it is no longer possible to find a solution node corresponding to this logical node rp and which can be associated with the solution node n. For a downward logical node rp of the logical node r associated with the solution node n, this second condition can be evaluated using the search context for rp associated with the solution node n. So in the case of the expression / a / b, when processing the event representing the closing tag of an element a, If no solution node representing a element b son of this element has been found, then the solution node representing a is deleted. The same situation also occurs when evaluating the expression / a [b]. Step 1170 is followed by step 1190 terminating the algorithm. In order to implement the method for evaluating an expression on elements of a structured document, a device for evaluating an expression on elements of a structured document notably comprises generation means, starting from the expression of a set of target nodes corresponding to items to be searched in the structured document; means for generating a logical representation of the expression, a logical representation comprising a set of nodes, representing the elementary sub-expressions of the expression, related as a function of the relationships between these elementary sub-expressions; and means for evaluating the expression on items of the structured document from the set of target nodes generated and the generated logical representation.

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. This device for evaluating an expression on elements of a structured document can be incorporated in a computer 1200 as illustrated in FIG. 12. In particular, the various means identified above can be incorporated into a read-only memory. 1205 ("Read-Only Memory" or ROM) adapted to store a program for evaluating an expression on elements of a structured document according to the 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é. RAM 1210 ("Random Access Memory" or RAM) is adapted to store in the registers the values modified during the execution of the evaluation program of an expression on elements of a structured document.

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'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. The microprocessor 1220 is integrated with a computer 1200 which can be connected to different peripherals and other computers of a communication network. This computer comprises in known manner a communication interface 1230 connected to the communication network 1235 for receiving or transmitting messages. The computer further comprises document storage means, such as a hard disk 1270, or is adapted to cooperate by means of a disk drive 1280 (floppy disks, compact disks or computer cards) with storage means for storing data. removable documents, such as disks 1285. These fixed or removable storage means may comprise the code of the evaluation method of an expression on elements of a structured document according to the invention. They are also suitable for storing an electronic document containing hierarchical data as defined by the present invention. As a variant, the program enabling the evaluation device of an expression to implement the invention can be stored in the read-only memory 1205. In the second variant, the program can be received to be stored as previously described by the user. 1235. The computer 1200 also has a screen 1240 for example to interface with an operator using the 1250 keyboard or mouse 1260 or any other means. The central unit 1220 (CPU) will then execute the instructions relating to the implementation of the invention. When powering on, the programs and methods relating to the invention stored in a non-volatile memory, for example the memory 1205, are transferred into the memory 1210 which will then contain the executable code of the invention as well as the necessary variables. to the implementation of the 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 sous-élément directement ou par l'intermédiaire d'un autre sous-élément. 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. The communication bus 1290 allows communication between the various sub-elements of the computer or linked to it. The representation of this bus 1290 is not limiting and in particular the microprocessor 1220 is able to communicate instructions to any sub-element directly or via another sub-element. Of course, many modifications can be made to the embodiments described above without departing from the scope of the invention.

Claims

A method of evaluating an expression on items of a structured document, an expression comprising a set of elementary sub-expressions, characterized in that it comprises the following preliminary steps: - generation, from the expression of a set of target nodes (920) corresponding to items to be searched in the structured document; generating a logical representation (930) of the expression, a logical representation comprising a set of nodes, representing the elementary sub-expressions of the expression, related as a function of the relations between these elementary sub-expressions; and a step of - evaluating the expression on items of the structured document from the set of target nodes generated and the generated logical representation.

2. Method according to claim 1, characterized in that the step of generating a set of target nodes further comprises generating a representation of the relations between the target nodes.

3. Method according to claim 1 or claim 2, characterized in that the evaluation step of the expression comprises: a step of filtering the items of the document from the set of target nodes; and a step of evaluating the filtered items from the logical representation. 30

4. Method according to claim 3, characterized in that the step of filtering the items of the document from the set of target nodes comprises a step of identifying the items of the document corresponding to target nodes of all the nodes of the document. target nodes.

5. Method according to claim 3 or claim 4, characterized in that the step of evaluating the filtered items comprises a step of creating a solution node associated with a node of the logical representation, this solution node representing a result. evaluation for the node of the logical representation.

6. Method according to claim 5, characterized in that the step of creating a solution node associated with a node of the logical representation comprises a step of associating a filtered item with this solution node.

7. Method according to claim 6, characterized in that the step of evaluating the filtered items further comprises a step of creating a relationship between a first solution node associated with a first node of the logical representation and at least one second solution node associated with a second node of the logical representation in accordance with the relationship between the first node of the logical representation and the second node of the logical representation.

8. Method according to claim 7, characterized in that the evaluation step of the expression further comprises a step of verifying the completeness of a solution comprising the following substeps: - verification of the existence for each node of the logical representation of at least one associated solution node; selecting for each node the logical representation of an associated solution node, the set of selected solution nodes forming a solution; for each relationship between two nodes of the logical representation, checking that a similar relationship exists between the selected associated solution nodes.

9. Method according to claim 8, characterized in that the evaluation step of the expression comprises, if the step of verifying the completeness of a solution is positive, a step of generating a result from of the solution.

10. Method according to any one of claims 3 to 9, characterized in that a search context is associated with a filtered item corresponding to a node of the logical representation and a node of the descending logical representation of the node corresponding to the filtered item.

11. The method of claim 10, characterized in that a search context comprises identification information of a part of the document in which is searched for an item corresponding to the descending node.

12. Method according to any one of the preceding claims, characterized in that it comprises a step of transmitting a result at the end of the evaluation of the expression.

13. Method according to any one of claims 5 to 12 characterized in that it comprises a step of deleting a solution node, the deletion of a solution node being performed according to a validity criterion of the solution node. .

14. Method according to claim 13, characterized in that the criterion of validity of a solution node depends on the relationships existing between this solution node and other solution nodes and search contexts associated with the node of the logical representation associated with this solution node. node solution. 25 30

15. A device for evaluating an expression on items of a structured document, an expression comprising a set of elementary sub-expressions, characterized in that it comprises: generation means, based on the expression of a set 5 of the target nodes corresponding to items to be searched in the structured document; means for generating a logical representation of the expression, a logical representation comprising a set of nodes, representing the elementary sub-expressions of the expression, related as a function of the relationships between these elementary sub-expressions; and means for evaluating the expression on items of the structured document from the set of target nodes generated and the generated logical representation. 15

16. Device according to claim 15, characterized in that the means for generating a set of target nodes further comprise means for generating a representation of the relationships between the target nodes. 20

17. Device according to claim 15 or claim 16, characterized in that the means for evaluating the expression comprise: means for filtering the items of the document from the set of target nodes; and means for evaluating the filtered items from the logical representation.

18. The device as claimed in claim 17, characterized in that the means for filtering the items of the document from the set of target nodes comprise means for identifying the items of the document corresponding to target nodes of all the nodes of the document. target nodes.

19. Device according to claim 17 or claim 18, characterized in that the means for evaluating the filtered items comprise means for creating a solution node associated with a node of the logical representation, this solution node representing a result of evaluation for the node of the logical representation.

20. Device according to claim 19, characterized in that the means for creating a solution node associated with a node of the logical representation comprises means for associating a filtered item with the solution node.

21. Device according to claim 20, characterized in that the means for evaluating the filtered items further comprises means for creating a relationship between a first solution node associated with a first node of the logical representation and at least one second solution node associated with a second node of the logical representation according to the relationship between the first node of the logical representation and the second node of the logical representation.

22. Device according to claim 21, characterized in that the means for evaluating the expression further comprise means for verifying the completeness of a solution comprising: existence verification means for each node of the logical representation of at least one associated solution node; selection means for each node of the logical representation of an associated solution node, the set of selected solution nodes forming a solution; verification means capable of verifying, for each relation between two nodes of the logical representation, that a similar relationship exists between the selected associated solution nodes.

23. Device according to claim 22, characterized in that the means for evaluating the expression comprise means for generating a result from the solution.

24. Device according to any one of claims 17 to 23, characterized in that it comprises means for associating a search context to a filtered item corresponding to a node of the logical representation and to a node of the descending logical representation of the node corresponding to the filtered item.

25. Device according to claim 24, characterized in that a search context comprises identification information of a part of the document in which is searched for an item corresponding to the descending node.

26. Device according to any one of claims 15 to 25, characterized in that it comprises means for transmitting a result at the end of the evaluation of the expression. 20

27. Device according to any one of claims 19 to 26, characterized in that it comprises means for deleting a solution node, the deletion of a solution node being performed according to a criterion of validity of the node. solution. 25

28. Device according to claim 27, characterized in that the criterion of validity of a solution node depends on the relationships existing between this solution node and other solution nodes and search contexts associated with the node of the logical representation associated with this solution node. node solution. 30

29. Computer program product that can be loaded into a programmable device, characterized in that it comprises instruction sequences for implementing a method of evaluating an expression on items of a structured document according to one of the following: any of claims 1 to 14, when this program is loaded and executed by the programmable apparatus.

30. Information storage medium, readable by a computer or a microprocessor retaining instructions of a computer program, characterized in that it allows the implementation of a method for evaluating an expression on a computer program. items of a structured document according to any one of claims 1 to 14.10