JP4519028B2 - XPath processing equipment - Google Patents

Description

The present invention relates to the XPath expression processing equipment.

  XML (Extensible Markup Language) is a technology that provides a standard data description method that can be exchanged on a network, and is currently widely used including newsML. The XPath (XML Path Language) expression is a technology that provides a description method for specifying a part of XML data, and plays an important role in queries and conversions for XML data.

  A technique for extracting a part specified by an XPath expression when XML data and an XPath expression representing a part of the XML data are input has been attracting attention. For example, newsML can send news articles and related images, videos, voices, and the like to various terminals such as a web terminal, a mobile phone, and a television (data broadcast). At this time, 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.

  XPath is a standard recommended by the World Wide Web Consortium (W3C) and defines a description method for indicating a specific element in an XML document. XPath is an independent description method for position designation used in XML Stylesheet Language Transformations (XSLT) and XML Pointer Language (XPointer). XPath provides a means for accessing every element and attribute in a document by following a tree structure representing XML data, unlike designation by an artificially added anchor used for a hyperlink or the like. The XPath expression is an actual expression according to the XPath standard.

  Parsing processing of XML data is classified into DOM (Document Object Model) or SAX (Simple API for XML). DOM is a technology that performs processing by paying attention to the fact that XML can be expressed by a tree. A branch process can be handled by scanning DOM (XML represented by an internal tree). However, in DOM, an internal tree (hereinafter referred to as a DOM tree) must be created even for a large XML, so that the amount of memory used becomes enormous. In addition, when it is sent as sequential data (such as time series data) and requires real-time processing as in news distribution or stock price distribution, XPath processing using a DOM tree is impossible.

  On the other hand, SAX is a technology aimed at real-time performance and memory usage reduction, which are weak points of the DOM. In DOM, XML is expressed as a tree, and scanning and filtering processing is performed by scanning when an XPath expression is given. On the other hand, when SAX is used, since XML can only scan a document from top to bottom, XPath expression processing cannot be performed as in DOM.

Therefore, as an XPath processing technique using SAX, there are a method using NFA (Nondeterministic Finite Automaton) and a method using DFA (Deterministic Finite Automaton). NFA and DFA are not completely independent, and each has advantages and disadvantages. NFA constructs one automaton for one XPath expression. When multiple XPath expressions are given, it is necessary to construct a number of automata. The DFA is constructed from NFA. The advantages and disadvantages of each are shown in Table 1.

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

  A method called delayed DFA (lazy DFA) realizes high-speed processing by converting only the automaton used when XML is input, without converting immediately from the non-deterministic automaton to the DFA. (Non-Patent Document 1).

A technique that expands the XPath-type processing apparatus using the SAX and supports a plurality of search conditions for one XPath expression is a branched XPath-type processing apparatus (Non-patent Document 3 and Patent Document 1). In this system, a plurality of branch XPath expressions are processed one by one. That is, one search index is constructed for one XPath expression. Since there are as many search indexes as there are XPath expressions, it is known that the processing time increases linearly as the XPath expressions increase.
JP 2005-135199 A TJGreen, G. Miklau, M. Onizuka, D. Suciu, “Processing XML Streams with Deterministic Automata”, In Proceeding of ICDT (2003). Y.Diao, P. Fischer and M. Franklin, “Yfilter: Efficient and scalable filtering of xml documents”, In Proceedings of the ICDE (2002). M. Onizuka, “Light-weight XPath processing of XML stream with deterministic automata”, CIKM (2003).

  Since the branch XPath processing device described above uses NFA for processing a plurality of conditions, as the number of registered XPath expressions increases, the processing for determining the conditions included in the XPath expressions increases, and the performance is improved. There is a problem of significant deterioration. Since it is highly necessary to specify a plurality of conditions in actual operation, this performance deterioration is a bottleneck in the branch XPath processing apparatus.

  Therefore, the present invention solves the above-described problem, and when there are a plurality of branch XPath expressions indicating search conditions for filtering XML data, the filtering process can be accelerated and the memory usage can be reduced. The main object is to provide a means for processing a branched XPath expression so that it can.

