THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY1 A QUERY OPTIMIZATION IN DISTRIBUTED DATABASE SYSTEMS C-W. Chung CRL-TR-4-83 Under the Direction of Professor Keki B. Irani FEBRUARY 1983 Room 1079. East Engineering Building Ann Arbor, Michigan 48109 USA Tel: (313) 763-8000 tThis research was supported by the Department of the Army, Ballistic Missile Defense Advanced Technology Center, Rome Air Development Center, and the Defense Mapping Agency under contract F30602-80-C-0173, and by the Air Force O-ffice of Scientific Research/AFSC, United States Air Force under AFOSR contract F49620-82-C-0089. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the funding agency.

LMi eA LI Ul^;ljLfJ

ABSTRACT A QUERY OPTIMIZATION IN DISTRIBUTED DATABASE SYSTEMS By Chin-Wan Chung Chairman: Professor Keki B. Irani This research is concerned with a model and a method of minimizing the inter-site data traffic incurred by a query in distributed relational database systems. In order to process a query which references data from multiple sites in a computer network, portions of the database at other sites have to be transferred to the user's site. The usual methodology for distributed query processing consists of reducing the referenced relations using a sequence of semijoin operations after initial local processing. The mathematical model has been developed to determine an optimal sequence of semijoins which minimizes the total inter-site data flow in processing a distributed query. The core of this model is a method which efficiently and accurately estimates the size of an intermediate result of a query. In particular, the assumption that joining attributes are independent during the processing of a query by a sequence of semijoins has been relaxed. ii

Since the distributed query optimization problem is known to be NP-hard, a heuristic algorithm has been developed to determine a low-cost sequence of semijoins. The efficiency of the algorithm is increased by partitioning the set of joining attributes into blocks and sequencing these blocks, as well as by a straightforward, yet effective sequencing among the semijoins between the joining attributes inside a block. The algorithm decreases the cost of a query by selecting the low-cost, highly reductive semijoins first. Cost comparisons with the existing algorithms have been provided. The time complexity of the main features of the algorithm has been analytically derived. The algorithm has been implemented in PASCAL. The tests show that the scheduling time for a sequence of semijoins for a reasonable size query is less than 0.05 seconds when the program is executed by a main-frame computer. iii

TABLE OF CONTENTS LIST OF TABLES.................. vi LIST OF FIGURES................. vii LIST OF APPENDICES............... viii NOTATIONS..................... ix CHAPTER 1. I NTRODUCT I ON................ 1 1.1 Background.............. 1 1.2 The Problem and the Approach.... 4 1.3 Literature Survey.......... 10 2. DATABASE STATE TRANSITION MODEL. 20 2.1 Query Information.......... 20 2.2 Lattice Model of the Effects of Semijoin.............. 30 2.2.1 Estimation of Effects..... 30 2.2.2 Initial Lattice......... 37 2.2.3 Expanded Sublattice...... 47 2.2.4 Expanded Lattice........ 51 3. OPTIMIZATION MODEL............. 65 3.1 Cost Reduction Model......... 65 3.2 Problem Formulation......... 74 4. DOMINANT TERM OPTIMIZATION..... 79 4.1 Efficient Use of the Lattice Model. 80 4.2 Efficient Appoximation of Equation (2.6)................. 94 5. AN OPTIMIZATION ALGORITHM......... 103 5.1 Complexity Consideration of Optimal Algorithms....... 103 5.2 A Block-Oriented Heuristic Algorithm 106 5.2.1 Process Blocks....... 108 5.2.2 Reverse Process Blocks... 113 5.2.3 Completion........... 114 5.3 Control Features......... 115 5.3.1 Initial Inactivation of Attributes...... 116 5.3.2 Path Construction.... 118 5.3.3 Hill-Climbing........ 122 5.3.4 Screening.........123 5.4 Algorithm H and Its Complexity Analysis 125 iv

6. TESTING THE SOLUTION ALGORITHM....... 128 6.1 Data Traffic Reduction........128 6.2 Efficiency of the Algorithm...... 155 7. CONCLUSION..........157 APPENDICES........... 162 BIBLIOGRAPHY.................... 172 v

LIST OF TABLES Table 4.1 Comparison of Approximations of Equation (2.6) for n = 100 and m = 30........ 98 4.2 Comparison of Approximations of Equation (2.6) for n = 1000 and m = 500....... 99 4.3 Comparison of Approximations of Equation (2.6) for n = 10000 and m = 100....... 100 4.4 Comparison of Approximations of Equation (2.6) for n = 10000 and m = 2000...... 101 5.1 The Size of the Solution Space for CASE 1.. 105 5.2 The Size of the Solution Space for CASE 2.. 106 6.1 The Sequence of Semijoins by Algorithm H and Its Effect for Hevner and Yao's Example... 136 6.2 The Sequence of Semijoins by the SDD-1 Algorithm and Its Effect for Hevner and Yao's Example................... 138 6.3 Query Costs for Hevner and Yao's Example.. 140 6.4 The Sequence of Semijoins by Algorithm H and Its Effect for the Example Given by Bernstein et al................. 146 6.5 Query Costs for the Example Given by Bernstein et al............ 147 6.6 Query Costs for Cheung's Example...... 151 6.7 Query Costs for Example 5.4......... 153 6.8 Summary of Query Cost Comparisons...... 154 6.9 Scheduling Time of a Sequence of Semijoins using Algorithm H............ 156 vi

LIST OF FIGURES Figure 2.1 The Hasse Diagram of the Initial Lattice and the Effect of Each Semijoin for Example 2.3. 46 2.2 The Hasse Diagram of the Expanded Sublattice and the Effect of a Semijoin for Example 2.4 52 2.3 The Hasse Diagram of the Initial Lattice for Example 2.5................. 59 2.4 The Hasse Diagram of the Intermediate Poset for Example 2.5............... 60 2.5 The Hasse Diagram of the Expanded Lattice and the Effect of Each Semijoin for Example 2.5. 61 4.1 The Hasse Diagram of the Expanded Lattice and the Effect of Each Semijoin for Example 4.1. 83 4.2 The Hasse Diagram of the Poset of Reachable Sets Used in Example 4.4.......... 93 4.3 The Plots of %Error Incurred by Using Equation (4.6) vs. k............ 102 6.1 The Expansions of the Lattices by the Sequence of Semijoins Generated by Algorithm H for Example 6.1........ 133 6.2 The Schedule by Hevner and Yao's Algorithm for Example 6.2.............. 142 6.3 The Serial Schedules by Cheung's Algorithm for Example 6.2.............. 143 6.4 The Expansions of the Lattices by the Sequence of Semijoins Generated by Algorithm H for Example 6.2........ 145 A.1 The Examples of Relations.......... 164 A.2 The Examples of Relational Operations.... 165 vii

LIST OF APPENDICES Appendix A. B. Some Concepts of Relational Model... Some Definitions from Lattice Theory. 163 170 vi ii

NOTATIONS A(B): The set of active attributes in block B. Ai: The initial set of values of ai after initial local processing. ai: The ith attribute in the user query. AJA = AJAi I Ai e J}. AJAj: The set of all attributes associated with aj. An+m: The reduced set for the mth expanded lattice. AB(ai): The set of associate blocks of ai. BC(k): The block cost of unvisited block Bk. bi: The benefit achieved by 0i. bij: The benefit achieved by fij. Bk: The kth block in n. c: Z X — > REAL: The cost reduction function. CA = {IKil | ai e J}. CD = {IDi I Bi e n1}. ci: The cost incurred by 0i. cij: The cost incurred by fij. C(M): The transmission cost to transfer the message of length M. nCi(= C0): The number of combinations of n objects taken i at a time. CR = {IRl I Ri e R 1. X I C: The set of elements in L covered by X. DB = <INFO, PAR>: The state of the database. Di: The domain of the attributes in block Bi. ix

di: The density of ai. dim(LI): The dimension of the initial lattice LI. DIST = <STR, STU>: The data distribution information. dN: The depth function of LN. d[x]: The depth of an element x in a lattice. dz[X]: The relative depth of an element X e L. EJA = {EJAi | Ai e J}. EJAi: The set of all attributes equivalent to ai excluding ai. END_AB: The set of end associate blocks. E[X]: The expected value of random variable X. EX: The expanded sublattice with the greatest element X. fij: The semijoin from ai to aj, where ai and aj are the joining attributes in the same block. Z Z G: The set of generators of L. IC: The initial cost of a query. INFO = <NR, NB, JR, SJR, EJA, AJA, 4>. I: The index set of a reachable set X. J: The set of joining attributes of the user query. JR: The set of all joining relations. Ki: The current set of values of ai. L: (i) The expanded lattice for block B. (ii) A lattice. L: The initial lattice for block B. 1(L): The length of a lattice L. x

LN: The new expanded lattice after the generation of EX for X e L. LZ: The LI-type lattice with the greatest element Z. M: The length of a message. NB = {Bil I Bi e 11}. ni: The net benefit of 0i. nij: The net benefit of fij. NR = {lail | Ri e R+}. Z Z O: The least element of L. PAR = <CR, CD, CA, WA> Pc (1, C): The cost function, of path r and candidate block BC, used in selecting the next block to be visited. Pn(r, C): The cost function, of path ir leading to candidate block BC, used in determining a path. Q = <T, J, R+, II, U, V>. R: The set of relations referenced by the user query. RA: The answer relation of a user query. REAL: The set of real numbers. Ri: The ith relation in R. RSk: The current set of all reachable sets for Bk. RSk: (i) The initial set of all reachable sets for k block Bk. (ii) The initial reachable sets in level k of xi

the lattice for block B. RSX: The poset corresponding to EX S = <INFO, PAR, DIST>: The state of the distributed database. s: Z X 4 — > Z: The state transition function. Si: The state of distributed database before 0i. SI(B): The sequence of inactive attributes in B. Si+1: The state of distributed database after 0i. SITE: The partition of R such that any two relations in the same block are stored at the same site. SJR: The set of all singleton joining relations. S(R): The size of a relation R. STi: The ith block in SITE. STR = {STR I Ri e R }. i STR: STj e SITE such that Ri e STj. STU: The set of relations stored at the user site. SVB: The sequence of visited blocks. T: The target list of the user query. Tij: The restricting set of Ki and K.. UB: The set of unvisited blocks. Vf: The fixed portion of the message overhead. ~N~~~~N vN: The level function of LN V: The portion of the message overhead which is proportional to the length of the message. v[x]: The level of an elements x in a lattice. VB: The set of visited blocks. xii

WA = {wi I ai e T U J}. wi: The width (in bytes) of attribute ai e T U J. IXI: The cardinality of set X. ai: The set of component attributes of relation Ri. B: The set of all blocks. ]i: (T U J) — > R is a membership function. II: The partition of J induced by the equivalence relation '=' iT: The path consisting of a sequence of semijoins. T i: The path for candidate block Bci Z: The state space of the distributed database. o: The sequence of semijoins being scheduled. u = 1 + Vp/M: The proportional coefficient. 4: The set of all possible semijoins to process a given user query. 0: An empty set. 0i: The ith semijoin in a sequence of semijoins. 3: J — > I is a partition function. R: The set intersection. X A Y: The greatest lower bound of X and Y. X v Y: The least upper bound of X and Y. xi ii

CHAPTER 1 I NTRODUCTI ON 1.1 Background In this section, we will briefly review the concept and the development of the area in which our research problem is embedded. The value and size of data in organizations have been continuously increasing in recent years. In order to provide an efficient and flexible use of data while maintaining its consistency and security, the technology of database management has been rapidly developed. A database is a collection of stored interrelated data used by the numerous application programs of any organization. In traditional file systems, each application program has its own private data files [NOLA 73]. This results in redundant storage of data, generally in different formats. The uncontrolled separate update of redundant data by each application program leads to the severe problem of data inconsistency. Also because of the lack of unity of formats, it is difficult to develop new application programs to operate against many existing data files. The purpose of the database system is to overcome the drawbacks of the file system through the integration of the organization's data so 1

2 that the stored data can be shared. An integrated database provides the organization with centralized control of its operational data. There are many advantages of having centralized control of data [DATE 77, MART 77]. A database management system is a set of generalized system software which manipulates databases and provides interfaces with a broad range of languages to aid all users. An information processing system which uses a database management system is referred to as a database system. Database systems are mainly classified into two categories: centralized database systems and distributed database systems. In a centralized database system, the whole database is stored at one computer site at which a database management system also resides. In a distributed database system, the database is scattered among the computer sites, each of which is equipped with a local database management system and supporting modules to interface with other local database management systems. A distributed database system is implemented on a computer network, that is, a set of computer sites which communicate with one another via a communication network consisting of the switching computers and the communication channels. The main characteristics of the distributed database system is that it acts conceptually as a centralized system in terms of user view and system control, while physically permitting the geographic distribution of an organization's data and accesses to them. For this reason, the distributed

3 database system is a suitable solution to the information processing problems of geographically dispersed organizations such as the military, government affiliated organizations and large corporations. The major advantages of the distributed database system over the centralized database system, in terms of applications requiring access to an integrated database from geographically dispersed locations, can be stated as follows: 1) A portion of the database is stored at or near the sites where it is frequently accessed. Consequently, the communication cost and delay are reduced. 2) Since the distributed database system is implemented on a computer network including multiple computer sites, the breakdown of some computers or a part of the communication network does not cause the total failure of the system. Therefore, the distributed database system is more reliable. 3) Evolution of one subsystem is possible without disturbing the rest of the system. Hence the expansion of the system is easier. 4) For transactions referencing data from multiple sites, intermediate processing can be performed at each site at the same time. This indicates increased parallel processing and load distribution among sites.

4 There have been a number of special purpose distributed database system implementations reported in the literature [CHAM 77]. However, there are only a few prototype systems [ROTH 80, STON 77] which can be classified as general purpose systems. No general purpose distributed database system is available because an assortment of difficult technical problems must be solved before a workable system can be produced. These problems include: 1. Database distribution, 2. Distributed query processing, 3. Distributed concurrency control, 4. Continuity of operation in the presence of failures, 5. Directory management. Research in distributed database systems has been continuing since the late 1970's. Many new results have been found. Nevertheless, none of the above problems has been completely solved. 1.2 The Problem and the Approach In this section, we will state the research problem and discuss the major issues of our approach. We will present them first in general terms and then in more specific terms. In this investigation we are concerned with developing a model and arriving at a methodology for deriving an optimal strategy for processing a distributed query. A query is a user transaction to retrieve information from the database. The user transactions in database systems are

5 queries and updates. An update is always preceded by a query to locate the necessary part to be updated. A query is called distributed if data from multiple sites is necessary to answer the query. The locations of necessary data are known to the distributed query processing routine beforehand. In order to process a distributed query, the portions of the database referenced by the query at each site have to be transferred to the user site where the final processing is performed. Distributed query processing is fundamentally different from centralized query processing in two respects: 1) The delay caused by the transfer of data among the sites involved in the query is substantial. 2) Local processing can be performed simultaneously by the computers at the sites involved in the query. The type of communication network assumed in this research is the point-to-point packet switching network which uses ground lines as communication channels. In a packet switching network, the delay due to transmission of a fair amount of data between source and destination is proportional to the volume of the data [KLEI 76]. It was observed by [WONG 77] for the Arpanet that the data transfer rate between sites is some 100 times slower than the transfer rate between disk and main memory in typical largescale computers. Consequently, the minimization of the inter-site data transfer is of primary importance in processing the distributed query. The efficiency of a

6 strategy for distributed query processing is mainly determined by the way the inter-site data transfer is handled. As illustrated in [ROTH 77], there is enormous variation in communication delay among a set of plausible distributed query processing schemes. A relational model [CODD 70] is assumed to be the underlying data model. A relational model represents data logically and can be used as a conceptual framework for other data models. Some basic concepts of the relational model are presented in Appendix A. In order to describe the problem more precisely, the terminology of the relational model will be used. We assume that a relation is a unit of distribution. A relation may be further partitioned into smaller units by performing selection and/or projection on it to increase flexibility. The original relation can be recovered by joining the smaller relations. This extension to relations partitioned among many sites is straightforward [DAYA 79]. We will only consider the conjunctive queries. For a non-conjunctive query, the qualification clause can be transformed into a disjunctive normal form and the query can be decomposed into conjunctive queries. The answer to the complete query then is the union of the partial answers obtained for each conjunctive query. Since selection and projection are the unary operations, they are always performed locally. Join can also be performed locally if the relations involved in the join are stored at the same site. Hence a query which does

7 not require a join of the relations stored at different sites can be decomposed into local queries. Such a query need not be considered a distributed query even if the query references relations from multiple sites. Definition 1.1: A query is distributed if its qualification clause contains at least one join term which includes relations stored at different sites. For any distributed query, initial local processing is mandatory to reduce the amount of data to be transferred locally. Initial local processings are performed in parallel at the sites containing the relations referenced by the query. Large portions of referenced relations are reduced by initial local processing for most of the distributed queries. A crude way of processing a distributed query may be to transfer all the remaining portions of relations after initial local processing to the user site. Another possibility is to transfer relations involved in joins to other sites to enable local joins. Among many alternatives, the data reduction strategy we will attempt to model is based on the properties of the semijoin. Suppose a distributed query contains a join term R.A = S.B where R and S are located at different sites. The semijoin (Appendix A) has the following properties [BERN 79]: (1) R[A=B]S = (R<A=B]S)[A=B]S (2) R<A=B]S c R

8 (3) R<A=B]S = R<A=B](S[B]) From (1), the join term can be processed with R<A=B]S instead of R. From (2), R<A=B]S is smaller in size than R. From (3), to perform R<A=B]S at the site of R, only S[B] is needed to be transferred instead of S itself from the site of S to the site of R. Hence if j|R - R<A=B]S I > IS[B]II, where IIRI denotes the size of a relation R, then the transfer of S[B] contributes to the reduction of the total amount of data transfer without affecting the final query answer. After R is reduced to R<A=B]S, (R<A=B]S)[A] can also be sent to reduce S. Basically the distributed query processing strategy after initial local processing is a sequence of semijoins which consists of a set of inter-site data moves combined with local processings between the data moves. When the relations at each site cannot be further reduced, the remaining relations are transferred to the user site, where the final processing of the query is performed. We assume that the delay caused by the local processing between inter-site data moves is constant compared with the great variation of the communication delay. This is especially valid when the data manipulation operations are performed by database machines because the processing time of operations is less dependent on the size of the operands and much shorter than when general purpose computers are used. Also the fact that the computing cost is reducing at a faster rate than the communication cost indicates that the communication delay will become the more dominant term in

9 the future. In summary, our approach is to find a sequence of semijoins which minimizes the total amount of inter-site data communication necessary in transferring the data to the user site for the final processing. In addition to the operational importance to the distributed database system, distributed query processing is crucial for the optimization of database distribution which is known as the problem of file allocation. The file allocation problem has to assume a certain distributed query processing method to formulate the communication cost in terms of file allocation variables. If the distributed query processing transfers all the remaining portions of relations, after initial local processing, to the user site, the formulation is straightforward. However, the resultant file allocation may be far from optimal. If the distributed query processing uses semijoins, the effect of semijoins on the communication cost has to be considered for an optimal allocation. Even if the data flow generated by semijoins for each pair of relations before the allocation are given as input, the contribution of semijoins to the communication cost cannot be formulated using only file allocation variables. One of the reasons is that when two relations are clustered at the same site, not only the semijoin between them vanishes but also the data flow generated by semijoins between each of these two relations and the rest of the relations change in a complex way. Hence the choice

10 of a good distributed query processing strategy and the successful modeling of its features are essential for realistic optimal database distribution. 1.3 Literature Survey The purpose of this section is to review the published results of related work by others and to analyze their inadequacies. The primitive concept of distributed query processing appeared in the context of file allocation problems. As mentioned before, every file allocation model has to use some type of distributed query processing method. In traditional file allocation models [CASE 72, CASE 73, CHU 69, IRAN 82, LEVI 75, MAHM 76], the derivation of the communication cost is based on the amount of data flow from each site to each file. This implies either that there is no distributed query, or that distributed queries are processed at the point where the query originates with all the necessary data moved to that point possibly after some degree of local processing. This type of distributed query processing incurs large volumes of unnecessary inter-site data traffic which can be screened out by using semijoins or local joins. Among the file allocation models, [RAMA 79] introduced a somewhat different distributed query processing method to reduce inter-site data transfer. A technique was proposed to add redundant information onto the distributed database

11 so that distributed queries can be decomposed into local queries. The redundant information is an extra bit for each tuple indicating whether the tuple will participate in processing some specific join term. Hence if the relations in the join term are located at different sites, the necessary tuples in each relation can be selected by checking the extra bits without moving one relation to the site of the other. This approach often requires a great deal of system overhead to maintain redundant information in accordance with the update of the database. From a distributed query processing point of view, the impact of initial local processing in reducing the amount of intersite data traffic is not properly reflected. The use of semijoins can further decrease the amount of data transfer. The earliest work reported in the area of distributed query processing as an independent subject was in [WONG 77]. Since then, numerous strategies have been developed for distributed query processing. We will review some of the more important ones. Among the distributed query processing algorithms reported in the literature, [WONG 77] was the first one to consider communication delay as a key element of query processing cost. Communication delay depends on the quantity of data transferred between sites. Thus the minimization of data transferred is the primary objective in optimization though not the only one. The concept of query decomposition in [WONG 76] is adapted to reduce a

12 distributed query to a series of local queries. A basic tactic proposed in [WONG 76], to decompose a query which references many relations into a set of queries referencing only one relation, is tuple substitution. Tuple substitution is a procedure by which one of the relations in a join term is successively replaced by the actual tuples. Tuple substitution for a distributed query implies the transfer of data, one tuple at a time, between sites. However, bulk transfer of data is more efficient than tupleat-a-time transfer because of the overhead per message. Hence a distributed query is transformed into local queries by moving subrelations. The initial solution for this strategy is to transfer all the remaining relations referenced by the query to a single site after the initial local processing. An improved solution is a set of costeffective subrelation moves among sites followed by local processings. The optimization procedure is applied recursively until no improvement is gained. Since the algorithm looks for an immediate improvement, it is classified as a greedy one and terminates at a local optimum. It is necessary to estimate the sizes of the relations resulting from local operations in order to determine the cost-effectiveness of subrelation moves. This problem was left unsolved. Moreover, the move of a subrelation is less effective than the semijoin in reducing the inter-site data transfer because the semijoin only requires transmission of values of the joining attributes.

