Query evaluation on distributed semi-structured data

• US 6,076,087 A
• Filed: 04/13/1998
• Issued: 06/13/2000
• Est. Priority Date: 11/26/1997
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Suciu, Dan
• Primary Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US09/059,640
• Time in Patent Office: 792 Days
• Field of Search: 707/2, 707/3, 707/100, 707/5, 707/4
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2448 for particular applications; for extensibility, e.g. user defined types
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9558 Details of hyperlinks; Management of linked annotations
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

The invention provides a system and method for evaluating a query on a distributed database across multiple sites. Database portion contained within each site is processed by a respective terminal. A client terminal is a terminal that distributes and collects information for evaluating the query. Each of the terminals receives the query and performs evaluation of the query on the respective distributed portion of the database. The terminals generate an accessibility graph based on the query evaluation of the respective distributive portion of the database and transmit the accessibility graphs to the client terminal. The client terminal receives all the accessibility graphs from each of the terminals and constructs an accessibility graph for the complete distributed database. The client terminal then traces through the accessibility graph for the distributed database and determines which parts of each of the distributed portions contribute to the query result. The client terminal transmits to each of the terminals information identifying the respective parts that contribute to the query result. The terminals returns the parts of the respective portions of the distributed database to the client terminal for construction of the query result.

Claims

1. A method for generating a final result of a query of a database that is represented by an edge-labeled tree and decomposed into a plurality of separated portions, comprising:

evaluating the query for each of the separated portions;

generating accessibility graphs for the separated portions based on respective query evaluations, each of the accessibility graphs corresponding to one of the separated portions;

combining the accessibility graphs into a single graph;

identifying parts of the separated portions that contribute to the final query result based on the single graph; and

generating the final query result based on identified parts of the separated portions.

2. The method of claim 1, further comprising identifying input and output nodes corresponding to cross links, wherein cross links are edges of the edge-labeled tree that cross between two of the separated portions, the output nodes being associated with separated portions from which the cross links emanate and the input nodes being associated with separated portions to which the cross links terminate.

3. The method of claim 2, wherein the evaluating step comprises:

resolving the query into a plurality of match patterns, the match patterns having an order relationship with each other based on the query;

forming groups of match patterns, each of the groups beginning with one of the match patterns and ending with an ending match pattern based on the order of relationships, the ending match pattern preceding a subtree which may contribute to the final query result; and

matching each of the groups of match patterns with patterns of edges of a separated portion of the separated portions beginning with each of input nodes of the separated portion and ending at either output nodes or leaf nodes of the separated portion.

4. The method of claim 3, wherein the generating accessibility graph step comprises:

generating at least one of at least one first accessibility node corresponding to all pairs of ones of the input nodes of the separated portion and ones of the groups of matching patterns, and at least one second accessibility node corresponding to all pairs of ones of the output nodes of the separated portion and one of the groups of matching patterns;

generating at least one of at least one third accessibility node corresponding to all input nodes of the separated portion and at least one fourth accessibility node corresponding to all output nodes of the separated portion; and

connecting the first and third accessibility nodes to the second and the fourth accessibility nodes with at least one directed graph edge based on results of the matching step.

5. The method of claim 4, wherein the combining step comprises connecting first, second, third, and fourth accessibility nodes of each of the accessibility graphs to first, second, third and fourth accessibility nodes of accessibility graphs of other separated portions based on the cross links of corresponding input nodes and corresponding output nodes to form the single graph.

6. The method of claim 5, wherein the identifying step comprises:

tracing directed edges of the single graph to locate accessibility nodes that are associated with the final query result; and

identifying parts of the separated portion associated with located accessibility nodes as the parts that contribute to the final result.

7. The method of claim 6, wherein the generating the final query result step comprises:

retrieving edge labels and subtrees of the parts that contribute to the final query result; and

forming the query result based on the edge labels and subtrees of the identified separated portions.

8. The method of claim 3, wherein the match patterns correspond to a plurality of match-set nodes, the match-set nodes being formed into a match-set node graph of connected match-set nodes based on the query, starting with an empty accessibility graph, the generating accessibility graphs step comprising:

matching match patterns corresponding to first match-set nodes of the match-set node graph with patterns of edges of each of the separated portions;

adding to the accessibility graph a first matched match-set node if corresponding match patterns of the first match-set node is found and adding one first match node for each match connected below the first matched match-set node;

