Automated query optimization method using both global and parallel local optimizations for materialization access planning for distributed databases

Abstract

In a Distributed Database System (DDS), database management and transaction management are extended to a distributed environment among a plurality of local sites which each have transaction server, file server, and data storage facilities. The Materialization and Access Planning (MAP) method of a distributed query, update, or transaction is an important part of the processing of the query, update, or transaction. Materialization and access planning results in a strategy for processing a query, update, or transaction in the distributed database management system (DSDBMS). Materialization consists of selecting data copies used to process the query, update, or transaction. This step is necessary since data may be stored at more than one site (i.e., computer) on the network. Access planing consists of choosing the execution order of operations and the actual execution site of each operation. Three access planning methods are used: General (Response), General (Total) and Initial Feasible Solution (IFS). For a distributed query, General (Response) and General (Total) decrease the communication cost and increase the local processing costs as compared to the IFS.

Claims

What is claimed is:

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.

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.

3. The method of claim 1 wherein the step of local process planning for a leaf node comprises the steps of:

A. determining the select, project and join operations that can be performed on base relations or temporary relations that reside at the same node; and

B. estimating parameters of temporary relations produced by select, project and join operators using the parameter of the base relations.

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.

5. The method of claim 4 wherein the optimization criteria is to minimize the total time for communications among the sites.

6. The method of claim 5 wherein the communication time between sites is a function of the size parameter of the data to be transmitted.

7. The method of claim 6 wherein the size parameter is reduced by use of semi join operations on the base relations or temporary relations.

8. The method of claim 7 wherein the reduction of the size parameter by use of the semi join operations is estimated by use of selectivity parameters.

9. The method of claim 4 wherein the optimization criteria is to minimize the response time for communication among the sites.

10. The method of claim 9 wherein the communication time between sites is a function of the size parameter of the data to be transmitted.

11. The method of claim 10 wherein the size parameter is reduced by use of semi join operations on the base relations or temporary relations.

12. The method of claim 11 wherein the reduction of the size parameter by use of the semi join operations is estimated by use of selectivity parameters.

13. The method of claim 4 wherein the optimization criteria is to ignore the parameters and to have all base relations and temporary relations transmitted to the result data processor chosen by materialization planning and perform remaining operators at the result data processor.

14. The method of claim 1 wherein the step of building for a leaf node further comprises the step of building select, project, join and move requests resulting from the local process planning and non-local process planning steps.

15. The method of claim 1 wherein the step of materialization planning for a non-leaf node comprises the steps of:

A. determining a site for each temporary relation that is an operand of a non-leaf node based upon the result data processor chosen for each child node;

B. for a union, intersection or difference operator, choosing a 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 temporary relations; and

C. for a delete, modify or insert operator, determining all sites where the base relation to be updated resides.

16. The method of claim 1 wherein the step of local process planning for a non-leaf node comprises the steps of:

A. determining union, intersection or difference operations that can be performed on temporary relations that reside at the same node; and

B. determining delete, modify or insert operations that can be performed on base relations that reside at the same node as the temporary relations.

17. The method of claim 1 wherein the step of non-local process planning for a non-leaf node comprises the steps of:

A. for a union, intersection or difference operator, transmitting all temporary relations to the result data processor chosen by materialization planning and perform the remaining operations at the result data processor; and

B. for a delete, modify or insert operator, transmitting all temporary relations to the sites where the base relation to be updated resides as determined by materialization planning and performing the delete, modify or insert operation at those sites.

18. The method of claim 1 wherein the step of execution strategy building for a non-leaf node further comprises the step of building union, intersection, difference, delete, modify, insert and move requests resulting from the local process planning and non-local process planning steps.

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates to computer database systems; and more specifically to a method for optimizing queries, updates and transactions in a distributed database system.

2. Description of the Prior Art

Modern database systems are frequently distributed, meaning that the data is kept at widely dispersed locations. Several different computers control access to different parts of the data, and several computers are used to interface with users at different locations; these may or may not be the same machines that access the data itself. The various computers are connected by communications links, and it is normal for these links to be relatively low speed, compared with, say, the speed at which a file can be read off of a disk. The consequence of this assumption about communication is that the transfer of data between computers becomes a bottleneck, and most of the issues unique to distributed systems concern ways of dealing with this bottleneck.

A distributed database consists of a number of sites, each of which is a computer and a facility for storing data. In general, each site has both a transaction server to process queries and updates generated by a user, and a file server to handle data access. However, it is possible that one of these two functions is missing at any particular site, and often one computer will act as both the transaction and file server.

A database is composed of "items", which are individually lockable pieces of data. It is a possibility that some items are duplicated, in the sense that they appear at two or more sites. The reason for doing so is that accesses to frequently read items may be sped up if the item is available at the same site that processed the read request. Further, the redundant storage of items makes it less likely that the item will be lost in a crash. The penalty is that more messages must be sent to update or lock a duplicated item than an item that appears only once.

Some or all pairs of sites are connected by links, over which messages can be sent and data transmitted. Based on the technology of the early 1980's, the time to send even a short message between geographically distributed sites is nontrivial, say 0.1 seconds, and the rate at which data can be transmitted across a link is not too great, perhaps around 10,000 bytes per second or less. The tenth of a second overhead to send a message represents the time for the two processors connected by a link to execute the protocol necessary for one to send a message, assured that the other will receive it and know what to do with it. The shipping rate for data is limited by the speed at which a processor can send or receive data, or the bandwidth of the link (rate at which data can be transmitted across the line) or both.

A prior art system which optimizes queries in a distributed database system is System R*. System R* is the experimental extension of System R to the distributed environment. Like its parent, it performs optimization in an exhaustive way, confident that the cost of considering many strategies will pay off in lower execution costs for queries, especially for queries that are compiled and used many times.

The optimization method of System R* applies to an algebraic query, where the expression to be optimized represents the query applied to logical relations, which in turn are expressed in terms of physical relations. The operators assumed to appear in the query are the usual select, project, join and union, plus a new operator choice, which represents the ability of the system to choose any of the identical, replicated copies of a given relation. The System R* method of optimization considers all ways to evaluate the nodes of the compacted tree, taking into account

1. the various orders in which an operator like union or join of many relations can be performed as a sequence of binary steps,

2. the various sites at which each node of the tree could have its result computed, and

3. several different ways that the join could be computed.

When the System R* method considers each of the options listed above, it must evaluate the cost of these methods. The actual cost function used in System R* is quite complex, it takes account of the computation cost at a site as well as the transmission cost between sites. Further, the System R* method for optimizing distributed queries exhaustively considers all possible strategies for query evaluation that can be built from a fixed collection of options. The System R* is described in greater detail in Principles of Database Systems, by Jeffrey D. Ullman, Computer Science Press, 1982, which is incorporated herein by reference.

