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 4:
4. The method of claim 1 wherein the step of non-local process planning for a leaf node further comprises determining a strategy for performing the remaining join operators by transmission of base relations and temporary relations among the sites by an optimization criteria using the parameters of the temporary relations estimated by local process planning and the parameters of the base relations.