matching match patterns corresponding to second match-set nodes that appear below the first matched match-set node in the match-set node graph, if a match is found for any of the second match-set nodes, then adding to the accessibility graph second matched match-set nodes connected below the first matched match-set node and for each match, adding one second match node connected below the second matched match-set node; and

generating at least a data edge emanating from each of the match nodes labeled by at least one of a variable of a respective corresponding match pattern and an identification of a part of each of the separated portions identified by the respective corresponding match pattern.

9. The method of claim 8, further comprising:

adding to the accessibility graph local existence nodes corresponding to each of the match-set nodes and match nodes and connecting the local existence nodes in a similar manner as the match-set nodes and the match nodes are connected;

setting the values of each of the local existence nodes corresponding to leaf match nodes to ACC;

setting values of each of the local existence nodes corresponding to other match nodes to ACC if values of the local existence nodes below each of the local existence nodes are all ACC; and

setting values of each of the local existence nodes corresponding to match-set nodes to ACC if any values of local existence nodes below each of the local existence nodes is ACC.

10. The method of claim 9, wherein the combining step comprises:

connecting all accessibility graphs corresponding to each of the separated portions based on the match-set node graph, wherein a connection is not made if a match node associated with an input node does not correspond to a match-set node associated with a corresponding output node, and if a match-set node associated with an input node does correspond to a match node associated with a corresponding output node.

11. The method of claim 10, further comprising:

adding global existence nodes to the accessibility graph corresponding to each of the match-set and match nodes of the accessibility graph and connecting the global existence nodes in the similar manner as the match-set and match nodes;

setting a value of a first global existence node to the value of a corresponding local existence node that corresponds to a match node a match pattern corresponding to a highest level match-set node;

setting a value of a second global existence node corresponding to the highest level match-set node to the value of ACC if any of the first global existence node has a value of ACC;

setting values of all other global existence nodes to values of global existence nodes of a next higher level in the accessibility graph if a next higher level exists and setting values to NOT-ACC if the next higher level does not exists and the other global existence nodes does not correspond to the highest level match-set node;

assigning an ACC value to a match-set node of the match-set nodes if the match-set node is connected to the highest level match-set node in the accessibility graph and if the corresponding global existence node has a value of ACC, otherwise assigning a NOT-ACC value to the match-set node; and

assigning an ACC value to a match node or a match-set node that is connected below a match-set node or a match node, respectively that is assigned a value of ACC.

12. The method of claim 11, wherein the generating the final query step comprises:

identifying leaf match nodes of the accessibility graph having an assigned value of ACC and whose corresponding global existence nodes have values of ACC;

identifying result match nodes which are all match nodes along a path from the highest level match-set node to identified leaf match nodes;

collecting parts of separated portions stored or identified by data edges of result match nodes; and

selecting from the collected parts to form the final query result.

13. A system operating in a network that generates a final result of a query of a database that is represented by an edge-labeled tree and decomposed into a plurality of separated portions, comprising:

a plurality of terminals coupled to the network, each of the terminals having immediate access to one of the separated portions;

a client terminal coupled to the terminals through the network, wherein the terminals evaluate the query for each of respective separated portions, and generate accessibility graphs for each of the separated portions based on respective query evaluations, the client terminal combining the accessibility graphs into a single graph, identifying parts of the separated portions that contribute to the final query result based on the single graph, and generating the final query result based on identified parts of the separated portions.

14. The system of claim 13, further comprising identifying input and output nodes corresponding to cross links, wherein cross links are edges of the edge-labeled tree that cross between two of the separated portions, the output nodes being associated with separated portions from which the cross links emanate and the input nodes being associated with separated portions to which the cross links terminate.

15. The system of claim 14, wherein the query is resolved into a plurality of match patterns, the match patterns having an order relationship with each other based on the query, groups of match patterns being formed, each of the groups beginning with one of the match patterns and ending with an ending match pattern based on the order of relationships, the ending match pattern preceding a subtree which may contribute to the final query result, each of the groups of match patterns being matched with patterns of edges of a separated portion of the separated portions beginning with each of input nodes of the separated portion and ending at either output nodes or leaf nodes of the separated portion to generate match results.

