Query evaluation on distributed semi-structured data
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
24 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
Specification