The System R* method has the disadvantage that the computation time spent in determining an optimum query execution strategy may exceed the time to be saved by execution of the optimal strategy. Further, the System R* method requires the site at which optimization is being performed to have access to sufficient information about the various sites so that the computation cost at the sites can be calculated. This site information has to be transmitted to the optimization site and must be updated as conditions at the various sites change. In addition, the System R* optimization method requires that all, global and local, optimization must be performed before any execution of the query can be started.

OBJECTS OF THE INVENTION

Accordingly, it is an object of the present invention to provide a distributed database query optimization method that allows some of the optimization to be done locally.

It is another object of the present invention to provide a distributed database query optimization method that separates optimization into global and local processes allowing multiple local optimizations to be done in parallel thereby decreasing the elapsed optimization time.

It is a further object of the present invention to provide a distributed database query optimization method which has a less exhaustive global optimization process and allows some of the optimization to be done locally.

It is a yet further object of the present invention to provide a distributed database query optimization method which does not require local database parameters to be present at all sites which perform query optimization.

It is a still further object of the present invention to provide a distributed database query optimization method which performs local optimization at the local sites using current local database parameters.

This invention is pointed out with particularly in the appended claims. An understanding of the above and further objects and advantages of this invention can be obtained by referring to the following description taken in conjunction with the drawings.

SUMMARY OF THE INVENTION

A method for determining an optimal execution strategy for a request comprising query, update or transaction operations on a distributed database system having multiple data sites interconnected by communication lines in which optimization is done by inputting the request in the form of a compacted tree having leaf and non-leaf nodes and then for each node in the compacted tree: (1) doing materialization planning to choose the data sites from which data is to be accessed; (2) doing 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) doing non-local process planning to determine strategy for remaining operations which can not be performed locally without transmission of data between sites; and then (4) building the requests for each data site in the distributed database system at which data is processed by access or manipulation. After performing the optimization, the built requests are output to a process that coordinates the execution of the built requests at sites within the distributed database system.

BRIEF DESCRIPTION OF THE DRAWINGS

The manner in which the method of the present invention is performed can best be understood in light of the following detailed description together with the accompanying drawings in which like reference numbers identify like elements in the several figures and in which:

FIG. 1 is a diagram of the five schema architecture of the distributed data system.

FIG. 2 is a diagram of a distributed data system logical architecture showing data processors and application processors connected by a communications network.

FIG. 3 is a diagram of the steps associated with processing a distributed data system query, update or transaction.

FIG. 4 is a diagram of an example Entry-Category-Relationship (ECR) schema.

FIG. 5 is a diagram of an example relational schema corresponding to the example ECR schema of FIG. 4.

FIG. 6 is a diagram of an example binary tree.

FIG. 7 is a compacted tree corresponding to the binary tree of FIG. 6.

FIG. 8 is a flow diagram of the optimization method of the present invention.

DESCRIPTION OF THE PREFERRED EMBODIMENT

In a Distributed Database System (DDS), database management and transaction management are extended to a distributed environment.

This distributed environment may provide multiple user interfaces including non-procedural query interfaces and programming language interfaces; distributed database processing; an active Data Dictionary/Directory (DD/D) system that may be distributed; multiple database managers; and a comprehensive set of user support facilities.

The Materialization and Access Planning (MAP) process for a distributed query, update, or transaction is an important part of the processing of the query, update, or transaction. Materialization and access planning results in a strategy for processing a query, update, or transaction in the Distributed Database Management System (DDBMS). Materialization consists of selecting data copies used to process the query, update, or transaction. This step is necessary since data may be stored at more than one site (i.e., computer) on the network. Access planning consists of choosing the execution order of operations and the actual execution site of each operation.

The MAP process of the preferred embodiment selects a good materialization for all data in the query, update, or transaction. Three different access planning methods are provided, GENERAL (RESPONSE), GENERAL (TOTAL), and Initial Feasible Solution (IFS). GENERAL (RESPONSE) and GENERAL (TOTAL) build optimal execution strategies using a cost function of the communications costs. Local processing costs are not considered. GENERAL (RESPONSE) builds an execution strategy with minimum response time, the time elapsed between the start of the first transmission and the time at which the result arrives at the required computer. GENERAL (TOTAL) builds an execution strategy with minimum total time, the sum of the time of all transmissions. IFS does not perform any optimization.

The IFS solution is optimal when small amounts of data are required for transmission by the user request. The IFS solution always has the smallest number of messages; GENERAL (RESPONSE) and GENERAL (TOTAL) consider solutions with additional messages that result in additional local processing in an attempt to minimize the amount of data transmitted, i.e., these solutions have more messages than the IFS solution, but the sum of the size of the messages is smaller. When small amounts of data in the database are being accessed, the solution of IFS is optimal.

Further performance improvements can be obtained by improving the cost function used by GENERAL (RESPONSE) and GENERAL (TOTAL). The current function only includes communications costs. The communications costs were assumed to be a linear function of the message size, and the same cost function was used for sending a message between any two sites. Local processing costs could be included in the cost function. In addition, the load and capacity of each site are very important to overall performance. For the DDS system environment in which the sites are locally distributed, these factors are not negligible compared to communications. For geographically distributed environments, they will be much less important.

GENERAL (RESPONSE) should be used when optimal user response time is the goal of the system; GENERAL (TOTAL) should be used when optimal total communications time is the goal of the system. The choice between GENERAL (RESPONSE) and GENERAL (TOTAL) depends on the particular system applications and goals. The cost functions used by GENERAL (RESPONSE) and GENERAL (TOTAL) can be tuned for each system. The communications cost function can be determined from system performance data. For a geographically distributed system, this function may be sufficient. In a locally distributed system, the inclusion of local processing costs, load, and capacity of the sites should be considered. The MAP method of the preferred embodiment is also described in "A Study of Materialization and Access Planning", by P. A. Dwyer, CSC-84-10: 8212, Honeywell Inc. Computer Sciences Center, February 1984, which is incorporated herein by reference.

The Distributed Database System Architecture

In this section, the information architecture, system architecture, and transaction management of DDS are described. The information architecture describes how information is to be conceptually modeled, represented, and allocated. The system architecture describes processor characteristics, processor locations, communications, and system level protocols for distributed execution. Transaction management describes the processing steps required for a query, update, or transaction using the information and system architectures.

Information Architecture

The ANSI/SPARC 3-schema architecture described in "The ANSI/X3/SPARC Report of the Study Group on Data Base Management Systems", edited by A. Klug and D. Tsichritzis, AFIPS Press, 1977, which is incorporated herein by reference, a database system is extended in DDS to provide for a distributed system. In the 3-schema architecture, the three levels of database description are the conceptual schema, the external schemas, and the internal schema. The conceptual schema is a description of the portion of the world being modeled by the database. An external schema is a consistent and logical subset of the conceptual schema; it is the description of a user view of the database. The internal schema describes the system representation of the database.

