JP2005135199A - Automaton generating method, method, device, and program for xml data retrieval, and recording medium for xml data retrieval program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To propose an XML data retrieval system using an XPath expression having a plurality of conditions. <P>SOLUTION: An automaton generating method of generating an automaton from the XPath expression by using an XML schema is characterized in that the XML schema prescribes the order of appearance of nodes included in XML data, and an XML data retrieval device 1 performs a procedure of generating a start state corresponding to a context node, a procedure of specifying the order of appearance of predicates from the appearance order of the nodes prescribed by the XML schema, a procedure of generating states by the predicates and prescribing transition of the states according to the appearance order of the predicates, and a procedure of determining a state corresponding to the end of the appearance order as a reception state and generating an automaton from the XPath expression. <P>COPYRIGHT: (C)2005,JPO&NCIPI

Description

  The present invention relates to an automaton creation method, an XML data search method, an XML data search device, an XML data search program, and an XML data search program recording medium.

  XML (Extensible Markup Language) is a technology that provides a standard data description method that can be exchanged on a network, and expresses a data structure using tags (Non-Patent Document 1, etc.). Therefore, data created in accordance with XML is structured in a form that can be processed by a computer, and is currently widely used, including newsML.

  A specific language for processing data in XML format is also widely used according to XML. For example, XPath (XML Path Language) is a technology that provides a description method for specifying a part of XML data, and is an expression for efficiently accessing XML data, such as a query and conversion for XML data. As a method, it plays an important role. For example, when searching for XML data that meets a predetermined condition from a set of XML data, the predetermined condition is described as an XPath expression to facilitate the search to the XML data.

  As an example of a search process for XML data, there is a process for searching for data according to the newsML format, for example. newsML can send news articles and related images, videos, sounds, etc. to various terminals such as web, mobile phone, TV (data broadcasting). Therefore, the recipient (user) of newsML can obtain only necessary information from a vast amount of information by registering the XPath expression in the distribution server.

  The search processing for XML data can be roughly classified into two types depending on the order in which the XML data to be searched is parsed (scanned).

  First, the first parsing method is DOM (Document Object Model). DOM is a technology that performs processing paying attention to the fact that XML can be expressed by a tree. By scanning DOM (XML expressed as an internal tree), it is possible to handle branch processing. However, DOM has an internal tree (hereinafter referred to as DOM tree) even for a large XML. If the memory usage is enormous, or if it is sent as sequential data (such as time series data) and requires real-time processing, such as news distribution or stock price distribution, the DOM tree It is difficult to apply the XPath type processing using.

  On the other hand, the second parsing method is SAX (Simple API for XML). SAX is a technology aimed at real-time performance and memory usage reduction, which are weak points of the DOM. In DOM, XML is represented as a tree, and scanning and filtering are performed by scanning when an XPath expression is given. On the other hand, when SAX is used, since XML data can only be scanned from top to bottom, XPath processing cannot be performed like DOM.

  Therefore, as an XPath type processing technique using SAX, there are a method using a non-deterministic automaton and a method using a deterministic automaton. Non-deterministic automata and deterministic automata are not completely independent, and each has advantages and disadvantages. Note that a nondeterministic automaton constructs one automaton for one XPath expression. Incidentally, when a plurality of XPath expressions are given, it is necessary to construct a number of automata. Therefore, the memory usage is small, but the processing speed is low. On the other hand, a deterministic automaton is constructed from a non-deterministic automaton according to a subset generation method. Therefore, the memory usage is increased, but the processing speed is increased.

  When a non-deterministic automaton or a deterministic automaton is created, it is possible to determine which part of the input XML matches the XPath expression. The method using a nondeterministic automaton creates one nondeterministic automaton for one XPath expression. This method has a feature that the processing speed is remarkably deteriorated as the number of XPath expressions increases (see Non-Patent Document 2). A method using a deterministic automaton can be realized by converting the non-deterministic automaton. The deterministic automaton is characterized in that even if the number of XPath expressions increases, the processing speed can be maintained at a high speed. However, there is a disadvantage that the memory usage becomes enormous during conversion.