In order to solve the above problems, the present invention provides:
An XPath-type processing apparatus that processes a branch XPath expression for filtering XML data,
The XPath type processing device includes an XPath type storage means, a path extraction means, a shared index construction means, a shared buffer management means, and an XPath type processing means,
The XPath expression storage means stores a plurality of input branch XPath expressions in a storage means,
The path extraction means is provided for each branch XPath expression stored in the storage means by the XPath expression storage means.
The path to be returned when the predicate condition of the branch XPath expression is satisfied is the absolute path of the target path,
The scope path of the target path is the context path of the predicate at the leftmost of the branch XPath expression.
By combining the predicate expressed by the relative path and the context path of the predicate, the absolute path of the predicate is obtained.
Extract the context path of the predicate as the scope path of the predicate,
The shared index construction means includes:
Generate a TAN (Target Absolute Node) from the absolute path of the target path extracted by the path extraction means,
A TSN (Target Scope Node) is generated from the scope path of the target path extracted by the path extraction means,
Generate a PAN (Predicate Absolute Node) from the absolute path of the previous description word extracted by the path extraction means,
A PSN (Predicate Scope Node) is generated from the scope path of the previous description word extracted by the path extraction means,
When there are a plurality of pairs having the same path among the TAN and TSN pairs extracted from the same branch XPath expression, these sets are combined into one set,
When there are a plurality of pairs having the same path among the PAN and PSN pairs extracted from the same branch XPath expression, these sets are merged into one set;
The TSN and the PSN are SNs (Scope Nodes), and when there are multiple SNs with matching paths, they are integrated into one SN,
The branch XPath expression generated from the extraction source branch XPath expression can be expressed by a combination of nodes, and corresponds to the TAN extracted from the same extraction source branch XPath expression and the absolute path indicated by the TAN. The SN corresponding to the scope path is connected by a link, and the PAN extracted from the branch XPath expression of the same extraction source and the SN corresponding to the scope path corresponding to the absolute path indicated by the PAN are connected by a link. The TAN and the PAN extracted from the same extraction source branch XPath expression are connected with a logical symbol representing a logical sum or logical product indicated by the same extraction source branch XPath expression, Construct one shared index from multiple branch XPath expressions,
The shared buffer management means constructs, for each TAN of the shared index, a shared buffer in which numbers are assigned in order according to the appearance order for each component of the input XML data. XML data for the range of the target path indicated by each TAN is stored in the shared buffer,
The XPath processing means is:
By parsing the input XML data with a SAX parser, a callback function is generated,
When the end of the scope path indicated by the SN of the shared index is notified by the callback function,
In the shared index, the authenticity determination of the predicate indicated by the PAN connected by a link from the notified SN is performed,
When the determination result of the PAN linked to the TAN is false for the TAN connected by a link from the PAN that has performed the authenticity determination of the previous description word, the scope indicated by the SN from the shared buffer of the TAN After deleting the XML data for the range of the path, and after determining the authenticity of the previous descriptive word for all the PANs connected by links from the notified SN, from the notified SN For all the TANs connected by the link, output the XML data for the range not deleted from the XML data for the range of the target path indicated by the TAN from the TAN shared buffer as a filtering result. Features.

  As a result, the filtering process can be speeded up and the amount of memory used can be reduced.

  According to the present invention, when a plurality of branch XPath expressions are input, the speed of filtering is increased by constructing a shared index so as to reduce the number of conditional judgments and callback calls regarding the branch XPath expressions. Can do.

  Hereinafter, an embodiment of an XPath processing system to which the present invention is applied will be described in detail with reference to the drawings.

  First, an outline of the present embodiment will be described. First, the XPath expression will be described, and then the XML will be described.