This 3-schema proposal for centralized DBMSs has been extended to the 5-schema architecture in DDS as illustrated in FIG. 1 as described in "Transaction Processing in a Multi-schema Distributed Database Testbed System" by C. C. Devor, R. Elmasri and S. Rahimi, HR-81-253: 17-38, Honeywell Corporate Computer Sciences Center, February 1981, which is incorporated herein by reference. The external schemas 4a, 4b and 4c are descriptions of the users 2a, 2b, 2c and 2d views, and serve as the user interface. The conceptual schema 6 is a semantic description of the total distributed database. The global representation schema 8 is a synthetic representation of the total database content. The local representation schemas 12a, 12b and 12c are syntactic descriptions of the data resident at specific nodes. The local internal schemas 14a, 14b and 14c are the local database management system implementations that manage the database fragments 16a, 16b and 16c.

In DDS, the global representation schema 8 and the local representation schemas 12a, 12b and 12c are described with the relational model, as described in "A Relational Model for Large Shared Data Banks" by E. F. Codd, Communications of the ACM, Vol. 13, No. 6, June 1970, which is incorporated herein by reference, because the relational data model is convenient for describing the distribution and replication of data across the sites of the DDBMS, and data described in this model can be accessed using a nonprocedural set oriented data manipulation language as opposed to a procedural, record at a time data manipulation language. In the DDS implementation of the preferred embodiment, the local internal schemas 14a, 14b and 14c use the network model because the local database management systems are IDS/II systems described in GCOS 6 IDS/II User's Guide, Honeywell Information Systems Inc., Waltham, Mass., November 1978, which is incorporated herein by reference. Other DBMSs with possibly different local internal schemas can be used.

System Architecture

DDS consists of a set of Application Processors (APs) 20a, 20b and 20c and Data Processors (DPs) 24a, 24b and 24c connected by a communications network 22 (See FIG. 2). The APs control the interface to the users 24a, 24b and 24c and all transaction management, and the DPs perform the data management of the databases 26a, 26b and 26c. DDS of the preferred embodiment is implemented on Honeywell Level 6 computers 24a, 24b and 24c with the GCOS6 MOD400 operating system. Each Level 6 computer 24a, 24b and 24c can support zero or more APs and/or zero or more DPs. Additional details of the DDS system architecture can be found in "Implementing the Distributed Database Testbed System (DDTS) in a Multi-computer GCOS 6/MOD Environment", by C. C. Devor, M. Spinrad, P. A. Tovo, K. Koeneman, and M. Smith, HR-81-264: 17-38, Honeywell Corporate Computer Sciences Center, June 1981, which is incorporated herein by reference.

Transaction Management

The user's view of DDS is built around the concepts of a query, an update, or a transaction. The steps involved in processing a query, an update, or a transaction are illustrated in FIG. 3. A query, an update, and a transaction in DDS are defined in the GORDAS high-level data manipulation and description language as described in "GORDAS: A Data Definition, Query and Update Language for the Entity-Category-Relationship Model of Data", by R. Elmasri, HR-81-250: 17-38, Honeywell Corporate Computer Sciences Center, January 1981, which is incorporated herein by reference. GORDAS (Graph ORiented DAta Selection Language) is a language for graph-oriented data models such as the Entity-Relationship (ER) model as described in "The Entity-Relationship Model: Towards a Unified View of Data", by P. P-S. Chen, ACM Transactions on Database Systems, Volumn 1, Number 1, March 1976, which is incorporated herein by reference and the Entity-Category-Relationship (ECR) model described in "The Entity-Category-Relationship Model of Data" by J. A. Weeldreyer, HR-80-250: 17-38, Honeywell Corporate Computer Sciences Center, March 1980, which is incorporated herein by reference. A transaction expressed in GORDAS 30 is simply more than one GORDAS query or update to be processed as a group. Currently, GORDAS transactions cannot contain control constructs such as, IF-THEN-ELSE-ENDIF and DO-WHILE. A query or an update in GORDAS 30 is translated to a single cluster tree that is an internal non-procedural representation of the query or update (see FIG. 3). A transaction expressed in GORDAS 30 is translated to a list of cluster trees 34 by Transaction and Integrity Control (TIC) 32; there is one cluster tree per query or update in the transaction. The cluster tree operators operate on the data described by the global representation schema.

After translation of a query, an update, or a transaction, materialization and access planning 38 take place. For each query or update, a materialization is chosen and an execution strategy 40 is built. The execution strategy is expressed in terms of the local representation schemas. Both TIC 32 and MPA 38 use information from the database dictionary directory (DD/D) 36 to perform their functions.

A Distributed Execution Monitor (DEM) 42 coordinates the processing of the execution strategy. The DEM 42 sends commands that specify the local relational operations to one or more Local Execution Monitors (LEMs) 44a, 44a for local optimization and execution. The DEM 42 coordinates synchronization among the commands, and is responsible for commitment and concurrency control of updates at multiple sites. The local relational operators are translated to the operations on the local DBMS 46a and 46b by the Local Operations Module (LOM) 45a and 45b and are executed against the databases 48a, 48b.

Compiling and saving a transaction for later execution offers an alternative scheme. "Compilation" consists of processing the transaction through materialization and access planning 38. At this point the operations are expressed in terms of the local representation schemas. They are stored at the local nodes for later execution. At execution time the DEM 42 sends commands to the local execution monitors 44a and 44b specifying which stored operations to execute.

The MAP 38 System Environment

This section presents the system environment of the DDS that is relevant to the MAP 38 process. The five areas discussed are the internal data model, the type of data distribution, the level of distribution transparency, the usage characteristics, and the transaction management facilities.

The Internal Data Model

In DDS, MAP 38 is applied to queries, updates, and transactions whose operations are expressed in terms of the global representation schema. Using location information, MAP 38 produces an execution strategy that contains operations against the local representation schemas. Each Local Operations Module (LOM) 45a and 45b translates its operationss to operationss against an IDS/II schema. Both the global and local representation schemas are defined using the relational model of data.

The following terms, as defined, are used in the following description. References for these terms can be found in Fundamentals of Data Structures, by E. Horowitz and S. Sahni, Computer Science Press, Inc., 1967, and An Introduction to Database Systems, Second Edition, by D. J. Data, Addison-Wesley Publishing Company, Inc., 1977, which are incorporated herein by reference.

relation: Given a collection of sets D1, D2, . . . , Dn (not necessarily distinct), R is a relation on these n sets if it is a set of ordered n-tuples <d1, d2, . . . , dn> such that d1 belongs to D1, d2 belongs to D2, . . . , dn belongs to Dn. Sets D1, D2, . . . , Dn are the domains of R. The value n is the degree of R.

attribute: The use of a domain within a relation.

relational model of a database: A user's view of that database as a collection of time-varying, normalized relations of assorted degrees.

normalized relation: Every value in the relation, i.e., each attribute value in each tuple, is atomic (nondecomposable).

tuple: Each row of the table represents one n-tuple (or simply one tuple) of the relation.

cardinality: The number of tuples in a relation.

data sublanguage: The set of operators provided to manipulate data in relational form.

relational algebra: A collection of high level operations on relations.

retrieval or query operators: The set of operators for retrieving data in relational form.

storage or update operators: The set of operators for storing data in relational form.