A method called a delay-type deterministic finite automaton does not immediately convert a nondeterministic automaton to a deterministic automaton, but determinizes only the automaton used when XML is input, thereby reducing the amount of memory used at high speed. (See Non-Patent Document 3).
Mikitoshi Nakayama, Yasuhiro Okui, “Revised Standard XML Complete Description (above)”, ISBN4-7741-1186-4, First Edition, April 2001, Publisher “Technical Reviewer” Yanlei Diao, Peter M. Fischer, Michael J. Franklin, Raymond To, “YFilter: Efficient and Scalable Filtering of XML Documents.”, In Proceedings of the ICDE (2002) Todd J. Green, Gerome Miklau, Makoto Onizuka, Dan Suciu, “Processing XML Streams with Deterministic Automata”, ICDT (2003)

  However, a system that realizes processing for a plurality of predicates (search conditions) has not been proposed. This is because the SAX-based XPath processing system sequentially processes XML, so that a search system that handles only one search condition cannot be adapted to a plurality of search conditions as it is. .

  Here, it is necessary to specify a plurality of conditions in order to efficiently search XML data that matches the search conditions from the XML data to be searched. In a conventional search system that handles only one search condition, even XML data that is not required by the user is output to the search result as noise, which is not efficient.

  The XML data to be searched includes a set of nodes having a parent-child relationship. Further, the XPath expression as a search condition includes one or more sets of correspondence relationships between a context node for designating a node of XML data and a plurality of predicates corresponding to the context node. Here, the predicate indicates individual search conditions, and is hereinafter referred to as “predicate” or “condition”.

  In view of the above, the main object of the present invention is to propose an XML data search system that uses the XPath expression having a plurality of conditions to solve the above-described problems.

In order to solve the above problem, an automaton creation method according to claim 1 is an automaton creation method for creating an automaton from an XPath expression, and the XPath expression includes a context node and a plurality of readys corresponding to the context node. A computer including at least one pair of correspondence relations with Kate, and having at least a memory as a storage area used when performing arithmetic processing, and an arithmetic processing device that performs the arithmetic processing,
A procedure for creating a start state corresponding to the context node, a procedure for creating a reception state for each predicate with the predicate as an input, and an association between the start state and the reception state by an epsilon transition. And a step of creating an automaton from the formula.

The automaton creation method according to claim 2 is an automaton creation method for creating an automaton from an XPath expression using an XML schema, wherein the XPath expression includes a context node and a plurality of predicates corresponding to the context node. And the XML schema prescribes the order of appearance of nodes included in the XML data, the memory serving as a storage area used when performing the arithmetic processing, and the arithmetic processing A computer comprising at least an arithmetic processing unit for performing
A procedure for creating a start state corresponding to the context node; a procedure for specifying the appearance order of the predicate from the order of appearance of the node specified in the XML schema; and creating a state for each predicate A procedure for defining state transitions according to the appearance order of predicates, and a procedure for creating an automaton from an XPath expression with the state corresponding to the end of the appearance order as an accepting state are executed.

The XML data search method according to claim 3 is an XML data search method for searching XML data using the automaton created by the automaton creation method according to claim 1 or claim 2, wherein the arithmetic processing is performed. A computer comprising at least a memory as a storage area used when performing, and an arithmetic processing device that performs the arithmetic processing,
A procedure for accepting input of XML data to be searched, a procedure for sequentially scanning the XML data to generate a SAX event, and a transition of the automaton state by inputting the SAX event to the created automaton And a step of outputting the XML data as a search result when the state of the automaton reaches all acceptance states included in the automaton.

The XML data retrieval apparatus according to claim 4 is an XML data retrieval apparatus that retrieves XML data that conforms to an XPath expression of a retrieval condition from XML data to be retrieved, and the XML data retrieval apparatus performs arithmetic processing. At least a memory used as a storage area and an arithmetic processing unit that performs the arithmetic processing, and the XML data stored in the memory includes a set of nodes having a parent-child relationship, and is stored in the memory The XPath expression to be included includes one or more sets of correspondence relations between a context node and a plurality of predicates corresponding to the context node, and the XML data search device includes:
A SAX event generation unit that sequentially scans XML data to be searched to generate a SAX event, an automaton creation unit that creates an automaton for each context node from the XPath expression, and the automaton that is created using the SAX event as an input And an XPath search unit that searches for XML data based on the state transition of the above.