/bib/book[contains(title/text(),'XML')][.//author='Bob'][publication<=1999]… Formula 1
An XPath expression such as Expression 1 defines a description method for indicating a specific element in an XML document. The basic description method of the XPath expression is similar to the file system of UNIX (registered trademark). The root node that is the vertex of the document tree structure is represented by “/”, and the elements are separated by “/” and traced. To go. To refer to the value b in the a element, write “/ a / b”. There are also provisions for node data types, node types, handling of namespaces, etc., and these can be used to specify complex locations including conditional expressions and operations.

  A path pointing to a specific element in the XML document is expressed in the form of an absolute path or a relative path. The absolute path is an XPath expression as described from the root node. An absolute path is an XPath expression that has complete information for pointing to a certain node, and that the absolute path is used to completely determine the equivalence of search target nodes, that is, whether the absolute path and the absolute path are the same. It becomes possible to determine whether or not. On the other hand, the relative path is a path indicating a relative position as viewed from a node of interest (also referred to as a context).

  From one XPath expression, one target path (Target Path) and one or more predicates (Predicate) are extracted. The target path is a path indicating the portion of XML to be returned when the branch XPath expression satisfies the condition. The target path is obtained by extracting a portion excluding a portion surrounded by parentheses [...] in the XPath expression.

  On the other hand, the predicate is a condition part existing in the XPath expression, and is enclosed in parentheses [...] of the XPath expression. One predicate corresponds to one parenthesis [...]. The branch XPath expression is an XPath expression having a plurality of predicates. The present embodiment is characterized in that the branch XPath expression is processed with high efficiency by converting one or more branch XPath expressions into one shared index, as will be described later.

Next, an absolute path and a scope path (SP) are defined for the target path and the predicate. The scope path is an absolute path for indicating that the absolute path of the predicate and the target path are valid. Even if the absolute path and target path of the predicate are called by the callback function, if they are not included in the corresponding scope path at that time, the true / false judgment and output judgment of the absolute path and target path of the predicate are performed. I can't.

  As described above, the target path absolute path (TAP: Target Absolute Path) is obtained by extracting a portion excluding a portion surrounded by parentheses [...] Of the XPath expression. The target path scope path (TSP: Target Scope Path) is the absolute path up to the predicate on the most root side of the XPath expression, that is, the context path of the predicate on the leftmost side of the branch XPath expression.

  A predicate absolute path (PAP) is obtained by combining an XPath expression (relative path of a predicate) included in a predicate and a scope path of a predicate described later. A predicate scope path (PSP) can be constructed by using a context path. The context path indicates in which situation the XPath expression expressed by the relative path included in the predicate is effective. Actually, the branch XPath expression from the head of the branch XPath expression to the predicate is analyzed and acquired. A context path is obtained by removing all predicates from the obtained branch XPath expression.

  Next, description will be made regarding XML and SAX-based filtering processing that applies an XPath expression to the XML. Details of XML are detailed in, for example, the literature “Mikitoshi Nakayama, Yasuhiro Okui,“ Revised Standard XML Complete Explanation (above) (below) ”, Technical Review (2001).”.

  FIG. 1 is an explanatory diagram showing the relationship between the SAX filter and the user application. First, the SAX callback function will be described. As described above, SAX does not construct a tree when analyzing XML data. Therefore, a technique using a callback function is employed when performing XML data analysis processing.

When XML data is input to the SAX filter, it is read sequentially from the top. When bib is recognized, the SAX device calls the startElement function on the user application. At this time, by inserting bib in the argument of the startElement function, information called bib can be acquired on the user application side. Thus, calling the function of the user application by the filter device is called a callback. Table 3 shows the callback functions.

  FIG. 2A shows an example of XML data. It is XML for documents, and there is a book tag under the bib tag. Below the book tag, there are a title (title) tag, an author (author) tag, a publication (issue year) tag, and a price (price) tag. For such XML, an XPath expression that extracts a book element that matches the condition that the publication year is before 1999, the title includes XML, and the author is Bob is expressed as Expression 1. be able to.

  A return value expected when the XPath expression of Expression 1 is applied to the XML of FIG. 2A is as shown in FIG. Note that the part included in the book tag is returned. Indicates the tag name returned when the description / bib / book satisfies the predicate condition. This / bib / book is the TAP described above. The PSP of each predicate is / bib / book because it connects the paths leading to the predicate.

Next, consider Equation 2.
/ bib / book [contains (title / text (), 'XPath')] [publication = 2000] / authors… expression 2
Formula 2 is to acquire the author of a book whose title includes the character string “XPath” and whose publication year is 2000. The return value when this XPath expression is applied to the XML of FIG. 2A is as shown in FIG. The TAP at this time is / bib / book / authors. PSP is / bib / book.

  The XPath type processing system shown in FIG. 3 includes an XPath type registration device 110, a path extraction device 160, a shared index construction device 150, a shared buffer management device 180, an XPath type processing device 190, a shared index search device 140, and A branchless XPath processing apparatus 200 is included. The storage unit of the XPath type processing system stores the XPath type of the XPath type storage device 120, the input XML data 130 to be analyzed, and the shared buffer 170 generated from the XML data 130. The number of computers constituting this XPath processing system is not limited to the number shown in FIG. 3, and various configurations such as a single unit can be adopted.

  Each device of the XPath processing system is configured as a computer including at least a memory serving as a storage unit used when performing arithmetic processing and an arithmetic processing device that performs the arithmetic processing. The memory is constituted by a RAM (Random Access Memory) or the like. Arithmetic processing is realized by an arithmetic processing unit configured by a CPU (Central Processing Unit) executing a program on a memory. Details of each device will be described below.

  In FIG. 3, the dashed arrows indicate the data flow. When XML data 130 is input to the XPath processing system, it is transferred to the XPath processing device 190. The XPath processing device 190 outputs the input XML data 130 to the branchless XPath processing device 200. The branchless XPath processing device 200 analyzes the input XML data 130 and sends the result for the branchless XPath formula registered in the shared index device 150 to the XPath processing device 190. At this time, the branchless XPath processing device 200 can process the XML data 130 on an SAX basis, and can order the return values.

  In FIG. 3, the solid line arrows indicate the function call relationship, and the direction is drawn from the use to the use. The XPath processing device 190 sends the result of the branchless XPath processing device 200 to the shared buffer management device 180. At this time, data is sent using a callback function.

  The XPath type registration device 110 registers the input branch XPath type in the XPath type storage device 120. The path extraction device 160 calls the XPath expression storage device 120 to obtain a branch XPath expression, and extracts each path (TAP, TSP, PAP, PSP) from the branch XPath expression. Hereinafter, the path extraction process will be described in detail.

  The path extraction device 160 decomposes the branch XPath expression into a target path and a predicate, and constructs each absolute path (AP). The path extraction device 160 constructs a TAP by concatenating predicates from the branch XPath expression, and constructs a PAP by extracting predicates from the branch XPath expression and concatenating relative paths included in the predicate and paths to the predicates. Since the constructed absolute path is a branchless XPath expression, the filter processing of itself can be performed by using the branchless XPath processing apparatus 200.

  Then, the path extraction device 160 constructs the SP by setting the TSP as the target path itself and the PSP as the context path of the predicate. The context path of the predicate indicates in what situation the XPath expression expressed by the relative path included in the predicate is effective. Actually, the branch XPath expression from the head of the branch XPath expression to the predicate is analyzed and acquired. A context path is obtained by removing all predicates from the obtained branch XPath expression.

  In branch XPath expression processing, unlike branchless XPath expression processing, it is not possible to determine whether or not to output until the predicate is true or false, so it is necessary to buffer data that may be output. Become. FIG. 4 is an explanatory diagram showing an example of the buffer structure of the TAN. First, XML data 130 that may be output in the input stream XML is stored in the basic buffer. For each of the plurality of branch XPath expressions, what kind of buffer each has is constructed using reference information to the basic buffer. That is, it is possible to have only one buffer entity for a plurality of branch XPath expressions, and to reduce the memory usage.

  The shared index construction device 150 constructs a shared index using each path extracted by the path extraction device 160. The shared index is a graph in which a logical product or logical sum of predicate groups, an absolute path corresponding to the predicate is a node, and a relationship between each node is a link. The predicate of the branch XPath expression in the shared index is expressed using the logical product or logical sum of the decomposed predicate group.

  In the shared index, partially equal nodes and links are shared from a plurality of branch XPath expressions. When a plurality of branch XPath expressions are input and each has a shared index, there are relatively many cases where similar processing is performed when a stream is input. A part that performs the same processing is shared, that is, a plurality of branch XPath-type shared indexes are shared to construct a shared index. It is possible to process a plurality of branch XPath expressions at once using the shared index.

Specifically, when a plurality of branch XPath expressions are input, the shared index construction apparatus 150 first constructs a shared index for the first branch XPath expression. Next, another branch XPath expression is analyzed by the path extraction device 160 and the shared index construction device 150. At this time, the shared index construction device 150 scans the first branch XPath-type shared index, and there is a part in the shared index that performs the same processing as another branch XPath-type shared index. In this case, the first branch XPath type shared index is used. In this way, a shared index is sequentially constructed for all branch XPath expressions. Hereinafter, the nodes constituting the shared index will be described. The branchless XPath processing device 200 outputs a return value held by each node described later from each input path.

  TAN (Target Absolute Node) is a node corresponding to TAP. TSN (Target Scope Node) is a node corresponding to TSP. PAN (Predicate Absolute Node) is a node corresponding to PAP. PSN (Predicate Scope Node) is a node corresponding to PSP. Nodes corresponding to absolute paths (AN: Absolute path Node) are TAN and PAN, and nodes corresponding to scope paths (SN: Scope path Node) are TSN and PSN. The shared index may include a logical node (LN: Logical Node) in addition to the nodes described above. Note that LN is a node that connects TAN, PAN, and LN by logical operators (and, or).

  Here, multiple pairs of matching paths (TAP and TSP) can be combined into one node pair (TAN and TSN). Similarly, multiple matching sets of paths (PAP and PSP) can be combined into a single set of nodes (PAN and PSN). Furthermore, multiple SPs (TSP or PSP) with matching paths can be integrated into one SN. As a result, it is expected that the number of nodes will be smaller than the number of paths, and accordingly, the number of comparisons related to the predicate node and the number of calls of the callback function for TAP and PAP are also expected to decrease.

  The shared buffer management device 180 constructs a shared buffer 170 in which a buffer necessary for constructing a result for a branch XPath target path is shared. That is, the shared buffer management device 180 prepares one basic buffer and buffers the input XML data 130 when there is a possibility that the input XML data 130 may conform to the branch XPath expression. When a plurality of branch XPath expressions are processed, the buffer related to each branch XPath expression does not have the actual XML data 130 but holds the section address of the basic buffer. By doing so, it is not necessary to prepare a large buffer for each branch XPath expression, and the amount of memory used can be reduced.

  The XPath type processing device 190 performs a branching XPath type filtering process. That is, the XPath processing device 190 receives the callback function from the branchless XPath processing device 200, performs a branching XPath filtering process, and outputs the result. The XPath processing device 190 uses a shared index search device 140 and a shared buffer management device 180. Specifically, the XPath processing device 190 processes the input XML data 130 using a SAX parser and an automaton, and immediately after the end of the scope path implemented using the callback function is notified, A predicate for the path is determined to be true or false, and a plurality of branch XPath expressions are collectively filtered.

  The branchless XPath processing device 200 is an existing SAX-based XPath processing device (see Non-Patent Document 1 and Non-Patent Document 2), and registers XPath expressions without branching of target paths, predicates, and scope paths. When the XML data 130 of the stream is input, the result for the branchless XPath expression is returned through the callback function.

It is known that the branchless XPath processing apparatus 200 can process a plurality of branchless XPath expressions as follows. Although this XPath does not include a predicate, it is possible to decompose and register a branch XPath expression. By comparing the return value of the SAX callback function with the predicate condition, the branch XPath expression can determine whether the stream XML data 130 matches the predicate.
/ bib / book
/ bib / book / title
/ bib / book / publication

FIG. 5 is an explanatory diagram showing an execution example of the path extraction processing by the path extraction device, and shows an output when the XPath expressions of Expressions 3 to 5 are input. Results are output for each branch XPath expression.
/ bib / book [price <= 21OO] [publication <= 2000] / authors [author = 'Bob']… Formula 3
/ bib / book [price <= 21OO] [publication <= 2000] / authors / author… Formula 4
/ bib [book / price = 21OO] [book / publication <= 2000] / book / authors / author… Formula 5
For Equation 3, first, let TAP be an XPath equation as described below after extracting all predicates from the branched XPath equation.
/ bib / book / authors

Next, the predicate at the root side
[price <= 2100]
Let the XPath expression up to be TSP. Next, consider all the predicates described below.
[price <= 2100]
[publication <= 2000]
[author = 'Bob']
Each XPath expression until just before the predicate appears is
/ bib / book
/ bib / book
/ bib / book / authors
And each PSP (= context path). The relative path of the predicate is as follows.
price
publication
author

An XPath expression obtained by combining the relative path and the scope path is a PAP as described later.
/ bib / book / price
/ bib / book / publication
/ bib / book / authors / author

Equation 4 is omitted because it is substantially the same as Equation 3. Similarly for Expression 5, first, the following XPath expression obtained by removing all predicates from the branched XPath expression is defined as TAP.
/ bib / book / authors / author
Next, the predicate at the root side
[book / price = 2100]
Let the XPath expression up to be TSP. That means
/ bib
It becomes.

Next, consider all the following predicates:
[book / price = 2100]
[book / publication <= 2000]
Each XPath expression until just before the predicate appears is
/ bib
/ bib
And each PSP (= context path). The relative path of the predicate is as follows:
book / price
book / publication

The XPath expression combining the relative path and the scope path is the following PAP.
/ bib / book / price
/ bib / book / publication
/ bib / book / authors / author
Note that the PAPs in Equation 3 and Equation 5 are equal, but the PSP has changed.

  FIG. 6 is an explanatory diagram illustrating an execution example of a shared index construction process. FIG. 6 shows a schematic diagram when a shared index is constructed from two XPath expressions (Expression 3 and Expression 4). The rectangular frames are TAN (TAN1, TAN2), PAN (PAN1, PAN2, PAN3) (the predicate condition part is also expressed as a node for sharing), SN (SN1, SN2), LN (LN1, LN2). A line connecting the nodes indicates that the two nodes are linked. LN1 corresponds to the parent node of the nodes “<= 2100” and “<= 2000”, and LN2 corresponds to the parent node of LN1.

  What should be noted is that, in Equation 3 and Equation 4, the condition judgment of [price <= 2100] [publication <= 2000] is shared. In the specific example, only two XPath expressions are listed for simplicity, but the XPath expressions registered in practice are registered in units of tens of thousands to hundreds of thousands. Therefore, when the processing is the same as described above, sharing can be achieved by integrating them into one. In addition, when a shared index is not used, an index having the same meaning is duplicated and unnecessary memory is used. In other words, the use of a shared index can reduce the amount of memory used.

Table 5 is an explanatory diagram showing an execution example of the construction process of the shared buffer 170. The order called by the callback function corresponds to the numbers in the counter sequence. The numbers in the counter row indicate the indexes in the shared buffer 170, and by using these numbers, it is possible to buffer each XPath expression. Compared to a method in which the number of stored XML data 130 is the number of XPath expressions, only one shared buffer 170 needs to be stored regardless of the number of XPath expressions.

  FIG. 4 is an explanatory diagram showing an example of the buffer structure of the TAN. The buffer is stacked in a form that represents the interval (start, end). Since there are cases where a plurality of sections to be buffered should be influenced by the predicate, they are managed using a stack as shown in FIG. The counter when the first <book> appears is 2. The first </ book> appears at 23. The counter when the second <book> appears is 24. The second </ book> appears at 42. In this way, holding the buffer to be output as the address of the shared buffer 170 makes it possible to greatly reduce the amount of memory used for buffer processing.

  FIG. 7 is an explanatory diagram showing an execution example of a subroutine “PAN process” of the filtering process described later. This explanatory diagram assumes that the XML data 130 of FIG. 2B is input to the shared index shown in FIG. FIG. 8 is an explanatory diagram showing an execution example of a subroutine “SN process” of the filtering process described later. This explanatory diagram shows an example executed for the XML data 130 of FIG.

  FIG. 9 is a flowchart showing the process of building the target path, the absolute path of the predicate, and each scope path by dividing the branch XPath expression. Consider three XPath equations (Equation 3, Equation 4, and Equation 5). Below, it demonstrates based on these XPath type | formulas.

  First, the path extraction device 160 inputs a plurality of branch XPath expressions (S102), and if all the XPath expressions are processed (S104, Yes), the process ends (S106). That is, combinations of variables P and T corresponding to each branch XPath expression are output as many as the number of input branch XPath expressions.

  Next, if all the XPath expressions are not processed (S104, No), the path extraction device 160 stores the variable P that can store the PAP and PSP of the branch XPath expression and the variable T that can store the TAP and TSP. One for each branch XPath expression is prepared (S108). Add all predicates from the branch XPath expression to the variable T as TAP (S110), and add to the variable T as the TSP the context path to the predicate that appears first from the root of the branch XPath expression. (S112).

  If all the predicates are not processed (S114, No), the path extracting device 160 adds the PAP and PSP for the selected predicate to the variable P (S116). Specifically, the one obtained by removing all predicates from the branch XPath expression up to the predicate is added as a PSP to the variable P, and the path simply combining the relative path included in the PSP and the predicate is defined as the PAP. Add to If all the predicates have been processed (S114, Yes), the process returns to S104.

  10 and 11 are flowcharts showing the shared index construction process. In the shared index, the node is defined as a node when the shared index is represented by a graph structure. A shared index link is obtained by connecting nodes with edges. When there are a plurality of predicates, these predicates are combined with and or or. LN can be used to express this combination of predicates.

  First, the shared index construction device 150 inputs each path (TAP, TSP, PAP, PSP) extracted from the branch XPath expression for all branch XPath expressions (S202), and processes all the branch XPath expressions. If so (S204, Yes), the shared index constructed at that time is output, and the process ends (S206).

  Next, if all the branch XPath expressions are not processed (S204, No), the shared index construction apparatus 150 creates a TAN from the TAP (S208), and there is no TSN linked to the TAN in the shared index. If so (S210, No), a TSN is created (S212). Note that TAN determines the conditions of the predicate for all predicates included in the branch XPath expression by a tree structure using LN and outputs the buffer.

  The shared index construction device 150 links TAN and TSN (S214), and prepares a variable P for holding LN (S216). The variable P is used to construct a tree structure having one LN as a root.

  Furthermore, if the shared index construction device 150 includes only one LN in the variable P (S218, Yes in FIG. 11), it can construct a tree structure having that one LN as a root. Thus, LN and TAN are linked (S220 in FIG. 10), and the process returns to S204. As a result, one branch XPath expression can be incorporated into the shared index.

  When the shared index construction apparatus 150 does not include only one LN in the variable P (S218, No in FIG. 11), the processing is completed for all the predicates of the selected branch XPath expression. If no PAN exists (S224, No), a PAN is created and added to the variable P (S226).

  Furthermore, if the PSN does not exist (S228, No), the shared index construction apparatus 150 creates a PSN (S230). Then, the shared index construction device 150 links the PSN and the PAN (S232), and returns the process to S218.

  Then, the shared index construction device 150 satisfies the condition of S222 or S224, and if there is no predicate having the same LN in the existing shared index (S234, No), the newly created PAN is stored in the variable P. Add (S236), and return the process to S218. The newly created PAN is a node that stores a logical operator, a PAN, and a node arbitrarily selected from PAN or LN included in the variable P. On the other hand, if there is a predicate (S234, Yes), the existing LN is added to the variable P, the LN and PAN stored in the LN are deleted from the variable P (S238), and the process returns to S218.

  FIG. 12 is a flowchart showing the construction process of the shared buffer 170.

  First, the shared buffer management device 180 is activated by the callback of the branchless XPath processing device 200 (S302). Next, the shared buffer management device 180 terminates by calling endDocument () (S304, Yes) (S322).

  Then, the shared buffer management device 180 does not call endDocument () (S304, No). When a new XML document is input, the shared buffer management device 180 changes the buffer order by calling startDocument () (S306, Yes). A counter variable C is prepared and initialized with C = 0 (S308).

  Further, the shared buffer management device 180 increments the counter C by calling startElement (var) (S310, Yes) instead of calling startDocument () (S306, No), and is given by the counter C and the argument var. The data set is added to the shared buffer 170 (S312).

  Then, the shared buffer management device 180 increments the counter C by calling endElement (var) (S314, No) instead of calling startElement (var) (S314, No), and gives the counter C and the argument var. The obtained data set is added to the shared buffer 170 (S316).

  Further, the shared buffer management device 180 increments the counter C by calling character (var) (S318, Yes) instead of calling endElement (var) (S314, No), and gives it by the counter C and the argument var. The set of data is added to the shared buffer 170 (S320). If it is not a call for character (var) (S318, No), the process returns to S302.

  FIG. 13 is a flowchart showing processing for filtering using the shared index and shared buffer 170.

  First, the shared index search device 140 is activated by the callback of the branchless XPath processing device 200 (S402) and has processed all callbacks (S404, Yes), and ends (S406). Similar to the shared buffer management device 180, the XPath processing device 190 passes the processing result of the branchless XPath processing device 200 using a callback function.

  Next, when the shared index search device 140 has not processed all the callbacks (S404, No), if it has not processed all TANs for the callback (S408, No), it is unprocessed. The subroutine “TAN processing” is executed with a certain TAN as an argument (S410).

  Then, the shared index search device 140 processes all TANs (S408, Yes). If all PANs are not processed for the callback (S412, No), the unprocessed PAN is used as an argument. The subroutine “PAN process” is executed (S414).

  Furthermore, the shared index search device 140 processes all PANs (S412, Yes), and if not all SNs are processed for the callback (S416, No), the unprocessed SN is used as an argument. The subroutine “SN process” is executed (S418). If all the SNs have been processed (S416, Yes), the process returns to S404.

  FIG. 14 is a flowchart showing a subroutine “TAN process”.

  First, the shared index search device 140 is activated when the callback of the branchless XPath processing device 200 is called back (S502), and when all the callback function calls are completed (S504, Yes), the processing ends (S506). ).

  Next, if all the callback function calls have not been completed (S504, No), the shared index search device 140 prepares a counter C by calling startDocument () (S508, C = 0). (S510).

  Then, the shared index search device 140 increments the counter C by calling startElement (var) (S512, Yes) instead of calling startDocument () (S508, No) (S514). Furthermore, the shared index search device 140 increments the counter C by calling endElement (var) (S516, Yes) instead of calling startElement (var) (S512, No) (S518). Then, the shared index search device 140 increments the counter C by calling character (var) (S520, Yes) instead of calling endElement (var) (S516, No) (S522).

  In the startElement, endElement, and character functions, the variable C is incremented to have the same counter value as the shared buffer management device 180. As a result, when performing the corresponding XPath buffer, it is possible to perform buffering with the counter value of the shared buffer 170.

  Furthermore, the shared index search device 140 adds a buffer not by calling character (var) (S520, No) but by calling startContext () (S524, Yes), and adds the value of the counter C to the start address + 1. Is substituted (S526).

  Then, the shared index search device 140 substitutes the value of the counter C for the end address of the buffer (S530) by calling endContext () instead of calling startContext () (S524, No) (S530). . In this case, the counter value is buffered when the endContext function is called. If it is not a call to endContext () (S528, No), the process returns to S502.

  FIG. 15 is a flowchart showing a subroutine “PAN process”. Here, the shared index is used to determine what the branch XPath expression is suitable for the predicate condition.

  First, the shared index search device 140 is activated when the callback of the branchless XPath processing device 200 is called back (S602) and all the callback function calls are finished (S604, Yes), and is finished (S606). ).

  Next, the shared index search device 140 has not finished calling all the callback functions (S604, No), is not calling character (var) (S608, No), and is calling startContext () ( S610, Yes), “ture” is set to the flag EVAL indicating that the condition of the predicate is to be checked (S612). When the PAN is called from the branchless XPath processing device 200 through the startContext and endContext functions, it is determined whether or not the condition is to be evaluated. startContext indicates that the absolute path of the predicate has entered an interval to be evaluated.

  Then, the shared index search device 140 sets false to the flag EVAL indicating that the condition of the predicate is to be checked by calling endContext () (S614, Yes) instead of calling startContext () (S610, No). Set (S616). endContext indicates that the absolute path of the predicate is out of the interval to be evaluated. Each state is represented by an EVAL flag. The process returns to S604.

  Further, the shared index search device 140 calls character (var) (S608, Yes), and if EVAL = false (S618, Yes) or all conditions of the PAN are processed (S620, Yes), the process is performed. Returning to S604, if EVAL = false (S618, No) and all the conditions of the PAN have not been processed (S620, No), the following processing is performed.

  That is, the shared index search device 140 evaluates whether the argument var of the character function that satisfies the condition satisfies the predicate node condition (S622). If the condition is not satisfied (S622, No), the condition is satisfied. Notify the condition that the condition is not satisfied through the link to the parent node of the node that has not been notified (S624), and if the notified parent node changes its state, the notification is sent to a higher-order parent node. . On the other hand, if the condition is satisfied (S622, Yes), the fact that the condition is satisfied (the condition part is true) is notified through the parent node (operator node) of the node that satisfies the condition (S626), The notified parent node further notifies the parent node. The process returns to S618.