16. The system of claim 15, wherein each of the terminals generates at least one of at least one first accessibility node corresponding to all pairs of ones of the input nodes of the respective separated portion and ones of the groups of matching patterns, and at least one second accessibility node corresponding to all pairs of ones of the output nodes of the separated portion and one of the groups of matching patterns, generate at least one of at least one third accessibility node corresponding to all input nodes of the separated portion and at least one fourth accessibility node corresponding to all output nodes of the separated portion, and connected the first and third accessibility nodes to the second and the fourth accessibility nodes with at least one directed graph edge based on the match results.

17. The system of claim 16, wherein the client terminal connects first, second, third, and fourth accessibility nodes of each of the accessibility graphs to first, second, third and fourth accessibility nodes of accessibility graphs of other separated portions based on the cross links of corresponding input nodes and corresponding output nodes to form the single graph.

18. The system of claim 17, wherein the client terminal traces directed edges of the single graph to locate accessibility nodes that are associated with the final query result, and identifies parts of the separated portion associated with located accessibility nodes as the parts that contribute to the final result.

19. The system of claim 18, wherein the client terminal retrieves edge labels and subtrees of the parts that contribute to the final query result, and forms the query result based on the edge labels and subtrees of the identified separated portions.

20. The system of claim 15, wherein the match patterns correspond to a plurality of match-set nodes, the match-set nodes being formed into a match-set node graph of connected match-set nodes based on the query, starting with an empty accessibility graph, the terminals:

1) matching match patterns corresponding to first match-set nodes of the match-set node graph with patterns of edges of each of the separated portions,

2) adding to the accessibility graph a first matched match-set node if corresponding match patterns of the first match-set node is found and adding one first match node for each match connected below the first matched match-set node,

3) matching match patterns corresponding to second match-set nodes that appear below the first matched match-set node in the match-set node graph, if a match is found for any of the second match-set nodes, then adding to the accessibility graph second matched match-set nodes connected below the first matched match-set node and for each match, adding one second match node connected below the second matched match-set node, and

4) generating at least a data edge emanating from each of the match nodes labeled by at least one of a variable of a respective corresponding match pattern and an identification of a part of each of the separated portions identified by the respective corresponding match pattern.

21. The system of claim 20, wherein the terminals add to the accessibility graph local existence nodes corresponding to each of the match-set nodes and match nodes and connecting the local existence nodes in a similar manner as the match-set nodes and the match nodes are connected, set the values of each of the local existence nodes corresponding to leaf match nodes to ACC, set values of each of the local existence nodes corresponding to other match nodes to ACC if values of the local existence nodes below each of the local existence nodes are all ACC, and set values of each of the local existence nodes corresponding to match-set nodes to ACC if any values of local existence nodes below each of the local existence nodes is ACC.

22. The method of claim 21, wherein the client terminal connects all accessibility graphs corresponding to each of the separated portions based on the match-set node graph, a connection being not made if a match node associated with an input node does not correspond to a match-set node associated with a corresponding output node, and if a match-set node associated with an input node does correspond to a match node associated with a corresponding output node.

23. The system of claim 22, wherein the client terminal adds global existence nodes to the accessibility graph corresponding to each of the match-set and match nodes of the accessibility graph, connects the global existence nodes in the similar manner as the match-set and match nodes, sets a value of a first global existence node to the value of a corresponding local existence node that corresponds to a match node a match pattern corresponding to a highest level match-set node, sets a value of a second global existence node corresponding to the highest level match-set node to the value of ACC if any of the first global existence node has a value of ACC, sets values of all other global existence nodes to values of global existence nodes of a next higher level in the accessibility graph if a next higher level exists and setting values to NOT-ACC if the next higher level does not exists and the other global existence nodes does not correspond to the highest level match-set node, assigns an ACC value to a match-set node of the match-set nodes if the match-set node is connected to the highest level match-set node in the accessibility graph and if the corresponding global existence node has a value of ACC, otherwise assigning a NOT-ACC value to the match-set node, and assigns an ACC value to a match node or a match-set node that is connected below a match-set node or a match node, respectively that is assigned a value of ACC.

24. The system of claim 23, wherein the client terminal identifies leaf match nodes of the accessibility graph having an assigned value of ACC and whose corresponding global existence nodes have values of ACC, identifies result match nodes which are all match nodes along a path from the highest level match-set node to identified leaf match nodes, collects parts of separated portions stored or identified by data edges of result match nodes, and selects from the collected parts to form the final query result.