JP4320004B2 - XPath processing method, XPath processing device, XPath processing program, and storage medium storing the program - Google Patents

Description

The present invention relates to a process an XPath expression using an automaton, in particular performs differential additional XPath expressions, XPath expression processing method, XPath expression processor relates to a storage medium body which stores the XPath expression processing program, and a program.

  For example, a new news distribution format based on XML (Extensible Markup Language) is NewsML. NewsML can freely combine news materials such as news articles, images, videos, and voices, and can send information to various devices such as websites, mobile phones, and televisions (TV data broadcasts). A recipient (user) of NewsML can obtain necessary information by registering a search condition in the filter engine. Since the search condition is described in the XML query language, the filter engine processes each XPath expression and also adds an XPath (XML Path Language) expression.

  When filtering XML data (stream data or the like) input using the XPath expression, it is effective to use an automaton derived from the XPath expression. Incidentally, an automaton is a general term for models that mathematically represent a calculation mechanism such as a computer, and has an input, an output, and a state. Among these, a deterministic finite automaton (DFA) is an automaton in which a transition destination (transition destination) for an input is determined as one. On the other hand, a nondeterministic finite automaton (NFA) is an automaton having a plurality of transition destinations (transition destinations) for an input in a certain state.

In the conventional technique for adding to an already input XPath expression, a DFA for processing the XPath expression is separately generated each time the XPath expression is added. Therefore, the DFA increases every time an XPath expression is added. There was a problem with it. Therefore, the technique disclosed in Patent Document 1 uses the XPath expression for the desired condition of each user, and extracts and distributes partial XML data desired by a plurality of users from the XML data. In accordance with the addition, the DFA derived from the XPath expression can be updated with the difference between before and after the addition.
JP 2003-323429 A (Claim 1)

  In the related art (for example, Patent Document 1) related to DFA difference update (difference addition), XML data is required when adding an XPath-type difference. Therefore, during the evaluation of data conversion processing of XML data, automaton update processing that reflects the addition / deletion of the XPath expression in the automaton becomes an overhead, and the performance at the time of evaluation of XML data deteriorates. As a result, there is a problem that it takes time until the user acquires the latest XML data. In particular, when the XML data is news data with immediacy such as traffic information, it is important for the user not to take time until acquisition.

  Accordingly, the main object of the present invention is to solve the above-described problems, update the automaton for evaluating the XML data, and allow the automaton to process the XML data quickly.

In order to solve the above-described problem, the present invention updates the pre-update DFA indicating the pre-update XPath expression input to process the XML data to the post-update DFA indicating the input post-update XPath expression. A processing method in which a computer reads the pre-update DFA derived to process the pre-update XPath expression, holds the start state as a state ds, reads the XPath expression to be added, and Deriving a differential NFA and holding its start state as a state ns, calling a first subroutine for performing an XPath expression addition operation using the state ds and the state ns as arguments, and the updating The difference NFA is reflected in the pre-update NFA for processing the previous XPath expression to obtain the post-update NFA. And when the state ds exists, the first subroutine adds the state ns to the NFA state group held by the state ds, and a transition group from the state ns. , A step of selecting an unprocessed transition from the acquired transition group one by one as a transition ne, calling a second subroutine with the state ds and the transition ne as arguments, and the transition ne A step of ending this subroutine when there is no unprocessed transition to be selected, and the second subroutine is a transition that matches the transition ne in the transition group held by the state ds. If there is not, the step of newly adding the transition ne to the transition group of the state ds and ending this subroutine, and the state ds is retained If there is a transition that matches the transition ne in the transition group, the unprocessed transitions are selected one by one as the transition de, the DFA state of the transition destination of the transition de is held as the state ds1, and the transition The NFA state of the transition destination of ne is held as the state ns1, and the step of calling the first subroutine with the state ds1 and the state ns1 as an argument is sequentially executed, thereby updating the pre-update DFA. It is characterized by being configured as a subroutine for updating to a later DFA .
Furthermore, the present invention is an XPath type processing apparatus that is the computer, an XPath type processing program executed by the computer, and a storage medium that stores the XPath type processing program.

As a result, since only the information of the XPath expression to be updated is differentially updated in the DFA (existing DFA) generated so far, it is not necessary to generate a new DFA separately. For this reason, the memory space can be effectively used. Further, since XML data is not required for the difference update, the XPath-type information can be quickly updated by difference.
Furthermore, it is possible to reliably update the difference of the XPath type information for the DFA, and to use the memory space more efficiently.
Then, DFA can be added quickly while making effective use of the memory space.

The present invention is an XPath expression processing method for updating a pre-update DFA indicating an XPath expression before update input to process XML data into an updated DFA indicating an input XPath expression after update. A computer reads the pre-update DFA derived to process the pre-update XPath expression, holds the start state as a state ds, derives an NFA to be deleted, and sets the start state as a state ns A step of holding, a step of calling a third subroutine for performing an XPath expression deletion operation using the state ds and the state ns as arguments, and the pre-update NFA for processing the pre-update XPath expression, Deleting the NFA to be deleted and setting it as an updated NFA, and the third subroutine is When the state ds exists, the state ns is deleted from the NFA state group held by the state ds, and when there is no NFA state group held by the state ds, the subordinate of the state ds is deleted. A step, a step of acquiring a transition group from the state ns, and selecting an unprocessed transition of the acquired transition group one by one as a transition ne, and using the state ds and the transition ne as arguments, A step of calling a subroutine and a step of ending the subroutine when there is no unprocessed transition to be selected as the transition ne, and the fourth subroutine is a transition held by the state ds. If there is no transition suitable for the transition ne in the group, the step of ending this subroutine and the transition group held by the state ds If there is a transition that matches the transition ne, the transitions that are not processed are selected one by one as the transition de, the DFA state of the transition destination of the transition de is held as the state ds1, and the transition ne The NFA state of the transition destination is held as the state ns1, and the step of calling the third subroutine using the state ds1 and the state ns1 as an argument is sequentially executed, whereby the pre-update DFA is changed to the post-update DFA. It is characterized by being configured as a subroutine to be updated .
Furthermore, the present invention is an XPath type processing apparatus that is the computer, an XPath type processing program executed by the computer, and a storage medium that stores the XPath type processing program.