The XML data retrieval apparatus according to claim 5 is an XML data retrieval apparatus that retrieves XML data that conforms to an XPath expression of a retrieval condition from XML data to be retrieved, and the XML data retrieval apparatus performs arithmetic processing. At least a memory used as a storage area and an arithmetic processing unit that performs the arithmetic processing, and the XML data stored in the memory includes a set of nodes having a parent-child relationship, and is stored in the memory The XPath expression to be included includes at least one set of correspondences between a context node and a plurality of predicates corresponding to the context node, and the XML schema stored in the memory is included in the XML data. The order of appearance of nodes shall be defined, and the XML data retrieval apparatus
An SAX event generation unit that sequentially scans XML data to be searched to generate a SAX event; and an automaton creation unit that creates an automaton for each context node from the appearance order of the nodes specified in the XPath expression and the XML schema. , And an XPath search unit that searches for XML data based on the state transition of the created automaton using the SAX event as an input.

The XML data search program according to claim 6 is an XML data search program for searching XML data that conforms to an XPath expression of a search condition from XML data to be searched, the XML data being a node having a parent-child relationship. The XPath expression includes one or more sets of correspondences between a context node and a plurality of predicates corresponding to the context node, and a memory as a storage area used when performing arithmetic processing And a computer comprising at least an arithmetic processing unit that performs the arithmetic processing,
SAX event generation means for generating SAX events by sequentially scanning XML data to be searched, automaton creation means for creating an automaton for each context node from the XPath expression, and the automaton created using the SAX event as an input It is made to function as an XPath search means for searching XML data by the state transition.

The XML data search program according to claim 7 is an XML data search program for searching XML data that conforms to an XPath expression of a search condition from XML data to be searched, wherein the XML data is a node having a parent-child relationship. The XPath expression includes one or more pairs of correspondence relationships between a context node and a plurality of predicates corresponding to the context node, and the XML schema includes the occurrence of a node included in the XML data. A computer that includes at least a memory as a storage area that is used when performing arithmetic processing and an arithmetic processing device that performs the arithmetic processing, which defines the order.
SAX event generation means for generating SAX events by sequentially scanning XML data to be searched; and automaton creation means for creating an automaton for each context node from the appearance order of nodes defined in the XPath expression and the XML schema. , And an XPath search means for searching XML data based on the state transition of the created automaton using the SAX event as an input.

  As described above, according to the present invention, in the SAX-based XML data search apparatus, it is possible to perform search processing even if the XPath expression includes a plurality of conditions.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings.

  FIG. 1 shows an overall configuration relating to an embodiment of the present invention. The XML data search apparatus 1 shown in FIG. 1 has a function of searching for XML data that matches a search condition from XML data to be searched. Therefore, the XML data search apparatus 1 includes an XML data storage unit 10 that stores XML data to be searched, an XML data registration unit 11 that registers XML data to be searched in the XML data storage unit, and XML data to be searched. An XML schema storage unit 12 that stores an XML schema that follows, an SAX event generation unit 13 that sequentially scans XML data to be searched to generate an SAX event, an XPath storage unit 20 that stores an XPath that is a search condition, An XPath registration unit 21 that registers an XPath that is a search condition in the XPath storage unit, an XPath search unit 22 that searches XML data using transitions of the automaton generated from the XPath, and an automaton that stores the automaton generated from the XPath And the storage unit 30. The arrows shown in FIG. 1 indicate the flow of data.

  The XML data retrieval apparatus 1 also has an ordered automaton creation unit 31 that creates an automaton from XPath using the appearance order of XML data nodes defined in the XML schema, as an automaton creation means, and an XML data node It is assumed that at least one of the unordered automaton creating unit 32 that creates an automaton from XPath without using the appearance order is provided. Whether or not the ordered automaton creating unit 31 or the unordered automaton creating unit 32 is used as the automaton creating means is determined depending on whether or not the XML data to be searched is created according to a specific XML schema.

  The XML schema is a grammar that defines the appearance order of nodes (represented by tags) constituting XML data in the XML data. First, when the XML data to be searched is created in accordance with the XML schema, the XML data search apparatus 1 uses either the ordered automaton creation unit 31 or the unordered automaton creation unit 32 as a search condition. Create an automaton from XPath. On the other hand, when the XML data to be searched is not created according to the XML schema, the XML data search apparatus 1 uses the unordered automaton creating unit 32 to create an automaton from XPath that is a search condition. The created automaton is stored in the automaton storage unit 30.

  Here, the ordered automaton creation unit 31 creates an automaton with higher search processing efficiency than the unordered automaton creation unit 32. This is because the automaton created by the ordered automaton creating unit 31 uses order information, and therefore, the automaton created by the unordered automaton creating unit 32 requires fewer acceptance states to be verified. Therefore, when the XML data to be searched is created according to the XML schema, the ordered automaton creation unit 31 is used in preference to the unordered automaton creation unit 32.

  Then, the XML data search apparatus 1 performs a search process using the created automaton. Specifically, the XML data search apparatus 1 causes the SAX event generation unit 13 to generate SAX events by sequentially scanning the XML data in the XML data storage unit 10. Next, the XPath search unit 22 of the XML data search apparatus 1 verifies the state transition of the automaton stored in the automaton storage unit 30 by using the generated SAX event as an input. Then, when the state transition of the automaton becomes an accepting state, the XPath search unit 22 assumes that the XML data that is the generation source of the SAX event matches the XPath that is the generation source of the automaton. Output as search results. The outline of the XML data search apparatus 1 has been described above. Next, each component of the XML data search apparatus 1 will be specifically described.