13 The approach in [EPST 78] is basically the same as the one in [WONG 77]. The following modifications were made on the framework established in [WONG 77]: (1) each relation may be at a unique site or may be spread over several sites in a computer network; (2) the cost criteria considered are minimum response time and minimum communication traffic; (3) the algorithm treats point-to-point and broadcast networks separately. Some of the rules to determine the values of the variables are based on heuristics rather than wellgrounded analysis. The basis of the model developed in [CHU 79, CHU 82] is also the reduction of inter-site data transfer by using the transmission of subrelations. A query operation graph was defined, in which a node represents a subset of the sequence of operations that must be executed at the same site and arcs represent data transmissions between sites. Given a query, the set of query operation graphs which represent the sequence of operations is constructed. To determine a query processing policy, it is necessary to select a site for performing the operations represented by each node. Theorems were developed to find the best sites for performing the operations of a given graph. A linear operating cost function was derived to compute the cost of a processing policy represented by each query operation graph. The major considerations of the proposed operating cost model are communication cost, processing cost, and data reduction functions for processing a query for a given

14 environment. Data reduction functions describe the volume of output data in relation to the volume of input data for performing a specific operation. The operating cost function assumes the values of many parameters as given. Data reduction functions are key elements which make the distributed query optimization problem difficult. However, they are assumed to be estimated by simulation or measurement on the actual distributed database. [HEVN 78] developed an optimal processing algorithm for a narrow class of distributed queries called simple queries. A simple query was defined as one by which, after initial local processing, each relation that is referenced contains only one attribute - a common joining attribute, which is also the only attribute in the target list. Hence the subrelation move in this case is the move of current values of the common joining attribute for each relation. Although the class of queries considered is so narrow that the algorithm is of little practical value, this strategy introduced the concept of the semijoin. The result of [HEVN 78] was extended for general distributed queries by the same authors [HEVN 79b]. The semijoin is used as a major tactic to reduce inter-site data transmission. The general algorithm is heuristic and uses an improved exhaustive search. Two cost measures, response time and total time, were used. The data transmission pattern containing the transmission of a relation to the result node is called the schedule for the relation. Each

15 joining attribute in a relation is handled separately. The schedule for a joining attribute is a sequence of semijoins. The minimal cost schedule for each joining attribute is selected from a set of cost beneficial schedules. However, the algorithm maintains other cost beneficial schedules since they may lead to more beneficial cost reductions on other attribute schedules. When the minimal time schedules are found for each joining attribute, the algorithm integrates these schedules into the overall schedule for the relation. The query processing strategy is then constructed by synchronizing the schedules of all referenced relations in the query. Schedules to minimize response time include as much parallelism of data transmission as possible. This parallelism is not taken into consideration in the schedules for the minimization of the total time. It was emphasized that the consideration of parallel transmissions to minimize the response time increases the complexity of the algorithm by a significant amount while the reduction in schedule response time is limited in almost all cases. The time complexity analysis of the algorithm was carried out only for total time minimization. The major weakness of the strategy presented here comes from the assumption that joining attributes within each relation are independent. Thus a reduction of values of a joining attribute by the semijoin does not reduce the values of other joining attributes in the same relation under this assumption. This assumption simplifies the problem in many respects. For

16 example, each joining attribute in a relation can be handled separately, due to attribute independence. In reality, this assumption is clearly not true. Consequently, the validity of the query processing strategy is seriously affected by this assumption. Another shortcoming is that the schedule of each relation is separately constructed and these schedules are not integrated. As a result, if an optimal strategy contains non-cost-beneficial schedules for some relation, such an optimal schedule can not be found. An improvement over [HEVN 79b] was suggested in [CCA 80b]. The assumption of attribute independence is partially relaxed. Attributes in the same relation are considered to be dependent. However, attributes in different relations are assumed to be independent throughout the processing of a query. The objective is to process the distributed query with a minimum quantity of inter-site data transfer. That is, network bandwidth is regarded as the system bottleneck, and the optimization objective is to minimize the use of this resource. The semijoin is extensively used to reduce the inter-site data transfer. The proposed algorithm is a greedy optimization algorithm whose main function is to construct a profitable sequence of semijoins. Starting with a null sequence, the algorithm iteratively appends the cheapest profitable semijoins to the sequence until all such semijoins have been used. Then the algorithm determines the cheapest site at which to assemble the remaining relations, and appends commands to move the

17 remaining relations to that site. Techniques for improving the generated sequence were presented to help compensate for the short-sightedness of the greedy algorithm. While the consideration of attribute dependence is essential to the development of a realistic distributed query processing strategy, it substantially increases the complexity of the problem. The effects of the attribute dependence were not completely modeled in this work. The estimation of the reduction of relations by arbitrary semijoins is particularly important, but was not considered. Consequently, the reduction of relations due to an arbitrary sequence of semijoins can not be estimated accurately. Hence the class of sequence of semijoins allowed is very limited. The restriction of the solution space has a significant impact on the development of the algorithm. The reoccurrences of a semijoin are not allowed in the greedy algorithm. The assembly site is used because the relations are not completely reduced by all possible semijoins. The extra cost of sending the result from the assembly site to the query origin is generally substantial compared with the cost of sending the completely reduced relations directly to the query origin. The second pass enhancement is necessary to compensate for the deficiencies caused by the greedy nature of the algorithm and the use of an assembly site. An improved version of the algorithm in [CCA 80b] was reported in [BERN 81]. Specifically, the, following improvements were made: (1) the assumption that the

18 attributes in different relations are independent is relaxed; (2) the reoccurrences of a semijoin are allowed in the modified greedy algorithm which appends the most profitable semijoin to the sequence. The shortcomings of the algorithm in [BERN 81] are as follows: (1) the estimation method of the intermediate result size involves a complex graph search; (2) when the assembly site and the user site are different, the cost of moving the assembled answer to the user site was not considered; (3) both reported enhancements sometimes require significant computation. Another improvement of the method presented in [HEVN 79b] was made in [CHEU 82]. A general query is decomposed into simple queries, the number of which is equal to the number of domains associated with the general query. To minimize the total time, a sequence of semijoins is scheduled by applying STRATEGY SERIAL [HEVN 79b] for each simple query. The remaining relations, except those which do not contain any target list and are involved in only one of the equijoin clauses of the given query, are transferred to the user site. This method also assumes that the joining attributes within each relation are independent. All the distributed query processing strategies we have discussed assumed knowledge of the necessary data locations to be accessed. Query processing experiments on a distributed database were reported in [EPST 80]. The strategies were compared by

19 simulation on the basis of number of bytes moved. The conclusions were: (1) limited search performs very poorly compared with exhaustive search; (2) good intermediate size estimates are crucial; (3) dynamic decision making consistently performs better than static decision making; however, because dynamic decision making has a greater runtime cost, it may not be a big winner.

CHAPTER 2 DATABASE STATE TRANSITION MODEL In this chapter, we present a mathematical model for database state transition which allows us to estimate the change in database parameter values for any possible sequence of semijoins to process a given distributed query. This model will be used as a basis for developing a query optimization model in the next chapter. The database state transition model includes two components described in set-theoretic terms. These components are: (1) Information from the user query, (2) The effect of the semijoin on the database. The database state transition model can be considered a function which determines the next state of the database given the current database state and a semijoin. The initial set of all possible semijoins is derived from the user query. 2.1 Query Information In this section, the query is formally defined. From the query definition, the necessary information is derived and the parameters to describe the database are defined. 20

21 The original user query is reduced after initial local processing has been performed. During the initial local processing, all the selection terms and the join terms whose relations are stored at the same site are processed. Also the columns of the attributes which are neither in the target list nor in the remaining join terms are eliminated by projections. As a result, the reduced query contains relations and attributes which are necessary to further process the query. Some of the relations referenced by the reduced query may have been created by local joins. Hereafter, the term "query" will represent the reduced query which necessitates distributed query processing. The attributes are differenciated whenever they are used in different relations. In other words, if an attribute A is used both in relations R and S, R.A and S.A are considered different attributes, since R.A and S.A represent different sets of values. Definition 2.1: A query Q is an ordered six-tuple Q = < T, J, R, I, i, ~ > where T is the target list of the user query, J is the set of joining attributes of the user query, R is the set of relations referenced by the user query, n1 is the partition of J induced by the equivalence relation '=' i: (T U J) -- R+ is a membership function, and 4: J — > n is a partition function.