As a result, since only the information of the XPath expression to be updated is differentially updated in the DFA (existing DFA) generated so far, it is not necessary to generate a new DFA separately. For this reason, the memory space can be effectively used. Further, since XML data is not required for the difference update, the XPath-type information can be quickly updated by difference.
Furthermore, it is possible to reliably update the difference of the XPath type information for the DFA, and to use the memory space more efficiently.
Then, the DFA difference can be quickly deleted while effectively using the memory space.

  According to the present invention, since the XPath expression to be added / deleted is immediately updated in the DFA generated so far, the DFA difference update operation does not occur when the XML data is evaluated. As described above, since the deterministic automaton is updated when an XPath expression is added / deleted, performance degradation due to the influence of the addition / deletion operation of the XPath expression does not occur when XML data is evaluated.

  Hereinafter, an embodiment of an XPath processing method of the present invention will be described in detail with reference to the drawings. Note that the XPath type processing method described below also embodies an XPath type processing apparatus and an XPath type processing program. In the first embodiment, difference update for adding a new XPath expression to an existing XPath expression will be described, and in the second embodiment, difference update for deleting a part of an existing XPath expression will be described. Hereinafter, the first embodiment will be described.

  FIG. 1 is a diagram showing an outline of a filter engine to which the XPath processing method is applied. XML data generated according to the XML format by a data provider (not shown) is transmitted to the filter engine 10 that executes the XPath processing method via a network such as an intranet. In the filter engine 10, each user who receives the XML data registers in advance the data condition (personal profile) he wants in the filter engine 10 in the form of an XML query as in the conventional example.

  The filter engine 10 filters and converts XML data such as a news source sent according to a registered personal profile, and distributes the converted XML data to individual users. A specific example of XML data such as a news source is NewsML. As mentioned above, NewsML is a new news distribution format based on XML, which can freely combine news materials such as news articles, images, videos, and voices, and send information to various devices such as websites and mobile phones. be able to. It is also suitable for structuring and centrally managing various news materials such as news articles, images, videos, and voices.

  The filter engine 10 also includes the XPath processing device and the XPath processing program of the claims. Incidentally, XML is a meta language recommended by the World Wide Web Consortium (W3C) as an Internet standard. Meta language means the language that makes a language. XML data (XML document: also called XMLDocument) is a document or data created using a language created by XML.

  Then, the filter engine 10 extracts XML data that conforms to the XPath expression, which is a user's desired condition, from the XML data. Here, as will be described in detail later, the filter engine 10 is characterized in that all additions and deletions of the XPath expression are immediately reflected in the DFA derived from the XPath expression. As a result, there is an effect that the processing is speeded up because no operation related to the update of the XPath expression occurs at the time of processing the XML data.

  FIG. 2 is a block diagram showing an internal configuration of the filter engine 10 of FIG. As shown in FIG. 2, the filter engine 10 includes an XML parsing module 11, an inquiry parsing module 12, a data extraction module 13, a DFA creation module 13B, an automaton management unit 15, a data conversion module 16, a DFA update module 17, and The update automaton management unit 18 is included. The filter engine 10 includes a main control device including a CPU and a RAM, an external storage device including a hard disk, a computer having a NIC (Network Interface Card) for communication, and a router. Composed. The automaton management unit 15 and the updated automaton management unit 18 are stored in, for example, an external storage device.

  The XML parsing module (XML parser) 11 parses input XML data, converts it into internal format XML data (SAX (Simple API for XML) event), and outputs the data to the data extraction module 13. Note that parsing is analysis processing that reads XML data described in a text format and analyzes document elements, attributes, and the like specified by XML tags (in this embodiment, parsing procedures are particularly limited). Not) Incidentally, API (Application Programming Interface) for manipulating XML data through the XML parsing module 11 has two types of standard interfaces, DOM (Document Object Mode) and SAX. In this embodiment, the XML parsing module 11 corresponds to the latter SAX.

  Note that the XML parsing module 11 corresponding to SAX sequentially reads XML data and starts various handlers added in each time an XML tag (start tag, end tag, empty element tag) is detected. Here, the handler is a program that defines a method for processing each element of XML data based on the SAX interface. Further, the tag is a character string described in the XML data for clearly indicating the position of the element and storing the attribute.

  The inquiry parsing module 12 generates an XPath expression. Specifically, the inquiry parsing module 12 parses (analyzes) an individual profile to be added (search conditions described in the XML inquiry language), and performs “data conversion operation” and “individual XPath” which are data extraction operations. Separated into "expression". The XPath expression is converted to an automaton by the DFA creation module 13B and then output to the data extraction module 13. The data conversion operation is output to the data conversion module 16. The XPath expression is a language indicating a specific part of the XML data. If the XPath expression is used, an arbitrary position in the data can be indicated even if an anchor or the like is not embedded in the XML data.

  The DFA creation module 13B converts each XPath expression input from the inquiry parsing module 12 into NFA (generates NFA), combines the NFA with a combined NFA, generates a DFA from the combined NFA, and generates an automaton management unit. 15 is registered (added).

  The data extraction module 13 uses the DFA stored in the automaton management unit 15 to convert the partial XML extracted from the XML data input to the XML parsing module 11 into the internal format XML data (filtered internal format XML data). ) To the data conversion module 16.

  The data conversion module 16 performs a predetermined conversion from the data conversion operation and the extracted XML data in the internal format, and outputs the result as filtered XML data (converted XML data). The predetermined conversion is not particularly limited in the present invention.

  Next, the automaton management unit 15 will be described in detail. FIG. 3 is a diagram showing a data structure on the memory of the automaton management unit 15 in FIG. Details of the DFA are shown in FIG.

  As shown in FIG. 3, an NFA is generated for each XPath expression. The plurality of NFAs generated in this way are combined by one node, and connected to individual NFAs from the root by epsilon edges (combined NFA). The epsilon edge is an “empty character string” normally defined in, for example, an automaton. The DFA is generated and updated sequentially using the combined NFA. Alternatively, DFA sequentially generates and updates necessary states according to the input of combined NFA and XML data.