First, the XML data storage unit 10 stores XML data to be searched. FIG. 10A is a diagram illustrating an example of stored XML data. The XML data in FIG. 10A is a document XML, and has a book tag under the bib tag. Below the book tag are a title tag and an author tag. In order to extract book elements that match the conditions such that the year of publication is 1999, XML is included in the title, and the author is Bob, for this XML, the XPath search formula of (Formula 1) Is used. At this time, the portion surrounded by [] represents the condition of the XPath expression. Then, the XML data search apparatus 1 obtains the search result of FIG. 10B using the search expression of (Expression 1) for the XML data of FIG. 10 (A). The main feature of the present invention is that the present invention can be processed even when there are a plurality of [] parts in (Expression 1).
/ bib / book [contains (title / text (), `XML`)] [author =` Bob`] [@ year = 1999] ... (Formula 1)

  Next, the SAX event generation unit 13 scans the XML data, and when a predetermined node (tag) is read from the XML data, generates a callback function corresponding to the type of the node. This is because SAX does not construct a tree when analyzing XML as described above. FIG. 11B lists examples of callback functions.

  FIG. 2 shows the relationship between the SAX filter (SAX event generation unit 13) and the user application. When XML data is input to the SAX filter of FIG. 2, the XML data is read in order from the top. When bib is recognized, the SAX filter calls the startElement function on the user application. At this time, by putting bib in the argument of the startElement function, information called bib can be acquired on the user application side. In this way, calling the function of the user application by the SAX event generation unit 13 is called a callback.

  FIG. 11A shows an XML schema DTD (Document Type Definition) stored in the XML schema storage unit 12. The XML schema defines the order of appearance of XML nodes. According to this, it can be seen that the XML document example shown in FIG. 10A satisfies the XML schema of FIG. 11A. Note that one or more attributes shown in the third line of FIG. 11A can be added to each element, and are expressed in the format [attribute name = `value '].

  In this embodiment, the term “XML schema” is used to mean a generic name of grammar that defines the order of appearance of nodes in XML data. Thus, examples of a grammar description method that defines the appearance order of nodes include DTD defined by W3C, XML Schema, and the like. However, in the present embodiment, the present invention is not limited to these specific examples. Various grammar description methods may be used.

  Further, FIG. 3 shows a state in which the unordered automaton creating unit 32 creates an automaton from the XPath expression. There are various description methods for the automaton, and in this embodiment, the automaton is described as a state transition diagram. The state indicated by the circle is the state, and what is written accompanying the arrow is the input for changing the state. When the XPath search unit 22 verifies the automaton, the input for changing the state corresponds to the SAX event given from the SAX event generation unit 13.

  First, the unordered automaton creating unit 32 extracts each condition surrounded by [] marks in the XPath expression as an input for changing the state. Next, the unordered automaton creation unit 32 sets the state after the transition of each condition as the accepting state of the automaton. Further, the unordered automaton creating unit 32 integrates the automaton generated from each condition into one automaton using the epsilon transition. Note that the epsilon transition indicates that the transition does not depend on the input. The automaton created in this way branches to one of the conditions from the epsilon transition, and is therefore referred to as a branching automaton.

  FIG. 4 shows a state in which the ordered automaton creation unit 31 creates a post-conversion automaton from the pre-conversion XPath expression. Note that in FIG. 4A and FIG. 4B, the XPath expression used to generate the automaton is equivalent, but the appearance order of the conditions surrounded by [] marks is different. The generated automaton will also be different. That is, a feature of the automaton generated by the ordered automaton creation unit 31 is that the automaton changes if the order of the conditions is different.

  FIG. 4A will be described. State 0 indicates an initial state. In order to shift from state 0 to state 1, it is necessary that a book element comes after the bib element. In order to move from state 1 to state 2, it is necessary to include the character `XML 'in the data between the title elements. From state 2 to 3, author moves with Bob. Finally, when the book element has a year attribute and its value is 1999, the acceptance state is entered, and XML data is extracted as a search result.

  FIG. 5 shows a case where a grammar indicating the structure of XML data is used, and the order in which conditions are applied is extracted using the grammar, and an XPath expression having conditions for a plurality of child nodes is converted into an equivalent nondeterministic automaton. It is a flowchart which shows the process to perform. FIG. 5 shows a flowchart of the operation mainly performed by the ordered automaton creation unit 31. The conversion result to the non-deterministic automaton is registered in the automaton storage unit 30. As a result, an XPath expression having a plurality of conditions can be processed. Hereinafter, each process of FIG. 5 is demonstrated in order.

  First, the XML data search apparatus 1 accepts an input of an XPath that is a search condition (S101). Since this flowchart operates when the input XML has a schema, the XML data retrieval apparatus 1 determines whether the input XML has a schema (S102). Here, since the XML data having no schema is not a processing target of the ordered automaton creation unit 31, the processing ends (S103).

  Next, the XML data search apparatus 1 analyzes the grammar (schema) and obtains the appearance order of elements (S104). In the case of DTD, such an appearance order is expressed in the element type declaration. Element type declaration is <! ELEMENT element content model>. In the content model portion, the order of elements is expressed by separating them with commas such as “element name 1, element name 2, element name 3,.

  Therefore, the XML data retrieval apparatus 1 stores the order of element name 1, element name 2, element name 3,. For example, in the case of the grammar as shown in FIG. 11A, it is specified that it always appears in the order of ear, title, author.

  Note that the attribute is treated specially and is declared as shown in order 3 in FIG. Since the appearance position of the attribute in the XML data is the same as that of the target element, the condition for the attribute must be processed first. Therefore, if there is a condition for the attribute when there are a plurality of conditions (S105, Y), such a condition portion is brought first (S106). If the conditions for all the attributes are brought forward, the order for the elements (title, author) is moved to the order obtained from the DTD (S107). The XPath expression thus obtained is output as an output to the XPath registration unit 21 (S108).

This will be described using a specific example. When the XPath expression (Expression 2) is given, first, all the conditions related to the attribute are moved to the front of the condition group to obtain (Expression 3). Next, the conditions of (Equation 3) are aligned according to the grammar to obtain (Equation 4). In this way, the conditions are arranged in the order according to the grammar. This XPath expression is equivalent to the original XPath expression with respect to the DTD shown in the example. Therefore, the search process can be performed using the output XPath expression.
/ bib / book [author = `Bob`] [contains (title / text (),` XML`)] [@ year = 1999] ... (Formula 2)
/ bib / book [@ year = 1999] [author = `Bob`] [contains (title / text (),` XML`)] ... (Formula 3)
/ bib / book [@ year = 1999] [contains (title / text (), `XML`)] [author =` Bob`] ... (Formula 4)

  FIG. 6 is a flowchart that enables a search process for XML data using an XPath expression having conditions for a plurality of child nodes when the grammar (schema) indicating the structure of the XML data is not provided. That is, FIG. 6 shows processing for converting an XPath expression having conditions for a plurality of child nodes into a nondeterministic automaton with a branch. FIG. 6 shows the operation of the unordered automaton creating unit 32. Hereafter, each procedure of FIG. 6 is demonstrated in order.

  First, when a plurality of XPath expressions are given (S201), the XML data retrieval apparatus 1 processes each XPath one by one. Therefore, the XML data retrieval apparatus 1 determines whether all the XPath expressions have been processed (S202). When all the XPath expressions have been processed, the process ends (S203).

  Next, when the XPath expression is input (S204), the XML data search apparatus 1 analyzes the input XPath expression (S205) and determines whether the XPath expression has a condition (predicate) (S206). ). That is, the part of the condition surrounded by [] is searched from the XPath expression. Therefore, the XML data retrieval apparatus 1 divides the respective conditions and stacks them. Then, the XML data retrieval apparatus 1 extracts and connects one condition from the plurality of stacked conditions, and registers it in the XPath processor (S207). The connected conditions are removed from the stack, only the selected conditions are deleted, and XPath is output as a new XPath (S208).

  Further, when the XML data search apparatus 1 repeats until there are no more conditions from the stack (S206, N), as many XPath expression sets as the number of conditions are constructed. Finally, an XPath expression-Parent obtained by removing the condition part from the original XPath expression is acquired (S209). Information indicating a parent-child relationship is constructed between the XPath expression-Parent and the XPath expression set (S210).

  This will be described using an example. Assume that XML data having no grammar is given as shown in FIG. At this time, the XPath formula (Formula 1) is considered. At this time, even if an automaton is simply configured from the above consideration, filtering cannot be performed. First, the XPath expression is divided as shown in FIG. In this method, a part from which the condition part is omitted and a plurality of conditions are divided into one condition.

  Next, each condition part and a context node corresponding to each condition part can be connected to obtain an XPath expression set as shown in FIG. Note that the XPath expression group obtained here has a parent-child relationship. The branching nondeterministic automaton for the above example is constructed as shown in FIG.

  The XML data search apparatus 1 according to an embodiment of the present invention registers the XPath expression group constructed by the unordered automaton creation unit 32 in the XPath storage unit 20 in advance. In the examples, #Y, #Z, #U, #X, etc. are used, but these perform the same function as the actual XPath expression. For example, when / bib / book is called from startContext, #Y is called. The reason why #Z, #U, and #X are defined using #Y is to support // book. An XPath expression such as // book must also support the case where XML holds book elements nested. Since #Y expresses an XPath expression after // book is expanded, #Z, #U, and #X can be defined as relative XPath expressions to #Y, respectively.

  Here, an outline of the XML data search process shown in FIG. 8 will be described using a specific example shown in FIG. In addition, the state shown in gray in FIG. 7 indicates the acceptance state.