FIG. 16 is a flowchart showing a subroutine “SN process”. Specifically, to use the scope path to perform output management of the target path, deletion from the buffer stored in the target path node when the predicate evaluation is false, and clearing the shared index holding information The flowchart of is shown. For simplicity, consider the following branch XPath expression.
/ bib / book [price <= 2100] [publication <= 2000] / authors / author
Even when there are a plurality of branch XPath expressions, it is possible to perform the same processing for each branch XPath expression using the shared index and the shared buffer 170.

  First, the shared index search device 140 is started when the callback of the branchless XPath processing device 200 is called back (S702) and all the callback function calls are finished (S704, Yes), and is finished (S706). ).

  Next, if all the callback function calls have not ended (S704, No), the shared index search device 140 prepares a counter C by calling startDocument () (S708, Yes), and C = O (S710). Counter C is processed to use the counter of shared buffer 170. In addition, start and end variables representing the scope section are prepared and initialized with 0.

  Then, the shared index search device 140 increments the counter C by calling startElement (var) (S712, Yes) instead of calling startDocument () (S708, No) (S714). Furthermore, the shared index search device 140 increments the counter C by calling endElement (var) (S716, Yes) instead of calling startElement (var) (S712, No) (S718). The shared index search device 140 increments the counter C by calling character (var) (S720, Yes) instead of calling endElement (var) (S716, No) (S722).

  Further, the shared index search device 140 substitutes C + 1 for start (S726) by calling startContext () instead of calling character (var) (S720, No) (S726). The shared index search device 140 substitutes C for end (S730) by calling endContext () instead of calling startContext () (S724, No) (S730). When the startContext and endContext functions are called, you can first determine the scope range and set it to the variables start and end. If it is not a call to endContext () (S728, No), the process returns to S702.

  Furthermore, the shared index search device 140 does not process all PANs linked to the SN (S732, No), and if the condition of all PANs linked to the SN is false, this All the buffers included in the start address and end address are cleared from all TAN buffers having predicates as conditions (S734), and the predicate node and its associated operator node are set to false.

  Then, the shared index search device 140 processes all PANs linked to SN (S732, Yes), and does not process all TANs linked to TSN (S736, No). The section (start, end) of the shared buffer 170 in which all TANs linked to the TAN are buffered is output (S738), and all PANs and LNs linked to the TANs are set to false. If all TANs linked to the TSN have been processed (S736, No), the process returns to S702.

  The present invention described above is compared with the following comparative examples.