FIG. 4 is a diagram showing a data structure on the specific program of FIG. In FIG. 4, a variable class (class variable) is a class that generates an instance for each XPath expression, and has the following attributes. Note that an instance refers to an object actually created by using a class definition as a model in, for example, object-oriented programming.
* "Id" which is an internal identifier that is different for each instance
* "XPath expression" which is an expression of each XPath expression
* "VarName" which is a name for the user to distinguish Variable

The State class (class State) is a class that expresses the state of the NFA and has the following attributes.
* A set of edges “edges” representing transitions from one state to another
* “Type” indicating whether its own state is termination or non-termination (when the expression of the XPath expression is converted to NFA, the last state is termination and the other states are non-termination)
* “Var” indicating from which Variable instance (that is, from the XPath expression) its state was created

The DFAState class (class DFAState) represents the state of the DFA, the State class is defined using object-oriented inheritance, and has the following attributes.
* “States” that expresses the NFA state group that is required when generating a DFA using NFA
Although “edges” is inherited from the “State” class, it can be redefined using a hash or map structure instead of “list” in order to increase the processing speed.

The Edge class (class Edge) represents an edge between NFA state states or an edge between DFA states, and has the following attributes.
* State "to" that is the edge destination of its own edge
* State "from" which is the edge source of its own edge

  FIG. 5 is a diagram illustrating a data structure on the memory of the DFA of FIG. However, in FIG. 5, unlike FIG. 4, a map structure is used instead of a list in order to realize “edges”.

  DFAState located on the left side of FIG. 5 is an instance of the DFAState class, and expresses one state of DFA. In the state of FIG. 5, the values of states, edges, type, var, and varId that are attribute values are set. Here, states represents an NFA state group. edge represents a set of a reference to an edge label and an edge instance. Since type is non-terminal, it is “non-terminal”. var is a reference to a Variable instance. In this example, varId is 3, which means that this DFAState reflects the state up to the third variable (XPath expression).

  An Edge instance group is located in the middle (left middle) of FIG. Further, a DFAState instance group corresponding to the transition destination of Edge is located in the right middle of FIG. As shown in FIG. 5, the transition destination of Edge is allowed to be Null (DFAState is not generated).

  The DFA update module 17 identifies the pre-update automaton state corresponding to the state permitted by the updated automaton from the constructed DFA managed by the automaton management unit 15, and updates the identified individual states with differences.

  In other words, the process of updating with the difference means that instead of using all the updated XPath expressions, the difference XPath expression that is the difference between the pre-update XPath expression and the post-update XPath expression is used to change from the pre-update DFA to the post-update DFA. It is a process to update. First, the automaton management unit 15 calculates the pre-update XPath expression, the pre-update NFA derived from the pre-update XPath expression (the middle NFA in FIG. 3), and the pre-update DFA derived from the pre-update NFA (the lower half of FIG. 3). DFA) is managed. Next, the updated automaton management unit 18 manages the difference NFA derived from the difference XPath expression.

  Then, the DFA update module 17 performs partial update from the pre-update DFA to the post-update DFA using the differential NFA. In other words, the DFA update module 17 adds the difference XPath expression information by converting the difference XPath expression into a difference NFA and adding the difference NFA to the pre-update NFA and the pre-update DFA.

  Next, an example of data before update shown in FIG. 6 and an example of data after update shown in FIG. 7 will be described.

  FIG. 6 is a diagram illustrating an example of data managed by the automaton management unit 15. The DFA creation module 13B derives NFA corresponding to each expression from the three XPath expressions (pre-update XPath expression: see FIG. 6A), and integrates these NFAs (NFA before update: FIG. 6B). )) And DFA (DFA before update: see FIG. 6C) is derived therefrom.

  For example, “/ a // b” illustrated in FIG. 6A includes the states of S1, S2, and S3 and transitions of a, *, and b. Since // label matches the element whose name of the arbitrary depth of the input XML data is “label”, in NFA, it is associated with self-transition by a wild card (*). “/ D // b” is composed of the states of S4, S5, and S6 and transitions of d, *, and b. “/ A / c / b” is the states of S7, S8, S9, and S10. It consists of transitions of a, c, b.

  Next, the DFA creation module 13B integrates these three NFAs with the state of S0 and the start state of each NFA in the state of S0 based on the transition of epsilon (the integrated NFA shown in FIG. 6B). Create).

  Further, the DFA creation module 13B generates a DFA equivalent to this integrated NFA (FIG. 6C). The DFA is created by, for example, subset construction. In this example, an example of a delay evaluation DFA as shown in Patent Document 1 is used, and the state is partially NULL. Each state of the DFA includes an NFA state group representing an NFA state corresponding to the transition group. In order to simplify the notation, in the notation of the NFA state group, the prefix S representing the NFA state is omitted and only the number is described. Therefore, for example, the state S0 in FIG. 6B corresponds to “0” in the state {0, 1, 4, 7} in FIG.

  FIG. 7 is a diagram illustrating an example of data stored in the storage device. The updated automaton management unit 18 manages an XPath expression to be added (difference XPath expression: see FIG. 7A) and an NFA derived from the XPath expression (difference NFA: see FIG. 7B). The automaton management unit 15 manages the NFA in which the differential NFA is added to the pre-update NFA (FIG. 6B) (post-update NFA: see FIG. 7C).

  FIGS. 8 and 9 show the updated DFA, which is the result of the DFA update module 17 adding the difference NFA of FIG. 7B to the pre-update DFA shown in FIG. 6C. . The hatched state represents the updated state.

  Details of the processing of the DFA update module 17 will be described below with reference to flowcharts. The DFA update module 17 performs DFA difference update according to the flowcharts shown in FIGS.

  FIG. 10 shows a DFA update flow. In S200, the DFA (pre-update DFA) derived to process a plurality of XPath expressions (pre-update XPath expressions) is read, and the start state is held as the state ds. In S210, the XPath expression (difference XPath expression) to be added is read, an NFA (difference NFA) is derived therefrom, and the start state is held as the state ns. Using these state ds and state ns as arguments, the subroutine DFA (pre-update DFA) state shown in S220 is updated. At any timing in the DFA update flow (FIG. 10), the DFA update module 17 reflects the difference NFA in FIG. 7B on the pre-update NFA in FIG. It will be NFA after the update.

  FIG. 11 shows details of the DFA state update flow which is a subroutine. Here, the flow for the addition operation of the XPath expression is particularly shown. In this subroutine, in addition to the regular DFA, the delay evaluation type DFA described in Patent Document 1 is also supported. Therefore, in S310, it is determined whether or not the state ds is NULL (not evaluated). If it is NULL (S310, Yes), the status of the update target has not been evaluated, so this subroutine is terminated (return). If the state ds exists (S310, No), the NFA state ns of the XPath expression to be added is added to the NFA state group held by the state ds in S320.

  Subsequently, in order to update the DFA using the transition from the NFA state ns, a transition group from the state ns is acquired in S330. It is determined whether or not there is a transition in which the processes of S350 and S360 are unprocessed in the transition group acquired in S340. If there is no unprocessed transition, updating of the DFA for all transitions is completed (return). If there is an unprocessed transition, one unprocessed transition is selected in S350 and held as a transition ne. Then, the subroutine “DFA state update by transition” shown in S360 is performed using the state ds and the transition ne as arguments.

  FIG. 12 shows details of the DFA state update flow based on the transition that is a subroutine. In S400, a transition that matches the transition ne on the NFA side is specified in the transition group held by the DFA state ds. In S410, it is determined whether there is a suitable transition. If there is no suitable transition, the process proceeds to S450, a transition ne is newly added to the transition group of the state ds, and this subroutine is terminated (return). If there is a matching transition, the process proceeds to S420, and it is determined whether there is a transition that has not been processed.

  If there is no unprocessed transition, the DFA update by the transition ne is complete, so this subroutine is terminated (return). If there is a transition that has not been processed, one transition that has not been processed is selected in S430 and held as a transition de. In S440, the transition DFA state of the transition de is held as the state ds1, and the transition destination NFA state of the transition ne is held as the state ns1. Using these state ds1 and state ns1 as arguments, the subroutine “DFA state update” shown in S220 is performed.

  As shown in FIGS. 10 to 12, the present invention executes a process of sequentially tracing the state according to the transition for the NFA derived from the updated XPath expression, and in the execution process, the DFA conforming to each transition in the NFA. The transition is specified, the NFA state group and the transition group held by each state of the DFA are confirmed, and the difference between the NFA state group and the transition group and the difference NFA is updated.

  In order to specifically describe the processing of FIGS. 10 to 12 described above, a method of differential update of DFA performed by the DFA update module 17 will be described by applying the example shown in FIGS. 6 to 9.

  In S200 of FIG. 10, the state ds holds a state constituted by {0, 1, 4, 7}. In S210, the state ns holds the state of S11 in FIG. 7. In S220, the DFA state is updated from these states ds and ns.

  Since the state ds {0, 1, 4, 7} is not NULL in S310 of FIG. 11, the state S11 of the state ns is added to the state ds in S320, and as a result, the NFA state group held by the state ds is {0, 1, 4, 7, 11}. Next, in S330, a is acquired as a transition from the state ns. Since there is an unprocessed transition a in S340, a is held in transition ne in S350.

  Next, “update DFA state by transition” in S360 is performed with the state ds and the transition ne.

  In S400 of FIG. 12, a which is a transition suitable for the transition ne (a) is specified from the transition groups a and d of the state ds ({0, 1, 4, 7, 11}). Since there is a suitable transition in S410, the process proceeds to S420, and since there is a transition a that has not been processed, the process proceeds to S430. In S430, a suitable transition a is extracted and held in the transition de. In S440, the DFA state {2, 8} of the transition destination of the transition de (a) is held as the state ds1, the NFA state S12 of the transition destination of the transition ne (a) is held as the state ns1, and these are used as arguments in the S220. Subroutine DFA status update is performed.

  The first recursion of the DFA state update subroutine will be described.

  Since the state ds {2, 8} is not NULL in S310 in FIG. 11, the state S12 of the state ns is added to the state ds in S320, and as a result, the NFA state group held by the state ds is {2, 8, 12}. Become. Next, in S330, d and * are acquired as transitions from the state ns. Since there is a transition d that is not processed in S340, d is held in the transition ne in S350.

  Next, “update DFA state by transition” in S360 is performed with the state ds and the transition ne. In S400 of FIG. 12, among the transition groups b, c, and other of the state ds ({2, 8, 12}), the other that is a transition that matches the transition ne (d) is specified. Since there is a suitable transition in S410, the process proceeds to S420, and since there is an unprocessed transition d, the process proceeds to S430.

  In S430, a suitable transition d is extracted and held in the transition de. At this time, since the transition of the DFA to which the transition d is matched is other, the transition by other is divided into other and d, and the structure of the transition destination is copied. In S440, the transition DFA state {2} of the transition de (d) is held as the state ds1, the transition destination NFA state S13 of the transition ne (d) is held as the state ns1, and these are used as arguments to the subroutine DFA of S220. Update the state.

  The second recursion of the DFA state update subroutine will be described.

  Since the state ds {2} is not NULL in S310 in FIG. 11, the state S13 of the state ns is added to the state ds in S320, and as a result, the NFA state group held by the state ds is {2, 13}. Next, in S330, the transition from the state ns is acquired, but there is no transition. Since there is no unprocessed transition in S340, the processing of this subroutine is terminated (return). FIG. 8 shows the DFA at this point.

  Since the process of S220 of FIG. 12 is completed, the process proceeds to S420. Since there is no unprocessed transition in S420, the processing of this subroutine is terminated (return).

  Since the process of S360 in FIG. 11 is completed, the process proceeds to S340. Since there is an unprocessed transition * in S340, * is held in transition ne in S350. Next, “update DFA state by transition” in S360 is performed with the state ds and the transition ne. In S400 of FIG. 12, among transition groups d, b, c, and other of state ds ({2, 8, 12}), d, b, c, and other that are transitions that match transition ne (*) are identified. To do. Since there is a suitable transition in S410, the process proceeds to S420, and since there is an unprocessed transition d, the process proceeds to S430. In S430, a suitable transition d is extracted and held in the transition de.

  In S440, the DFA state {2, 13} of the transition de (d) is held as the state ds1, the NFA state S12 of the transition ne (*) is held as the state ns1, and these are used as arguments in S220. Subroutine DFA status update is performed.

  By recursively repeating the above process, the DFA in FIG. 6 is updated to finally become the DFA shown in FIG.

  The first embodiment (difference addition) has been described above. Next, a second embodiment (difference deletion) will be described. In addition, since the structure of the filter engine 10 in 2nd Embodiment is the same as 1st Embodiment, description is abbreviate | omitted.

  FIG. 13 shows an example of data to be deleted from the pre-update data shown in FIG. 14 to 16 show the DFA obtained as a result of deleting the NFA of FIG. 13B from the DFA shown in FIG. The hatched state represents the updated state.

  The DFA update module 17 performs DFA difference update (difference deletion) along the flow shown in FIGS.

  FIG. 17 shows a DFA deletion flow. In S500, the DFA derived to process a plurality of XPath expressions is read, and the start state is held as the state ds. In S510, the NFA corresponding to the deletion target is read, and the start state is held as the state ns. The subroutine DFA state shown in S520 is deleted using these state ds and state ns as arguments. After the deletion of the DFA state, the NFA corresponding to the deletion target is deleted in S530.

  FIG. 18 shows the details of the DFA state deletion flow which is a subroutine. Here, a flow for an XPath-type deletion operation is particularly shown. In this subroutine, similarly to the difference addition, in S610, it is determined whether or not the state ds is NULL (not evaluated). If it is NULL (S610, Yes), the status of the addition target has not been evaluated, so this subroutine is terminated (return).

  When the state ds exists, the NFA state ns of the XPath expression to be deleted is deleted from the NFA state group held by the state ds in S620. At this time, the NFA state group held by the state ds is confirmed in S630. If there is no NFA state group, the subordinate of this state ds is deleted in S640. If there is an NFA state group, the transition group from the state ns is acquired in S650 in order to delete the DFA using the transition from the NFA state ns.

  It is determined whether or not there is a transition in which the processes of S670 and S680 are unprocessed in the transition group acquired in S650. If there is no unprocessed transition (S660, none), the DFA deletion for all transitions is completed. If there is an unprocessed transition (S660, yes), one unprocessed transition is selected in S670 and held as a transition ne. Then, using the state ds and the transition ne as arguments, the DFA state deletion by the subroutine transition shown in S680 is performed, and the process returns to S660.

  FIG. 19 shows the details of the DFA state deletion flow by the transition which is a subroutine. In S700, a transition that matches the transition ne on the NFA side is identified in the transition group held by the DFA state ds. In S710, it is determined whether there is a suitable transition. If there is no matching transition, this subroutine is terminated (return). If there is a suitable transition, the process proceeds to S720. It is determined whether or not there is an unprocessed transition. If there is no unprocessed transition, the DFA deletion by the transition ne is complete, so this subroutine is terminated (return).

  If there is a transition that has not been processed, one transition that has not been processed is selected in S730 and held as a transition de. In S740, the DFA state of the transition destination of the transition de is held as the state ds1, and the NFA state of the transition destination of the transition ne is held as the state ns1. Using these state ds1 and state ns1 as arguments, the subroutine “DFA state deletion” shown in S520 is performed.

  In order to specifically describe the processes of FIGS. 17 to 19 described above, a method of differential update of DFA performed by the DFA update module 17 will be described by applying the examples shown in FIGS. 6 and 13 to 16. .

  In S500 of FIG. 17, the state ds holds a state constituted by {0, 1, 4, 7}. In S510, the state ns holds the state of S1 in FIG. In S520, the DFA state is deleted from these state ds and state ns.

  In S610 of FIG. 18, since the state ds {0, 1, 4, 7} is not NULL, the state S1 of the state ns is deleted from the state ds in S620, and as a result, the NFA state group held by the state ds is { 0, 4, 7}. Since the state ds {0, 4, 7} holds the NFA state group in S630, a is acquired as a transition from the state ns in S650. Since there is a transition a that has not been processed in S660, a is held in transition ne in S670. Next, “DFA state deletion by transition” of S680 is performed with the state ds and the transition ne.

  In S700 of FIG. 19, a that is a transition that matches the transition ne (a) is specified from the transition groups a and d of the state ds {0, 4, 7}. Since there is a suitable transition in S710, the process proceeds to S720, and since there is a transition a that has not been processed, the process proceeds to S730. In S730, the suitable transition a is extracted and held in the transition de. In S740, the DFA state {2, 8} of the transition de (a) is held as the state ds1, the NFA state S2 of the transition ne (a) is held as the state ns1, and these are used as arguments in S520. Subroutine DFA state deletion is performed.

  The first recursion of the DFA state deletion subroutine will be described.

  In S610 of FIG. 18, since the state ds {2, 8} is not NULL, the state S2 of the state ns is deleted from the state ds in S620, and as a result, the NFA state group held by the state ds becomes {8}. Since the state ds {8} holds the NFA state in S630, b and * are acquired as transitions from the state ns in S650. Since there is an unprocessed transition b in S660, b is held in the transition ne in S670. Next, “DFA state deletion by transition” of S680 is performed with the state ds and the transition ne.

  In S700 of FIG. 19, among the transition groups b, c, and other of the state ds {8}, b and other that are transitions that match the transition ne (b) are specified. Since there is a suitable transition in S710, the process proceeds to S720, and since there is a transition b that is not processed, the process proceeds to S730. In S730, the suitable transition b is extracted and held in the transition de. In S740, the transition DFA state {2, 3} of the transition de (b) is retained as the state ds1, and the transition destination NFA state S3 of the transition ne (b) is retained as the state ns1. Using these as arguments, the subroutine DFA state is deleted in S520.

  The second recursion of the DFA state deletion subroutine will be described.

  In S610 of FIG. 18, since the state ds {2, 3} is not NULL, the state S3 of the state ns is deleted from the state ds in S620, and as a result, the NFA state group held by the state ds becomes {2}. . Since the state ds {2} holds the NFA state in S630, the transition from the state ns is acquired in S650. Next, since there is no unprocessed transition in S660, the processing of this subroutine is terminated (return). FIG. 14 shows the DFA at this time.

  Since the process of S520 of FIG. 19 is completed, the process proceeds to S720. Since there is a transition other that has not been processed in S720, the process proceeds to S730. In S730, a suitable transition other is extracted and held in the transition de. In S740, the transition DFA state {2} of the transition de (other) is held as the state ds1, the NFA state S2 of the transition ne (other) is held as the state ns1, and these are used as arguments to the subroutine DFA of S520. Delete state.

  The third recursion of the DFA state deletion subroutine will be described.

  In S610 of FIG. 18, since the state ds {2} is not NULL, the state S2 of the state ns is deleted from the state ds in S620, and as a result, the NFA state group held by the state ds becomes NULL. Since the state ds does not hold the NFA state in S630, d8 is deleted in S640, and the process of this subroutine ends (return).

  Since the process of S520 of FIG. 19 is completed, the process proceeds to S720. In S720, since there is no unprocessed transition, the processing of this subroutine is terminated (return). FIG. 15 shows the DFA at this time.

  Since the process of S680 in FIG. 18 is completed, the process proceeds to S660. Since there is an unprocessed transition * in S660, * is held in transition ne in S670. Next, “DFA state deletion by transition” of S360 is performed with the state ds and the transition ne.

  In S700 of FIG. 19, among the state groups b, c, other of the state ds {8}, the transitions b, c, other that are suitable for the transition ne (*) are specified. Since there is a suitable transition in S710, the process proceeds to S720, and since there is a transition c that has not been processed, the process proceeds to S730. In S730, the suitable transition c is extracted and held in the transition de. In S740, the DFA state {2, 9} of the transition de (c) is held as the state ds1, the NFA state S2 of the transition ne (*) is held as the state ns1, and these are used as arguments in S520. Subroutine DFA state deletion is performed.

  By repeating the above processing, the DFA in FIG. 6 is updated to finally become the DFA shown in FIG. Thus, after the DFA state update is completed in S520 in FIG. 17, the NFA corresponding to the XPath expression to be deleted from the NFA in FIG. 6 is deleted in S530, and the NFA in FIG. 16 is obtained.

  The second embodiment (difference deletion) has been described above. As shown in the first embodiment (FIGS. 10 to 12) and the second embodiment (FIGS. 17 to 19), the present invention is in a state according to the transition with respect to the pre-update NFA derived from the pre-update XPath expression. Are executed in order (depth priority, width priority, etc.), the transition of the pre-update DFA that matches each transition in the pre-update NFA is specified in the execution process, and the NFA status held by each state of the pre-update DFA The group and the transition group are confirmed, and the difference between the NFA state group and the transition group and the difference NFA is updated.

  The present invention is not limited to the above-described embodiment, and can be widely modified. For example, NewsML is an example, and XML data is not limited to NewsML. For example, the XML data may be NITF (News Industry Text Format) data. The filter engine 10 is installed by, for example, an ASP (Application Service Provider) for a company or an individual user, or a company, an organization, or the like is installed for an employee or a member of the company. Further, the means / method for adding the difference of the XPath expression information to the DFA shown in the embodiment is merely an example, and the present invention is not limited to the means / method for adding the difference shown in the embodiment. The above-described flow or the like is transmitted as an XPath processing program over a network, or stored and distributed in a storage medium such as a CD-ROM.

  Moreover, the apparatus which comprises the filter engine 10 is not limited to 1 unit | set, You may distribute and arrange | position a function to several apparatus. For example, a device that executes filter processing (XML parsing module 11, data extraction module 13, and data conversion module 16) and a device that creates an automaton for filtering (inquiry parsing module 11, DFA creation module 13B, automaton) The management unit 15, the DFA update module 17, and the update automaton management unit 18) may be configured as separate devices. As a result, the load on each device is distributed, and high-speed processing can be realized.