First, XML data as shown in FIG. 10B is a search target. Assume that an XPath expression such as (Expression 5) is input and an automaton as shown in FIG. 7A is created.
/ bib / book [author = `Bob`] [@ year = 1999] [contains (title / text (),` XML`)] ... (Formula 5)

  At this time, the startElement function is called twice, and a transition is made to $ Y. Then, since the child automaton for $ Y has a state, the argument of the endEelment function also includes attribute information `year = 1999 ', so $ X is in the accepting state (see FIG. 7B). . Therefore, it registers itself to $ Y, which is the parent automaton, and informs that $ X is in an accepting state.

  Similarly, after the endElement function is called, the conditions of “contains (title / text (),` XML ') and author = `Bob" are satisfied, and $ Z and $ U are in the accepting state (FIG. 7 ( c) and FIG. 7 (d)). Next, when the endElement function is called with respect to </ book>, the automaton corresponding to $ Y checks whether all child automata are in the accepting state, and accepts $ Y because it is in the accepting state (FIG. 7). (See (e)).

  Here, the stack of xpath_variable will be described with reference to FIG. FIG. 9 shows a stack of $ Y, $ Z, $ U, and $ X. Since the stack is composed of registers indicating the acceptance state of the child automaton, $ Y stacks registers {$ Z, $ U, $ X}. By doing this, the acceptance status of the child automaton can be received. Leaf automata have no child automata, so the stack is empty.

  The reason for using the stack will be described. In the example introduced this time, $ Y is expressed by an absolute path for simplicity. Actually, there is an XPath that recursively designates a book element, such as // book. At this time, if there is only one register that can be registered, when a plurality of book elements receive a callback from the startElement function, the book element to be processed at the present time cannot be determined. For this reason, the stack is used to store a plurality of registers and determine an element to be processed.

  In this way, in order to output the XML data accepted by the XPath expression when accepted, the XML data is stored in the register from the place where the transition occurred in the root automaton. When it is accepted, all registered data is output. When the acceptance state is not reached, the automaton that has not entered the acceptance state opens the register. As described above, even when there is no grammar (XML schema), it is possible to perform processing of an XPath expression having a plurality of conditions.

  FIG. 8 is a flowchart showing a process for searching input XML data using the created automaton. Here, as an example of the created automaton, the branching nondeterministic automaton created by the unordered automaton creating unit 32 is used. FIG. 8 shows an operation mainly performed by the XPath search unit 22. Hereinafter, the processing of FIG. 8 will be described in order.

  The XML data search apparatus 1 uses the callback (S302) from the SAX event generation unit 13 for the input XML data (S301) as a trigger for processing. First, the startContext function and the endContext function, which are callback functions, have a variable xpath_variable indicating the target XPath expression as an argument.

  Here, when the startContext function is called back, a stack corresponding to xpath_variable is prepared (S305). What is stacked is a register that can store the accept states of all child automata possessed by xpath_variable as true / false. If the child automaton is in an accepting state with respect to the parent automaton, the child automaton notifies the parent automaton of true. The register is initialized to false.

  On the other hand, when the endContext function is called back, if it is a leaf on a branching automaton (S306, Y), since there is a register related to xpath_variable for xpath corresponding to the parent of xpath_variable, Let it be true. Here, the leaf refers to a portion that becomes a leaf when FIG. 3 is regarded as a tree. When xpath_variable is not a leaf (N in S306), it is determined based on the state of the register whether all child automata corresponding to the children of xpath_variable are in an accepting state.

  A condition expressed by a plurality of child automata is expressed by a logical expression using and / or. Thus, true / false included in each child automaton included in the register is assigned to the logical expression of the condition group to determine whether the logical expression is true.

  If the logical expression of the condition group is true (S307, Y), the condition represented by the child automaton group is an acceptance state. If it is in the accepting state, xpath_variable is accepted. On the other hand, if the logical expression of the condition group is false (S307, N), the condition represented by the child automaton group is not in the accepting state. If it is not in the accepting state, xpath_variable is not accepted. Then, the current register is popped from the stack of xpath_variable whether it is in the accepting state or not (S309, S310).

  In the case of an acceptance state (S307, Y), the process branches depending on whether the automaton corresponding to xpath_variable is a route (S311). If it is a route (S311, Y), the target branch automaton is accepted, indicating that the original XPath expression is in the accepted state. Therefore, the XPath expression is pushed to the list A (S313). If it is not the root (S311; N), xpath_variable is pushed to the XPath expression corresponding to the parent of xpath_variable (S312). In either case, the process waits until the next callback function is called (S302).

  The present invention described above is not limited to the embodiments described above, and can be implemented in various forms within the scope of the technical idea.