FIG. 17 is a state transition diagram showing an automaton created from the XPath expression related to the comparative example. A plurality of existing SAX-based XPath processing apparatuses 190 (see Non-Patent Document 3) creates an automaton as shown in FIG. 17 when an XPath expression such as Expression 6 is given.
/ bib / book [contains (title / text (), 'XML')] [publication> = 1999 and publication <= 2000]… Formula 6
An automaton is like a state transition diagram. The state indicated by the circle is the state, and what is written accompanying the arrow is the condition for changing the state. State 0 indicates an initial state. In order to go from state 0 to state 1, it is necessary for the bib element to come. In order to go from state 1 to state 2, it is necessary for the book element to come in state 1.

  In state 2, a transition called an ε (epsilon) transition is performed. This transition indicates that when a transition occurs in the state 2, it automatically transitions to the state indicated by the arrow. That is, when transitioning to state 2, transition is made to states 3, 5, and 7, respectively. The state 3 to the state 4 correspond to the first condition of the expression 6 ([contains (title / text (), 'XML')]). When the character string “XML” is included in the text between the title tags, the state transitions to state 4. State 5 to state 6 and state 7 to 8 correspond to [publication> = 1999] [publication <= 2000], respectively.

  Finally, when all of the state 4, the state 6, and the state 8 are satisfied, it can be said that the XML data 130 satisfies the expression 6. At this time, in the existing technology, the condition determination process is performed twice for the same search target node called publication. If the number is increased to a plurality of XPath expressions, it is very inefficient to perform the same number of processes on the same search target node.

  On the other hand, according to the present invention, in the shared index illustrated in FIG. 6, the number of comparisons between the XML data 130 and the predicate is not proportional to the number of XPath expressions or the number of predicates included in the XPath expression, but overlaps. By integrating the data, the number of comparisons is suppressed.