22 Since an attribute in the target list can also appear in a joining term, T Q J, where 2f denotes the set intersection, may not be empty. T U J is a set of all attributes referenced by the query Q. The membership function Vi specifies the relation to which each attribute belongs. The partition II is a set of blocks. II = {B1, B2,..., Bn} Here Bk 6 n is an equivalence class under equality. Therefore for any attributes ai,aj e Bk, ai = aj. Suppose u(ai)=Ri and ](aj)=Rj for Ri, Rj e R. Since all the local joins were performed during initial local processing, Ri and Rj are necessarily stored at different sites. Consequently a semijoin is possible between any pair of joining attributes in Bk e n for k=1, 2,..., n. The partition function * indicates the block to which a joining attribute belongs. It is clear that the attributes in each block have a common domain. Example 2.1 illustrates how to formulate a query information model. Example 2.1 The following relations are stored in a hypothetical distributed database. DEPARTMENT (D#, DNAME, COLLEGE) COURSE (C#, CNAME, SUBJECT) STUDENT (S#, SNAME, YEAR)

23 OFFER (D#, C#, TERM) ELECTION (C#, S#, GRADE) Consider the following user query. "Find the names of the computer courses offered by the departments in the college of engineering during the fall term of 1980 in which a senior student received an A grade with the corresponding names of the senior students" The user query in relational form is: F I ND (COURSE.CNAME, STUDENT.SNAME) WHERE (DEPARTMENT.D# = OFFER.D#) AND (DEPARTMENT.COLLEGE = 'Engineering') AND (OFFER.TERM = 'Fall 1980') AND (OFFER.C# = COURSE.C#) AND (COURSE.SUBJECT = 'Computer') AND (COURSE.C# = ELECTION.C#) AND (ELECTION.S# = STUDENT.S#) AND (ELECTION.GRADE = 'A') AND (STUDENT.YEAR = 'Senior') Suppose the relations selected to process the above user query are all stored at different sites. The relations and the user query are reduced by the initial local processing as follows. Reduced relations: DEPARTMENT (D#)

24 COURSE (C#, CNAME) STUDENT (S#, SNAME) OFFER (D#, C#) ELECTION (C#, S#) Reduced query: F I ND (COURSE. CNAME, STUDENT. SNAME) WHERE (DEPARTMENT.D# = OFFER.D#) AND (OFFER.C# = COURSE.C#) AND (COURSE.C# = ELECTION.C#) AND (ELECTION.S# = STUDENT.S#) Now we formulate the query information model of the reduced query. Let al = DEPARTMENT.D# a2 = COURSE.C# a3 = COURSE.CNAME a4 = STUDENT.S# a5 = STUDENT.SNAME a6 = OFFER.D# a7 = OFFER.C# a8 = ELECTION.C# a9 = ELECTION.S# R = DEPARTMENT R2 = COURSE R3 = STUDENT R4 = OFFER R5 = ELECTION

25 Then Q = < T, T = {a3, J = {a 1 R ={R1' n = {B1' I = {<a1 <a2 <a4 <a6 <a8 * = {<a1 <a2 <a4 + J, R, nl, ], p > a5} a2' a4 6 a6 a7, R2, R3, R4, R51 B2, B3, R2>2 R2>, <a3, R2>' R3>, <a5, R3>,, R4>, <a7, R4>,, R5>, <a9, R5>}, B>, <a6, B1>,, B2>, <a7, B2>,, B3>, <ag, B3>} a8, a9 <a8, B2>,. Definition 2.2: Attributes ai and aj are equivalent if ai, aj e Bk for some Bk e II. EJAi is the set of all attributes equivalent to ai excluding ai. Since *(ai) is the block in which ai is included, EJAi = (ai)-{ai} for all ai e J. We define the following parameters: (1) ai = the set of component attributes of relation Ri (2) IXI = the cardinality of a set X (3) Di = the domain of the attributes in block Bi (4) Ki = the current set of values of joining attribute ai (5) Ai = the initial set of values of ai after initial local processing (6) w. = the width (in bytes) of attribute ai e T U J

26 (7)fij = the semijoin from ai to aj, where ai and aj are the joining attributes in the same block Consider equivalent joining attributes ai and aj. Suppose i(aj)=Rj. The semijoin fij reduces IKjl. As a result, IRjl is decreased. From the attribute dependence, IKkl is reduced for all k such that akeJ and i(ak)=Rj. Definition 2.3: Two attributes aj and ak are associated with each other if aj, ak e J and ](aj)=](ak). AJAj is the set of all attributes associated with aj. It is assumed that the query being considered is not decomposable further into simpler queries. That is, for each block, there is an attribute which is associated with an attribute in another block. The set of values of a joining attribute ai necessary to process a query is completely included in the relation containing aj after a semijoin fij. As a result, if the relation containing ai does not contain any attribute in the target list, the set of values of ai can be ignored after fij in some cases which will be explained in detail in Section 3.1. This is always true when a relation consists of only one joining attribute. We want to distinguish these relations. Definition 2.4: A relation Ri is a joining relation if a e J for all a e ai. JR is the set of all joining relations. Ri is a singleton joining relation if R.e JR and 1 1

27 a-il=1. SJR is the set of all singleton joining relations. Let 4 be the set of all possible semijoins to process a given user query. 4 is initially obtained from Q by identifying equivalent joining attributes. = {fij I aiaj e Bk and Bk e n} The query information model Q determines most of the parameters which describe the portion of database necessary to process the user query. Furthermore, the initial values of some of the parameters are provided by Q. Such a set of parameters is defined separately and called INFO. INFO = < NR, NB JR, JRR,, EJA, AJA, 4 > WHERE NR = {lil I Ri e R+}, NB = {Bil I Bi e n}, EJA = {EJAi | Ai e J, AJA = {AJAi | Ai e J}, and JR, SJR, q are defined as before. Example 2.2 shows the derivation of the initial value of INFO from Q. Example 2.2 Consider Q formulated in Example 2.1. The initial value of INFO = < NR, NB, JR, SJR, EJA, AJA, $ > is derived from Q. (1) NR = l{al I i = 1, 2, 3, 4, 5} |all = 1, 1a21 = 2, la31 = 2, lal4 = 2, 1a51 = 2

28 (2) NB = iIBil I i = 1, 2, 3} IB1 = 2, |B21 = 3, IB3j = 2 (3) JR = {R1, R4, R5} (4) SJR = {R11 (5) EJA = {EJAi I i = 1, 2, 4, 6, 7, 8, 9} EJA1 = a6, EJA2 = {a7, a8}, EJA4 = {a91, EJA6 = {a1}, EJA7 = Ia2, a8}, EJA8 = {a2, a7}, EJA9 = {a4} (6) AJA = {AJAi I i = 1, 2, 4, 6, 7, 8, 9} AJA1 = 0, where 0 denotes an empty set, AJA2 = 0, AJA4 = 0, AJA6 = {a7}, AJA7 = {a6}, AJA8 = {a9}, AJA9 = {a8} (7) = {f 16 f61' f27' f72' 28' f82' f78' f87' f49' f94} The initial values of the rest of the parameters can not be derived from Q. This set of parameters is called PAR. PAR = < CR, CD, CA, WA > where CR = { IRi I Ri e R+, CD = {IDi I Bi e n}, CA = {Kil I ai e J}, and WA = {i ai T U J}. There are basically two approaches to determine the

29 initial value of PAR. One way is to use estimation. In a database system, the data directory maintains necessary system informations and periodically updates them. By estimating the effect of initial local processing on the value of PAR obtained from the data directory, the initial value is determined. The other way is to get the actual value of PAR after initial local processing from the sites involved in handling the query. Although estimation is a simpler way, there are many advantages of using the actual value. Since large portions of referenced relations are reduced by initial local processing, the accuracy of the value of PAR after initial local processing is important for accurate estimation of the effects of subsequent semijoins. Also it sometimes happens that users issue queries without being certain of the existence of tuples satisfying the qualification clause. In this case, if any of the results of terms locally processed is null then the final answer to the query must be null. Consequently no further processing of the query is necessary. These observations are consistent with the conclusion derived in [EPST 80] in favor of dynamic decision making. While dynamic decision making for the entire processing of a query is not practical because of great run-time delay, the delay of the initial dynamic decision is preferable to the inaccuracy of the initial value of PAR. Since initial local processing is performed simultaneously at multiple sites and

30 the counting on the partial results can be done at the same time, the delay caused by initial dynamic decision is not significant either. The values of CD and WA are static, so they can be obtained from the data directory without the need of further manipulation. The initial values of CR and CA are obtained using either approach discussed above. We define the state DB of the database as follows: DB = < INFO, PAR > 2.2 Lattice Model of the Effects of Semijoin In this section, we discuss a method of estimating the effect of semijoins on the database which involves probabilistic analysis. Based on this analysis, a very general model is developed using a lattice which represents the reduction of the set of values of a joining attribute by an arbitrary sequence of semijoins. 2.2.1 Estimation of Effects In this subsection, an estimation method is presented to determine the change of values of parameters describing database. The basic assumptions are stated and formulas are derived. We have completely relaxed the assumption of attribute independence in the process of a sequence of semijoins. The use of conditional probability to handle attribute dependence has not been considered in past research.

31 Our strategy for distributed query processing is to construct a sequence of semijoins which minimizes the total amount of data communication. In order to determine the contribution of a member semijoin to the total data flow of the sequence, we must know the volume of data flow involved in the semijoin and the amount of data reduced by the semijoin. The values of the database state before and after the semijoin are sufficient to determine these. Since we start from a given initial database state, our problem is to estimate the next database state induced by a semijoin given the current database state. Note that the actual database is not affected by any semijoin. Temporary copies of referenced relations are retained after initial local processing and then the query is processed on the temporary copies. The change of the INFO value is deterministic. It can be simply determined by inspecting the current value of INFO and the semijoin to be used. Since it does not require estimation and is more closely related to the optimization model, we will discuss it in the next chapter. Among the elements in PAR, the values of CD and WA are static during a certain period. So they are not affected by a semijoin. The most important and difficult problem is the estimation of values of CR and CA, which are indispensable for the determination of the size of the intermediate result. The estimation of the size of the intermediate result is crucial for the optimization of query processing

32 in centralized as well as distributed database systems. We discuss a method of estimating the cardinality of a relation reduced by a semijoin. Consider a relation Rg and its attribute aj such that IKjl = m. Define a counting random variable Xi for each vi e Kj which counts the number of tuples in R in which the 3 9 value of aj is vi. Then for each Xi, possible values are 1, 2,..., |Rgl-m+1 and i=1 Xi = |Rg'. Assuming that Xi's are identically distributed, E[m=1 X] = =1 E[Xi] = mE[Xi] = |RgI where E[X] denotes the expected value of X. Hence E[Xi] = IRg9I/KjI for all vi e Kj (2.1) If a semijoin changes the value of a variable, we will append 'N' to the name of the variable to designate the new value. After applying a semijoin fij, R and Kj are reduced to RgN and KjN, respectively. Since |R9N| = v.eK. X from (2.1), IRgNI = E[Ev.iKjN Xi] EvieKjN E[Xi = IKjNI x E[Xi] = IKjNI x IRg9 / IKjl (2.2) Therefore, if we know IKjNI for some aj which is an attribute of Rg, then we can. compute |R9N|. Hence we

33 investigate the reductions in Kj's caused by semijoins. There are two different ways by which a Kj can be reduced: (1) By a semijoin from the equivalent joining attribute of aj.: If attributes ai and aj are in a block, a semijoin fij reduces Kj to a new set KiKj, where KiKj denotes K iKj, the intersection of Ki and Kj. (2) By a semijoin to an attribute associated with aj: If aj and as are the attributes in the same relation, they are in different blocks. The reduction of Ks by the semijoin f rs, where ar is in the same block as as, also reduces Kj. First, we discuss the estimation of IKjNI due to a semijoin fij' Suppose Bk = {al,..., ai, aj,..., an } Consider fij as the first element in a sequence of semijoins to process a query. If Dk is perceived to be the sample space, any X c Dk is the probabilistic event that v e X for v e Dk. Initially Kh = Ah for all ah e Bk, and the only restriction on Ah's is that they be subsets of Dk. Therefore the events Ah's are mutually independent events. After fij, KjN = AiAj. From P(AiAj) = P(Ai)P(Aj), IKjNI/IDk| = (IKi/IDDkI) x (IKj |/DkI) which reduces to IKjNI = IKi x IKjl / IDkl (2.3)

34 This result, obtained differently, was used in [CCA 80b]. A new procedure must be established to derive the correct estimation of IKjNI or IKiNI for a subsequent fij or fji, respectively. The reason is that Kj is a subset of Ki as a result of the first fij. This implies that a dependence between the events Ki and Kj is created as a consequence of the initial fij. Initially Ki and Kj are independent and the only restriction is that they are both contained in Dk. As a query is processed, more restrictions are added on Ki and Kj by themselves or through some other subset of Dk. We want to characterize the set which imposes a restriction on Ki and Kj in estimating the effect of fij or fji. We generalize (2.3) by using conditional -probability. The dependence formed by a semijoin comes from the containment relation among the value sets of joining attributes in the same block. However, not all the subsets of Dk represent the set of values of some ai e Bk during query processing. Unless a set can be generated by applying a sequence of semijoins to Ai for some ai e Bk, the identity of the set is not known. Let 0i be the ith semijoin in a sequence of semijoins. Definition 2.5: For a block Bk = {a,..., an}, let H be a proper subset of Dk. Consider a sequence of semijoins Sm = 1' 02 **t' 0m. H is a reachable set for Bk after 0m if there exists a concatenation V, W of two sequences of semijoins, V and W, where: (i) V is a subsequence of Sm;

35 (ii) any semijoin in W is between the attributes in Bk; and (iii) the sequence V, W reduces Ai to H for some ai e Bk. When a query is partially processed after a sequence S, the current set of all reachable sets for Bk, denoted by RSk, is defined to be the set containing Dk and all reachable sets for Bk after Sm. Since Sm is a special case of the sequence V, W, every Ki is an element of RSk. Sm is a null sequence after initial local processing. In this case, V, W = W, and the current set of all reachable sets for Bk is called the initial set of all reachable sets for Bk, and is denoted by RSk. Consider a set K e RSk which is the smallest set containing both Ki and Kj. The only information available for Ki, Kj and K is that the values of Ki and Kj are distributed in the set of values K. Hence the knowledge that the event Kj has occurred does not affect the probability of occurrence of the event Ki when the effective sample space is reduced to the event K. That is P(KIK jK) = P(KilK) Multiplying both sides by P(Kj|K) gives P(KiKjlK) = P(KijK) P(Kj K) (2.4) Hence the events Ki and Kj are conditionally independent given the event K. Note that conditional independence does not imply independence. For any K' e RSk such that K c K'

36 P(Ki.KjK') = P(KijKjK) = P(KiIK) > P(KijK') Hence the events Ki and Kj are conditionally dependent given the event K'. By using Definition 2.5, we formally define the restricting set. Definition 2.6: Let aiaj e Bk for some Bk e II. The restricting set of K. and K. is the smallest set in RSk that is a superset of both Ki and Kj. For example, initially Ki = Ai and Kj = Aj. The restricting set of Ki and Kj is Dk. After fij, Kj c Ki. Hence Ki is the restricting set of Ki and Kj. The estimation of IKjNI after a semijoin fij as an element in an arbitrary position in a sequence of semijoins is as follows: P(KiKj) = P(KiKjlK)P(K) + P(KiKjlK)P(K) Since KiKjK = 0 because KiKj c K, we have IKiKjl/IDkI - P(KiKjlK)(IKI/IDkl) Multiplying both sides by IDkl and using (2.4) gives IKiKj = IKIP(KiIK)P(KjIK) = IKil x IKjl / KI Hence IKjNI = IKij x Kjl / |K| (2.5) Initially the restricting set is Dk for any Ki and Kj. In this case, (2.5) is reduced to (2.3). In order to evaluate

37 (2.5), it is necessary to develop a method to calculate the cardinality of the restricting set of Ki and Kj at any point in the sequence of semijoins. This will be discussed in the subsequent subsections. Next we consider the change in the cardinality of the set of values of a joining attribute aj by a semijoin frs which goes to an attribute as associated with aj. This change is caused by the dependence among associated joining attributes. We consider the dependence among associated joining attributes in set level. In other words, associated joining attributes aj and as are dependent in the sense that the change of IKjl depends on the change of IKSl, and vice versa. For cardinality estimation purposes, it is proper to handle the attribute dependence in set level. To estimate IKjN| due to a semijoin frs' where ar is in the same block as as, and aj and as are the attributes in the same relation Rg, a solution to the problem considered by Yao [YAO 77] is used. This reduction was ignored in most of the previous semijoin strategies. It was first observed in [CCA 80b] that Yao's solution is applicable for the estimation of IKjNI. IRgNI due to a semijoin frs can be computed using (2.2) and (2.5). Suppose IRgI = n, IKjl = m and IRgNI = k. Then IKjNI after a semijoin frs is given by: m x [1 - nk=1{(nx(-1/m) - i + 1)/(n - i + 1)}] (2.6) i1 2.2.2 Initial Lattice

38 In this subsection, we show that the set RSk forms a lattice. This, we show by generating the elements of RSk in a step by step manner. The lattice (RS,, c) is called an initial lattice and it will be used as a building block to generate a lattice for more general cases. Consider Bk = {al, a2,..., an. As the dependence among attributes in Bk is formed by a sequence of semijoins, the pairwise relationship of the sets in {Ki | ai e Bk} plays an important role in parameter estimation. Because of the probabilistic nature of estimation, at any instance during the query processing, KiKj ~ 0 for any ai,aj e Bk. At some point in the process of a sequence of semijoins, there are four difference cases: (1) Ki = Kj (2) Ki c Kj (3) Kj c Ki (4) Ki ~ Kj and Kj f Ki Let Tij be the restricting set of Ki and Kj. We have the following equivalences: (a) K = Kj iff Tij = Ki = Kj (b) Ki c Kj iff Tij = Kj (c) Kj c Kj iff Tij = Ki (d) Ki f Kj and Kj ~ Ki iff Tij ~ Ki and Tij I Kj Hence the relationship between Ki and Kj can be determined from the knowledge of Tij. Consequently, it is sufficient to develop a model from which we can find the restricting set of Ki and Kj at any point in the sequence of semijoins.

39 Since the characteristic of the model is common to each block Bk e In, we will drop the block index for the rest of this chapter for simplicity unless it is necessary. For example, B denotes a block, RS denotes the set of all reachable sets for B, and so on. Without loss of generality, let B = {al, a2, '... an } Ai is the set of values of ai after initial local processing. fij reduces Kj and generates a new set KjN. Since KjN = {v e Kj | v e Ki}, KjN = KiK. From the remark after Definition 2.5 concerning RS, we observe that for any X e RS, X can be reached from Ai for ai e B after a sequence of semijoins each of which is between the attributes of B. Hence for any X e RSI, X = QieIAi where I c {1, 2,..., n}. We will discuss later the dynamic change of RS. This is caused by the generation of new sets which cannot be represented by the intersection of sets in { Ai ai e B}. Let RS1 = {Ai | ai e B}, i.e. RSI = {A1, A2,..., An The elements in RS1 are pairwise incomparable sets with respect to the set-inclusion relation. The set RSI is generated by intersecting i sets in RS; at a time for i = 1, 2,..., n. Let nCi denote the number of combinations of n objects taken i at a time. There are Ci elements in RSIi RS2 = {A1A2, A1A3,, An-1 n

40 RS =AA A RSn 1A 2... An Let RS0 = {D}. Then RS = Un RSI i=0 i In developing a lattice model, we try to use the standard terminologies and notations from the existing lattice theory. Some definitions used in lattice theory are presented in Appendix B. If new concepts are introduced or it is necessary to modify the existing definition because of the particular structure of our model, separate definitions will be given. In a lattice, g.l.b.{X,Y} is denoted by X A Y, and l.u.b.{X,Y} is denoted by X v Y. We will show that (RSI, c) is a lattice. Let X, Y and Z be the elements in RSI. Define g.l.b.{X,Y} = XY, l.u.b.{X,Y} = minimum{Z e RSI X c Z and Y c Z} It was proved as a theorem in [BIRK 67] that any family of subsets of a set which is closed under intersection forms a lattice under set-inclusion by taking the g.l.b. of two sets as the intersection of the two sets and the l.u.b. of two sets as the smallest set in the family which contains the union of the two sets. It follows that (RSI, c) is a lattice. From the above discussion, we state the theorem which relates the lattice theory and query processing in database systems.

41 Theorem 2.1: Given a block B e n, the initial set of all reachable sets RSI forms a lattice under set-inclusion with g.l.b.{X,Y} = XY and l.u.b.{X,Y} = minimum{Z e RSI | X c Z and Y c Z} for any X,Y e RSI. In estimating the effect of fij or fji for ai,aj e B, the restricting set is l.u.b.{Ki, Kj} and the reduced set is g.l.b.{Ki, Kj}. The initial lattice (RS, c) is denoted by LI. The greatest element of L is D, the domain of the attributes in the block. Since a block is finite and nonempty, the lattice which models our problem is also finite and nonempty. The structure of the initial lattice and the expanded sublattice, which will be discussed in the next subsection, are exactly the same. The structure of LI is important in generalizing the model. Especially the concept of level, which has already been indicated by the subscript i in RSi, is essential in expanding the lattice and performing the search in the lattice when searching is necessary during the query optimization procedure. We will devote the rest of the subsection to identify the structure I of L. rI I I First, the relationships among {RS RSi c RS I are investigated. These relationships will be used to establish the level structure in LI. Lemma 2.1: The following is true for RSI:

42 (i) For any Xj 6 RS and 0 < RSI such that X. c Xi, (ii) For any Xi 6 RSI and 0 RSI RS such that Xi c Xj, (iii) If X1,X2 e RSI and X incomparable, (iv) If Xj c Xi for Xi e RSi a J 1i 1 i < j < n, there exists Xi e < i < j < n, there is no Xj e are # X2 then X1 and X2 RSI then i e RSI then i < j. J Proof: Obvious. Lemma 2.2: In RS, if Xj c Xi and there is no Xk such that Xj c Xk c Xi for Xi e RSI, Xj e RS. and Xk RS then j j k 1 1XR j1 k = i+1. Proof: Obvious. The next lemma further restricts the structure of the initial lattice. Lemma 2.3: L is a boolean lattice. Proof: Let P (X) be the power set of a set X. For any set X, (P (X), c) is a boolean lattice under set-inclusion. Intersection and union are used for meet and join, respectively. Hence L = (P+(RSI), c) is a boolean lattice. Define a function 81: L — > L such that 61(Y) = Y', a set complement of Y e P+(RS). It can be shown that 81 is a dual isomorphism. Hence L' = ({e1(Y)IY e P+(RSI1), c) is also a boolean lattice with the ordering relation reversed. Define a function 82: L' -- L such that e2(X) D Q (fAieX

41 Theorem 2.1: Given a block B e n, the initial set of all reachable sets RSI forms a lattice under set-inclusion with g.l.b.{X,Y} = XY and l.u.b.{X,Y} = minimum{Z e RSI I X c Z and Y c Z} for any X,Y e RSI. In estimating the effect of fij or fji for ai,aj e B, the restricting set is l.u.b.{Ki, Kj} and the reduced set is g.l.b.{Ki, Kj}. The initial lattice (RS, c) is denoted by LI. The greatest element of LI is D, the domain of the attributes in the block. Since a block is finite and nonempty, the lattice which models our problem is also finite and nonempty. The structure of the initial lattice and the expanded sublattice, which will be discussed in the next subsection, are exactly the same. The structure of L is important in generalizing the model. Especially the concept of level, which has already been indicated by the subscript i in RSi, is essential in expanding the lattice and performing the search in the lattice when searching is necessary during the query optimization procedure. We will devote the rest of the subsection to identify the structure of L. rI I I First, the relationships among {RS RSi c RS} are investigated. These relationships will be used to establish the level structure in LI. Lemma 2.1: The following is true for RSI:

43 Ai). Clearly 82 is an isomorphism. It follows that L is a boolean lattice. In a poset P, 'a covers b' means that a > b and there is no x such that a > x > b for any x e P. We introduce the concept of level in the lattice. Definition 2.7: A leveled lattice is a lattice L with a strict antitone function v: L —? Z from L to the chain of all integers such that if x covers y, then v[x] = v[y] - 1 for all x,y e L. Definition 2.8: The length 1(L) of a lattice L is the l.u.b. of the lengths of the chains in L, where a chain in L is a subset L' of L such that x < y or y < x for all x,y e L'. When 1(L) is finite, L is said to be of finite length. Definition 2.9: In a lattice L of finite length, the depth d[x] of an element x e L is the l.u.b. of the lengths of the chains I = x0 > x >... > xk = x between the greatest element I and x. It is obvious that d[O] = 1(L) where 0 is the least element. The following theorem completely characterizes the structure of LI. Theorem 2.2: L is a leveled boolean lattice with v[X] = d[X] for all X e RSI.

44 I (RSI, c), I n Proof: In a boolean lattice L = (RSI, ), RS = U i=0 RSi and D is the greatest element. The mathematical induction is used. The length of maximal chains from D to X is 1 if and only if X e RS1. Hence d[X1] = 1 if and only if X1 e RSI From Lemma 2.1.(i), for any Xi+ e RS+, there exists at least one Xi e RS such that Xi+ c Xi. Also from lemma 2.1.(ii), there is no Xj e RSj such that Xi1 c Xj for j J i+1 j > i+1. Hence d[X+1] = i+1 if and only if Xi e RSi+ j > ii+. Hence d 1 ]1+1 RSi+i Consequently, d[Xi] = i if and only if Xi e RSI for all i. Now let v[X} = d[X] and consider Xi e RSI and X. RS. Xi 1i 1 j i > Xj implies < D, Xi, Xj > is a chain. clearly v[Xi] < v[Xj]. If Xi covers Xj, then from Lemma 2.2, i = j-1. Hence v[Xi] = v[Xj] - 1. Note that v[X] = i if and only if X e RSI for all X LI Since L is completely characterized by the elements in RSI, we can consider that L is generated by the elements in RS1 1' Definition 2.10: The dimension dim(LI) of the initial lattice LI is the cardinality of the elements in RS1 The elements in RSI are the generators of LI. For the initial lattice LI, 1(L) = dim(LI). If dim(LI) = n, the number of elements in level i is nCi and the total number of elements in L is i=0 nCi i Since LI is of finite length and leveled by d[X], it

45 satisfies the condition that all maximal chains between the same endpoints have the same finite length which is known as the Jordan-Dedekind chain condition. we give an example of an initial lattice model to illustrate the effect of a sequence of semijoins. Example 2.3 In this example, we construct LI for B = {ala2,a3}. Then LI is used to determine the restricting set and the reduced set for each semijoin in a sequence of semijoins between the attributes in B. From the initial value sets {A1, A2, A3}: RS = {A1, A2, A3} RS2 = {A1A2, A1A3, A2A3} RS = {A1A2A3} With RSO = {D, RSI is given by: RSI - {D, A 1, A2, A3 A1A2, A1A3, A2A3, A1A2A3} It is obvious that v[X] = i iff X e RSIi. The Hasse diagram of L is depicted in Figure 2.1. Consider an arbitrary sequence of semijoins f21' 32' f13' f21' f12 Let 0i: the ith semijoin in the sequence Ti: the restricting set for 0i Ei: the reduced set by 0i Initially Ki = Ai for all ai e B. If 0i = fjk then Kk is reduced to Ei. The effect of each semijoin is: (1) 0 =f21

Level 0 Level 1 ' ^ 2 Level 2 A1A2< / A2A XA A / A2A3 Level 3 A1A2A3 The Hasse Diagram of the Initial Lattice and the Effect of Each Semi join for Example 2.3 Figure 2.1

47 T = K1 v E1 = K1 A (2) 02 = f32 T2 = K2 v E2 = K2 A (3) 03 = f13 T3 = K1 v E3 = K1 A (4) 04 = f21 T = K1 v E4 = K1 A (5) 05 = f12 T5 = K1 v E5 = K1 A K = 2 = K = 2 A1 v 1 A A1 A A2 =D A2 = A 1A2 K3 = A2 v K3 = A2 A A3 A3 K3 K3 K2 K2 K2 K2 =E1 v A3 = E1 A A3 = D = A A 2 3 = D = A1A2A3 = A2 = A 1A2A3 = A A =- A 1A 12 3 = E = E v E2 A E2 = E v E2 = E4 A E2 Since K1 = K = K3 reduced by any semijoin = A12A3 after 05' Ki will not be for all ai e B. The effect of each Oi is shown in Figure 2.1.. 2.2.3 Expanded Sublattice In this subsection, the preliminary step in generalizing the initial lattice model is presented. This subsection and the next systematically generate the elements of RS at any instance during the query processing in order to identify its structure and useful properties. For B e, Ki for any ai e B is in L before any semijoin to an attribute associated with ai is made. The effect of a semijoin to ak e AJAi on ai cannot be modeled by

48 LI. In other words, LI cannot model the effect of semijoin between the attributes in one block has on the attribute in another block. Definition 2.11: An expanded sublattice is a lattice generated to model the effect of a semijoin fjk, between the equivalent joining attributes aj and ak in one block, on the attribute ai, which is associated with ak, in another block. The expanded sublattice with the greatest element X will be denoted by EX and the corresponding poset will be denoted by RSX. We shall illustrate the generation of the expanded sublattice by generating the first expanded sublattice. Suppose Ki = X e L for ai e B before fjk is performed for ak e AJAi and aj e EJAk. The reduction of Kk results in the reduction of Ki. The reduced Ki, namely KiN, cannot be expressed by the intersection of sets in RS1. The only restriction on KiN is that it has to be a subset of X. Hence it is incomparable with the sets in LI covered by X. The generation of an expanded sublattice that reflects fjk can be described as follows: (ES1) Suppose RS~ = {A1, A2,..., An}. Let An+1 represent the KiN formed by semijoin fjk. Then An+1 c X and An+i Ai if X ~ Ai(ES2) Let Cx be the set of elements in LI covered by X. Let RS1 = {X 2 An+} U CX. (ES3) Generate EX with X as the greatest element and RSX as

49 the set of generators. An+1 is the reduced Ki by fjk. From Lemma 2.1, any two elements in CX are incomparable. From (ES1), An+1X is incomparable with any element in CX. Consequently the elements in RS1 are pairwise incomparable. From (ES3), if IRSXI = RS1 then EX and LI are isomorphic. Since C c EX, for any Y e L, Y c X implies Y e EX. Since An+1 c X, An+1 = XAn+1. We prefer to denote the new element by XAn+1. This will enable the elements in the same level of EX to be represented by the intersection of the same number of elements in the set {A1, A2,..., An, An+1. Also all the elements smaller than X are represented by the intersection of X and the elements chosen from the set {A1,..., An, An+l}. Therefore, An+l is used when the set is used as a basic element while XAn+1 is used to designate a specific element in a lattice. For the mth expanded sublattice, the reduced set will be represented by An+me A lattice which is generated as L by the set of incomparable elements covered by the greatest element is called an L -type lattice. The LI-type lattice with the greatest element Z is denoted by LZ and its least element is denoted by O. The set of generators of LZ is denoted by GZ. The expanded sublattice is an LI-type lattice. I Z Definition 2.12: In an LI-type lattice LZ of finite length, the relative depth dz[X] of an element X e L is the

50 l.u.b. of the lengths of the chains between Z and X. The following lemma provides an useful property for proving subsequent lemmas. Lemma 2.4: Let W e L and L be an L -type sublattice of L generated by the elements in L covered by W. Then, z = OW Proof: Let RS = {Z, Z and I {1, 2, R1 2z1, Z2 Fn n}. If dz[W] = k then W = QjeJZj for J c I and IJ[ = k. There are n-k elements in Lz covered by W. Denote these n-k elements by W1, W2,..., Wnk. Without loss of generality, let J = {1, 2,..., k}. It follows that W = k1 Zj and Wh = W Q Zk+h for h = 1, 2,..., n-k. Hence W n-k = n-k o = 9h w = W a (Oh= zk+h = =1 Zh (f4h Zk ) (n=l Zh = Oz. ~ The following example shows when and how to generate an expanded sublattice. Example 2.4 Assume that we already have LI as illustrated in Example 2.3. Let B' = {ai, aj} be another block and aj e AJA3. Consider the following sequence of semijoins: f21 f32' fij The effect of 1 = f21 and 02 = f32 are the same as in Example 2.3. As a result of 3 f K3 = A3 is reduced. The generation of L is as follows The generation of L is as follows:

51 (1) Since RS1 = {A1, A2, A3}, introduce A4 such that A4 c A3, A4 A A1 and A4 ' A2 A A3 (2) Since C = {A1A3, A2A3, RS1 = {A1A3, A2A3, A3A4} A3 (3) Generate E with A3 as the greatest element and A3 A3 RS1 as the set of generators. RS = {A3 A1A3 A2A3, A3A A1A2A3 AA3A4, A2A3A4, A1A2A3A4} A3 The relative depth dA [X] = i iff X e RSi. The 3 1A3 reduced set of K3 by 03 is A3A4. The Hasse diagram of L and the effect of 03 are shown in Figure 2.2. 2.2.4 Expanded Lattice In this subsection, we show that RS at any instance during the query processing also forms a lattice. An algorithm to generate such a lattice is presented and its correctness is proved. Definition 2.13: An expanded lattice is the smallest lattice that contains the initial lattice and all the expanded sublattices subsequently generated. The expanded lattice models the state transitions which are caused by the dependence among equivalent joining attributes and associated joining attributes mixed together. The expanded lattice for a block B models RS, and is denoted by L. Initially L = LI. Subsequently, L dynamically grows as a query is processed by a sequence of semijoins which contains a semijoin between the attributes

52 Relative depth 0 1 2 AIA3 A1A3 A1A2A3 The Hasse Diagram of the Expanded Sublattice and the Effect of a Semi join for Example 2.4 Figure 2.2

53 of a block other than B. Different expanded lattices will be generated for different sequences. Consider the new expanded lattice after the generation of EX, for X e L. The new expanded lattice is denoted by L. We define the lattice union as follows: Definition 2.14: Let L1 = (P1, <) and L2 = (P2, <) be lattices such that: (1) P1 and P2 are the collections of subsets of a set D, (2) In both L1 and L2, < denotes set-inclusion, (3) In both L1 and L2, g.l.b. and l.u.b. are defined to be the same as in L, The lattice union L1 U L2 is (P1 U P2, <) with g.l.b., l.u.b. and < as defined in L1 and L2. L1L2, L1-L2 and L2-L1 are similarly defined. It is clear that L1 U L2, L1L2, L1-L2 and L2-L1 are all posets. It can be shown that L n E is a lattice. Since the elements of L and EX are subsets of the domain D, L U EX is well-defined. However, L U E is not always a lattice. The following lemma determines when L U EX is a lattice. Lemma 2.5: Let 0 be the least element of L. L U E is a lattice if and only if O e EX. Proof: We have to show that XivXj e LUEX and XiAXj e LUEX for any Xi,Xj e LUEX. It is obvious when Xi,X e L or 1 J X.,Xj e EX. Assume Xi e L-EX and Xj e E-L. We will first show that XvXj e LUEX. This does not require O e EX. Let sho tht jv~ ELU i

54 UB be the set of upper bounds of Xi and Xj, then UB c L. Since the greatest element of EX is X, Xj < X < D. Also Xi < D. Hence D UB and UB ~ 0. Since UiAUj e UB for any Ui,Uj e UB, XivXj = g.l.b.UB e L. Now consider XiAXj. (->) Suppose XiAXj e LUEX and 0 g EX. Since O 0 EX O is a X X minimal element in L U EX E is an expanded sublattice such that X' 0 L for some X' e RS1. Hence OX L, which implies OX is also a minimal element in L U EX. Since O and OX are both minimal elements in L U EX, OAOX g LUEX This contradicts that XiAXj e LUEX. (<-) For any Xi e L-E and X e EX-L, XiAXj = XiA(XAX). From the associativity of A, XiA(XAXj) = (XiAX)AXj. Since Xi, e L, XiAX e L. On the other hand, for any Xk e L, O e EX implies Xk e EX whenever Xk < X. Since XiAX < X, XiAX e EX XiAX e EX and Xj E implies (XAX)AX XAXj e EX. Therefore sometimes it is sufficient to generate an expanded sublattice to form LN and sometimes not. If O 0 E, we have to construct the smallest lattice containing L U EX It is necessary to construct a lattice in order to generalize the properties of RSI to RS so that the g.l.b. and l.u.b. of any two sets in {Kilai e BI can be determined at any time during the query processing. The algorithm to generate an expanded lattice is given below. PROCEDURE GEN LAT (L, EX) // GEN_SUBLAT (X, G) is a procedure to generate // // an LI-type lattice with the greatest element X // // and the set of generators G //

55 IF 0 EX THEN LN <- L U EX ELSE BEGIN Y1 <- max {Y I Y covers elements in L - E and elements in EX L} y1 C Y1 L IF <- {y IY e L U EX <- GEN_SUBLAT (Y1 y.L 1 0 e L' and Y1 covers Y} y1 C ') THEN LN <- L U EX U L ELSE BEGIN m <- 1 WHI LE O L WHILE O ~ L DO BEG I N Ym+l <- max {Y I Y covers elements in + L - m L - L m and elements in L - LI Cm+ < y c <- [ Y L U EX U k L) I Y C L U EX U (Uk L k) k=l and Y m covers Y} m <- m+1l Y Y. L m <- GENSUBLAT (Ym, C ) END LN <- L U EX U (U L k) END END END GEN LAT We show that GENLAT (L, lattice containing L U EX. ) generates the smallest E ) generates the smallest Lemma 2.6: Suppose 0 0 EX. L U EX U (U 1 L k) is the k=l V smallest lattice containing L U EX if and only if O e Lm Proof: () Consider E. Proof: (<-) Consider EX and L 1 Since Y1 e L Q Ex Y ~~~~ w

56 Y X e EX Let L 1 be the sublattice of EX generated by the X y1x elements covered by Y1. From Lemma 2.4, O =. Since Y X Y Y Y 1 1 X 1 X 1 L c L 1, e L. From Lemma 2.5, E U L is a lattice. Following the same procedure, EXU(Umk1L ) is a y Y lattice. Since O e L m, e EXU(UMkL ). Consider Xi e L{EXU(Uk=1L k)} and X {EXU(Uk=1L k)-L. Using the same X k X(ULk Using the same arguments of the proof of Lemma 2.5, XivXj e LUEXU(U=L k). Y Y Suppose Xj e L h for some h, where 0 < h < m, and L = E. XiAXj = XiA(YhAX) = (XiAYh)AXj. Since Yh > XiAYh > 0 and O Y Y e EXU(Uk=L k) XiAYh e L g for some g > h. Hence XiAXj 6 Y Y EX ~m k C LUk EXU(UkL ). Consider LUEXU(Uk=L )-{Z} for any Z e U=1L k -(LUEX) and let Cz be the set of elements in UXU(Um k LUEXU(Uk=L ) covering Z. For any Z1,Z2 e CZ, Z1AZ2 Y Y LUEXU(UmL ) - {Z}. Hence LUEXU(UmkL ) is the smallest lattice. Y Y (->) If 0 0 L m then O and 0 are minimal elements in Yk Y Y LUEXU(U L k). So OAO m 0 LUEXU(Uk L ). k ~X km Consequently LUEXU(Uk=L ) is the new expanded lattice K=I Y X N X m k after the generation of EX. Therefore L = LUEXU(Ukm=L ). Denote the level function and the depth function of LN by vN and dN, respectively. Summing up the previous discussions, we have the following theorem. 3 N =X U m L k iY Theorem 2.3: L = L U Ex U (Uk= L ) is the smallest k=1

57 leveled lattice containing L U EX with VN[Z] = dN[Z] for all Z e LN where dN[Z] is given such that: (i) dN[Z] = d[Z] for Z e L (ii) dN[Z] = dx[Z] + d[X] for Z e EX (iii) dN[Z] = dy [Z] + d[Yk] for Z e L k and 1 < k - m. k Proof: We have only to show that LN is a leveled lattice. This follows immediately from Theorem 2.2 and the fact that LN is a union of a finite number of LI-type lattices. Consider Z e LHLM, where L and LM are either E I Yk' or L or one of the L s. We will show that vN[Z] is consistent whether we use dH[Z] or dM[Z]. Suppose Z1 e LH covers Z and there is Z2 e LM such that Z > Z > Z. Since HI H H L is an L -type lattice Z1,Z e L implies Z2 e L. This is a contradiction. The fact that an expanded lattice is a leveled lattice can be used to reduce the search space when some elements of the lattice are stored and they are searched to retrieve the data associated with those elements. Suppose an expanded lattice L contains m expanded sublattices. Since every element in level k, 1 < k < n+m, of L is represented by the intersection of k elements in the set {A1, A2,..., An An+l' *'. An+m}, we can easily identify the level of an element. Therefore, if the elements in the same level of L are stored together, we have only to search the elements in the level in which the element being searched is. We give an example which shows how to generate an expanded lattice.

58 Example 2.5 In this example, we generate an expanded lattice which models the interaction among equivalent joining attributes as well as among associated joining attributes by a sequence of semijoins. Let B1 = {al, a2, a3' a4}, 2 = {ag, ah, B3 = {ai, a}, B4 = {ak, am, an}, and ag e AJA1, an e AJA2, ai e AJA4 Consider a sequence of semijoins f12' f43' f21' fhg' f34' fkn' fji L is shown in Figure 2.3. Initially L = L. The effect of each semijoin is given as follows: (1) 01 f12 - K2 is reduced from A2 to A1A2. (2) 02 = f43 - K is reduced from A3 to A3A4. (3) 03 f21 - K1 is reduced from A1 to A1A2. (4) 04 = fhg - Introduce A5 to create A1A2A5. A1A A A - Generate E with G1 = {A1A2A3, A1A2A4, A1A2A5}. A A AA 1 2 N A1A2 - Since O = A1A2A3A4 e E L= LUE - K1 is reduced from A1A2 to A1A2A5. (5) 05 = f34

59 12A4 4 1A2 A12A3 1A A2A A1A2A3A4 The Hasse Diagram of the Initial Lattice for Example 2.5 Figure 2.3

D A 'I~~A2 ~~~ ~ ~ A3A4 A1A2A A A A A1A2A 1A 3A4 AAA A3AA7 1 2 1 2~ 31 34 2 3 4 4 7 AIA2A3A4A5 AiA2A3A4A5A6 The Hasse Diagram of the Intermediate Poset for Example 2.5 Figure 2.4

Level 0 51,1 A1A 2A3A4 2 al6 a #4 07 oa ' ~ l Al alaza~ A "A 45A 3 A1A~ABA 6 ~ A1A2A3A4A7 5 6 A ^A23A4A5A6A7 7 The Hasse Diagram of the Expanded Lattice and the Effect of Each Semijoin For Example 2.5 Figure 2.5

62 - K4 is reduced from A4 to A3A4 (6) 06 = fkn - Introduce A6 to create A A2A6. A1A2 A1A2 - Generate E with G {A1A2A3, A1A2A4, A1A2A5, A1A2A6}. 1 A2 N A1A2 -Since O = A1A2A3A4A5 e E, L LUE. - K2 is reduced from A1A2 to A1A2A6. (7) 07 = fji - Introduce A7 to create A3A4A7. A3A4 A A4A - Generate E with G = {A 13A4, A2A3A4, A3A4A7}. A3A4 A3A4 - Since O = A1A2A3A4A5A6 L E, LUE is not a A A 34. lattice. LUE is shown in Figure 2.4. Only the greatest element, the least element and the generators of each expanded sublattice are labeled. Y - In this example, Y1 = A1A2A3A4 Generate L with G 1 = {A1A2A3A4A6, A A2A3A4A5, A1A2A3A4A7. Y AA Y 1 N 3 4 Y1 N - Since 0 e L L = LUE UL.L is shown in Figure 2.5. - K4 is reduced from A3A4 to A3A4A7. The expanded lattice is the generalization of the initial lattice L'. The current set of all reachable sets has the same properties as those for RSI given in Theorem 2.1. We summarize the above discussion in the following theorem:

63 Theorem 2.4: Given a block B = a1, a2,..., an}, the current set of all reachable sets RS at any point in the sequence of semijoins forms a lattice under set-inclusion with g.l.b.{X,Y} = XY and l.u.b.{X,Y} = minimum {Z e RS X c Z and Y c Z) for any X,Y e RS. In estimating the effect of fij or fji for ai,aj e B, (i) Ki,Kj e RS, (ii) The restricting set is l.u.b.{Ki, Kj}, and (iii) The reduced set is g.l.b.{Ki, Kj}. The formula to compute IKjNI resulting from fij can be obtained using Theorem 2.4. Substituting IKI = Il.u.b.{Ki, Kj}l in (2.5), we have the following basic formula: |KjN| = Ig.l.b.{Ki, Kj}| = IKil x IKjl / |l.u.b.{Ki, Kj}| (2.7) We have modelled the effect of a sequence of semijoins using a lattice and carried out a structural analysis of the lattice model to establish a basis for the future research. The theory developed in this chapter is general enough that it can be applied to a broad class of query processing problems. The lattice model for estimating the reduction of relations during query processing can be used for broadcasting communication networks as well as for point-topoint communication networks.

64 The lattice model not only enables us to compute IKil's but also gives information about the containment relation among Ki's. This fact can be used to increase the efficiency of the query optimization algorithm. For example, if Ki c Kj, fji can be excluded from the set of the next possible semijoins because fji does not reduce any relation. Also if Ki c Kj, K.N = Ki after fij. In this case, IKjN| can be determined without any computation.

CHAPTER 3 OPTIMI ZATION MODEL In this chapter, we present a mathematical model for distributed query optimization. The cost reduction model of a sequence of semijoins is developed in terms of the cost and benefit associated with each member semijoin of the sequence. The optimization model is formulated using the cost reduction model and the database state transition model presented in Chapter 2. 3.1 Cost Reduction Model In this section, the computation of the processing cost of a query is discussed. The expressions of the benefit achieved by a semijoin are derived for a few different cases depending on the change of the value of INFO by the semijoin. The net benefit of a sequence of semijoins is expressed in formulae. Our cost measure of the distributed query is the total inter-site data flow transferring the necessary data to the user site. As mentioned in Chapter 1, the transmission delay between source and destination in packet switching networks is proportional to the volume of data being transmitted. We also include the message overhead incurred 65

66 by inter-site flow to the data traffic. Here, the term "message" is used not to designate a specific number of packets but a continuous stream of inter-site data flow. A message overhead is defined in [KLEI 76] as all those characters that are transmitted but not exchanged between user processes in the attached host computers. The message overhead can be approximately divided into the following two parts which are measured in bytes: (1) Vf: the fixed portion of the message overhead, (2) Vp: the portion of the message overhead which is proportional to the length of the message. The transmission cost to transfer the message of length M bytes is given by: C(M) = Vf + Vp + M = Vf + (1 + Vp/M) x M = Vf + u x M (3.1) where u denotes the proportional coefficient and it is given by u = 1 + Vp/M. Vf and u are the parameters determined by the communication network being used. By including the message overhead in the transmission cost function, we want to include the effect of the length of the sequence of semijoins in minimizing the total amount of data transferred in processing a query. In other words, any semijoin which has a negligible effect in reducing the amount of data transfer is excluded from the sequence to avoid the message

67 overhead. After the initial local processing, there are one or more relations of R at each site involved in the query. When the reduced relations are finally transferred to the user site, all the relations at one site can be sent by a single message. Consequently the message overhead to move the relations depends on the number of sites. The relations stored at the user site do not have to be moved. Hence we have to make use of the site information in formulating the query cost. R is partitioned into blocks such that any two relations in the same block are stored at the same site. This partition is called SITE. If there are m sites involved in the query, SITE = {ST1, ST2'..., ST } The block STi can be considered a set of relations stored at site i. Let STR be STj e SITE such that Ri e STj for R e R and let STU be the set of relations stored at the user site. If STU 0, S STj for some STj e SITE. The data distribution information is described by a set of parameters called DIST: DIST = < STR, STU > ~i I " + where STR = {STR | Ri e R }. The following example shows the derivation of the initial value of DIST from SITE and STu. Example 3.1

68 Consider the relations presented in Example 2.1. It was assumed that the relations are all stored at different sites. Let R4 = OFFER be the relation at the user site. Since there are five sites involved in the query, SITE = {T1, ST2 T ST T, ST, } where STi = {R } for i = 1, 2, 3, 4, 5. i Since ST = {R4}, ST ST4. In this case, the initial value of STR for data distribution information DIST = < STR, STU > is given by ST' = i{Ri for i = 1,2, 3, 4, 5. The data distribution information together with the state of the database gives a complete description of the distributed database to which the user query is issued. We define the state S of the distributed database as follows: S = < INFO, PAR, DIST > The state space is denoted by I. The initial cost of a query is the total communication cost to retrieve all the relations in R to the user site after initial local processing without using any semijoin. Let IC be the initial cost of a query and S(R) the size of a relation R. IC = Vf x (ISITEI - t ) + u x RiR+ST S(R = Vf x (|SITE| - tU) + x (RRieR-STU(IRiI x lEa jei w) (3.2)

69 where t -= (1 if STU 0, 0 otherwise. The value of INFO makes it necessary to differenciate a few cases in computing the benefit achieved by a semijoin. The change in the value of INFO is caused by SJR. In Chapter 2, INFO is defined as follows: INFO = < NR, NB, JR, SJR, EJA, AJA, P > If SJR 0 0, the initial value of INFO is not changed throughout the query processing. Consider aiaj e Bh for some Bh e II. Suppose I(ai) = Ri, u(aj) = Rj and Ri e SJR. After fij, all the values of Ki necessary to process the query are included in K.N. Since the information contained in Ri has been completely transferred to Rj, Ri can be ignored. The elimination of Ri from R causes the following changes: (1) Ng = {IBkl Bk e n} - Since ai is ignored, if IBh. > 2, IBhNI = IBhl - 1. - If IBhl = 2, EJAj = 0 after ai is ignored. Hence if ai,aj 0 T then Bh is ignored and IBhNI| 0. (2) NR = {lakl j Rk e R+} - laiNI = 0, which implies Ri is ignored. - If IBhNI = 0, aj can also be ignored. In this case, |ajN| | j - 1. (3) SJR - SJRN = SJR - {Ri}.

70 - If jajNI = 1 and Rj e JR, then Rj becomes a singleton joining relation. Hence SJRN = SJR - {Ri} U {Rj}. (4) JR - JRN = JR - {Ri } (5) EJA - EJAhN = EJAh - ai} for all h such that ah e EJAi. (6) AJA - If IBhNI = 0, aj will not participate in any semijoin. Hence AJA N = AJA - {aj} for all g such that ag e AJAj. (7) ~ - If IBhNI| 0, ON = - {fix'fxi I a e EJAi}. If IBhNI = 0, ON = - {fij, fji}. (8) DIST * i - ST N = ST - {Ri}. i i If STRN = 0, STR can be ignored. (9) CR = {|Rkl | Rk e R } - If R becomes a singleton joining relation, IRjNI = IKjNI. The following example shows the change in the value of state S caused by a semijoin. Example 3.2 Assume the query information model Q in Example 2.1, the initial value of INFO in Example 2.2, and the initial value of DIST in Example 3.1.

71 Consider the first semijoin 01 = f16. This semijoin is to perform R4 <a6 = a1] R1. Here U(a1) = R1, i(a6) = R4 and *(a.) = *(a6) = B1. Since R1 e SJR, the value of S is changed after 01 as follows: (1) NB -Since |B1 = 2 and a1 a6 0 T, IB1NI = 0. (2) NR I- NI = 0. Since IB1Nj, l =N c141- 1=1. (3) SJR - Since la 4N = 1 and R4 e JR, SJRN = SJR - {R1} U {R4} = {R4}. (4) JR -JRN = JR - {R1} = {R4, R5}. (5) EJA - EJA6N = EJA6 {a } = (6) AJA -Since IB1NI = 0, AJA7N = AJA7 - {a6} = 0 (7) c - Since IB1NI = 0, ON = O - {f16 f61} = {27' f72' f28' f82' f78' f87' f49' f941. (8) DIST -STN =ST - {R1 = 0.

72 (9) CR - Since R4 becomes a singleton joining relation, IR4N = IK6NI We derive expressions for the net benefit of a semijoin by using the parameters describing the database state. Consider fij with a(ai) = Ri, u(aj) = Rj and ai,aj e Bh at any point during the query processing. Let nij be the net benefit of fij, cij the cost incurred by fij and bij the benefit achieved by fij. The cost cij is the communication cost to transfer the current set of values of ai. cij = Vf + u x (Kil x wi) (3.3) The benefit bij is classified into the following three different parts: 1. ij: The benefit due to the reduction of IRjl which results from the reduction of IKj|. 1 U bj tR X [u x (IRj-lRjNI) x ahe Wh] (3.4) where tU if R 0 STU, 0 otherwise. 2. b2j: The benefit due to the elimination of Ri. If Ri 0 STU and Ri e SJR, the benefit is: u x S(Ri) = u x (IKil x wi) Furthermore, if STRN = 0, Vf is eliminated.

73 2 U S x V x t x (Ki x wi)] b i = t xtR X Vf X tR x i 1 1 (3.5) where tS 1 0 and tL = 1 R 0O if R e SJR, otherwise; if STiN = 0, otherwise. 3. b3: The benefit due to the elimination of aj. If Rj P STU and IBhN| = 0, the benefit is: u x |RjNI x wj In addition, if IajNI = 1 and ak e J where i(ak) Rj, the additional benefit can be given as follows: u x (IRjNI - IKkNI) x wk b3 1i tR x t x u x [ |RjN x wj j Bh 3 + ta x ta x (RjNI - IKkN) x wk] where t1 if |BhN| 0 h otherwise 0 otherwise; and t = { 1 if iaf NI - 1, 0 otherwise; and t 1 if a e J, v0 otherwise. (3.6) From (3.4), (3.5) and (3.6), 1 + b2 + b3 b. = b. +b. + 1 3 1 3 1 ) i1 (3.7) Using (3.3) and (3.7),

74 ni j - ij (3.8) We now compute the cost of a query associated with a sequence of semijoins. Consider the following sequence. SEQ = 01' 012' '' 0 where 0i e p for i = 1 2,..., m. Let ni be the net benefit of 0i, ci the cost incurred by 0i, bi the benefit achieved by oi, and SC the cost of a query associated with SEQ. SC = IC + Cm sc = ic+ i=1 ci -i I=1 bi =I - T= (bi - ci) = IC - m= n (3.9) IC -.=1 bi corresponds to the cost of retrieving the remaining portions of the relations to the user site and mi=1 ci corresponds to the cost of semijoins incurred by SEQ. The cost reduced by SEQ is m ni which is the net benefit of SEQ. 3.2 Problem Formulation In this section, we formulate the optimization problem of distributed query processing. The model for database state transition was presented in Chapter 2. The expressions for the cost reduction achieved by a sequence of semijoins were derived in Section 3.1 in terms of database state parameters. The optimization model is based on the database state transition model and the cost reduction

75 model. The optimization problem of distributed query processing is described as follows: Given: - Query information model Q of the user query reduced by the initial local processing. Q = < T, J, R, II, u, I > where T is the target list of the user query, J is the set of joining attributes of the user query, R is the set of relations referenced by the user query, II is the partition of J induced by the equivalence relation '=' ]: (T U J) — > R specifies the relation to which each attribute belongs, and i): J — ~ n specifies the block of II to which each joining attribute belongs. - The value of PAR after initial local processing. PAR = <{IRil I Ri e R+}, {IDil I Bi e II, {JKil I ai C J}, {wi | ai e T U J}> where IRil is the cardinality of tuples in relation Ri, IDil is the cardinality of values in the domain of the attributes in block Bi, IKil is the cardinality of the current set of values of joining attribute ai, and wi is the width (in bytes) of attribute 1

76 ai e T U J. - The data distribution information SITE and STU. SITE = {ST1, ST2,..., STm} where m is the number of sites involved in the user query and STi is the set of relations stored at the ith site. STU is the set of relations stored at the user site. Determine: A sequence of semijoins 01, 02'.' 0 which has the minimal cost of the user query IC - n where 0i e $, the set of possible semijoins to process the user query, IC is the initial cost of the user query given by (3.2), and ni is the net benefit of 0i given by (3.8). Since IC is fixed, minimizing IC - = ni is equivalent to maximizing i1 ni. The initial state of the distributed database before using any semijoin is known: - The initial value of INFO is derived from Q. - The initial value of DIST is derived from SITE and STU. - The initial value of PAR is given. The subsequent change in the value of the distributed database state S caused by a sequence of semijoins can be

77 computed by using the methods presented in Chapter 2 and Section 3.1. The state transition model for the distributed database is considered a function which determines the next state given the current state and a semijoin. The net benefit of a semijoin at any position in a sequence can be computed using the expressions derived in Section 3.1. The cost reduction model is considered a function which determines the net benefit of a semijoin given the current state and the next state of the distributed database and a semijoin. Consider the ith semijoin o i Let Si be the state of distributed database before 0,i Si+1 be the state of distributed database after 0i' and REAL be the set of real numbers. Then Si+1 is a function of Si and 0i' and this definition can be expressed as follows: Si+ d 1i0 (3.10) Si+ = ir i where s: Z X 0 — > Z is defined to be the state transition function. Further, ni is a function c' of Si, Si+1 and 0i' which can be defined as follows: ni d c(iS+l'i) d = c' (Sis(S0),0) d c(Si0i) - (3.11) 1 1i where c: Z X A — > REAL is defined to be the cost reduction

78 function. Now, the optimization model can be described as follows: Let r be a set of sequences of semijoins and let y e r where y = 01, 02, '..., * 0(y) The optimal sequence of semijoins can solving the following: maximize E(y n subject to Si is given, be obtained by I Si+1 = s(Si0i) ni = c(Si'0i) 0i e 6 (i = 1,...,x(y)), (i =,..., X(-y) ), (i = 1,...,X(y)). and

CHAPTER 4 DOMINANT TERM OPTIMIZATION The purpose of this chapter is to develop efficient methods for computing the values of variables which need to be evaluated frequently in the query optimization procedure. There are two important standards in evaluating a computer algorithm designed for an optimization problem. One is the optimality of the solution produced by the algorithm. The other is the efficiency of the algorithm itself. The execution time of an algorithm is determined by the product of the number of executions of the dominant term and the time required to execute the dominant term. In solving our problem, we have to frequently compute the net benefits of semijoins. Hence it can be considered the dominant term in our case to find out Si+1 and ni given Si and 0i. Especially efficient computations of the cardinalities of the sets of values of joining attributes reduced by semijoins are crucial in reducing the time required to execute the dominant term. In Chapter 2, we have developed a lattice model and a method which systematically generates the lattice in order to characterize the properties and the structure of the set of researchable sets for a block of joining attributes. The 79

80 efficiency in application, however, was not considered. Also we have to develop an efficient approximation for (2.6) which requires long computation time for a large value of k. The dominant term optimization is important because it is common whether we develop an optimal algorithm or a heuristic algorithm for the query optimization. 4.1 Efficient Use of the Lattice Model In this section, we present an efficient algorithm to compute the cardinality of the set of values of a joining attribute reduced by a semijoin from its equivalent joining attribute. Since the query optimization will be done using a computer, all the operations involved in query processing have to be developed with computer implementations in mind. First, we discuss the operations in the lattice. Consider a block B = {a1, a2,..., an} and the current set of all reachable sets RS for B. We have to identify l.u.b.{Ki, Kj} and g.l.b.{Ki, Kj} to apply Theorem 2.4 and Equation (2.7) in estimating the effect of fij or fji for ai,aj e B. A natural way of implementing a lattice in a computer is to use doubly linked lists. A node represents an element and pointers are used to specify the covering relationship among elements. However, searching for g.l.b. and l.u.b. by following pointers takes a long time apart from the cost of space.

81 In our case, the special structure of (RS, c) and the naming rule of its elements can be used to implement efficient lattice operations. Suppose (RS, c) contains m expanded sublattices. Let I be an index set {1, 2,.., n, n+1,..., n+m}. Since each reachable set in RS is the intersection of elements from the set {A1, A2,..., An, An+1'., An+m}' for any X,Y e RS X = ieI Ai for some Ix c I (4.1.a) and Y = jeIy Aj for some I c I (4.1.b) y Furthermore, from the naming rule of the elements in RS, X > Y if and only if I c I. Note that X = D if and only if I = 0. Hence, g.l.b.{X, Y} = XY (=ieI Ai) Q (QjeIy Aj) x y keIZ Ak (4.2.a) where I = Ix U I z x y Similarly, l.u.b.{X, Y} = minimum{Z e RS | X c Z and Y c Z} aheIw Ah (4.2.b) = ~hei Ah where Iw = IxIy In this way, we can identify l.u.b.{Ki, Kj} and g.l.b.{Ki, Kj} without storing the whole lattice and searching it.

82 The lattice model provides the theoretical basis for computing the state transition of the database. There may be many different algorithm designs based on the results presented in Chapter 2. Our goal is to find an algorithm which reduces the sum of the time for computing cardinalities and the time for maintaining information necessary for computation. In order to use (2.7), we have not only to identify l.u.b.{Ki, Kj} but also to know |l.u.b.{Ki, Kj}|. Since A1, A2,..., A are the sets from which all other reachable sets are reached, their cardinalities have to be available. Suppose l.u.b.{Ki, Kj} f {D, A1, A2,..., An}. In many cases for n < 4, l.u.b.{Ki, Kj} is the reduced set by an earlier semijoin in the sequence. That is, |l.u.b.{Ki, Kj}| has been computed previously by using (2.6) or (2.7). If this is always the case, we have only to store the cardinalities of A1, A2,.. An and the reduced sets by the previous semijoins. The following counter example shows that this conjecture is not true. Example 4.1 In this example, we construct a sequence of semijoins such that for a semijoin in the sequence, (1) l.u.b.{Ki, Kj} 0 {D, A l,..., An} (2) l.u.b.{Ki, Kj} is not a set reduced by any previous semijoin.

D Level 0 A3A4 2 /2A2A3A 4 A\^9^ff^ ~l 4A<^ ^^ ^^ <^rA AiA~ A I 2Z(4A6 ^ ^ ^ A1A23A4A 5 AA2A3A4A5A6A7 7 The Hasse Diagram of the Expanded Lattice and the Effect of Each Semijoin for Example 4.1 Figure 4.1

84 We use the expanded lattice generated in Example 2.5: Let B1 = {a1, a2, a, a}, B2 = tag, ah}, B3 = ai, aj}, B4 = {ak, ap' aq, and ag e AJA aq e AJA ai AJA4. Consider a sequence of semijoins: f12' f43' f21' fhg' f34' fkn' fji' f31' f24' f41 The expanded lattice and the effects of 01 = f12 07 = fji are shown in Figure 2.5. After 07F K1 = A1A2A5, K2 =A1A2A6, K3 = A3A4 and K4 = A3A4A7. The effects of the rest of semijoins are: (1) 08 = f31 - K1 is reduced from AA2A5 to A1A2A3A4A5. - l.u.b.(K1, K3) =D (2) 09 = f24 - K is reduced from A3A4A7 to A1A2A3A4A6A7 - l.u.b.(K2, K4) = D (3) 010 = f41 - K is. reduced from A1A2A3A4A5 to A1A2 A3AA5A6A7. - l.u.b.(K1, K4) = AA2A3A4 For 10'i l.u.b.(K1, K4) = A1A2A3A4 is not a set reduced by any semijoin in the sequence. The effect of each semijoin is shown in Figure 4.1. Hence it is not sufficient to store the cardinalities of the reduced sets and those of D, A1,... AA in order to find |l.u.b.{K., Kj}| by searching. If we store the

85 cardinalities of all the elements of RS, we can definitely find the cardinality of a reduced set by using Theorem 2.4. If the entire RS is to be stored with the cardinality of each reachable set, the cardinalities can be computed using the following properties: (1) For any LI-type lattice, the events corresponding to the generators are mutually conditionally independent given the event corresponding to the greatest element. (2) Whenever an LI-type lattice is generated to make a new expanded lattice, the cardinalities of the greatest element and generators of the L-type lattice have been computed and stored. Although the above method is a conceptually simple way of find.ing the cardinalities of reduced sets, it involves many complex procedures. The major time consuming components are as follows: (1) Procedure GEN_LAT has to be run for each expanded sublattice to generate a new expanded lattice. (2) The cardinalities of all the elements in RS have to be computed and stored. (3) g.l.b.{Ki, Kj} has to be searched to retrieve its cardinality. Since the lattice (RS, c) may grow very large depending on the sequence of semijoins, this method is not efficient. We must develop an algorithm which does not need to store the entire lattice and the cardinality of each reachable set.

86 Therefore, we present a recursive algorithm which computes the cardinality of any reachable set in the lattice without storing the lattice. Once |l.u.b.{Ki, Kj}| is computed by this algorithm, the cardinality of the reduced set is obtained by (2.7). Since the number of tuples in each referenced relation is finite and a semijoin has to reduce at least one tuple to process a query, a sequence of semijoins to process a query is necessarily finite. As a result, the lattice of reachable sets corresponding to such a sequence is finite. Even for an infinite sequence of semijoins, unless a semijoin reduces a tuple in a relation, an expanded sublattice will not be generated. Therefore the lattice of reachable sets is always finite. Since a finite lattice is a complete lattice, every subset in (RS, c) has a g.l.b. and a l.u.b. From the completeness of an expanded lattice and the associative property of g.l.b., we have the following general result: Lemma 4.1: Let the lattice L = (RS, c) for a block B = {a1, a2,..., an} contain n initial sets A1, A2,..., A and m sets An+l An+2' ', An+m generated by semijoins between the attributes in other blocks. Let I = {1, 2,..., n, n+1,..., n+m). Then for any set X e RS with the index set I c X -- I, X = g.l.b.{X1, X2,..., Xp} for some Xj e RS, j e J = {1, 2,..., p}, if and only if

87 Ix = UjeJ Ij where Ij is the index set of Xj for j e J. Proof: (->) Since A is associative, g.l.b.{X1,..., Xp} = g.l.b.(X1AX2), X3,..., Xp} = (...((X1AX2)AX3)...)AXp. From (4.2.a), X1AX2 = I1I2 Ai Following the same procedure, g.l.b.{X1,..., Xp} = Hie1I2...Ience g.l.b.{X1,..., Xp} = X implies UjeJ Ij = Ix. (<-) If UjeJ Ij = Ix, then g.l.b.{X1,..., Xp} -o A A - ~iCI UI2...Ip Ai ieIx Ai = X. I U2 P X Definition 4.1: In (RS, c) for a block {a1, a2,..., a } with m expanded sublattices, let X = 2ieI Ai for Ix c I n 1 - x = {1, 2,.., n, n+1,.., n+m}. The index set of a reachable set X is I. X Since the index set of a reachable set uniquely determines the reachable set, we will represent reachable sets by their index sets. Suppose the greatest element of the kth expanded sublattice is Z. Then An+k = ZAn+k The index set of An+k is given, by convention, by IA = I U n+k {n+kl. Using (4.1.a), we represent a reachable set by its index set in the algorithms to determine the cardinality of a reachable set. In computing the cardinality of a set X e L, we determine sets X1, X2,..., X such that X1, X2,..., Xp L, g.l.b.{X1, X2,..., Xp} = X and the cardinalities of X1, X2,..., Xp are easily obtainable. In fact, the following algorithm generates the index sets of X1,..., X P

88 such that either Xi e {A n+ An+2'... An+m or Xi L for i = 1,..., p. If Xi e {An+1 An+2,.. An+m}, I Xi can be computed by (2.6). If Xi e L, IXil can be computed using the fact that the events corresponding to A1, A2,..., An are mutually independent. The cardinality of the set X can then be computed by using the associativity of g.l.b. and repetitive application of (2.7). PROCEDURE SETCOVER (I ) // I is the index set of X e RS. I, is the // q // index set of A for q = n+l,..., n+m // C <- 0; initialize the cover being constructed. u <- max I WHILE u > n; n: the size of block DO BEGIN C <- C U {IA } AU u Ix x- Ix IA IF I 0 THEN u <- 0 ELSE u <- maximum I END IF u ~ 0 THEN C <- C U {I } RETURN (C) x END SET COVER Let Ii and Ij be the index sets of Xi, Xj, respectively and Xi, Xj e RSI U {An1,..., A }. Since An is in the 1 j {An+1F n+m n+k kth expanded sublattice, An+g > A+h implies g < h. Hence Xi > Xj implies max Ii < max Ij. Consequently, if Ii c Ij then max Ii < max Ij. Suppose Xi > Xj > X and there is no Xk e RSIU {An+l,..., An+m} such that max Ij < max Ik < max

89 Ix, where Ik denotes the index set of Xk. Procedure SET_COVER avoids producing Ii by producing Ij first. The following example illustrates the steps in procedure SET_COVER. Example 4.2 Consider the lattice shown in Figure 4.1. RS = A,{A A2, A3, A4} and m = 3. Since A5 = A1A2A5, A6 = A1A2A6 and A7 = A3A4A7 the index sets are: IA = {1, 2, 5}, I = {1,.5 6 2, 6}, and I = {3, 4, 7}. We apply SETCOVER for X A7 A1A2A3A4A5A6A7. The index set I = {1, 2, 3, 4, 5, 6, 7}. (1) Initially C = 0 and u = max I = 7. (2) First execution of WHILE statement: Since u = 7 > 4 = n, - C = 0 U {IA = I A A 7 7 - Ix = {1, 2, 3, 4, 5, 6, 7} - {3, 4, 7} = {1, 2, 5, 6} -Since Ix 0, u = max Ix = 6. (3) Second execution of WHILE statement: Since u = 6 > n, - = u {IA A A, A } 7 6 A7 6 - I = {1, 2, 5, 6} - {1, 2, 6} = {5} x - Since Ix 0, u = max I =5. X x (4) Third execution of WHILE statement: Since u = 5 > n, - C = I IA } U {I } = {IA IA IA 7 6 5 7 6 5 - x = {5} - {1, 2, 5} = 0 - Since Ix =, u = 0. x

90 (5) Since u = 0, C = {IA7 IA A5 7 6 5 From C = {IA IA IA}, we have: X = A3A4A7, X 7 6 5 1A2A6, X3 = A1A2A5. Clearly g.l.b.{A3A4A7, 1A2A6, A1A2A5} = A2A3A4A A6A7 and A3A4A7, 1A2A6 A 1A2 A5 e {A5 A6, A7}.5 Once the index sets of X,...,Xp e RS U {A+i ** An+m are determined by using SET_COVER such that g.l.b.{X1,..., Xp = X, we can compute IXI by applying (2.7) p-1 times using X1,..., Xp. We present an algorithm which takes the index set of X e RS and computes the cardinality of X. Let IBI = n and (RS, c) contain m expanded sublattices. PROCEDURE CAL_CARD (I ) // I is the index set of X. SETCOVER takes Ix and // // returns {I1,..., Ip} corresponding to {X1,..., Xp}// IF max I < n THEN CARD <- |D| ieI P(Ai; P(Ai)= IAil / IDI ELSE x BEGIN SETCOVER (I ) FOR i = 1 UNTIL p DO k. <- max Ii IF k1 < n; suppose k1 <... < kp THEN C_GLB <- IDI nieI P(Ai) ieI1 1 ELSE C_GLB <- jAk I 1 FOR i = 1 UNTIL p-1 DO BEGIN LUB <- I iI+1; LUB is the index; set of Xi v Xi+. IF LUB =0 THEN CLUB <- |DI ELSE CLUB <- CAL_CARD (LUB)

91 C GLB <- C GLB x IAk / C_LUB; use (2.7) i+1 I - <IUI Ii+ Ii U Ii+1 END CARD <- C GLB; CARD = IXI END END CALCARD The following examples show how to compute the cardinalities of arbitrary reachable sets by Procedure CALCARD. Example 4.3 In this example, we compute the cardinality of the reduced set by 010 = f41 in Example 4.1. For (RS, c) shown in Figure 4.1, let IDI = 10000, IA1J = 2500, |A21 = 4000, IA31 = 5000, jA4J = 6000, IA51 = 400, IA6I = 600, jA71 = 000. For = f K1 = A1A2A3A4A5 and K4 = A1A2A3A4A6A7 From the given cardinalities, IK11 = 120 and IK41 = 60. To compute |K1 A K.4 = 1A1A2A3A4A5A6A7|, we have to know JK1 v K4 = IA1A2A3A41 CAL_CARD computes I|X = IAA2A3A4A by taking Ix = {1 2, 3, 4} as inputs. Since max Ix = 4 = n, CARD = |DI P(A1)P(A2)P(A3)P(A4) 10000 x (1/4) x (2/5) x (1/2) x (3/5) = 300 = A1A2A3A41 By (2.7), IK1 A K41 = IK1I x IK41 / 300 24. Example 4.4

92 Suppose the lattice shown in Figure 4.1 is a sublattice of (RS, c) and l.u.b.Ki, K} = A1A2A3A4A5A6A7. We compute IA1A2A3A4A5A6A7I using CAL_CARD. (1) Main procedure: Since I = {1, 2, 3, 4, 5, 6, 7}, max I > n. X ' - From Example 4.2, SETCOVER(I ) returns I = {1, 2, 5}, 12 {1, 2, 6} and 13 = {3, 4, 71. - k = max I 5 k = 5, k 6, k3 = 7. - Since k1 > n, C_GLB = IA5| = 400. - For i = 1, LUB = 1I2 = {1, 2}. Since LUB ' 0, C LUB = CAL CARD ({1, 2}). From the first recursion, CLUB = 1000. C_GLB <- C_GLB x IAg6 / C_LUB = 240. 12 - I1 U 12 = {1, 2, 5, 6}. - For i = 2, LUB = I2I3 = 0. Since LUB = 0, C_LUB = IDI = 10000. C_GLB <- C_GLB x IA71 / IDI = 24. I3 - 2 UI3 = {1, 2, 3, 4, 5, 6, 7}. - |X| = C_GLB = 24. (2) First recursion: -Since max I = max {1, 2} < n, CARD = IDIP(A1)P(A2) = 1000. - xl = 1000. The cardinality of X = A1A2A3A4A5A6A7 is identical to that obtained in Example 4.3. In this rather complicated example, only one extra recursion is necessary. The reachable sets used in this example form a sublattice of the

93 D A1 A1A2 A1A2A3A4A5A6A7 The Hasse Diagram of the Poset of Reachable Sets Used in Example 4.4 Figure 4.2

94 lattice shown in Figure 4.1. This sublattice is depicted in Figure 4.2. ~ In order to use CAL_CARD, we have only to store the information of D, A1,..., An, An+1,., An+m instead of the whole lattice. Since n is usually small and it is rare that a reachable set becomes the greatest element of more than one expanded sublattice, CALCARD generally terminates after a few recursions. 4.2 Efficient Appoximation of Equation (2.6) In this section, we derive an efficient approximate formula to compute the cardinality of the set of values of a joining attribute reduced by a semijoin to an attribute associated with it. Then we validate the accuracy of the approximate formula by providing data from computer simulation. Suppose ah and aj are the attributes of Rg. The effect of fij on IKhi is determined using (2.6), as presented in Chapter 2, as follows: |KhN| = m x [1 - n= {(nxd - i + 1)/(n - i + 1)}] h hNI- mx~l i=1 (2.6) where m = IKhI, k = IRgNI, n = IRg| and d = 1 - 1/m Since k is the number of tuples belonging to the reduced relation after a semijoin, k may be very large. In this case, k iterations required in (2.6) take a long computation time. We must eliminate the term involving the

95 iteration from (2.6) while preserving sufficient accuracy. In the literature, the following piecewise linear approximation of (2.6) was suggested in [CCA 80b]: k for k < m/2 KhN (k+m) / 3 for m/2 ~ k < 2m (4.3) m for 2m < k The above approximation generally produces large error because of the discontinuity of the formula. Especially, the amount of error is prohibitive near k = m/2 and k = 2m. We approximate (2.6) from its derivation procedure. It was shown in [YAO 77] that /IIk {(nd - i + 1)/(n - i + 1)} = C d / C where Cn denotes C. Since r n r C d / Ck = {(n-n/m)!(n-k)!}/{n!(n-n/m-k)!} we have C^d / C" = {(n-k)!/(n-n/m-k)!}{(n-n/m)!/n!} {(n-k)/ n {(n-k) / n/n/m = (1 - k/n)n/m (4.4.a) and Cnd / Cn = {(n-n/m)!/(n-n/m-k)!}{(n-k)!/n!} k k = {(n-n/m) / n}k

96 = (1 -./m) k From (4.4.a) i m x (1 - (1 - k/n)n/m). From (4.4.b), IKhNI = m x (1 - Cd/C) m x (1 - (1 - 1/mk). (4.4.b) (4.5.a) (4.5.b) By taking the smaller exponent error from approximation, we approximate formula: IKhNI = m x (1 - (1 - k/n)n/m) im x (1 - - (1- /m)k) in order to decrease the obtain the following if n/m < k, otherwise. (4.6) As pointed out in [YAO 77], it is obvious that IKhNI = m if k > n - n/m or m = 1. In summary, we can compute IKhNI as follows: k 1 IKhNI = m m(1-(1-k/n)n/m) m(l-(1-1/m) k) if if if if if m = n m = 1 1<m<n and k>n-n/m 1<m<n and n/m<kqn-n/m 1<m<n and k-min(n-n/m, (4.7) n/m) (2.6), 10000, We have performed the computer simulation of (4.3), (4.5.a) and (4.5.b) for n = 50, 100, 1000,

97 100000 and various values of m and k for each n. The result of the simulation shows that the errer generated by (4.6) is practically negligible and that the choice made between (4.5.a) and (4.5.b) depending on the values of k and n/m is always correct. Some of the data obtained from the simulation are presented in Tables 4.1 through 4.4. Table 4.1 shows the values of IKhNI for n = 100 and m = 30. Note that (4.6) is still effective when n/m is not an integer. Table 4.3 shows the data for n = 10000 and m = 100. Since n/m = 100, (4.5.a) and (4.5.b) produce the same results for k = 100. For k < 100, (4.5.b) is more accurate, whereas (4.5.a) is more accurate for k > 100. The plots of %error incurred by using (4.6) vs. k for n = 1000, m = 500 and for n = 10000, m = 2000 are shown in Figure 4.3.

98 Table 4.1 Comparison of Approximations of Equation (2.6) for n = 100 and m = 30 I k (2.6):YAO (4.5.a)) (4.5.b)3):CCA I ~ ~ ~ ~,.,.... I 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 75 90 Il 2.93 5.65 8.18 10.51 12.67 14.65 16.47 18.13 19.65 21.02 22.26 23.37 24.37 25.26 26.04 26.73 27.33 27.85 28.29 28.67 29.74 29.99 2.90 5.59 8.09 10.41 12.55 14.52 16.33 17.98 19.49 20.86 22.10 23.22 24.22 25.12 25.91 26.61 27.22 27.75 28.20 28.59 29.70 29.99 I I I 2.90 5.52 7.89 10.03 11.96 13.70 15.28 16.70 17.99 19.15 20.20 21.15 22.00 22.78 23.48 24.11 24.68 25.19 25.66 26.08 27.64 28.58 3.00 6.00 9..00 12.00 15.00 16.00 17.00 18.00 19.00 20.00 21.00 22.00 23.00 24.00 25.00 26.00 27.00 28.00 29.00 30.00 30.00 30.00 1 I

99 Table 4.2 Comparison of Approximations of Equation (2.6) for n = 1000 and m = 500 k (2.6):YAO (4.5.a) (4.5.b) (4.3):CCA ' -1 - -- -- - - I 50 100 150 200 250 300 350 400 450 500 550 600 650 700 750 800 850 900 48..78 95.05 138.82 180.09 218.86 255.12 288.89 320.14 348.89 375.14 398.89 420.13 438.87 455.11 468.85 480.08 488.82 495.05 48.75 95.00 138.75 1.80.00 218.75 255.00 288.75 320.00 348.75 375.00 398.75 420.00 438.75 455.00 468.75 480.00 488.75 495.00 I I 47.63 90.72 129.70 164.97 196.89 255.76 251.88 275.51 296.90 316.24 333.75 349.58 363.91 376.87 388.60 399.21 408.81 417.50 50.00 100.00 150.00 200.00 250.00 266.67 283.33 300.00 316.67 333.33 350.00 366.67 383.33 400.00 416.67 433.33 450.00 466.67 483.33 950 498.77 498.75 425.36

100 Table 4.3 Comparison of Approximations of Equation (2.6) for n = 10000 and m = 100 [ k (2.6):YAO (4.5.a) [(4.5.b) (4.3):CCA................. i I 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 180 200 300 I 9.57 18.23 26.06 33.16 39.58 45.38 50.64 55.39 59.69 63.58 67.10 70.28 73.16 75.76 78.11 80.23 83.89 86.87 95.32 I i 9.52 18.14 25.95 33.02 39.42 45.22 50.46 55.21 59.51 64.00 66.92 70.10 72.98 75.58 77.94 80.07 83.74 86.74 95.24 9.56 18.21 26.03 33.10 39.50 45.28 50.52 55.25 59.53 64.00 66.90 70.06 72.92 75.51 77.85 79.97 83.62 86.60 95.10 -j 10.00 20.00 30.00 40.00 50.00 53.33 56.67 60.00 63.33 66.67 70.00 73.33 76.67 80.00 83.33 86.67 93.33 100.00 100.00 100.00 -i 16 500 99.42 I 99.41 99.34

101 Table 4.4 Comparison of Approximations of Equation (2.6) for n = 10000 and m = 2000 k (2.6):YAO (4.5.a) (4.5.b) (4.3):CCA 400 369.49 369.25 362.61 400.00 1000 819.51 819.02 787.07 1000.00 1600 1164.16 1163.58 1101.50 1200.00 2200 1423.07 1422.57 1334.42 1400.00 2800 1613.44 1613.02 1506.96 1600.00 3400 1749.89 1749.53 1634.77 1800.00 4000 1844.77 1844.48 1729.45 2000.00 4600 1908.39 1908.17 1799.58 2000.00 5200 1949.18 1949.04 1851.54 2000.00 5800 1973.94 1973.86 1890.02 2000.00 8000 1999.36 1999.36 1963.40 2000.00

102 %ERROR 0.08 n - 10000 m - 2000 0.04 0 1000 3000 5000 0 1000 3000 5000 % ERROR 0.08 - n = 1000 m - 500 0.04 k 0 200 400 600 800 The Plots of %Error Incurred by Using Equation (4.6) vs. k Figure 4.3

CHAPTER 5 AN OPTIMIZATION ALGORITHM An optimization model for distributed query processing was described in Chapter 3, and a method to estimate intermediate results of a query was developed in Chapter 4 based on the lattice model in Chapter 2. In this chapter, an algorithm which solves the optimization model will be presented. 5.1 Complexity Consideration of Optimal Algorithms In this section, the computational complexity involved in finding an optimal solution will be discussed. It has been proven [HEVN 79a] that the distributed query optimization problem is NP-hard. Furthermore, it is unlikely that any of the existing optimization techniques can be used to solve the model because of the complexity of the state transition function s and the unconstraint of the final state in the optimization model. We will examine the sizes of the solution spaces for distributed queries to measure the amount of computational effort when exhaustive searches are made to determine optimal solutions. Since it is not always possible to compute the size of the solution space of a distributed 103

104 query, a few different cases will be considered separately to take advantage of the structure of the query. In all cases, the number of relations referenced by a query is n. CASE 1 There is one domain on which all joining attributes are defined. n relations referenced by a query are all singleton joining relations. Since a singleton joining relation is ignored after an outgoing semijoin from the relation, the maximum length of a sequence of semijoins is n-1. The number of possible semijoins is nP2, where P denotes the number of permutations of n elements, taken r at a time. Hence, the number of sequences of semijoins with length X are as follows: X=0: 1 X=1: nP2 X=2: nP2 x n-1P2 X=k: nP2 x n-1P2 x *. x n-k+1P2 The total number of sequences of semijoins involved in an exhaustive search is given by 1 + i n-1 ( k-1 ) (5.1) 1 x~ k=O n-kP2 The value of (5.1) for n = 2,..., 6 is given in Table

105 5. 1. Table 5.1 The Size of the Solution Space for CASE 1 n Number of Sequences 2 3 3 19 4 229 5 4581 6 137431 CASE 2 There is one domain on which all the joining attributes are defined. Each of the n relations includes target lists. The number of possible semijoins is nP2 which is n2-n. Since each semijoin can appear only once in a sequence of semijoins, the maximum length of a sequence of semijoins is nP2. Hence the total number of sequences of semijoins involved in an exhaustive search in this case is given by 2 n 1 + n -n 2 P = 1 '-n 'x (5.2) The value of (5.2) for n = 2,3,4 is given in Table 5.2. CASE 3 In this case, a distributed query in considered. There are more than one domain. general is There are

106 Table 5.2 The Size of the Solution Space for CASE 2 n Number of Sequences 2 5 3 1957 4 > 10, i I.u...,.... relations which include joining attributes defined on different domains. Joining attributes in such relations are associated with other joining attributes. Since a semijoin fij can appear more than once in a sequence of semijoins because of the semijoin to an attribute associated with ai, the maximum length of a sequence of semijoins can not be computed. Consequently, the size of the solution space can not be derived. From the above discussion, it is obvious that an exhaustive search method is prohibitive in finding an optimal solution for distributed query processing. As observed in CASE 3, one of the major difficulties is the possible reoccurrence of a semijoin in an optimal sequence of semijoins. For this reason, the length of an optimal sequence of semijoins can not be determined a priori. 5.2 A Block-Oriented Heuristic Algorithm

107 In this section, we present the main features of our heuristic algorithm for deriving a sequence of semijoins. Further, we discuss the heuristics on which these features are based. Hereafter, a modular approach will be used to explain algorithms. A high-level description of a procedure will be given in pseudo-codes. Parts of a procedure that need to be elaborated will be described as independent procedures. So far, no general heuristic method has been developed in the field of optimization for NP-hard sequencing problems. One technique generally applicable for sequencing problems is a neighbourhood search technique [BAKE 74]. This technique consists of the construction of a seed sequence followed by exchanges of positions of elements in the seed sequence. Ih our case, however, the neighbourhood search technique is very inefficient, since the number of sequences that can be generated from a seed sequence of length n is n!-1 and the cost of each of these n! sequences must be computed independently of the cost of another sequence already computed. The net benefit ni of a semijoin 0i is the difference between the benefit bi, the amount by which it reduces a relation, and the cost ci, the amount of data transferred for its execution. A semijoin may not have net benefit at all or it may not have significant net benefit. However, it may cause substantial net benefits for the subsequent semijoins. Therefore, placing such semijoins with low cost

108 in the front part of a sequence of semijoins can decrease the cost of a query considerably. In order to achieve this in an efficient manner, we make use of the structure of a query. For a given query, a block is a set of attributes defined on the same domain. A semijoin is possible between any pair of attributes in a block. Since blocks are linked through attributes in the same relations, the reduction of the cardinality of the set of values of attributes in one block can reduce those in other blocks. Our strategy is to process a block as a unit. That is, we select a block and schedule a sequence of semijoins among the attributes of the block, such that the cost of this sequence is minimal and the reduction caused by the sequence is maximally utilized in processing the subsequent blocks. Since there are smaller number of blocks than that of semijoins, processing a block as a unit leads to an efficient solution algorithm. Block-oriented processing is divided into three major modules discussed in the following subsections. 5.2.1 Process Blocks This subsection discusses how a block to be processed can be selected and processed. First, we consider the processing of a selected block. Definition 5.1: Let an attribute ai be defined on a domain Dk. The density di of ai is IKil|/Dkl.

109 Consider a block Bk = {a1,..., an. Initially Ki = Ai for all i, and fij reduces dj to didj. Hence if dh < di, then ah has more reductive power. Suppose d1 <... < dn for Bk. The basic strategy to process a block is to perform f2' *e fn-i n to achieve a maximal reduction within a block with a minimal cost. Processing a block by scheduling semijoins which go from the attribute with the smallest density in a block to the one with the largest density is called a block visit. We make the following observations about visiting a block which are useful in reducing the query cost: (1) It is generally beneficial to finish the visit of a block at an attribute associated with a joining attribute of an unvisited block. By reducing the values of that attribute with the maximal reductive power of the block being visited, the costs of subsequent block visits can be reduced. (2) If an attribute ai in a block Bk is not associated with any attribute in other block and if the visit to the block Bk does not end in ai, then the attribute ai can be excluded from further scheduling of semijoins because the values of a. are contained in the current values of some other attribute in the block Bk. After a block is visited, the remaining attributes are called active attributes, and the excluded ones inactive attributes.

110 Next, we consider the selection of a block to be processed. Suppose Bk = {al,..., a } with dl <... < dn. The amount of data' transferred by the first semijoin f12 in visiting a block Bk is IK1IW1 = IDkldlwl. Since IK2| = IDkld2 is reduced by f12 to IDkldld2, the amount of data transferred by f23 is IDkld1d2wl and is less than the data transferred by fl2. Following this argument it is easy to see that the amount of data transferred by each semijoin in visiting Bk is bounded by IK11W1. Therefore, we have elected to take IK11 W1 as a part of a measure for selecting the next block to be visited. In order to use the visit of a block to reduce the cost of visiting other blocks, we consider not only the cost incurred, but also the reductive power achieved by visiting a block when the next block to be visited is selected. Since Bk contains at least two joining attributes, dld2 is a rough approximation of the reduction achieved by visiting Bk. To complete the measure for selecting the next block, we, therefore, multiply IK1jw1 by a penalty factor 1 + dld2, and we define the block cost BC(k) of an unvisited block Bk as follows: BC(k) = IK1|w1(1 + d1d2) (5.3) The purpose of procedure PROCESS_BLOCKS is basically to 'The data transfer incurred by transmission overhead is not considered in order to avoid notational complexity. This does not cause any difference for the purpose of analysis.

111 select and visit an unvisited block from the set of unvisited blocks with the least value of the block cost defined by (5.3) until there is no unvisited block left. Procedure PROCESSBLOCKS, which includes some control features, will be presented in the next section. The following variables are defined to explain the algorithms: (1) B: the set of all blocks (2) US: the set of unvisited blocks (3) VB: the set of visited blocks (4) SVB: the sequence of visited blocks (5) 0: the sequence of semijoins being scheduled (6) A(B): the set of active attributes in block B (7) SI(B): the sequence of inactive attributes in block B AB(a.) is the set of blocks which contains the attributes associated with ai. The elements of AB(ai) are called the associate blocks of ai. The set of end associate blocks, END_AB, at the end of visiting a block Bk which ends in ai is given by AB(ai) f2 UB. Initially UB = B, VB = 0, A(B) = B, o = 0, SI(B) = 0, and END AB = 0. Procedure BLOCK VISIT is shown below. PROCEDURE BLOCK VISIT(B) //Suppose A(B)={ai,..., ain} // sort A(B) in ascending order of |Kij| //Suppose sorted list is {al,..., an}// For i=1 To n-1 Do BEGIN

112 append fiil to o and reflect the effect2 of f i+ on the database state IF ai is unassociated THEN BEGIN A(B) -(B) -{ai} append ai to SI (B) END END IF a is unassociated AND a e A(B)-{a } is n n associated with an attribute in Bk e UB U VB THEN //Suppose A8 c UB U VB is the set of blocks in// //which the attributes associated with an attribute// //in A(B)-{a } are contained// BEGIN IF AaB I Ug ~ 0 THEN //associated with an attribute in an // //unvisited block// BEGIN FOR {ai e A(B)-{a n} ai is associated with an attribute in AOB Q UB} DO FOR {Bj e AB 2 UB|a e Bj is associated with ai} DO compute block cost BC(j) after fni select ai with minimum block cost after fn END ELSE select ai associated with an attribute in most recently visited block in SVB append fni to o and reflect the effect of fni on the database state A(B) <- A(B)-{a } n append a to SI(B) END IF IA(B)I > 1 //B contains more than one active attribute// THEN BEGIN 2The effect of a semijoin on the database state is discussed in chapters 2, 3 and 4.

113 Vg <- Vf U {B} append B to SV6 END END BLOCK VISIT 5.2.2 Reverse Process Blocks This subsection discusses how to make use of the reduction of sets of values of joining attributes after all blocks have been visited. In procedure PROCESS_BLOCKS, the reductive power of a visited block is utilized by subsequent block visits whenever possible. Consequently, a block visited later benefits by the reductions achieved by the blocks visited earlier. In order to reduce the sets of values of joining attributes in the blocks visited earlier, using the reductive power of a block visited later, roughly the order of visits are reversed with respect to the order of visits during PROCESS_BLOCKS. Note that in procedure BLOCK_VISIT, a block which has more than one active attribute after it has been visited is appended to the sequence of visited blocks, because at least two joining attributes are necessary in a block to perform a semijoin. Procedure REVERSE_PROCESS_BLOCKS is given below. In REVERSEPROCESS BLOCKS, we make sure that a block has more than one active attribute, since some control features which will be explained in the next section may have excluded active attributes after the block has been visited.

114 PROCEDURE REVERSEPROCESS BLOCKS(SVB) REPEAT B <- the last block in SVB IF B e vB AND B has more than one active attribute THEN BEGIN //Suppose A(B)={ai, '..., ain}// sort A(B) in ascending order of |Kij1 //Suppose sorted list is {an,..., a }// FOR i=n DOWN TO 2 DO IF f.ii-1 reduces |KiJl at least by 1 THEN BEGIN append f ii. to o and reflect the effect of f ii on the database state 1,i-1 IF ai is unassociated THEN BEGIN A(B) <- A(B)-{ai} append ai to SI(B) END END V* <- V-{ B} END delete B from SVB UNTIL SVB = 0 END REVERSE PROCESS BLOCKS 5.2.3 Completion In this subsection, we present an algorithm which reduces the size of the relations containing inactive attributes and with at least one target attribute using the reductive power accumulated in active attributes. The sets of values of active attributes are reduced not only by procedure PROCESS_BLOCKS but also by procedure REVERSE PROCESS BLOCKS. For each block, the active

115 attribute with the smallest set of values is selected, then a sequence of beneficial3 semijoins from this attribute to inactive attributes is scheduled. Procedure COMPLETION is shown below. PROCEDURE COMPLETI ON FOR k=1 TO |I| DO IF A(Bk) ~ 0 AND SI(Bk). 0 THEN BEGIN //Suppose A(Bk) = {al,...,ai and // //SI(Bk) = ai, ai+1,.., an // select a e A(Bk) such that IKj is the minimum s <- j t <- i WHILE t < n DO BEGIN IF n > 0 st THEN BEGIN append fst to o and reflect the effect of ft on the database state s - t END t <- t+1 END END END COMPLETI ON 5.3 Control Features In this section, we present additional procedures which increase the robustness of the block-oriented heuristic algorithm for random input data. Throughout the development of the block-oriented 3A semijoin 0i is beneficial if ni = bi-ci > 0

116 heuristic algorithm, the stress test of the algorithm has been. performed. We have tried to break up the algorithm by providing unusual input data. Solution produced using the main features alone are sometimes not sufficiently close to optimum. Additional control features are, therefore, necessary. A few control features have been incorporated in the algorithm to obtain better solutions. These control features are mainly designed to take care of unusual database states and complex queries, and, therefore, are not invoked for typical applications. Four control features are presented in the following subsections. 5.3.1 Initial Inactivation of Attributes This subsection discusses the exclusion of unassociated joining attributes with high initial density to avoid semijoins which are neither beneficial themselves nor useful for subsequent semijoins. Even if a semijoin fij is not beneficial, if it reduces IKjl significantly, it can be useful to increase the benefits of subsequent semijoins. However, if the initial density of ai is high, fij may not be beneficial and the reduction of |Kjl is only IKjl(1-di). Therefore, in case the initial density of an unassociated attribute ai is high, it is better to exclude ai before using procedure PROCESS_BLOCKS, and then perform a semijoin to ai in procedure COMPLETION.

117 In the algorithm, an attribute ai is rendered inactive if its initial density is equal to or greater than 0.8. This value was determined from many query examples. Suppose a block contains unassociated attributes ai,..., ai+j with initial density equal to or greater than 0.8. These attributes are sorted in ascending order of their densities, and the sorted sequence of inactive attributes is appended by attributes inactivated by procedure BLOCK_VISIT. In this way, the reductive power of attributes ai,..., ai+j, although insignificant, is maximally utilized. Procedure INIT ATTR INACTIVATION is shown below. PROCEDURE INIT ATTR INACTIVATION FOR k=1 TO I|l DO //Initially A(Bk) = Bk and SI(Bk) = 0// BEGIN //Suppose Bk = {akl,..., akn}// FOR j=1 TO n DO IF dkj > 0.8 AND akj is unassociated //Suppose R is the relation of which akj is// //an attribute// THEN IF R t SJR OR R in user site THEN BEGIN A(Bk).- A(Bk)-{akj} append akj to SI(Bk) END IF ISI(Bk)I > 1 THEN sort SI(Bk) in ascending order of dkj IF IA(Bk)I < 2 THEN UB <- UB-{Bk} END END INIT ATTR INACTIVATION

118 5.3.2 Path Construction In this subsection, we shall describe the way to make better use of the reductive power accumulated in visited blocks to reduce the cost of visiting an unvisited block. Suppose BC is a candidate for the next block to be visited and there is an attribute aC e BC such that aC is associated with ajl in a visited block Bpl, and ail is an associated attribute with the smallest set of values in Bp1. Since filjl can reduce IKCI, fil jl may help reduce the total query cost by decreasing the cost while increasing the benefit of visiting BC if BC is selected as the next block to be visited. Likewise, if ail is associated with aj2 in a visited block Bp2, Bpl ~ Bp2, and ai2 is an attribute with the smallest set of values in Bp2, then fi2 j2 followed by fi,jl may be more beneficial than fi1 jl alone. In this way, we can construct a path consisting of a sequence of semijoins leading to a candidate for the next block to be visited. Each semijoin in the path is from a visited block. In order to construct the most profitable of many possible paths, we define the cost function of a path as follows: Let Ir be a path consisting of a sequence of semijoins 0op'..., pn where 0pi' 1 < i < n, is a semijoin between two attributes in a visited block Bpi. Let BC be a candidate for the next block to be visited. The cost function, of path r leading to BC, used in determining a path is given by

119 P(, = C)1 Cpi - Ei= bi + BC(C) -Ei=1 npi + BC(C) (5.4) Note that the block cost of BC also depends on path IT because the set of values of an attribute in BC is reduced due to the semijoins in T. We now define the symbols which are used in procedure BUILDPATH given below. PB = {Bpi 1 < i < n}. For each a e BC when Tr = 0 and for each a e Bpl when Tr 0 we define CAND_PB(a) = {Bk e AB(a) Q VB | there exists ah e Bk which is associated with a and ag e A(Bk) such that dg < dh}. = {a e Bc | CAND_Pa(a) ~ 0}. a* is an element of a with minimal density. PROCEDURE BUILDPATH(B,) PB <- 0 //Initialize the path with a null sequence of semijoins// r <- 0 IF o ~ 0 THEN BEGIN select a e a a0 <- a * <- CAND_PB(a0) REPEAT select B. e B* such that if 0Bj is the semijoin from the attribute with the smallest density in Bj to the attribute associated with a0 then Pn(0Bj,', C) is minimum PB <- PB U {Bj} T <- 0Bj'

120 //Suppose 0Bj fxy// a0 <- a B <- CAND_PB(a0) - PB UNTIL * = 0 //Suppose 'T = 0pl, p2 ' '' 0pn// select Tij = 0pj, 0pj+l... 0pn c such that Pn (rj,C) is minimum Tr <- Tj END END BUILDPATH Procedure BUILD_PATH is an indecomposable control feature of procedure PROCESS_BLOCKS mentioned in Section 5.2. Now that procedure BUILD_PATH has been presented, we are in the position to elaborate on the procedure PROCESS BLOCKS. In selecting a block to be visited, we sometimes choose two candidate blocks. This also serves to prevent the degeneration of the performance of the distributed query processing algorithm for unusual database states. After the initial local processing, END_Aa = 0. After the block Bk is visited ending with ai, the sets of values of attributes associated with ai are reduced, not only by the reductive power of Bk, but possibly the reductive power of the previously visited blocks. Hence if END_AB ~ 0, we select B c e END_AB with the minimum block cost as a candidate block to be visited next. It is usually the case that Bcl has the smallest block cost among all unvisited blocks, and is visited next. However, if this is not the

121 case, we select another candidate block, Bc2, with the minimum block cost among the blocks in UB. We build paths for both of the candidate blocks using (5.4) before selecting one as a block to be visited next. In comparing the two candidate blocks, we use another cost function as follows: Let E and BC be defined as before. The cost function, of path Tr and candidate block BC, used in selecting the next block to be visited is given by PC(T C) = = Cp + BC(C) (5.5) By using (5.4) in constructing a path for a selected block, we use the reductive power of visited blocks as much as possible. By using (5.5) in selecting the next block to be visited, the cost incurred by a sequence of semijoins is kept as low as possible. In case END_AB = 0, only one candidate block, Bcl, is selected such that Bc1 is with the minimum block cost among the blocks in UB. Procedure PROCESSBLOCKS is shown below. PROCEDURE PROCESS BLOCKS END_A <- 0 WHILE US ~ 0 DO BEGIN find candidate blocks //NUM CAND is the number of candidate blocks// //Trc is the path for candidate block Bci// FOR i = 1 TO NUM CAND DO BUILDPATH(B ) ci

122 //BN is the next block to be visited and T// //is the path to it// IF NUM_CAND = 1 OR Pc (c ' c1) < Pc (c2 c2) THEN BEGIN B. <- B N C- 1 I f- 'lcl END ELSE BEGIN BN - Bc2 T <- Tc2 END //Process the path and visit the block// append r to o and reflect the effects of semijoins in r on the database state append the sequence of visited blocks, corresponding to the sei ijoins in T, to SVB VISIT_BLOCK(BN) //Suppose visit ends with a e BN// Up <- - {BN} END_AB <- AB(a) Q UB END END PROCESS BLOCKS 5.3.3 Hill-Climbing A hill-climbing technique can be adopted before using procedure COMPLETION to further decrease the query cost. Only the semijoins between active attributes need to be considered. In order to maintain the efficiency of the algorithm at the same time decrease the query cost, the beneficial semijoin which has the least cost is appended to the scheduled sequence of semijoins until no such semijoin is available. Basically, the semijoins are checked in ascending order of their costs until a beneficial one is found.

123 Procedure HILLCLIMBING is shown below. PROCEDURE HILL CLIMBING SET_ACTIVE <- Uk A(Bk) where the union is performed over those k for which IA(Bk)I > 1 TEMP ACTIVE <- SET ACTIVE WHILE TEMP ACTIVE ~ 0 DO BEGIN select ai e TEMP_ACTIVE such that the cost of fix to its equivalent joining attribute ax is the least select aj e TEMP_ACTIVE such that nij is the largest IF n.. > O THEN BEGIN append fij to o and reflect the effect of fij on the database state TEMP ACTIVE <- SET ACTIVE - {a.} END ELSE TEMPACTIVE <- TEMPACTIVE - {ai} END END HILLCLIMBING 5.3.4 Screening In this subsection, a procedure which deletes obviously unnecessary semijoins scheduled by the procedures previously described will be presented. Suppose o = 01'.. 0t. Specifically, the following improvements are considered: (1) Let 0 = fij and aj be an attribute of relation R. If 0m neither comes from nor goes to the attribute of R for all m > h, 0h can be deleted from o without affecting the costs or benefits of other

124 semijoins. In this case, if n. < 0, the deletion of 0h decreases the query cost. (2) Let 0h and R be defined as in (1), and ai be an attribute of R'. In addition, let R be at the user site. If 0m does not go to an attribute of R' for all m > h, IR' I will not be reduced after 0h. In this case, by moving R' to the user site instead of performing 0h, the cost of 0h is saved. Procedure SCREENING is shown below. PROCEDURE SCREENING //Suppose o = o1, '... 0t// FOR h = t DOWN TO 1 //Suppose 0h =fij and aj is an attribute of R// IF nij < 0 THEN IF 0m neither comes from nor goes to the attribul of R for all m > h THEN delete 0h from o //Suppose o = 01 '.' 0 s STU is the set of// //relations at the user site// IF STU ^ 0 THEN FOR h = s DOWN TO 1 //Suppose 0h = fij, and ai and aj are attributes// //of R' and R, respectively// IF R e STU THEN IF 0m does not go to the attribute of R' for all m > h THEN BEGIN delete 0h from a insert "move R'" at the position of 0h END te

125 END SCREENING 5.4 Algorithm H and Its Complexity Analysis In summary, Algorithm H which generates a sequence of semijoins to process a distributed query consists of the procedures presented in Sections 5.2 and 5.3. Algorithm H is presented below. Algorithm H INPUT: User query and the initial database state OUTPUT: Sequence of semijoins INIT ATTR INACTIVATION PROCESS BLOCKS IF VB ~ 0 THEN REVERSE_PROCESS_BLOCKS HILLCLIMBING COMPLETION SCREENING We now consider the time complexity of Algorithm H. The measure of the complexity is the number of sequences of semijoins generated in accordance with the complexity of an exaustive search method discussed in Section 5.1. The existence of procedure HILL_CLIMBING in Algorithm H makes it difficult to derive a narrow-bound time complexity. Suppose there are s possible semijoins and m relations involved in processing a query, then there are s choices for

126 the ith semijoin in the sequence of semijoins being generated by procedure HILL_CLIMBING. The length X of the sequence of semijoins, however, cannot be determined a priori as mentioned before. Since a beneficial semijoin has to reduce at least one tuple in a relation, in the worst case X _ E=l1 IRil. Hence the worst case complexity of procedure HILLCLIMBING is O(sEm1|IR) Fortunately, procedure HILL_CLIMBING is a refinement feature and very seldom utilized. The derivation of the worst case complexity of procedure BUILDPATH is as follows: Let m = |I| and x the length of the path being constructed by procedure BUILDPATH. Since UB ~ 0 when procedure BUILD_PATH is invoked, X < |Iv < m-1. In the worst case, procedure BUILDPATH generates X(m-x) sequences when X = 1, 2,..., m-1. Therefore, the total number of sequences generated is E;:_1 X(m - x) m-1.1 m- 12 = m(2 X= ) -, 12 = m{(m-1)m/2} - (m-1)m(2m-1)/6 = (m3 - m)/6. Hence the worst case complexity of procedure BUILD PATH is 0(1 13). Just like procedure HILL_CLIMBING, procedure BUILD_PATH is very seldom utilized. Since most queries are handled only by the main

127 features of Algorithm H, we shall consider the complexity of the main features of Algorithm H. Theorem 5.1: The worst case complexity of the main features of Algorithm H without procedure BUILD_PATH is O(n*1| ), where n = max {J|B I B e $}. Proof: Procedures PROCESS BLOCKS, REVERSEPROCESS_ BLOCKS, and COMPLETION, the main features of Algorithm H, are sequentially invoked. Since some of the active attributes become inactive after the invocation of procedure PROCESS_BLOCKS, the number of sequences generated by procedure PROCESS_BLOCKS is greater than or equal to that by either of the other two procedures. Hence we have only to consider the complexity of procedure PROCESSBLOCKS. Procedure PROCESS_BLOCKS has two major loops, one embedded within the other. For each block in 8, procedure BLOCK_VISIT generates sequences of semijoins. Consider B = {a1,..., an} e B such that dl 5... < dn. Procedure BLOCK_VISIT schedules a sequence f12, '' ' fn-l,n' which may be appended by a semijoin fnj where 1 < j < n-1. Therefore, procedure BLOCK VISIT generates one sequence of length X, for X = 1,..., n-1, and maximum n-1 sequences of length n. The maximum number of sequences that can be generated by procedure BLOCK_VISIT is 2(n-1). Since n < n*, the worst case complexity of procedure PROCESS_BLOCKS is O(n *||). *

CHAPTER 6 TESTING THE SOLUTION ALGORITHM Algorithm H presented in the previous chapter has been implemented in PASCAL and runs on Amdahl 470V/8 under the Michigan Terminal Systems at the University of Michigan. The purpose of this chapter is to evaluate the performance of Algorithm H with respect to the effectiveness of the data reduction as well as the efficiency. The results of the test runs of the PASCAL program implementing Algorithm H are presented. In addition, comparisons with the results of other algorithms are made. 6.1 Data Traffic Reduction The goal of distributed query optimization is to minimize the data traffic incurred by a distributed query in a computer network. Reference solutions are needed to evaluate the solutions produced by Algorithm H. Since no optimal algorithm is available except an exhaustive search method for distributed query optimization, and the use of exhaustive search methods is prohibitive even for small-size queries as discussed in Section 5.1, the solutions produced by other algorithms in this area are used as a basis for comparison. 128

129 In order to make objective comparisons, we have selected examples from recently published papers [HEVN 79b, BERN 81, CHEU 82], which have similar formulations of the problem to ours, as benchmarks for tests. Further, an example is constructed to illustrate a particular feature of Algorithm H. Using these examples, we also show the execution steps of Algorithm H for different queries and database states. Throughout the computations involved in algorithms, the costs, benefits and cardinalities are first computed in real numbers, then the results are given in integers by rounding the real numbers. In actual databases, the cardinalities of tuples in relations or those of attribute values are integers. However, integer arithmetic is not only inappropriate to the nature of the statistical estimation method being used, but is also the source of computational overhead. Example 6.1 The example by Hevner and Yao [HEVN 79b] is considered. This example is also used by Cheung [CHEU 82]. The database has the following four relations each of which is located at a different site: EMPLOYEE(E#, ENAME, SEX) COURSE(C#, CNAME, LEVEL) STUDENT COURSE(E#, C#) TEACHER COURSE(E#, C#, ROOM)

130 The relation TEACHERCOURSE is at the user site. The query is: for all male employees who are teaching advanced courses in Room 103 and are students in at least one course, list the employees' names and the courses they are teaching. The relational form of the query is as follows: F I ND (EMPLOYEE.ENAME, COURSE.CNAME) WHERE (EMPLOYEE.E# = STUDENTCOURSE.E#) AND (EMPLOYEE.E# = TEACHERCOURSE.E#) AND (TEACHERCOURSE.C# = COURSE.C#) AND (COURSE.LEVEL = 'Advanced' ) AND (TEACHERCOURSE.ROOM = '103') AND (EMPLOYEE.SEX = 'M') The parameters for the query and the database are defined as follows: R = COURSE, R2 = TEACHER_COURSE R = EMPLOYEE, R4 = STUDENT_COURSE a1 = COURSE.C# a2 = TEACHERCOURSE.C# a3 = TEACHER_COURSE.E# a4 = EMPLOYEE.E# a5 = STUDENTCOURSE.E# 5 ac = COURSE.CNAME ae = EMPLOYEE.ENAME After initial local processing, the reduced query and the given initial database state are shown below.

131 The reduced query: FIND (ac, ae) WHERE (a = a) AND (a3 = a4) AND (a4 = a5) From the reduced query, we have B1 = {a1, a2} and B2 = {a3 a4, a5} The initial database state is: IR11 = 100, IR2j = 300, IR31 = 200, IR41 = 600 IAJ = 100, IA21 = IA31 = IA41 = 200, IAg5 = 600 w. = 1 for i = 1,..., 5 w = 11, w = 9 c e ID11 = 400, lD2I = 1000 In accordance with Hevner and Yao's example, the communication network parameters, fixed overhead Vf and proportional coefficient u, are set to 10 and 1, respectively. Then the initial cost of moving R1, R3 and R4 after initial local processings to the user site is 3830. For Hevner and Yao's method, the reported cost of the query [HEVN 79b] was 1324. The cost reported by Cheung's method [CHEU 82] was also 1324. We compute the cost for the same example by Algorithm H and the SDD-1 algorithm [BERN 81] using our estimation method for the cardinalities of reduced relations.

132 Query cost by Algorithm H The lattices L1 and L2 for B1 and B2, respectively, and the changes of Ki's during the application of o are shown in Figure 6.1. The changes of values of database state variables after each semijoin in o are shown in Table 6.1 along with bi, ci and ni for each semi join. 1. INIT ATTR INACTIVATION Since di < 0.8 for all ai, all the attributes are initially active. 2. PROCESSBLOCKS (1) Since initially END_AS = 0, a block to be visited is selected from U8 = {B1,B2} with the minimum block cost. Using (5.3), BC(1) = |K1jw1.(1 + dld2) = 100 x 1 x (1 + 0.25x0.5) = 112.5 BC(2) = IK3lw3(1 + d3d4) = 200 x 1 x (1 + 0.2x0.2) = 208 Since BC(1) < BC(2), B1 is selected for the visit. (2) Since VB = 0, no path is built for B1. By procedure BLOCK_VISIT, 01 = f12 is appended to o, and al is inactivated. After f12, a new set A3A6 which represents the reduced K3 is formed. After B1 is visited, U = END_A5 = {B2}. Since B1 has only one active attribute, B1 is not included in VB.

133 A1 \ 1A2 \ AIA2 A1A2A7 The Expansions of the Lattces by the The Expansions of the Lattices by the Sequence of Semijoins Generated by Algorithm H for Example 6.1 Figure 6.1

134 A5,A4A5 A3A6 A3A4A6 Figure 6.1 continued.

135 (3) Since Ug = {B2}, B2 is the next block to be visited. Since Vg = 0, no path is built for B2. In procedure BLOCKVISIT, 02 f34' 03 = f45 are appended to o, and a4 becomes inactive. VB becomes {B2} and UB becomes 0. 3. REVERSEPROCESS BLOCKS Since V = {B2}, 04 = f53 is appended to o. After f a new set A1A2A7 which represents the reduced K2 is formed. Since R4 e SJR, R4 is ignored after f53. 4. HILL CLIMBING Since none of the semijoins are beneficial, procedure HILL_CLOMBING does not append any semijoin to o. 5. COMPLETION (1) For B1, a2 is the only active attribute, while al is the only inactive attribute. Hence 05 = f21 is appended to o. (2) For B2, a3 is the only active attribute while a4 is the only inactive attribute. Hence 06 = f34 is appended to o. 6. SCREENING No semijoin is deleted from o by procedure SCREENING. From Table 6.1, the cost of the query QC by Algorithm H is: QC = IC -.i= n i1 n = 3830 - 3352

136 Table 6.1 The Sequence of Semijoins by Algorithm H and Its Effect for Hevner and Yao's Example i mi IR11 IKl11 JI 1 2 3 r 4 5 6 f1_2 f34 f45 f53 f21 f34 8.7 8.7 1~, --.............. 1R21 IK2 IK31 75.0 50.0 70.0 9.0 8.7 8.4 IR31 14.0 8.4 IK41 14.0 8.4 R41 8.4 IK51 8.4 bi 0.0 1860.0 591.6 18.4 1095.3 56.0 Ci 110.0 80.0 24.0 18.4 18.7 18.4 n. -110.0 1780.0 567.6 0.0 1076.6 37.6, 1. _,_......__,,_,,____ __._. = 478 Query cost by the SDD-1 algorithm We follow the same procedure used in the SDD-1 algorithm and compute the cost of transmitting the data

137 during the sequence of semijoins and transmitting the reduced relations to the assembly site. However, for the SDD-1 algorithm, we further include the cost of transmitting the assembled answer from the assembly site to the user site. 1. Hill-Climbing In this phase, the semi join with the largest net benefit is appended to the sequence of semijoins being constructed until there is no remaining beneficial semijoin. It should be noted that the reductions of relations at the user site are considered as benefits in the SDD-1 algorithm. Hence in computing the query cost, the costs of semijoins are used instead of their net benefits. The sequence of semijoins scheduled in this phase and its effect are summarized in Table 6.2. From Table 6.2, the part of the query cost QC1 incurred by the sequence of semijoins is: QC1 = 7=1 c = 410.0 2. Assembly In this phase, the reduced relations are moved to the site where the largest relation is located. Let S(R) denote the size of the relation R. After the hill-climbing phase, the size of each relation is as follows: S(R1) = |R11(w1 + wc) = 104.7

138 Table 6.2 The Sequence of Semijoins by the and Its Effect for Hevner and SDD-1 Algorithm Yao's Example I r r i IRl1 IKl1 IR21 IK21 IK3l IR31 IK4 I IR41 IK5l bi Ci 1 II r 1 f 2 r 3 r 4 f 5 6 7 1 f34 f45 f53 f21 f54 f12 f34 8.7 8.7 36.0 9.0 34.9 8.7 24.0 8.4 40.0 24.0 8.4 40.0 24.0 8.4 24.0 24.0 I I 1600.0 210.0 I 576.0 50.0 I 528.0k 34.0 1095.3 44.9 I 160.0 34.0 54.0+ 18.7 155.9 18.4 i - I L - - I I The actual benefits of these semijoins are 0, since R2 is at the user site. S(R2) = IR21(w2 + w3) = 18 S(R3) = IR31(W4 + we) = 84.1 S(R4) = IR41w5 = 24

139 Hence the site of R1 is selected as an assembly site. The part of the query cost QC2 to move R2, R3 and R4 to the assembly site is: QC2 = i=2 10 + S(R )} = 156.1 3. Enhancements In this phase, the sequence of semijoins scheduled in the hill-climbing phase is examined for possible reordering and/or deletion of semijoins. Since neither reordering nor deletion is applicable in this case, no enhancements are made. 4. Answer Move Since the assembly site is the site of R1, and the user site is the site of R2, it is necessary to move the query answer assembled at the assembly site to the user site. Let RA be the answer relation. Then RA = R[a1 = a2]R2[a3 = a4]R3[a4 = a5]R4}[ac, ae]. IRA = 9, since jR1j = IK, K1 = K2, JR31 = IK41, K4 = K3, K4 c K5 and IR21 = 9. The width of RA is w + we. Hence the part of the query cost QC3 to move RA to the user site is: QC3 = S(RA) + 10 3 A = 190

140 The cost of the query QC by the SDD-1 algorithm is: QC = QC1 + QC2 + QC3 = 756 The query costs for Hevner and Yao's example are summarized in Table 6.3. Table 6.3 Query Costs for Hevner and Yao's Example ~Algorithm Query Cost Initial Cost 3830 Hevner and Yao 1324 SDD-1 756 Cheung 1324 Algorithm H 478 Example 6.2 An example by Bernstein et al. [BERN 81] is considered. Their example is incomplete, since the user site is not specified. We assume that the user site is not one of the sites at which the relations referenced by the user query are located. The necessary informations to process the query are as follows: Database:

141 S(S#, NAME, LOCATION) Y(S#, P#) P(P#, NAME, TYPE) Each relation is stored at a separate site. Query: FIND (S.S#, S.NAME, S.LOCATION, Y.S#, Y.P#, P.P#, P.NAME, P.TYPE) WHERE (S.LOCATION = 'MA') AND (P.TYPE = 'Micro') AND (S.S# = Y.S#) AND (Y.P# = P.P#) Parameters: a1 = S.S#, a2 = Y.S#, a3 = Y.P#, a = P.P# as = S.NAME, al = S.LOCATION a = P.NAME, at = P.TYPE The reduced query after initial local processing: FIND (a, as, a, a, a a a4, ap, at) WHERE (a1 = a2) AND (a3 = a4) From the reduced query, B1 = {al, a2} and B2 = {a3, a4}. The initial database state: Isl = 200, IYI = 100000, I P = 2000

142 IA11 = 200, IA21 = JA31 = 1000, IA41 = 2000 All attributes have a width of 1. ID11 = ID2| = 10000 The communication network parameters: Vf = 10, u = 1 The initial cost of the query to move S, Y and P to the user site after initial local processing is 206630. We compute the cost of the query using different algorithms. Query cost by Hevner and Yao's algorithm The integrated schedule for each relation is shown in Figure 6.2. S 610 S: -------— I User site f 210 Y Y: ----- ---- 810 f34 1010 f43 210 ------ User site f34 1010 P 610 P: I --- —------ I --- —- User site The Schedule by Hevner and Yao's Algorithm for Example 6.2 Figure 6.2 Adding all the edge values in Figure 2, the query cost

143 is 4470. Query cost by Cheung's algorithm In Cheung's method, the qualification clause of the query is decomposed into simple query clauses as follows: q1 al = a2 q2 - a3 = a4 where qi is the qualification clause of the simple query Qi for i = 1, 2. Then, a serial schedule is constructed for each simple query as shown in Figure 6.3. S f12 Y f2 S Q: I --- —---— I --- —---— I 210 30 Y f34 P f43 Y Q2: I I --- —------- ------— I --- —--- 1010 210 The Serial Schedules by Cheung's Algorithm for Example 6.2 Figure 6.3 After the semijoins in Figure 6.3, S(S) = 60, S(Y) = 800 and S(P) = 600. Adding all the edge values in Figure 6.3 to the cost of moving reduced relations, the query cost is 2950. Query cost by Algorithm H

144 The sequence of semijoins generated by Algorithm H and its effect are shown in Table 6.4. The expansions of lattices L1 and L2 corresponding to B1 and B2, respectively, are shown in Figure 6.4. From Table 6.4, the query cost QC is: QC = IC - 4= " = 2711 Query cost by the SDD-1 algorithm The sequence of semijoins generated by the hillclimbing phase is the same as that generated by Algorithm H. However, since the site of Y is selected as an assembly site, 03 = f43 is deleted in the enhancement phase. Therefore, the part of the query cost QC1 by a sequence of semijoins is as follows: QC1 = c1 + c2 + 4 = 1117.4 The part of the query cost QC2 by moving the relations to the assembly site is: QC2 = S(S) + S(P) + 20 = 600.5 Let RA be the answer relation assembled at the site of Y. Before assembling RA, K1 = K2, K3 = K4 and IYI = 400.

146 Table 6.4 The Sequence of Semijoins by Algorithm H and Its Effect for the Example Given by Bernstein et al. 0i f12 f34 f43 f21 Isl 20.0 IK11 20.0 IYI 2000.0 400.0 IK21 20.0 20.0 IK3 867.4 173.5 PI P I 173.5 IK4 173.5 bi 196000.0 5479.5 3200.0 540.0 Ci 210.0 877.4 183.5 30.0 n. 195790.0 4602.1 3016.5 510.0 1, _ _ _ _ _ __ _ _ _ _ _...._ _ __ _ __ _._,___....._,_........ Hence query I RA cost = 400 and the width of RA is 6. The part of the QC3 to move RA to the user site is: QC3 = S(RA) + 10 = 2410 The query cost QC is: QC = QC, + QC2 + QC3 = 4128

147 Table 6.5 shows the costs of the query for this example obtained by different algorithms. Table 6.5 Query Costs for the Example Given by Bernstein et al. Algorithm Query Cost Initial Cost 206630 Hevner and Yao 4470 SDD-1 4128 Cheung 2950 Algorithm H 2711 If the site of Y is the user site, procedure SCREENING in Algorithm H eliminates 03 = f43 from a. Also, since the assembly site and the user site are the same for the SDD-1 algorithm, the assembled answer does not have to be moved. In this case, Algorithm H and the SDD-1 algorithm produce identical sequence of semijoins and query cost. However, if the user site is the site of S or P, the query cost according to the SDD-1 algorithm is also 4128. The query cost obtained by Algorithm H is 2611 when S is at the user site whereas the cost is 2181 when P is at the user site. Example 5.3 An example by Cheung [CHEU 82] is considered. The query and the database are as follows:

148 The database has the same relations as in Example 5.1: R = TEACHER_COURSE R2 = STUDENT_COURSE R3 = COURSE R4 = EMPLOYEE The relation EMPLOYEE is at the user site. Let a1 = EMPLOYEE.E# a = STUDENTCOURSE.E# a = TEACHER_COURSE.E# a = TEACHERCOURSE.C# a5 = COURSE.C# The reduced query after initial local processing: FIND (a1) WHERE (a1 = a2) AND (a2 = a3) AND (a4 = a5) From the reduced query, B1 = {al, a2 a3} and B2 = {a4 a5}. The initial database state: IR11 = 300, JR2 = 300, IR31 = 400, R41| 200 IA11 = 200, |A21 = 300, IA31 = 200, jA4j = 300, IA51 = 400 w. = 1 for all ai |D1| = 400, ID21 = 600 The communication network parameters: Vf = 10, u = 1 For this example, the initial cost of the query is 1330. The cost of the query reported using Hevner and Yao's

149 algorithm is 1240, whereas the cost using Cheung's algorithm is 865. We compute the cost of the query using Algorithm H and the SDD-1 algorithm. Query cost by Algorithm H The sequence of semijoins produced by Algorithm H is o = f13 f32 f23, f45, f54. After a is processed R2, R3, R4 are ignored, since they are singleton joining relations. Since al, a2 and a3 are joining attributes defined on the same domain D1, a3 can be used as a target attribute after a1 is ignored. The cost of the query QC given by Algorithm H is: QC = IC - i15 ni = 1330 - 647 = 683 Query cost by the SDD-1 algorithm 1. Hill-Climbing The sequence of semijoins constructed in this phase is o = f13' f45' f32' f54, f31. The part of the query cost QC1 incurred in this phase is: QC1 = [ c = 639.6 = 639.6 2. Assembly

150 After processing o, S(R1) = 150, S(R2) = 75, S(R3) = 75 and S(R4) = 64.6. Hence the site of R1 is selected as an assembly site. The assembly cost QC2 is: 4 QC2 = i=2 10 + S(Ri)} = 244.6 3. Enhancements In this phase, two enhancements are made: (1) In o, the positions of f32 and f54 are switched. Consequently, the cost of f32 is reduced from 110 to 74.6. Also, S(R2) is reduced from 75 to 48.5. (2) By the choice of an assembly site, f54 is deleted where the cost of f54 is 85. The total reduction QCR of the query cost by enhancements is: QC = (110 - 74.6) + (75 - 48.5) + 85 = 146.9 4. Answer Move Since the assembly site and the user site are different, the answer relation RA has to be moved. IRA| = A A 48.5 and its width is 1. The cost QC3 of moving RA is 58.5. The cost of the query QC by the SDD-1 algorithm is: QC = QC1 + QC2 + QC3 - QCR = 795.8 The query costs for Cheung's example by different

151 algorithms are compared in Table 6.6. Table 6.6 Query Costs for Cheung's Example I I I I N I I I I I I II I.... III...... I -- Algorithm Query Cost Initial Cost 1330 Hevner and Yao 1240 SDD-1 796 Cheung 865 Algorithm H 683.........,..,,.,,,.,.,. Example 5.4 An example is constructed to illustrate the chain effect on singleton joining relations. Consider a chain query referencing five relations as follows: Database: R1(a1), R2(a2, a3), R3(a4, a5), R4(a6, a7), R5(a8 a9) Each relation is stored at a separate site and the user is also at a different site. The reduced query after initial local processing: FIND (a9) WHERE (a1 = a2) AND (a3 = a4) AND (a5 = a6) 5 6

152 AND (a = a8) From the reduced query, B1 = {a1, a2}, B2 = {a3, a4} B3 = {a5, a6} and B4 = {a7, a8}. The initial database state: IR11 = 100, IR21 = 200, IR31 = 350, IR41 = 550, IR51 = 800 IA11 = 100, IA21 = 150, IA3I = 200, IA41 = 250 IA51 = 350, |A61 = 400, |A71 = 550, I|A8 = 600 All attributes have widths of 1. IDl:= 250, ID2 = 450, ID31 = 800, ID41 = 1200 The communication network parameters: Vf = 10, u = 1 Algorithm H produces a sequence of semijoins o = f2 f34' f56' f78. Note that Ri+l becomes a singleton joining relation after 0i for i = 1, 2, 3. Consequently, o completely solves the query. In order to avoid repetitive details, only the results are given in Table 6.7. The results in this section are summarized in Table 6.8. It is observed that Algorithm H performs uniformly better than other algorithms.

153 Table 6.7 Query Costs for Example 5.4 Algorithm Query Cost Initial Cost 3950 Hevner and Yao 2966 SDD-1 1646 Cheung 3112 Algorithm H 364

154 Table 6.8 Summary of Query Cost Comparisons Examples by Algorithm H & Y Bernstein Cheung Example 5.4 Init. Cost H & Y 3830 206630 1330 3950 1324 4470 1240 2966 756 4128 796 1646 1324 2950 865 3112 1~~~~~~...., SDD- 1 Cheung Algorithm H 478 2711 683 364

155 6.2 Efficiency of the Algorithm We have measured the execution time of the program which implements Algorithm H. The execution time of the program is recorded at three points: after reading inputs, after scheduling a sequence of semijoins, and after printing out results. Since reading inputs and printing outputs are related to system I/O and common to other algorithms, only the time taken to schedule a sequence of semijoins is relevant to the efficiency of the algorithm. The scheduling time for the examples presented in Section 6.1 using Algorithm H is shown in Table 6.9. The efficiency of Algorithm H is mainly achieved by the following factors: (1) Since the number of blocks is considerably less than the number of semijoins, the block-oriented nature of Algorithm H leads to a significant reduction of search space. (2) The estimation using the lattice model provides an efficient computation method for the dominant term in Algorithm H.

156 Table 6.9 Scheduling Time of a Sequence of Semijoins using Algorithm H Example by No. Sites Scheduling Time (Seconds) Hevner and Yao 4 0.0039 Bernstein et al. 3 0.0027 Cheung 4 0.0043 Example 5.4 5 0.0055

CHAPTER 7 CONCLUS I ON The problem of query optimization in distributed relational database systems has been addressed. In order to process a query which references data from multiple sites in a computer network, portions of the database at other sites have to be transferred to the user's site. Due to the rapid increase of computing power in recent years, it has been observed that the delay caused by inter-site data communication has become the more dominant factor in processing a distributed query. Therefore, the main objective in processing a distributed query is the minimization of the inter-site data traffic in a communication network. The methodology which has been used in this research consists of reducing the referenced relations using a sequence of semijoin operations after initial local processing. The semijoin strategy involves the following subproblems: (1) Estimation of the size of the relation reduced by each semijoin of a sequence of semijoins. (2) Design of an algorithm to determine an optimal sequence of semijoins which incurs the minimal 157

158 total inter-site data transfer. The previous semijoin strategies for distributed query optimization either produce erroneous estimations due to an unrealistic assumption or derive sequences of semijoins which do not sufficiently reduce inter-site data transfer. A query information model has been established which provides a compact represention of a user query. Especially, the concept of a block has been introduced, which plays a central role for developing a model and a solution algorithm for distributed query optimization. From the query information model, necessary variables which describe the database state have been defined. A mathematical model has been developed to determine an optimal sequence of semijoins which minimizes the total inter-site data flow in processing a distributed query. The net benefit of a semijoin in a sequence of semijoins has been expressed in terms of its contribution in reducing the total amount of inter-site data transfer in processing a distributed query. The core of the optimization model is a method which accurately estimates the size of an intermediate result of a query. In particular, the assumption that joining attributes are independent during the processing of a query by a sequence of semijoins has been relaxed. The data reduction due to a semijoin has been estimated using conditional probabilities and these reductions due to a sequence of semijoins have been modeled by a lattice.

159 A structural analysis of the lattice model has been carried out to establish a basis for developing algorithms which make use of the lattice model. A method that systematically generates the lattice has been developed. This method allows us to identify the relationships among the elements in the lattice, thus to construct examples of query processing by a sequence of semijoins. It has been proven that the lattice which models the data reduction is a leveled lattice. This property can be used to reduce the search space when some elements of the lattice are stored and they are searched to retrieve the data associated with those elements. In distributed query optimization, the computation of the reduction of the set of values of a joining attribute by a semijoin is a dominant term. Therefore, an efficient method for estimating the reduction is crucial in increasing the efficiency of the optimization algorithm. A special structure and a labeling rule of the elements in the lattice have been used to design a recursive algorithm which is essential in computing that reduction. It has been observed that this algorithm generally terminates without any recursion in processing resonable size queries. When a relation referenced by a query consists of only one joining attribute after initial local processing, this relation can be ignored after an outgoing semijoin from this attribute. In addition, if the block containing this attribute has only two attributes and neither is in the

160 target list, then both of them can be ignored after the semijoin. Since this situation can cause a chain effect to other relations, an additional reduction of inter-site data transfer can be achieved. This feature has been incorporated into our methodology. Since the distributed query optimization problem is known to be NP-hard, a heuristic algorithm has been developed to determine a low-cost sequence of semijoins. The algorithm decreases the cost of a query by selecting the low-cost, highly reductive semijoins first. The main feature of this algorithm is to select and "visit" an unvisited block with the least value of a heuristic cost function defined on the set of blocks until no more unvisited block exists. By "visiting" a block we mean that semijoins are scheduled which go from the attribute with the smallest cardinality in the block towards the one with the largest cardinality. After all the blocks have been visited, the visits are reversed. Several control features have been incorporated in the algorithm to increase the robustness for random input data. The time complexity of the main features of our algorithm has been analytically derived. It has been proven that the number of sequences of semijoins that can be generated by the main features of our algorithm is O(n*lSI) in the worst case, where a is the set of blocks and n is the size of the largest block. The comparisons of the query cost produced by our algorithm with those by the existing

161 algorithms, which schedule seminjoin strategies for general distributed queries, have been made. The examples in the articles which present existing algorithms have been used as benchmarks. It has been observed that our algorithm performs uniformly better than existing algorithms for those benchmarks. The algorithm has been implemented in PASCAL. The tests have shown that the scheduling time for a sequence of semijoins for a distributed query which references data from less than or equal to five sites is less than 0.01 seconds when the program is executed by Amdahl 470V/8. It is considered that the efficiency of our distributed query optimization algorithm is mainly achieved by the blockoriented nature of the algorithm and the estimation of data reductions using the lattice model.

APPENDICES 162

163 APPENDIX A Some Concepts of Relational Model 1. Structures In a relational database, the data is logically arranged in two dimensional tables. Each table corresponds to an entity. Here, a relationship between entities is also considered as an entity. An entity consists of several distinct attributes to describe it. Each row of the table is called a tuple, which corresponds to an occurrence of the entity with a specific value for each attribute. Each column of the table corresponds to the values of a component attribute. The set of all values that an attribute can take is called a domain. Note that many different attributes can take values from the same domain. The table consisting of a set of tuples is called a relation with its name the same as that of the corresponding entity. The number of attributes of a relation is called the degree of the relation. Relations of degree n are called n-ary and the tuples in them are called n-tuples. Hence the relational database consists of a collection of time-varying tabular relations. Figure A.1 illustrates example relations. 2. Relational Algebra The operators for the manipulation of relations must be defined compatible with the data structure. The definitions presented here are based on [BERN 79, CODD 79].

164 SUPPLIER S# SNAME CITY S1 Smith N.Y. S2 Jones L.A. S3 Clark L.A. S4 Adams N.Y. SUPPLY PART P# PNAME MATERIAL P1 Nut Steel P2 Pipe Plastic P3 Screw Steel P4 Screw Aluminium P5 Bolt Plastic P6 Wire Aluminium The Examples of Relations Figure A.1

165 SELECTION: SUPPLIER [CITY = 'N.Y.'] S# SNAME CITY S1 Smith N.Y. S4 Adams N.Y. I I - --- I~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~. PROJECTION: SUPPLY [QUANTITY, P#] QUANTITY P# 400 P1 290 P3 240 P4 160 P5 380 P6 300 P2 200 P1 350 P2 300 P6 I~~~~~~~~~. I,.. The Examples of Relational Operations Figure A.2

166 JOIN: SUPPLIER [S# = S#] SUPPLY S# SNAME CITY S# P# QUANTITY S1 Smith N.Y. S1 P1 400 S Smith N.Y. S1 P3 290 S1 Smith N.Y. S1 P4 240 S Smith N.Y. S1 P5 160 S1 Smith N.Y. S1 P6 380 S2 Jones L.A. S2 P2 300 S2 Jones L.A. S2 P3 290 S2 Jones L.A. S2 P5 160 S3 Clark L.A. S3 P1 200 S3 Clark L.A. S3 P2 350 S3 Clark L.A. S3 P4 240 S3 Clark L.A. S3 P6 300. i i., ~,,.,.... ~...,,, SEMIJOIN: SUPPLIER <S# = S#] SUPPLY,.... S# SNAME CITY S1 Smith N.Y. S2 Jones L.A. S3 Clark L.A..... I Figure A.2 continued.

167 SELECTION Let A be an attribute of a relation R and D be the domain from which A takes values. For v e D, the selection of R on A for v, denoted by R[A=v], is defined as {r e R | r.A=v} PROJECTION R[A1, A2,..., An] is the relation obtained by dropping all columns of R except those specified by A1, A2,..., An and then dropping redundant duplicate rows. JOIN Let A be an attribute of a relation R and B be an attribute of a relation S with A and B defined on the same domain. Then the join of R and S on A and B, denoted by R[A=B]S, is defined as {rslr e R and s e S and r.A=s.B} where rs is a concatenation of r and s. SEMIJOIN Let A,B,R and S be the same as in the definition of join. Let A be the attributes of R. The semijoin of R by S on A and B, denoted by R<A=B]S, is defined as (R[A=B]S)[Ar]. The selection, join and semijoin can be defined using binary relations other than equality. R[A=B]S contains two identical columns, one derived from A and the other from B. The NATURAL JOIN is the same as JOIN except that redundant columns generated by the join are removed. The examples of relational operations are shown in Figure A.2. 3. Relational Query

168 A relational query consists of a target list and a qualification clause. A qualification clause is a boolean combination of terms each of which equate two attributes or relate an attribute to a value [ULLM 80]. If the qualification clause is pure conjunctions of terms, the query is called a conjunctive query. The qualification clause specifies qualified tuples from the referenced relations and the target list specifies the attributes to be projected out. The following example shows the formulation of a relational query. Example A.1 Consider a user request to the database shown in Figure A. 1: For a supplier located in N.Y. who supplies parts made of steel more than 320 units, find the supplier name, the corresponding part name and the supply quantity. The relational query formulation is: FIND (SUPPLIER.SNAME, PART.PNAME, SUPPLY.QUANTITY) WHERE (SUPPLIER.CITY = 'N.Y.') AND (PART.MATERIAL = 'Steel') AND (SUPPLY.QUANTITY > 320) AND (SUPPLIER.S# = SUPPLY.S#) AND (SUPPLY.P# = PART.P#) It is clear that a relational query can be answered by applying a proper sequence of selections, projections and joins to the referenced relations. The term equating two

169 attributes is called a join term because it can be processed by join. Similarly, the term relating an attribute to a value is called a selection term. The attributes in a join term is called joining attributes.

170 APPENDIX B Some Definitions from Lattice Theory The definitions presented here are from [BIRK 67] and [GRAE 78]. Definition A.1: A lattice is a partially ordered set (poset) P any two of whose elements have a g.l.b. or "meet" denoted by x A y, and a l.u.b. or "join" denoted by x v y. Definition A.2: A bijection 0: P -- Q from a poset P to a poset Q is an isomorphism if and only if x < y implies 8(x) < 8(y) and 8(x) < 0(y) implies x s y. Definition A.3: A bijection 0: P — > Q from a poset P to a poset Q is a dual isomorphism if and only if x < y implies 6(x) > 8(y) and 0(x) < 8(y) implies x > y. Definition A.4: A lattice L is complete when each of its subsets has a g.l.b. and l.u.b. in L. Definition A.5: A lattice L with the greatest element I and the least element O is complemented if for all x e L there exists y e L such that x A y = O and x v y = I. Definition A.6: A lattice L is distributive if and only if x A (y v z) = (x A y) v (x A z) for all x,y,z e L.

171 Definition A.7: A boolean lattice is a complemented and distributive lattice. Definition A.8: A Sublattice of a lattice L is a subset X of L such that a e X, b e X imply a A b e X and a v b e X. Definition A.9: A join-semilattice is a poset P such that x v y e P for all x,y e P. A meet-semilattice is dually defined. Definition A.10: A chain is a poset P such that x < y or y < x for all x,y e P.

BIBLIOGRAPHY 172

173 BIBLIOGRAPHY [ADIB 78] Adiba, M. et al., "Issues in distributed database management system: a technical overview," Proc. of the Intl. Conf. on VLDB, West-Berlin, Sep. 1978, pp. 89-110. [BAKE 74] Baker, K.R., Introduction to sequencing and scheduling, John Wiley, 1974. [BERN 79] Bernstein, P.A. and Goodman, N., "The theory of semi-joins," Technical Report No. CCA-79-27, Computer Corporation of America, November 1979. [BERN 81] Bernstein, P.A. et al., "Query processig in a system for distributed databases (SDD-1)," ACM TODS, Vol. 6, No. 4, Dec. 1981, pp. 602-625. [BIRK 67] Birkhoff, G., Lattice theory, 3rd Edition, American Mathematical Society, RI., 1967. [BREI 70] Breipohl, A.M., Probabilistic systems analysis, John Wiley, 1970. [CASE 72] Casey, R. G., "Allocation of copies of files in an information network," AFIPS Conference Proceedings, Vol. 41, 1972, pp. 617-625. [CASE 73] Casey, R. G., "Design of tree networks for distributed data," AFIPS Conference Proceedings, Vol. 42, 1973, pp. 251-257. [CCA 80a] Computer Corporation of America, "A distributed database management system for command and control applications: Final technical report - Part I," Technical Report No. CCA-80-03, Jan. 1980. [CCA 80b] Computer Corporation of America, "A distributed database management system for command and control applications: Final technical report - Part II," Technical Report No. CCA-80-04, Jan. 1980. [CHAM 77] Champine, G.A., "Six approaches to distributed databases," Datamation, Vol. 23, No. 5, Technical Publishing Company, Barrington, Ill., May 1977, pp. 69-72.

174 [CHAN 77] Chandy, K.M., "Models of distributed systems," Proc. of the Intl. Conf. on VLDB, Tokyo, Oct. 1977, pp. 105-120. [CHEU 82] Cheung, T., "A method for equijoin queries in distributed relational databases," IEEE Trans. on Computers, Aug. 1982, pp. 746-751. [CHU 69] Chu, W.W., "Optimal file allocation in a multiple computer system," IEEE Trans. on Computers, Oct. 1969, pp. 885-889. [CHU 79] Chu, W.W. and Hurley, p., "A model for optimal query processing for distributed databases," Digest of Papers, COMPCON 79 Spring. [CHU 82] Chu, W.W. and Hurley, P., "Optimal query processing for distributed database systems," IEEE Trans. on Computers, Vol. C-31, No. 9, Sep. 1982, pp. 835-850. [CHUN 82] Chung, C. W. and Irani, K. B., "A methodology for query optimization in distributed database systems," Database Engineering: a quarterly bulletin of the IEEE Computer Society Technical Committee on Database Engineering, Sep. 1982, pp. 19-23. [CODD 70] Codd, E.F., "A relational model of data for large shared data banks," Comm. ACM, Vol, 13, June 1970, pp. 377-387. [CODD 71] Codd, E.F., "Relational completeness of database sublanguages," In Database Systems, Courant Computer Science Symposia Series, Vol. 6, Englewood Cliffs, N.J., Prentice-Hall, 1971, pp. 65-98. [CODD 79] Codd, E.F., "Extending the database relational model to capture more meaning," ACM TODS, 1979, pp. 29-52. [DATE 77] Date, C.J., An introduction to database systems, 2nd Edition, Addison-Wesley, MA., 1977. [DAVE 70] Davenport, W.B., Probability and random processes, McGraw-Hill, 1970. [DAYA 79] Dayal, U. and Bernstein, P.A., "The fragmentation problem: lossless decomposition of relations into files," Technical Report No. CCA-78-13, Computer Corporation of America, Nov. 1978. [EPST 80] Epstein, R. and Stonebraker, M., "Analysis of distributed database processing strategies," Proc. of the Intl. Conf. on VLDB, 1980, pp. 92-101.

175 [EPST 78] Epstein, R., Stonebraker, M., Wong, E., "Distributed query processing in a relational database system," Proc. 1978 ACM SIGMOD Conference, June 1978, pp. 169-180. [ESWA 74] Eswaran, K.P., "Placement of records in a file and file allocation in a computer netwwork," IFIP Conference Proceedings, Aug. 1974, pp. 304-307. [GARE 79] Garey, M.R. and Johnson, D.S., Computers and intractability, W.H. Freeman and Company, CA., 1979. [GOUD 81] Gouda, M.G. and Dayal, U., "Optimal semijoin schedules for query processing in local distributed database systems," Proc. 1981 ACM SIGMOD Conference, May 1981, pp.164-173. [GRAE 78] Graetzer, G., General lattice theory, stuttgart: Birkhaeuser, 1978. [HEVN 78] Hevner, A.R. and Yao, S.B., "Query processing on a distributed database," Proc. 1978 Berkeley Workshop on Distributed Data Management and Computer Networks, Berkeley, CA., Aug. 1978, pp. 91-107. [HEVN 79a] Hevner, A.R., The optimization of query processing on distributed database systems, Ph.D. dissertation, Purdue University, 1979. [HEVN 79b] Hevner, A.R. and Yao, S.B., "Query processing in distributed database systems," IEEE Trans. on Software Eng., Vol. SE-5, No.3, May 1979, pp. 177-187. [HORO 78] Horowitz, E. and Sahni, S., Fundamentals of computer algorithms, Computer Science Press, MD., 1978. [IRAN 82] Irani, K.B. and Khabbaz, N.G., " A methodology for the design of communication networks and the distribution of data in distributed supercomputer systems," IEEE Trans. on Computers, Vol. C-31, No. 5, May 1982, pp. 419-434. [KLEI 76] Kleinrock, L., Queueing systems, Vol.II: Computer Applications, John Wiley, 1976. [LEVI 75] Levin, K.D. and Morgan, H.L., "Optimizing distributed databases -A framework for research," AFIPS Conference Proceeding, Vol. 44, 1975, pp. 473-478. [LIEN 78] Lien, Y.E. and Ying, J.H., "Design of a distributed entity-relationship database system," Proc. COMPSAC 78. [MAHM 76] Mahmoud, S. and Riordan, J.S., "Optimal allocation

176 of resources in distributed information networks," ACM TODS, Vol. 1, No.1, March 1976, pp. 66-78. [MART 77] Martin, J., Computer database organization, 2nd Edition, Prentice-Hall, N.J., 1977. [MURT 76] Murty, K.G., Linear and combinatorial programming, John Wiley, 1976. [NOLA 73] Nolan, R.L., "Computer databases: the future is now," Harvard Business Review: Sept.-Oct. 1973, pp.98-114. [PAIK 79] Paik, I. and Delobel, C., "A strategy for optimizing the distributed query processing," The 1st Intl. Conf. on Distributed Computing Systems, Huntsville, AL., Oct. 1979, pp. 686-698. [PELA 79] Pelagatti, G. and Schreiber, F.A., "Evaluation of transmission requirements in distributed database access," Proc. 1979 ACM SIGMOD Conference, May 1979, pp. 102-108. [RAMA 79] Ramamoorthy, C.V. and Wah, B.W., "The placement of relations on a distributed relational database," The 1st Intl. Conf. on Distributed Computing Systems, Huntsville, AL., Oct. 1979, pp. 642-650. [ROTH 77] Rothnie, J.B. and Goodman, N., "A survey of research and development in distributed database management," Proc. of the Int. Conf. on VLDB, Tokyo, Oct. 1977, pp. 48-62. [ROTH 80] Rothnie, J.B. et al., "Introduction to a system for distributed Databases (SDD-1)," ACM TODS, Vol.5, No.1, March 1980, pp.1-17. [STON 77] Stonebraker, M. and Neuhold, E., "A distributed database version of INGRES," Proc. 1977 Berkeley Workshop on Distributed Data Management and Computer Networks, Lawrence Berkeley Lab., Univ. of California, Berkeley, CA., May 1977, pp. 19-36. [ULLM 80] Ullman, D.J., Principles of database systems, Computer Science Press, MS., 1980. [WONG 76] Wong, E. and Youssefi, K., "Decomposition-A strategy for query processing," ACM TODS, Vol. 1, No. 3, Sept. 1976, pp. 223-241. [WONG 77] Wong, E., "Retrieving dispersed data from SDD-1: A system for distributed databases," Proc. 1977 Berkeley Workshop on Distributed Data Management and Computer Networks, Lawrence Berkeley Lab., Univ. of California,

177 Berkeley, CA., May 1977, pp 217-235. [YAO 77] Yao, S.B., "Approximating database organizations," Comm. April 1977, pp. 260-261. block accesses in ACM. Vol. 20, No. 4, [ZANI 79] Zaniolo, C., "Design of relational views over network schemes," Proc. 1979 ACM SIGMOD Conference, May 1979, pp. 179-190.

UNIVERSITY OF MICHIGAN 3 9015 02829 5478