relational algebra retrieval operations: selection, projection, join, division, union, intersection, difference, and extended Cartesian product.

relational algebra storage operations: insert, delete, and modify.

union-compatible relations: Relations of the same degree, n, and the jth attribute of one relation must be drawn from the same doman as the jth attribute of the other relation (1<=j<=n).

union: The union of two union-compatible relations A and B, A UNION B, is the set of all tuples t belonging to either A or B (or both).

intersection: The intersection of two union-compatible relations A and B, A INTERSECT B, is the set of all tuples t belonging to both A and B.

difference: The difference between two union compatible relations A and B (in that order), A MINUS B, is the set of all tuples t belonging to A and not to B.

extended Cartesian product: The extended Cartesian product of two relations A and B, A TIMES B, is the set of all tuples t such that t is the concatenation of a tuple a belonging to A and a tuple b belonging to B. The concatenation of a tuple a=(a1, . . . , am) and a tuple b=(bm+1, . . . , bm+n), in that order, is the tuple t=(a1, . . . , am, bm+1, . . . , bm+n).

selection: select is an operator for constructing a horizontal subset of a relation, i.e., that subset of tuples within a relation for which a specified predicate is satisfied. The predicate is expressed as a Boolean combination of terms, each term being a simple comparison that can be established as true or false for a given tuple by inspecting that tuple in isolation.

projection: project is an operator for constructing a vertical subset of a relation, i.e., a subset obtained by selecting specified attributes and eliminating others (and also eliminating duplicate tuples within the attributes selected).

join: The equi-join of relation A on attribute X with relation B on attribute Y, join A and B where X=Y, is the set of all tuples t such that t is a concatenation of a tuple a belonging to A and a tuple b belonging to B, where x=y (x being the X component of a and y the Y component of b). We may define joins for each of the other comparison operators >, <>, >=, <, and <=.

division: An operation between a binary relation (the dividend) and a unary relation (the divisor) which produces a unary relation (the quotient) as its result. Let the divident A have attributes X and Y and let the divisor B have attribute Z, and let Y and Z be defined on the same underlying domain. The the divide operation, divide A by B over Y and Z, produces a quotient defined on the same domain as X; as value x will appear in the quotient if and only if the pair <x,y> appears in A for all values y appearing in B.

tree: A finite set of one or more nodes such that: (i) there is a specially designated node called the root; (ii) the remaining nodes are partitioned into n>=0 disjoint

sets T1, . . . , Tn where each of these sets is a tree. T1, . . . , Tn are called the subtrees of the root.

node: The item of information plus the branches to other items.

degree: The number of subtrees of a node.

leaf or terminal nodes: Nodes that have degree zero.

non-leaf or non-terminal nodes: Nodes that have degree greater than zero.

children: The roots of the subtrees of a node, X, are the children of X. X is that parent of its children.

degree of a tree: The maximum degree of the nodes in the tree.

binary tree: A finite set of nodes which is either empty or consists of a root and two disjoint binary trees called the left subtree and the right subtree.

FIG. 6 is an example binary tree having nodes N1 through N11. Node N1 is the root node of the tree and nodes N2 through N8 compose the left subtree and nodes N9 through N11 compose the right subtree. Nodes N2 and N9 are the children of node N1 and nodes N3 and N4 are the children of N2. Nodes N1, N2-N4 and N9 are non-leaf or non-terminal nodes and nodes N5-N8, N10 and N11 are leaf or terminal nodes. Nodes N1 and N9 are union operators and nodes N2, N3 and N4 are join operators.

FIG. 7 is a compacted tree corresponding to the binary tree of FIG. 6. A tree is compacted by combining nodes having the same associative and commutative binary operator into a single node, provided the nodes being combined form a tree, with no intervening nodes labeled by other operators. The binary operators, union and join, are associative and commutative, so this rule applies to each of them. A tree of nodes labeled by just one of these binary operators is called a cluster. All the nodes of a cluster can be replaced by a single node, and the children of the nodes in the cluster become children of the new node. The parent of the new node is the parent of the node in the cluster that is an ancestor of all the nodes in the cluster.

In DDS, the query, update, or transaction expressed in GORDAS is translated to an internal non-procedural representation. This representation has features of both relational algebra and relational calculus. It is similar to an internal representation of SQL, the language defined for System-R as described in "Implementation of a Structured English Query Language", by M. M. Astrahan and D. D. Chamberlin, Communications of the ACM, Vol. 18, Nov. 10, 1975, which is incorporated herein by reference.

The internal representation that is output from the GORDAS translator and input to the MAP module is a set of cluster trees. There is a cluster tree per query or update in a transaction. For queries, there is one cluster tree input. A cluster tree represents a compacted tree of a query or update. The operations that are commutable are combined into one cluster node so that the optimization is not restricted by a given order.

The non-leaf nodes in a cluster tree are used for set operations such as UNION, INTERSECTION, and DIFFERENCE. They are also used for update operations such as DELETE, INSERT, and MODIFY. The leaves of a cluster tree represent combinations of SELECT, PROJECT, and JOIN operations. Each leaf has a variable list of the base relations involved, V (Variables), a condition on the base relations, C (Condition), and a list of attributes to project for the result, P (Project).

For example, consider the Entry-Category-Relationship (ECR) and relational schemas of FIGS. 4 and 5. The ECR schema in FIG. 4 represents the conceptual schema in FIG. 4 in DDS, and the relational schema in FIG. 5 represents the corresponding global representation schema.

FIG. 4 show 2 entities, DEPT 52 and EMP 56 in a relationship WORKS-IN 54. DEPT 52 has one attribute NAMES 50 and EMP 56 has three attributes FNAME 58, LNAME 60 and SEX 62.

FIG. 5 shows two relations, DEPT 64 and EMP 66 with the corresponding attributes.

For the following query:

get <LName, Sex> of Emp, the cluster tree, T1, contains one node: ##STR1## For the query:

get <LName, Sex> of Emp where FName=`Mary` and Name of Dept=`ISA`, the following cluster tree, T2, is produced: ##STR2## For the query:

get <LName, Sex> of Emp where FName=`Mary` or Name of Dept=`ISA`, the following cluster tree, T3, is produced: ##STR3## Since the JOIN does not commute with the UNION, an additional cluster representing this procedurality is generated.

For the update:

delete Emp where LName=`Smith`, the following cluster tree, T4, is produced: ##STR4## The query cluster determined what relations are to be deleted, and the delete is applied to them.

In the MAP design of the preferred embodiment, the materialization and query optimization are applied to each leaf node in a cluster tree. For cluster trees with non-leaf set nodes, the location of the final result of each leaf is used to decide where the set operation is to occur. For cluster trees with non-leaf updates, the update is performed at all sites containing the relation. The record identifiers of the records to be updated are transmitted to all sites.

