XPath evaluation method, XML document processing system and program using the same

• US 20030163285A1
• Filed: 02/28/2003
• Published: 08/28/2003
• Est. Priority Date: 02/28/2002
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Yuriyama, Madoka, Takagi, Hironobu, Nakamura, Hiroaki
• Granted Patent: US 7,315,981 B2
• Time in Patent Office: Days
• US Class Current: 702/179
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures

Abstract

To efficiently search an evaluation result of a plurality of XPath expressions with respect to a data file such as an XML document: an evaluation result of an XPath expression is obtained by generating a data structure with a redundant element by evaluating what common part or dependency has been omitted from a plurality of XPath expressions to be evaluated, and then the data structure is used with respect to a data file to be processed.

Claims

1. An XPath evaluation method for evaluating a plurality of XPaths with respect to a predetermined data file by a computer, said method comprising the steps of:

reading out a plurality of XPath expressions to be evaluated from a memory and generating a data structure that has a common part of said plurality of XPath expressions as a common node in a tree structure;

inputting a data file to be an objective of processing from a memory and evaluating said data structure in node-by-node basis using said data structure with respect to said data file; and

obtaining an evaluation result for each XPath expression by combining said evaluation results for each of nodes and storing the obtained evaluation result into a memory.

2. The XPath evaluation method according to claim 1, wherein said step of generating a data structure comprises the steps of:

decomposing individual said XPath expressions into steps; and

associating a node with each step obtained from the decomposition and generating a data structure, in which a step common to a plurality of XPath expressions is associated with a single node.

3. The XPath evaluation method according to claim 2,

wherein when a plurality of said steps are written in a common particular form, a hash table or a binary search tree for searching for remaining steps in an XPath by using an evaluation result for a predicate expression in the step as a key is generated in said step of generating a data structure, and

wherein said remaining steps of an XPath obtained from a search by means of said hash table or said binary search tree are evaluated in said step of evaluating an XPath expression.

4. The XPath evaluation method according to claim 1,

wherein said step of generating a data structure comprises the steps of:

decomposing an operation expression or function into subexpressions when said plurality of XPath expressions include the operation expression or function; and

generating a non-repeating directed graph by combining common subexpressions of said subexpressions obtained from the decomposition, and

wherein each XPath expression is evaluated by using said non-repeating directed graph and sharing an evaluation result among the plurality of XPath expressions for a subexpression common to a plurality of XPath expressions in said step of evaluating an XPath expression.

5. An XPath evaluation method for evaluating a plurality of XPaths with respect to a predetermined data file by a computer, said method comprising:

a first step of reading out a plurality of XPath expressions to be evaluated from a memory and extracting a common part from the plurality of XPath expressions; and

a second step of reading out a data file to be an objective of processing from a memory, evaluating said part common to said XPath expressions and the other parts separately with respect to the data file, obtaining an evaluation result for each XPath expression by combining the evaluation results, and storing the obtained evaluation result into a memory,

wherein said second step comprises a step of using an evaluation result obtained at an evaluation of another XPath as an evaluation result for a common part of a predetermined XPath expression if such an evaluation result exists, with respect to said common part when evaluating the predetermined XPath expression.

6. An XPath evaluation method for evaluating a plurality of XPaths with respect to a predetermined data file by a computer, said method comprising the steps of:

reading out an XPath set including a plurality of XPath expressions to be evaluated from a memory and generating a data structure with a redundant element in the XPath expressions included in the XPath set omitted;

inputting a data file to be an objective of processing, evaluating said XPath set by using said data structure with respect to the data file, and storing the obtained evaluation result into a memory.

7. The XPath evaluation method according to claim 6, wherein an XPath expression commonly included in a plurality of XPath sets and an XPath expression unique to a predetermined XPath set are separated, and XPath expressions to be evaluated at an evaluation of said XPath sets are narrowed down in said step of generating a data structure.

8. The XPath evaluation method according to claim 6, wherein a connected XPath expression included in said XPath set is simplified by removing an XPath expression that can dispense with an evaluation from objectives of evaluation on the basis of dependency among respective XPaths constituting the connected XPath expression in said step of generating a data structure.

9. The XPath evaluation method according to claim 6, wherein an XPath expression that can dispense with an evaluation is removed from objectives of evaluation on the basis of dependency among a plurality of XPath expressions in said step of generating a data structure.