It is a block diagram of the XML data search apparatus regarding one Embodiment of this invention. It is explanatory drawing of the SAX event production | generation part regarding one Embodiment of this invention. It is explanatory drawing of the unordered automaton preparation part regarding one Embodiment of this invention. It is explanatory drawing of the ordered automaton preparation part regarding one Embodiment of this invention. It is a flowchart which shows the creation process of the automaton using the appearance order of the node regarding one Embodiment of this invention. It is a flowchart which shows the production process of the automaton produced without using the appearance order of the node regarding one Embodiment of this invention. It is a figure explaining the operation | movement of the search process of the XML data regarding one Embodiment of this invention. It is a flowchart which shows the operation | movement of the search process of the XML data regarding one Embodiment of this invention. It is a figure explaining the method of managing the acceptance state of the automaton regarding one Embodiment of this invention. It is a figure which shows an example of the XML data regarding one Embodiment of this invention. FIG. 4 illustrates an XML schema and SAX events for one embodiment of the present invention. It is a figure which shows the division process of the XPath type | formula regarding one Embodiment of this invention.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 XML data search apparatus 10 XML data storage part 12 XML schema storage part 13 SAX event generation part 20 XPath storage part 22 XPath search part 30 Automaton storage part 31 Ordered automaton creation part (automaton creation means)
32 Orderless automaton creation part (automata creation means)