It is explanatory drawing which shows the relationship between the SAX filter regarding one Embodiment of this invention, and a user application. It is explanatory drawing which shows the example of XML regarding one Embodiment of this invention. It is a block diagram which shows the XPath type processing apparatus regarding one Embodiment of this invention. It is explanatory drawing which shows an example of the buffer structure which TAN regarding one Embodiment of this invention has. It is explanatory drawing which shows the execution example of the construction process of the branch path | pass which divides | segments the branch XPath type | formula regarding one Embodiment of this invention, and the absolute path of a target path and a predicate, and each scope path. It is explanatory drawing which shows the execution example of the construction process of the shared index regarding one Embodiment of this invention. It is explanatory drawing which shows the example of execution of the subroutine "PAN process" of the filtering process regarding one Embodiment of this invention. It is explanatory drawing which shows the example of execution of the subroutine "SN process" of the filtering process regarding one Embodiment of this invention. It is a flowchart which divides | segments the branch XPath expression regarding one Embodiment of this invention, and shows the construction process of the absolute path | pass of a target path, a predicate, and each scope path. It is a flowchart which shows the construction process (the first half) of the shared index regarding one Embodiment of this invention. It is a flowchart which shows the construction process (latter half) of the shared index regarding one Embodiment of this invention. It is a flowchart which shows the construction process of the shared buffer regarding one Embodiment of this invention. It is a flowchart which shows the process which filters using the shared index and shared buffer regarding one Embodiment of this invention. It is a flowchart which shows the subroutine "TAN process" of the filtering process regarding one Embodiment of this invention. It is a flowchart which shows the subroutine "PAN process" of the filtering process regarding one Embodiment of this invention. It is a flowchart which shows the subroutine "SN process" of the filtering process regarding one Embodiment of this invention. It is a state transition diagram which shows the automaton created from the XPath type | formula regarding the comparative example of this invention.