It is a block diagram which shows the outline | summary of the filter engine which performs the XPath type | formula processing method regarding one Embodiment of this invention. It is a block diagram which shows the internal structure of the filter engine of FIG. 1 regarding one Embodiment of this invention. It is explanatory drawing which shows the data structure on the memory of the automaton management part in FIG. 2 regarding one Embodiment of this invention. It is explanatory drawing which shows the data structure on the specific program of FIG. 3 regarding one Embodiment of this invention. FIG. 5 is an explanatory diagram showing a data configuration on a memory of the DFA of FIG. 4 according to an embodiment of the present invention. It is a state transition diagram which shows the example of the data before the update regarding one Embodiment of this invention. It is a state transition diagram which shows the example of the data added regarding 1st Embodiment of this invention. It is a state transition diagram which shows the example (halfway state) of DFA addition regarding 1st Embodiment of this invention. It is a state transition diagram which shows the example (final state) of DFA addition regarding 1st Embodiment of this invention. It is a flowchart which shows the DFA addition process regarding 1st Embodiment of this invention. It is a flowchart which shows the DFA state update subroutine regarding 1st Embodiment of this invention. It is a flowchart which shows the DFA state update subroutine by transition regarding 1st Embodiment of this invention. It is a state transition diagram showing an XPath expression to be deleted and its NFA related to the second embodiment of the present invention. It is a state transition diagram which shows the example (halfway state) of the DFA deletion regarding 2nd Embodiment of this invention. It is a state transition diagram which shows the example (halfway state) of the DFA deletion regarding 2nd Embodiment of this invention. It is a state transition diagram which shows the example (final state) of the DFA deletion regarding 2nd Embodiment of this invention. It is a flowchart which shows the DFA deletion process regarding 2nd Embodiment of this invention. It is a flowchart which shows the DFA state deletion subroutine regarding 2nd Embodiment of this invention. It is a flowchart which shows the DFA state deletion subroutine by transition regarding 2nd Embodiment of this invention.

