Patent Document ID: 4769772
Application ID: 06706702

Base Claim:
1. A machine implemented method for automatically determining an optimal execution strategy for a request comprising query, update or transaction operations on a distributed database system having a plurality of data site, with each site having a computer and data storage facility, and said sites are interconnected by communication lines, said machine implemented method comprising the steps of: A. inputting an ad hoc relational query or update request from a first computer process that formulates the relational query or update request as a compacted tree having lead nodes that are select, project or join operators and non-leaf nodes that are union, intersection, difference, delete, modify or insert operators to a second computer process which thereafter performs step B; B. for each node in the compacted tree perform the following starting at the root node: 1. if the current node is a leaf node perform the following: a. materialization planning to choose the data sites from which data is to be accessed; b. local process planning to determine which operations can be processed locally at each site determined by materialization planning and estimate parameters of resultant data from the local operations; c. non-local process planning to determine strategy for remaining operations which can not be performed locally without transmission of data between sites; d. execution strategy building to build an execution strategy for each data site in the distributed database system at which data is processed by access or manipulation; 2.

---

Claim 2:
2. if the current node is a non-leaf node perform the following: a. for each child node make the child a root of a subtree and perform step 1 above for the subtree; and b. having processed all child nodes of the current non-leaf node perform the following for the current non-leaf node: 1. materialization planning to choose the data sites from which data is to be accessed; 2. local process planning to determine which operations can be processed locally at each site determined by materialization planning and estimate parameters of resultant data from the local operations; 3. non-local process planning to determine strategy for remaining operations which can not be performed locally without transmisson of data between sites; 4. execution strategy building to build an execution strategy for each data site in the distributed database system at which data is processed by access or manipulation; and then C. outputting execution strategy commands from said second computer process to a third computer process that coordinates the execution of the execution strategy commands at sites within the distributed database system. 2. The method of claim 1 wherein the step of materialization planning for a leaf node comprises the steps of: A. choosing a site for each base relation that is an operand of the leaf node by choosing the sites that have the most number of base relations; and B. choosing result data processor, a site where the final result of the operations will be built, by choosing the site that has the most number of base relations.