Explanation of symbols

110 XPath type registration device 120 XPath type storage device 130 XML data 140 Shared index search device 150 Shared index construction device 160 Path extraction device 170 Shared buffer 180 Shared buffer management device 190 XPath type processing device 200 Branchless XPath type processing apparatus

Claims (1)

An XPath-type processing apparatus that processes a branch XPath expression for filtering XML data,
The XPath type processing device includes an XPath type storage means, a path extraction means, a shared index construction means, a shared buffer management means, and an XPath type processing means,
The XPath expression storage means stores a plurality of input branch XPath expressions in a storage means,
The path extraction means is provided for each branch XPath expression stored in the storage means by the XPath expression storage means.
The path to be returned when the predicate condition of the branch XPath expression is satisfied is the absolute path of the target path,
The scope path of the target path is the context path of the predicate at the leftmost of the branch XPath expression.
By combining the predicate expressed by the relative path and the context path of the predicate, the absolute path of the predicate is obtained.
Extract the context path of the predicate as the scope path of the predicate,
The shared index construction means includes:
Generate a TAN (Target Absolute Node) from the absolute path of the target path extracted by the path extraction means,
A TSN (Target Scope Node) is generated from the scope path of the target path extracted by the path extraction means,
Generate a PAN (Predicate Absolute Node) from the absolute path of the previous description word extracted by the path extraction means,
A PSN (Predicate Scope Node) is generated from the scope path of the previous description word extracted by the path extraction means,
When there are a plurality of pairs having the same path among the TAN and TSN pairs extracted from the same branch XPath expression, these sets are combined into one set,
When there are a plurality of pairs having the same path among the PAN and PSN pairs extracted from the same branch XPath expression, these sets are merged into one set;
The TSN and the PSN are SNs (Scope Nodes), and when there are multiple SNs with matching paths, they are integrated into one SN,
The branch XPath expression generated from the extraction source branch XPath expression can be expressed by a combination of nodes, and corresponds to the TAN extracted from the same extraction source branch XPath expression and the absolute path indicated by the TAN. The SN corresponding to the scope path is connected by a link, and the PAN extracted from the branch XPath expression of the same extraction source and the SN corresponding to the scope path corresponding to the absolute path indicated by the PAN are connected by a link. The TAN and the PAN extracted from the same extraction source branch XPath expression are connected with a logical symbol representing a logical sum or logical product indicated by the same extraction source branch XPath expression, Construct one shared index from multiple branch XPath expressions,
The shared buffer management means constructs, for each TAN of the shared index, a shared buffer in which numbers are assigned in order according to the appearance order for each component of the input XML data. XML data for the range of the target path indicated by each TAN is stored in the shared buffer,
The XPath processing means is:
By parsing the input XML data with a SAX parser, a callback function is generated,
When the end of the scope path indicated by the SN of the shared index is notified by the callback function,
In the shared index, the authenticity determination of the predicate indicated by the PAN connected by a link from the notified SN is performed,
When the determination result of the PAN linked to the TAN is false for the TAN connected by a link from the PAN that has performed the authenticity determination of the previous description word, the scope indicated by the SN from the shared buffer of the TAN After deleting the XML data for the range of the path, and after determining the authenticity of the previous descriptive word for all the PANs connected by links from the notified SN, from the notified SN For all the TANs connected by the link, output the XML data for the range not deleted from the XML data for the range of the target path indicated by the TAN from the TAN shared buffer as a filtering result. A featured XPath processing device.

Images