Claims (8)

An automaton creation method for creating an automaton from an XPath expression, wherein the XPath expression includes at least one set of correspondences between a context node and a plurality of predicates corresponding to the context node, and performs an arithmetic process A computer including at least a memory as a storage area used at the time, and an arithmetic processing device that performs the arithmetic processing,
A procedure for creating a start state corresponding to the context node, a procedure for creating a reception state for each predicate with the predicate as an input, and an association between the start state and the reception state by an epsilon transition. A method for creating an automaton from an expression. An automaton creation method for creating an automaton from an XPath expression using an XML schema, wherein the XPath expression includes one or more pairs of correspondence relationships between a context node and a plurality of predicates corresponding to the context node. The XML schema defines the order of appearance of nodes included in the XML data, and a computer including at least a memory serving as a storage area used when performing arithmetic processing, and an arithmetic processing device that performs the arithmetic processing. ,
A procedure for creating a start state corresponding to the context node; a procedure for specifying the appearance order of the predicate from the order of appearance of the node specified in the XML schema; and creating a state for each predicate A method for creating an automaton, comprising: a step of defining a state transition in accordance with a predicate appearance order; and a step of creating an automaton from an XPath expression with a state corresponding to the end of the appearance order as an acceptance state. An XML data search method for searching XML data using an automaton created by the automaton creation method according to claim 1 or 2, wherein a memory as a storage area used when performing arithmetic processing; A computer comprising at least an arithmetic processing unit that performs the arithmetic processing,
A procedure for accepting input of XML data to be searched, a procedure for sequentially scanning the XML data to generate a SAX event, and a transition of the automaton state by inputting the SAX event to the created automaton An XML data search method comprising: executing a procedure; and outputting the XML data as a search result when the state of the automaton reaches all acceptance states included in the automaton. An XML data search device that searches XML data that conforms to an XPath expression of a search condition from XML data to be searched, the XML data search device including a memory as a storage area used when performing arithmetic processing, The XML data stored in the memory includes a set of nodes having a parent-child relationship, and the XPath expression stored in the memory includes a context node, It is assumed that the XML data retrieval apparatus includes at least one set of correspondences with a plurality of predicates corresponding to the context node.
A SAX event generation unit that sequentially scans XML data to be searched to generate a SAX event, an automaton creation unit that creates an automaton for each context node from the XPath expression, and the automaton created by using the SAX event as an input An XML data search device comprising: an XPath search unit that searches for XML data based on state transitions of: An XML data search device that searches XML data that conforms to an XPath expression of a search condition from XML data to be searched, the XML data search device including a memory as a storage area used when performing arithmetic processing, The XML data stored in the memory includes a set of nodes having a parent-child relationship, and the XPath expression stored in the memory includes a context node, The XML schema stored in the memory includes one or more pairs of correspondence relationships with a plurality of predicates corresponding to the context node, and defines the appearance order of nodes included in the XML data. The data retrieval device
An SAX event generation unit that sequentially scans XML data to be searched to generate a SAX event; and an automaton creation unit that creates an automaton for each context node from the appearance order of the nodes specified in the XPath expression and the XML schema. And an XPath search unit that searches for XML data based on the state transition of the created automaton using the SAX event as an input. An XML data search program for searching XML data that matches an XPath expression of a search condition from XML data to be searched, wherein the XML data includes a set of nodes having a parent-child relationship, and the XPath expression is a context node And one or more pairs of correspondence relationships with a plurality of predicates corresponding to the context node, a memory serving as a storage area used when performing the arithmetic processing, and an arithmetic processing device that performs the arithmetic processing A computer comprising at least
SAX event generation means for generating SAX events by sequentially scanning XML data to be searched, automaton creation means for creating an automaton for each context node from the XPath expression, and the automaton created using the SAX event as an input XML data search program for functioning as an XPath search means for searching XML data based on the state transition of. An XML data search program for searching XML data that matches an XPath expression of a search condition from XML data to be searched, wherein the XML data includes a set of nodes having a parent-child relationship, and the XPath expression is a context node And one or more pairs of correspondence relations with a plurality of predicates corresponding to the context node, and the XML schema prescribes the appearance order of the nodes included in the XML data. A computer comprising at least a memory as a storage area used for the above and an arithmetic processing unit that performs the arithmetic processing;
SAX event generation means for generating SAX events by sequentially scanning XML data to be searched; and automaton creation means for creating an automaton for each context node from the appearance order of nodes defined in the XPath expression and the XML schema. An XML data search program for functioning as an XPath search means for searching XML data based on the state transition of the created automaton with the SAX event as an input.   A computer-readable recording medium in which the program according to claim 6 or 7 is recorded.

Images