The output of the MAP process is an execution strategy. This strategy contains the operations that are to be distributed among the sites involved in the execution of the query, update, or transaction, and contains commands used by the DEM to coordinate the execution. The operations to be distributed among the sites are expressed against the local representation schemas. The format is similar to the relational algebra, and includes a move command that instructs the data processor to move a temporary relation to another data processor. Each command may have preconditions, commands that must be executed previous to the execution of the command. By using the commands and the preconditions, a query tree can be built. The Brakus Normal Form (BNF) used in DDS for the commands in the execution strategy follows.

    __________________________________________________________________________
    <network commands> ::=
                  { <preconditions> } ( <move command>
                  <insert command>   <execute command>
                  <modify command>   <delete command> )
    <preconditions> ::= { <preconditions> } <command>
    <move command> ::=
                <execution site> <temporary relation name>
                <destination>
    <insert command> ::= <execution site list> <insert>
    <execution site list> ::= { <execution site list> } <execution site>
    <execute command> ::= <execution site> <assignment>
    <modify command> ::= <execution site list> <modify>
    <delete command> ::= <execution site list> <delete>
    <assignment> ::= <target> <- <algebra expression>
    <target> ::= <temporary relation name>
    <algebra expression> ::=
                 <item list>    <selection>   <projection>
                 <join>   <two relation operation>
    <item list> ::= { <item list> , } <value spec>
    <value spec> ::= <variable>   <constant>
    <selection> ::= SELECT <term> WHERE <logical expression>
    <term> ::= <relation name>   `(` <algebra expression> `)`
    <projection> ::= PROJECT <term> OVER <attribute spec list>
    <attribute spec list> ::= { <attribute spec list> , } <attribute spec>
    <attribute spec> ::=
               <attribute name>   <relation name>
               <attribute name>
    <join> ::= <term> JOIN <term> WHERE <join attribute specs>
    <join attribute specs> ::=
                  {<join attribute spec> AND}
                  <join attribute spec>
    <join attribute spec> ::=  <attribute spec> = <attribute spec>
    <two relation operation> ::= <term> <two relation operator> <term>
    <two re1ation operator> ::=
                   UNION   INTERSECT   MINUS
                   TIMES   DIVIDEBY
    <logical expression> ::=
                 { <logical expression> (AND   OR) }
                 <logical term>
    <1ogical term> ::=
              { NOT } ( <condition>
              `(` <logical expression> `)` }
    <condition> ::=
             <set expr> <set comparison op> <set expr>
               <scalar expr> <scalar comparison op> <scalar expr>
    <set comparison op> ::= INCLUDES   INCLUDED --IN   =   <>
    <set expr> ::= <item list>   <relation spec>
    <relation spec> ::= <relation name> <attribute spec list>
    < scalar comparison op> ::= =   <>   <   >   <=   >=
    <scalr expr> ::= { <scalar expr> (+   -) } <term>
    <term> ::= {<term> (X   /   DIV   REM) } <factor>
    <factor> ::= `(` <scalar expr> `)`   <basic value>
    <basic value> ::=
              { <scalar function> } (<value spec>
              <attribute spec>)
    <scalar function> ::= ABS   SQRT
    <insert> ::=
           INSERT <temporary relation name> INTO
           <base relation name>
    <delete> ::= DELETE <base relation name> WHERE <logical expression>
    <modify> ::=
            MODIFY <attribute spec list> OF <base relation name> TO
            <scalar expr list>  WHERE <logical expression>
    <scalar expr list> ::= {<scalar expr list>,} <scalar expr>
    __________________________________________________________________________

    ______________________________________
    command#
            site   precondition
                              command
    ______________________________________
    1       1      --         T1<-SELECT Emp
    2       1      1          T2<-PROJECT T1
                              OVER Emp.LName, Emp.Sex
    3       1      2          MOVE T2 TO SITE 2
    ______________________________________

    ______________________________________
    com-
    mand# site    precondition
                             command
    ______________________________________
    1     1       --         T1<-SELECT Emp WHERE
                             Emp.FName = `Mary`
    2     1       1          MOVE T1 TO SITE 2
    3     2       --         T2<-SELECT Dept WHERE
                             Dept.DName = `ISA`
    4     2         2,3      T3<-JOIN T1, T2 WHERE
                             T1.Dep#=T2.D#
    5     2       4          T4<-PROJECT T3 OVER
                             T3.LName, T3.Sex
    ______________________________________

    ______________________________________
    com-
    mand# site    precondition
                             command
    ______________________________________
    1     1       --         T1<-SELECT Emp WHERE
                             Emp.FName = `Mary`
    2     1       1          MOVE T1 TO SITE 2
    3     1       --         T2<-SELECT Emp
    4     1       3          MOVE T2 TO SITE 2
    5     2       --         T3<-SELECT Dept WHERE
                             Dept.DName = `ISA`
    6     2         4,5      T4<-JOIN T2,T3 WHERE
                             T2.Dep#=T3.D#
    7     2       2          T5<-PROJECT T1 OVER
                             T1.LName, T1.Sex
    8     2       6          T6<-PROJECT T4 OVER
                             T4.LName, T4.Sex
    9     2         7,8      T7<-T5 UNION T6
    ______________________________________

    ______________________________________
    com-          precon-
    mand# site    dition   command
    ______________________________________
    1     1       --       T1<-SELECT Emp WHERE
                           Emp.LName = `Smith`
    2     1       1        T2<-PROJECT T1 OVER T1.E#
    3     1         1,2    DELETE Emp WHERE Emp.E#
                           INCLUDED IN T1
    ______________________________________

    ______________________________________
    n(i):   the number of tuples (cardinality),
    a(i):   the number of attributes (degree),
    s(i):   the size, s(i) = n(i) * (sum over all a(i) of w(i,j)).
    ______________________________________

    ______________________________________
    v(i,j):
           the number of possible domain values,
    u(i,j):
           the number of distinct domain values currently held,
    w(i,j):
           the size of one data item in attribute domain (bytes),
    h(i,j):
           the high value of d(i,j) in u(i,j),
    l(i,j):
           the low value d(i,j) in u(i,j).
    ______________________________________

    ______________________________________
    s(i,j) = size of all attributes j, = n(i) * w(i,j),
    p(i,j) = selectivity of attribute j, = u(i,j)/v(i,j).
    ______________________________________

    ______________________________________
    n(i):           the cardinality,
    a(i):           the number of attributes,
    s(i):           the size in bytes.
    ______________________________________

    ______________________________________
    p(i,j): the selectivity,
    s(i,j): the size in bytes of all of the data items in attribute
            d(i,j).
    ______________________________________

    ______________________________________
    (1) column = value
        F = 1/u(i,j)
    (2) column1 = column2
        F = 1/MAX (u(i,column1), u(i,column2))
    (3) column > value
        F = (h(i,column) - value) / (h(i,column) - l(i,column))
        = 0 (if F < 0)
    (4) column < value
        F = (value - l(i,column) / (h(i,column) - l(i,column))
        = 0 (if F < 0)
    (5) (pred1) OR (pred2)
        F = F(pred1) + F(pred2) - F(pred1) * F(pred2)
    (6) (pred1) AND (pred2)
        F = F(pred1) * F(pred2)
    (7) NOT pred
        F = 1 - F(pred)
    ______________________________________

    ______________________________________
    T <- SELECT R WHERE predicate
    n(T) = n(R) * F
    a(T) = a(R)
    s(T) = s(R) * F
    For all attributes, j,
    v(T,j) = v(R,j)
    u(T,j) = u(R,j) * F
    w(T,j) = w(R,j)  (size of ONE attribute)
    h(T,j) = h(R,j)
    l(T,j) = l(R,j)
    s(T,j) = s(R,j) * F
    p(T,j) = p(R,j) * F
    ______________________________________

    ______________________________________
    T <- PROJECT R OVER d(j), . . .
    n(T) = n(R)
    a(T) = count (d(j), . . .) - the number projected
    s(T) = n(T) * (the sum over the attributes projected)
    v(T,j) = v(R,j)
    u(T,j) = u(R,j)
    w(T,j) = w(R,j)
    h(T,j) = h(R,j)
    l(T,j) = l(R,j)
    s(T,j) = s(R,j)
    p(T,j) = p(R,j)
    ______________________________________

    ______________________________________
    JOIN R(1), R(2) WHERE R(1).A = R(2).A
    F(1) = p(2,A)    and   F(2) = p(1,A)
    n(1) = n(1) * F(1)      n(2) = n(2) * F(2)
    a(1) = a(1)             a(2) = a(2)
    s(1) = s(1) * F(1)      s(2) = s(2) * F(2)
    For the attributes, j:
    v(i,j) = v(i,j)
    u(i,j) = u(i,j) * F(i)
    w(i,j) = w(i,j)
    h(i,j) = h(i,j)
    l(i,j) = l(i,j)
    ______________________________________

    ______________________________________
    if (n(1) > n(2))
    n = n(1)
    s = s(1) + s(2) + (s(2) * ((n(1) - n(2))/n(2))
    else
    n = n(2)
    s = s(1) + s(2) + (s(1) * ((n(2) - n(1))/n(1))
    a = a(1) + a(2)
    ______________________________________

    ______________________________________
              s(i,j) = s(i,j) * p(k,l)
              and
              p(i,j) = p(i,j) * p(k,l).
    ______________________________________

    ______________________________________
    Static Design
    procedure map (
    in:       first --cluster: cluster --ptr,
              result --ap: node --id,
              opt --Type: map --optimization  --choices;
    out:      block --table: block --ptr,
              error: error --code
    );
    Permanent Data
    None
    Local Data
    cl --prt: pointer to cluster --list;
    req --table: request array;
    final --temp: relation --name;
    result --dp: node --id;
    ______________________________________

    ______________________________________
    P-Notation
    error := FALSE;
    initialize --req --table (out: req --table, error);
    if (not error)
    cl --ptr := first --cluster;
    do (cl --ptr  = NULL) and (not error)
    build --requests (in: cl --ptr->cluster --root, result --ap,
    opt --type, req --table; out: req --table, final --temp,
    result --dp, error)
    if (final --temp  = "") and (not error)
    add --move (in: req --table, final --temp, result --dp,
    result --ap; out: req --table, error);
    if (not error)
            add --print (in: req --table, final --temp,
            result --ap; out: req --table, error);
      (error)
            skip;
    fi;
      (error)
    skip;
    fi;
    cl --ptr := cl --ptr->next --root;
    od;
    if (not error)
    dataflow (in: req --table; out: req -- table, error);
    if (not error)
            build --command --list (in: req --table;
            out: block --ptr, error);
      (error)
    skip;
    fi;
      (error)
    skip;
    fi;
    free clusters;
    ______________________________________

    ______________________________________
    Static Design
    procedure build --requests
    in:      cl --root: pointer to cluster,
             result --ap: node --id,
             opt --type: map --optimization --choices,
             req --table: request array;
    out:     req --table: request array,
             final --temp: relation --name,
             result --dp: node --id,
             error: error --code;
    );
    Permanent Data
    None
    Local Data
    temp --info --list: temp --dp;
    var: cluster;
    temp: relation --name;
    dp: node --id;
    ______________________________________

    __________________________________________________________________________
    P-Notation
    error = FALSE;
    if (cl --root  = NULL)
     if (tag (cl --leaf) = BASE) { leaf }
    optimize --cluster (in: cl --root, result --ap, opt --type, req --table;
    out: final --temp, req --table, result --dp, error);
    .vertline. (otherwise) {UNION, INTERSECT, DIFFERENCE, DELETE, INSERT,
    MODIFY}
    var = cl --root->cl --var;
    temp --info --list = NULL;
    do (var  = NULL) and (not error)
    build --requests (in: var, result --ap, opt --type, req --table;
    out: req --table, temp, dp, error);
    if (not error)
     add --to --list (in: temp --info --list, temp, dp;
    out: temp --info --list, error);
    .vertline. (error)
     skip;
    fi;
    var := var->next --var;
    od;
    if (tag (cl --root) = UNION) or (tag (cl  --root) = INTERSECT) or
    (tag (cl --root) = DIFFERENCE)
    ( and (not error))
    pick --dp (in: temp --info --list, result --ap; out: dp, error);
    if (not error)
     add --set --ops (in: temp --info --list, dp, req --table,
      tag (cl --root); out: req --table, error);
    .vertline. (error)
    skip;
    fi;
    .vertline. ((tag (cl --root) = DELETE) or (tag (cl --root) = INSERT) or
    (tag (cl --root) = MODIFY)) and (not error)
      add --update --ops (in: temp --info --list, req --table, tag (cl
    --root),
       cl --root->update --cluster; out: req --table, error);
    .vertline. (otherwise)
    skip;
    fi;
     fi;
    fi
    __________________________________________________________________________

    ______________________________________
    Static Design
    procedure optimize --cluster (
    in:      cl --leaf: cluster,
             result --ap: node --id,
             opt --type: map --optimization --choices,
             req --table: request array;
    out:     final --temp: relation --name,
             req --table: request array,
             result --dp: node --id;
             error: error --code
    );
    Permanent Data
    Temp --rel --table: abstract; { table in data dictionary }
    Local Data
    rel --info: rel --info --ptr;
    ______________________________________

    ______________________________________
    P-Notation
    error := FALSE;
    { set the base sites in the cluster }
    materialization (in: cl --lear->bases, result --ap;
    out: cl --lear->bases, result --dp, error);
    if (not error)
     local --processing (in: cl --leaf; out:rel --info, error);
     if (not error)
    if (opt --type = GENERAL RESPONSE) or (opt --type =
    General --TOTAL)
     general (in: cl --leaf, result --dp, result --ap, rel --info;
    out: rel --info, error);
    .vertline. (otherwise)
    skip;
    fi;
    { don't do anything for IFS }
    if (not error)
     build --requests --table (in: rel --info, cl --leaf, req --table,
     result --dp;
    out: final --temp, req --table, error);
    .vertline. (error)
     skip;
    fi;
    free rel --info;
    .vertline. (error)
    skip;
     fi;
     .vertline. (error)
     skip;
    fi;
    ______________________________________

    ______________________________________
    Static Design
    procedure local --processing (
            in:  cl --leaf: pointer to cluster;
            out: rel --info: rel --info --ptr,
                 error: error --code;
    );
    Permanent Data
    None
    Local Data
    None
    ______________________________________

    ______________________________________
    n(i):      the number of tuples (cardinality),
    a(i):      the number of attributes (degree),
    s(i):      size,
    s(i) = n(i) * (sum over all a(i) of w(i,j))
    ______________________________________

    ______________________________________
    v(i,j):
           the number of possible domain values,
    u(i,j):
           the number of distinct domain values currently held
    w(i,j):
           the size of ONE data item in attribute domain (bytes)
    h(i,j):
           the high value of u(i,j)
    l(i,j):
           the low value of u(i,j)
    ______________________________________

    ______________________________________
    s(i,j) =      size of all attributes j,
    =             n(i) * w(i,j)
    p(i,j) =      selectivity of attribute j,
    =             u(i,j)/v(i,j)
    ______________________________________

    ______________________________________
    (1)   column = value
          F = 1/u(i,j)
    (2)   column1 = column2
          F = 1/MAX (u (i,column1), u(i,column2))
    (3)   column > value
          F = (h(i,column) - value) / h(i,column) - l(i,column))
          = 0 (if F < 0)
    (4)   column < value
          F = (value - l(i,column) / (h(i,column) - l(i,column))
          = 0 (if F < 0)
    (5)   (pred1) OR (pred2)
          F = F(pred1) + F(pred2) - F(pred1) * F(pred2)
    (6)   (pred1) AND (pred2)
          F = F(pred1) * F(pred2)
    (7)   NOT pred
          F = 1 - F(pred)
    ______________________________________

    ______________________________________
    T <- SELECT R WHERE predicate
    n(T) =      n(R) * F
    a(T) =      a(R)
    s(T) =      s(R) * F
    v(T,j) =    v(R, j)
    u(T,j) =    u(R,j) * F
    w(T,j) =    w(R,j) (recall size of ONE attribute)
    h(T,j) =    h(R,j)
    l(T,j) =    l(R,j)
    s(T,j) =    s(R,j) * F
    p(T,j) =    p(R,j) * F
    ______________________________________

    ______________________________________
    T <- PROJECT R over d(j), . . .
    n(T) =   n(R)
    a(T) =   count (d(j)) - the number projected
    s(T) =   n(T) * (the sum over the attributes projected)
    v(T,j) = v(R, j)
    u(T,j) = u(R,j)
    w(T,j) = w(R,j)
    h(T,j) = h(R,j)
    l(T,j) = l(R,j)
    s(T,j) = s(R,j)
    p(T,j) = p(R,j)
    ______________________________________

    ______________________________________
    JOIN R(1), R(2) where R(1).A = R(2).A
    F(1) = P(2,A)  and        F(2) = P(1,A)
    n(1) = n(1) * F(1)        n(2) = n(2) * F(2)
    a(1) = a(1)               a(2) = a(2)
    s(1) = s(1) * F(1)        s(2) = s(2) * F(2)
    For the attributes:
    v(i,A) = v(i,A)
    u(i,A) = u(i,A) * F(i)
    w(i,A) = w(i,A)
    h(i,A) = h(i,A)
    l(i,A) = l(i,A)
    ______________________________________

    ______________________________________
    if (n(1) > n(2))
    n = n(1)
    s = s(1) + s(2) + (s(2) * ((n(1) - n(2))/n(2))
    else
    n = n(2)
    s = s(1) + s(2) + (s(1) * ((n(2) - n(1))/n(1))
    a = a(1) + a(2)
    P-Notation
    error := FALSE;
    if tag(cl --leaf)  = BASE
    error := TRUE;
      tag(cl --leaf) = BASE
    rel --info --create
                     (in: cl --leaf.fwdarw.base --cluster;
                     .sup. out: re --info, error);
    if (not error)
     join --bases --at --same --node
                          (in: rel --info;
                          .sup. out: rel --info, error);
       (error)
           skip;
    fi;
    fi;
    ______________________________________

    ______________________________________
    Static Design
    procedure general (
            in:     cl --leaf: cluster --ptr,
                    opt --type: map --optimization --choices,
                    result --dp: node --id,
                    result --ap: node --id,
                    rel --info: rel --info --ptr;
            out:    rel --info: rel --info --ptr,
                    error: error --code
    );
    Permanent Data
    Total --number --of --joining --attrs: integer;
    Local Data
    ja: integer;
    temp --relp: rel --info --ptr;
    ______________________________________

    ______________________________________
    P-Notation
    error := FALSE;
    ja := 0;
    do (ja < Total --number --of --joining --attrs )
    and (not error)
    if (opt --type = GENERAL --RESPONSE)
    parallel (in: rel --info, ja; out: rel --info, error);
      (opt --type = GENERAL --TOTAL)
    serial    (in: rel --info, result --dp, ja;
              .sup. out: rel --info, error);
    fi;
    ja := ja + 1;
    od;
    if (not error)
    temp --relp := rel --info;
    do (temp --relp  = NULL) and (not error)
    if (opt --type = GENERAL --RESPONSE)
    response    (in: rel --info, temp --relp, result --dp;
                .sup. out: temp --relp, error);
      (opt --type = GENERAL --TOTAL)
    total     (in: rel --info, temp --relp, result --dp;
              .sup. out: temp --relp, error);
    fi;
    temp --relp := temp --relp.fwdarw.next --rel;
    od;
      (error)
    skip;
    fi;
    ______________________________________

    ______________________________________
    Static Design
    procedure build --requests --table (
            in:     rel --info: rel --info --ptr,
                    cl --base: pointer to base --cluster,
                    req --table: abstract,
                    result --dp: node --id,
                    opt --type: map --optimization --choices;
            out:    final --temp: relation --name,
                    req --table: abstract,
                    error: error --code;
    );
    Permanent Data
    None
    Local Data
    None
    ______________________________________

    __________________________________________________________________________
    P-Notation
    error := FALSE;
    generate --local --requests
                   (in: rel --info, cl --base, req --table;
                   .sup. out: req --table, error);
    if (not error)
    if (opt --type = GENERAL --RESPONSE) or (GENERAL --TOTAL)
    build --rel --ops --for --schedules
                        (in: rel --info, req --table;
                        .sup. out: req --table, error);
      (opt type = IFS)
    trelp := rel --info;
    do (trelp  = NULL)
    trelp.fwdarw.final --temp --rel := trelp.fwdarw.temp --rel;
    trelp := trelp.fwdarw.next --rel;
    od;
    fi;
    if (not error)
    get --final --result
                 (in: rel --info, cl --base.fwdarw.projects, result --dp,
                 .sup. req --table; out:req --table, final --temp, error);
      (error)
    skip;
    fi;
      (error)
    skip;
    fi;
    __________________________________________________________________________

    __________________________________________________________________________
    Program Module       Action
    __________________________________________________________________________
    TIC                  parse and translate query producing one
                         cluster tree, C1
     ##STR6##
    result --ap = 4 (user site)
    opt --type = GENERAL RESPONSE
    MAP                  requests --table is initialized.
                         C1 is passed to BUILD --REQUESTS.
    BUILD --REQUESTS(1)  first child is passed to BUILD --REQUESTS.
                          ##STR7##
    BUILD -- REQUESTS(2) first child is passed to OPTIMIZE --CLUSTER
    OPTIMIZE --CLUSTER   Materialization is chosen for EMPLOYEE at site 1,
                         result --dp = site 1.
                         first child is passed to LOCAL --PROCESSING.
    LOCAL --PROCESSING   Local processing is determined:
                         All operations can be performed locally.
                         Return to OPTIMIZE --CLUSTER.
    OPTIMIZE --CLUSTER   BUILD --REQUESTS --TABLE is called.
    BUILD --REQUESTS --TABLE
                         Requests are appended to requests --table.
                         Return to OPTIMIZE --CLUSTER.
    site                 requests-table:
     1
                          ##STR8##
     1
                          ##STR9##
    OPTIMIZE --CLUSTER   Return to BUILD --REQUESTS(2).
    BUILD --REQUESTS(2)  Return to BUILD --REQUESTS(1).
    BUILD --REQUESTS(1)  Keep track of T2 at site 1 in temp-info-list.
                         second-child is passed to BUILD --REQUESTS.
                          ##STR10##
    BUILD --REQUESTS(3)  second child is passed to OPTIMIZE --CLUSTER.
    OPTIMIZE --CLUSTER   Materialization is chosen - EMPLOYEE at site 1,
                         DEPARTMENT at site 2; result-dp = site 2.
                         LOCAL --PROCESSING is called.
    LOCAL --PROCESSING   Local processing is determined.
                         Select all EMPLOYEES at site 1 and
                         select `Accounting` DEPARTMENTS at site 2,
                         Project needed attributes.
                         Affect of select and project operations on
                         size and selectivity is computed.
                         Return to OPTIMIZE --CLUSTER.
    OPTIMIZE --CLUSTER   GENERAL is called.
    GENERAL              PARALLEL and RESPONSE are called.
                         They use size and selectivity values
                         estimated in local processing to produce
                         two schedules (one for each relation).
                         Assume that the schedules are to use a semi-join to
                         reduce EMPLOYEE relation and to use
                         DEPARTMENT relation as is.
                         Return to OPTIMIZE --CLUSTER.
    __________________________________________________________________________

    ______________________________________
    DEPARTMENT: Dept. D#
    EMPLOYEE: Dept. D# EMPLOYEE
    ______________________________________
    Program
    Module            Action
    ______________________________________
    OPTIMIZE --CLUSTER
                      BUILD --REQUESTS --
                      TABLE is called.
    BUILD --REQUESTS --TABLE
                      Requests are appended to
                      requests --table.
                      Return to OPTIMIZE --
                      CLUSTER.
    ______________________________________
    Site       Requests-table:
    ______________________________________
    1          T1 <- Select EMPLOYEE where Lastname
               = `Smith`
    1          T2 <- Project T1 over Firstname, Salary
    2          T3 <- Select DEPARTMENT where Dname
               = `Accounting`
    2          T4 <- Project T3 over D#
    2          Move T4 to site 1
    1          T5 <- Select EMPLOYEE
    1          T6 <- Join T4, T5 over D#
    1          T7 <- Project T6 over Firstname,
               Salary
    1          Move T7 to site 2
    OPTIMIZE --
               Return to BUILD --REQUESTS(3)
    CLUSTER
    BUILD --   Return to BUILD --REQUESTS(1)
    REQUESTS(3)
    BUILD --   Keep track of T7 at site 2
    REQUESTS(1)
               in temp-info-list.
               PICK-DP chooses site 1 for
               union operation.
               ADD-SET-OPS adds union to
               requests --table.
               Return to: MAP.
    (new ones added)
    ADD --MOVE and ADD --PRINT are called.
    1          Move T8 to site 4
    4          print T8
    DATAFLOW is called to generate
               dataflow dependencies.
    BUILD --COMMAND --LIST formats
               the message information needed by DEM.
               Final output to DEM based on
               requests-table (logically equivalent).
    ______________________________________

    ______________________________________
            PARTS (P#, PNAME)
            SUPPLIERS (S#, SNAME)
            ON-ORDER (S#, P#, QTY)
            S-P-J (S#, P#, J#)
    ______________________________________

    ______________________________________
    Relation    Size         d(i,1)=P#
                                      d(i,2)=S#
    R(i):       S(i)    s(i,1)   p(i,1)
                                      s(i,2) p(i,2)
    ______________________________________
    R(1):
         ON-ORDER   10000   1000   0.4   500   0.3
    R(2):
         S-P-J      15000   1000   0.5  1500   0.8
    R(3):
         PARTS      20000   2000   0.7  --     --
    ______________________________________

    ______________________________________
    site request
    ______________________________________
    1    T1 <- PROJECT PARTS OVER PARTS.P#,
         PARTS.PNAME
    1    MOVE T1 TO 4
    2    T2 <- PROJECT ON-ORDER OVER ON-ORDER.S#,
         ON-ORDER.P#
    2    MOVE T2 TO 4
    3    T3 <- SELECT S-P-J WHERE S-P-J.J# = 50
    3    T4 <- PROJECT T3 OVER T3.S#, T3.P#
    3    MOVE T4 TO 4
    4    T5 <- JOIN T2, T4 WHERE T2.S# = T4.S# AND
         T2.P# = T4.P#
    4    T6 <- JOIN T5, T1 WHERE T5.P# = T1.P#
    4    RESULT <- PROJECT T6 OVER T6.P#,
         T6.PNAME, T6.S#
    ______________________________________

    ______________________________________
    Attribute    Arrival Time
    ______________________________________
    d(2,2)        990
    d(2,1)       1020
    d(3,1)       1440
    ______________________________________

    ______________________________________
    Attribute    Arrival Time
    ______________________________________
    d(1,2)        520
    d(1,1)       1020
    d(3,1)       1440
    ______________________________________

    ______________________________________
    Attribute    Arrival Time
    ______________________________________
    d(1,1)       1020
    d(2,1)       1020
    ______________________________________

• Inventors
  Dwyer, Patricia A.;
• Assignee
  Honeywell Bull, Inc. (Minneapolis, MN)
• Published
  Sep-6-1988
• Current US Classes:
  707/2
  707/9
• Application #
  706702
• International Classes
  G06F 015/16; G06F 015/40
• Field of Search
  364/200
• Examiner
  Williams, Jr.; Archie E.
• Agent
  Linnell; William A., Grayson; George, Solakian; John S.
• US Patent References:
  4430699
  4432057
  4464650
  4479196
  4497039
  4499553
  4500960
  4506326
  4513390
  4531186
  4543630
  4553222
  4604686
  4606002
  4631673
  4635189
  4644471
  4648036