Explanation of symbols

DESCRIPTION OF SYMBOLS 10 Filter engine 11 XML parsing module 12 Inquiry parsing module 13 Data extraction module 13B DFA creation module 15 Automaton management part 16 Data conversion module 17 DFA update module 18 Update automaton management part

Claims (6)

An XPath expression processing method for updating a pre-update DFA indicating an XPath expression before update input to process XML data to an updated DFA indicating an input XPath expression after update,
Computer
Reading the pre-update DFA derived to process the pre-update XPath expression and holding its start state as state ds;
Reading the XPath expression to be added, deriving a difference NFA therefrom, and holding its start state as state ns;
Calling a first subroutine for performing an additional operation of the XPath expression using the state ds and the state ns as arguments;
Reflecting the difference NFA in the pre-update NFA for processing the pre-update XPath expression to make the post-update NFA,
The first subroutine is:
If the state ds exists, adding the state ns to the NFA state group held by the state ds;
Obtaining a transition group from said state ns;
Selecting an unprocessed transition from the acquired transition group one by one as a transition ne, calling a second subroutine with the state ds and the transition ne as arguments, and an unprocessed transition to be selected as the transition ne When there is not, the step of ending this subroutine is executed, and
The second subroutine is
In the transition group held by the state ds, if there is no transition matching the transition ne, the step of adding the transition ne to the transition group of the state ds and ending this subroutine;
In the transition group held by the state ds, when there is a transition that matches the transition ne, the unprocessed transitions are selected one by one as the transition de, and the DFA state of the transition destination of the transition de is set as the state ds1. Holding the NFA state of the transition destination of the transition ne as the state ns1, and sequentially calling the first subroutine using the state ds1 and the state ns1 as arguments. An XPath-type processing method characterized by being configured as a subroutine for updating a previous DFA to the updated DFA . An XPath expression processing method for updating a pre-update DFA indicating an XPath expression before update input to process XML data to an updated DFA indicating an input XPath expression after update,
Computer
Reading the pre-update DFA derived to process the pre-update XPath expression and holding its start state as state ds;
Deriving an NFA to be deleted and holding its start state as state ns;
Calling a third subroutine for performing an XPath expression deletion operation using the state ds and the state ns as arguments;
Performing the step of deleting the NFA to be deleted from the pre-update NFA for processing the pre-update XPath expression to make the post-update NFA,
The third subroutine is
If the state ds exists, the step of deleting the state ns from the NFA state group held by the state ds and deleting the subordinate of the state ds when there is no NFA state group held by the state ds When,
Obtaining a transition group from said state ns;
Selecting an unprocessed transition from the acquired transition group one by one as a transition ne, calling the fourth subroutine with the state ds and the transition ne as arguments, and an unprocessed transition to be selected as the transition ne When there is not, the step of ending this subroutine is executed, and
The fourth subroutine is
In the transition group held by the state ds, if there is no transition that matches the transition ne, the step of ending this subroutine;
In the transition group held by the state ds, when there is a transition that matches the transition ne, the unprocessed transitions are selected one by one as the transition de, and the DFA state of the transition destination of the transition de is set as the state ds1. Holding the NFA state of the transition destination of the transition ne as the state ns1, and sequentially calling the third subroutine using the state ds1 and the state ns1 as arguments. 2. The XPath processing method according to claim 1, wherein the XPath expression processing method is configured as a subroutine for updating a previous DFA to the updated DFA . XPath expression processing program for the XPath expression processing method according to claim 1 or claim 2, causes the computer to perform. A computer-readable recording medium storing the XPath processing program according to claim 3 . An XPath expression processing apparatus that updates a pre-update DFA indicating an XPath expression before update input to process XML data to an updated DFA indicating an input XPath expression after update,
Reading the pre-update DFA derived to process the pre-update XPath expression and holding its start state as state ds;
Reading the XPath expression to be added, deriving a difference NFA therefrom, and holding its start state as state ns;
Calling a first subroutine for performing an additional operation of the XPath expression using the state ds and the state ns as arguments;
Reflecting the difference NFA in the pre-update NFA for processing the pre-update XPath expression to make the post-update NFA,
The first subroutine is:
If the state ds exists, adding the state ns to the NFA state group held by the state ds;
Obtaining a transition group from said state ns;
Selecting an unprocessed transition from the acquired transition group one by one as a transition ne, calling a second subroutine with the state ds and the transition ne as arguments, and an unprocessed transition to be selected as the transition ne When there is not, the step of ending this subroutine is executed, and
The second subroutine is
In the transition group held by the state ds, if there is no transition matching the transition ne, the step of adding the transition ne to the transition group of the state ds and ending this subroutine;
In the transition group held by the state ds, when there is a transition that matches the transition ne, the unprocessed transitions are selected one by one as the transition de, and the DFA state of the transition destination of the transition de is set as the state ds1. Holding the NFA state of the transition destination of the transition ne as the state ns1, and sequentially calling the first subroutine using the state ds1 and the state ns1 as arguments. An XPath type processing apparatus configured as a subroutine for updating a previous DFA to the updated DFA . An XPath expression processing apparatus that updates a pre-update DFA indicating an XPath expression before update input to process XML data to an updated DFA indicating an input XPath expression after update,
Reading the pre-update DFA derived to process the pre-update XPath expression and holding its start state as state ds;
Deriving an NFA to be deleted and holding its start state as state ns;
Calling a third subroutine for performing an XPath expression deletion operation using the state ds and the state ns as arguments;
Performing the step of deleting the NFA to be deleted from the pre-update NFA for processing the pre-update XPath expression to make the post-update NFA,
The third subroutine is
If the state ds exists, the step of deleting the state ns from the NFA state group held by the state ds and deleting the subordinate of the state ds when there is no NFA state group held by the state ds When,
Obtaining a transition group from said state ns;
Selecting an unprocessed transition from the acquired transition group one by one as a transition ne, calling the fourth subroutine with the state ds and the transition ne as arguments, and an unprocessed transition to be selected as the transition ne When there is not, the step of ending this subroutine is executed, and
The fourth subroutine is
In the transition group held by the state ds, if there is no transition that matches the transition ne, the step of ending this subroutine;
In the transition group held by the state ds, when there is a transition that matches the transition ne, the unprocessed transitions are selected one by one as the transition de, and the DFA state of the transition destination of the transition de is set as the state ds1. Holding the NFA state of the transition destination of the transition ne as the state ns1, and sequentially calling the third subroutine using the state ds1 and the state ns1 as arguments. 6. The XPath processing apparatus according to claim 5, wherein the XPath processing apparatus is configured as a subroutine for updating a previous DFA to the updated DFA .

Images