10. The XPath evaluation method according to claim 6, wherein a part common to a plurality of XPath expressions and a part unique to each XPath expression are separated to make each part an objective of evaluation as an individual XPath expression in said step of generating a data structure.

11. A document processing system comprising:

an XPath storing part which stores a plurality of XPath expressions;

a data structure-generation part for generating a data structure with redundant elements of said plurality of XPath expressions stored in said XPath-storing part being omitted; and

an evaluation execution part for evaluating said plurality of XPath expressions with respect to a data file to be evaluated by using said data structure generated at said data structure-generation part.

12. The document processing system according to claim 11, wherein said data structure-generation part comprises:

a step decomposing means for decomposing individual said XPath expressions into steps; and

a tree generation means for generating a data structure, in which a step common to a plurality of XPath expressions is associated with a node by associating a node with each step obtained from the decomposition.

13. The document processing system according to claim 11, wherein if an XPath expression stored in said XPath storing part is changed, said data structure-generation part updates a data structure by generating a new node for a part which does not have a node corresponding to said data structure in newly added XPath expressions, adding the new node to the data structure, and removing only a node corresponding to a part unique to the XPath expression from nodes of said data structure corresponding to a part of deleted XPath expressions.

14. The document processing system according to claim 11, wherein the data structure generation part removes an XPath expression which overlaps other XPath expressions or an XPath expression whose evaluation result depends on other XPath expressions from objectives of evaluation.

15. The document processing system according to claim 11, further comprising a data structure-storing part for storing and retaining a data structure generated at said data structure-generation part, wherein said evaluation execution part evaluates said plurality of XPath expressions by using said data structure stored in said data structure-storing part.

16. The document processing system according to claim 12, wherein said evaluation execution part evaluates a part corresponding to each node in said data structure, obtains a general evaluation result for individual XPath expressions by combining the partial evaluation results, and shares an evaluation result for a part corresponding to a node common to a plurality of XPath expressions in evaluating the plurality of XPath expressions.

17. The document processing system according to claim 11, wherein:

said XPath storing part stores an XPath set configured with a plurality of XPath expressions;

said data structure generation part generates said data structure with respect to said XPath included in a plurality of XPath set stored in said XPath storing part; and

said evaluation execution part evaluates individual XPath expressions by using said data structure and obtains an evaluation result for an XPath set with respect to said data file on the basis of the obtained evaluation results for XPath expressions.

18. A program for controlling a computer to evaluate a plurality of XPaths with respect to a predetermined data file, said program causes said computer to execute the processes for:

generating a data structure having a part common to a plurality of XPath expressions to be evaluated as a common node in a tree structure;

said data structure with respect to a data file to be an objective of processing; and

obtaining each evaluation result for individual XPath expressions by combining evaluation results for each of said node.

19. The program according to claim 18, wherein said process for generating a data structure by a program comprises the processes for:

decomposing individual said XPath expressions into steps;

and

associating a node with each step obtained from the decomposition and generating a data structure, in which a step common to a plurality of XPath expressions is associated with a node.

20. The program according to claim 18, wherein:

when a plurality of said steps are written in a common particular form, a hash table or a binary search tree for searching for remaining steps in an XPath by using an evaluation result for a predicate expression in the step as a key is generated in said process for generating said data structure by said program; and

said remaining steps of an XPath obtained from a search by means of said hash table or said binary search tree are evaluated in said step of evaluating an XPath expression.

21. The program according to claim 18, wherein said process for generating data structure by said program comprises the processes for:

processes for;

decomposing an operation expression or function into subexpressions when said plurality of XPath expressions include the operation expression or function; and

generating a non-repeating directed graph by combining common subexpressions of said subexpressions obtained from the decomposition,

wherein each XPath expression is evaluated by using said non-repeating directed graph and sharing an evaluation result among the plurality of XPath expressions for a subexpression common to a plurality of XPath expressions in said process for evaluating an XPath expression.

22. The program according to claim 18, wherein said program further causes said computer to execute a process for updating a data structure by generating a new node for a part which does not have a node corresponding to said data structure in newly added XPath expressions, adding the new node to the data structure, and removing only a node corresponding to a part unique to the XPath expression from nodes of said data structure corresponding to a part of deleted XPath expressions, if said plurality of XPath expressions to be evaluated are changed.

23. A program for controlling a computer to evaluate a plurality of XPaths with respect to a predetermined data file, said program causes said computer to function as:

a data structure generation means for reading out a plurality of XPath expressions to be evaluated from a memory, generating a data structure with a redundant element in the plurality of XPath expressions omitted, and storing the generated data structure into a memory; and

an evaluation execution means for evaluating said plurality of XPath expressions with respect to a data file to be an objective of processing by using said generated data structure.

24. A program for controlling a computer to evaluate a plurality of XPaths with respect to a predetermined data file, said program causes said computer to execute the processes for:

extracting a common part from a plurality of XPath expressions to be evaluated; and

obtaining an evaluation result for each XPath expression, with respect to a data file to be an objective of processing, by evaluating said part common to said XPath expressions and the other parts separately and combining the evaluation results, wherein said process for obtaining an evaluation of an XPath expression by said program comprises a process for using an evaluation result obtained at an evaluation of another XPath as an evaluation result for a common part of a predetermined XPath expression if such an evaluation result exists, with respect to said common part when evaluating the predetermined XPath expression.

25. A program for controlling a computer to evaluate a plurality of XPaths with respect to a predetermined data file, said program causes said computer to execute the processes for:

generating a data structure with a redundant element of the XPath expressions omitted from an XPath set to be evaluated, which is configured as including a plurality of XPath expressions;

evaluating said data structure in node-by-node basis using said data structure with respect to said data file to be an objective of processing; and

evaluating said XPath set by using said data structure.

26. The program according to claim 25, wherein an XPath expression commonly included in a plurality of XPath sets and an XPath expression unique to a predetermined XPath set are separated, and XPath expressions to be evaluated at an evaluation of said XPath sets are narrowed down in said process for generating a data structure by said program.

27. The program according to claim 25, wherein a connected XPath expression included in said XPath set is simplified by removing an XPath expression that can dispense with an evaluation from objectives of evaluation on the basis of dependency among respective XPaths constituting the connected XPath expression in said process for generating a data structure by said program.

28. The program according to claim 25, wherein an XPath expression that can dispense with an evaluation from objectives of evaluation on the basis of dependency among a plurality of XPath expressions in said process for generating a data structure by said program.

29. The program according to claim 25, wherein a part common to a plurality of XPath expressions and a part unique to each XPath expression are separated to make each part an objective of evaluation as an individual XPath expression in said process for generating a data structure by said program.

30. The program according to claim 25, wherein said process for evaluating said XPath set by said program comprises the processes for:

evaluating an XPath expression unique to each XPath set; and

,

if each of the unique XPath expressions matches said data file to be an objective of processing, evaluating XPath expressions common to the remaining XPath sets within the XPath sets.

31. A storage medium for storing computer readably a program which controls a computer to evaluate a plurality of XPaths with respect to a predetermined data file, said program causes said computer to execute the processes for:

generating a data structure that has a common part of a plurality of XPath expressions to be evaluated as a common node in a tree structure;

evaluating said data structure in node-by-node basis using said data structure with respect to a data file to be an objective of processing; and

obtaining an evaluation result for individual XPath expressions by combining said evaluation results for each of nodes.

32. A storage medium for storing computer readably a program which controls a computer to evaluate a plurality of XPaths with respect to a predetermined data file, said program causes said computer to function as:

a data structure generation means for reading out a plurality of XPath expressions to be evaluated from a memory, generating a data structure with a redundant element in the plurality of XPath expressions omitted, and storing the generated data structure into a memory; and

an evaluation execution means for evaluating said plurality of XPath expressions with respect to a data file to be an objective of processing by using said generated data structure.

33. A storage medium for storing computer readably a program which controls a computer to evaluate a plurality of XPaths with respect to a predetermined data file, said program causes said computer to execute the processes for:

extracting a common part from a plurality of XPath expressions to be evaluated; and

obtaining an evaluation result for individual XPath expressions by evaluating said part common to said XPath expressions and the other parts separately with respect to a data file to be an objective of processing, and combining the evaluation results,

wherein said process for obtaining an evaluation of said XPath expression by said program comprises a process for using an evaluation result obtained at an evaluation of another XPath as an evaluation result for a common part of a predetermined XPath expression if such an evaluation result exists, with respect to said common part when evaluating the predetermined XPath expression.

34. A storage medium for storing computer readably a program which controls a computer to evaluate a plurality of XPaths with respect to a predetermined data file, said program causes said computer to execute the processes for:

XPath expressions omitted from an XPath set to be evaluated, which is configured as including a plurality of XPath expressions;

evaluating said data structure in node-by-node basis using said data structure with respect to an data file to be an objective of processing; and

evaluating said XPath set by using said data structure.