Query processing in a distributed data base

QUERY PROCESSING

IN A DISTRIBUTED

E. A. Unger Kansas State University

Diane dantz United Information Services

Jacob Slonim GEAC Corporation

R. McBride Kansas State University

algorithms and suggested a more comprehensive approach which will allow the selection of a suboptimal solution based upon beth response time and cost.

Abstract The current research on optimizing algorithms for queries in distributed data base networks is presented. An identification of additional factors which add cost and time to processing of a query both at a node and in the transporting of data along a link in the network is given. The idea of a user topology is presented as the basis for a query optimization algorithm and the effects of a user's query constraints on the user topology are illustrated. With the influencing factors on a query request identified, a model of query processing is described.

Kev Words and Processing Temporal Topology, Constraint

Queries A query is a request to the data base to restrict its contents to some item or set of items. A simple query is one which produces only one common joining domain after local processing, whereas a general query is one which can be further restricted by two or more common joining domains. The general query is of much more interest in that there are usually many ways to satisfy it. Query processing for a general query is the combination of data processing at one or more nodes (computers) and the transferral of data among nodes to the node designated as the resultant node. A retrieval strategy is the method of determining the extent of local processing plus the definition of time and place of transmission of data and the location(s) which are acceptable for the remote processing. If the retrieval strategy results in time or cost minimization for the processing of a query, then it is said query optimization has been achieved. In practice, a true optimum is difficult to impossible to ascertain; however, a suboptimal solution can often be found within a reasonable time and cost. A retrieval model may be based upon a set data base in which case it is a static selection model or may react to changes in the data base over time which makes it dynamic. In the paper, the discussion is limited to a static selection enviromnent but provide the basis for periodically changing the data base distribution description.

Phrases: Retrieval Strategy, Local Resources, Communications Resources, Profile, General Topology, User Restricted User Topology, Query Tuple, Query Processing Model.

QUERY PROCESSING IN A DISTRIBUTED DATA BASE Small and personal computers are rapidly appearing on the desks of executives and others in widely diverse industries. In some arenas, we see individual users creating their own data bases tailored to their own needs on these personal computers; yet, their data bases are usually not adequate in scope of data or integrity of the data. The personal computer is here to stay. The problem of providing comprehensive data base support may be attacked with the concepts of distributed data bases. In distributed systems, queries not answerable by the local unit may be answered by the aggregate of data in the network and often answerable in several different ways. In this paper, we have studied current optimization

Current Research There is considerable research being conducted in the area of query processing. Optimization algorithms focus on optimization of relational queries in a relational data base system. The initial work was accomplished by Wong [WONG76] in a rather efficient algorithm which often produces less than an optimal query processing strategy. The SDD-I system used this algorithmic method for its implementation [BERN81]. A decomposition method was developed by Epstein et al. [EPST78] to produce a query optimization algorithm which is implemented in the distributed INGRES data base system [EPST80]. Dynamic optimization algorithms

Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. © 1983

ACM

0-89791-123-7/83/012/0237

DATA BASE

$00.75

237

have been studied by Baldissera Takizawa [TAKI80].

etal.

say R i, is available at the result node. Total time is the sum of all transmission times in the schedule for R i. Formal definitions of the time minimizations are given below.

[BALD79] and

Hevner and Yao have developed several algorithms to accomplish query optimization for both simple queries and general queries [HEVN78, 79, 80, YA079, WONG76, 77]. The algorithms developed by Hevner and Yao [HEVN78, 79, 80] for simple queries have some shortcomings. For worst case queries, the algorithms have been shown not to have a polynomial complexity. An improvement of these algorithms for arbitrarily complex queries was developed by Apers et al. [APER83]. This new algorithm exists in three versions--one which minimizes response time and two to minimize total time.

I.

ResPonse Time Minimization. The response time r of a processing strategy is given by the maximum length schedule. Therefore, r = MAX {r~ i=1...m}. The minimal response time r is defined as ~=min {r} = min {max {r~ i=1...m}} where the minimum is defined over all strategies.

2.

Yotal Time Minimization. The total time t m of a processing strategy is t t and ^

For Hevner and Yao, query processing requires the transmission of data between nodes in the network. Their optimization strategy defines the arrangement for these transmissions and the local processing of the request. It is unclear in their articles whether they consider data in the restricted sense, collected facts only, or allow transmission of processing commands also. Most likely data is limited to the restricted definition. Their query processing scheme is defined in the following steps: "I.

Initial local processing. This includes PROJECTION, RESTRICTION, and intra-nodal JOIN.

2.

Perform a sequence of data transmission steps and local processing steps until all required data is received at the result node. The sequence of steps is called the processing strategy for the query.

3.

Form the node by [H~N80].

the minimal total time is all strategies [HEVN80].

-

i=I

i

t=min {t} over

Hevner and Yao's algorithm, FAST, which derives a minimum schedule (a pattern of data transmissions and local processing) reduces the amount of data transferred. After the initial processing, algorithm FAST optimizes the schedule of each relation in size order. Only data transmissions on common joining attributes from smaller relations are checked for cost benefits. As can be seen, cost is measured in time units; and to reduce time Hevner and Yao propose the reduction of data transfer amounts. Their proposition is a simple one in assuming that the smallest amount of data is the cheapest. But it should be proposed that local processing, the distance traveled and/or the security overhead associated with data, should be included in an optimization algorithm. Eugene Wong has worked on the design of the optimization algorithm being used by SDD-I, A ~ystem for ~istributed ~atabases, Computer Corporation of America. This design was developed from previous research by Wong and Youssefi, which reduced a multi-variable query, query formed from several relations, to a sequence of one-variable queries [WONG76]. This spurred the concept of doing a similar reduction on distributed queries to achieve a series of local queries.

result relation at the result a final local processing"

This processing is applied to a data base configuration that allows parallel transmission and to a subset of the data base that is a consistent, nonredundant mapping of the necessary data. The result of this application is a schedule of data transmission and local processing which reduces the size of the relation before it reaches the result node. Cost is measured in time units and they consider local processing to be well defined and not influential on query optimization.

Wong views query processing as "two tiered, consisting of a strategy of data transfer (distribution) interwoven with a strategy of local processing (decomposition)." Query processing is done in a network that is a combination of sites with dispersed and redundant data storage; it is unclear if the word data is used in the restricted sense. The data base during query processing (materialization) appears as a fixed, non-redundant, and relational model.

Their data transmission is defined as a "linear function C(X) = C + C I * X, where X is the amount of data transmit~ed.forCo represents the initial start-up cost each separate transmission. The cost and times of a query is in direct proportion to the amount of data, for if x < y then C(X) < C(Y)" [HEVN80]. Distance of transmission is not a concern for as they note "advances in communication technology are rapidly eliminating distance as an essential cost parameter."

Several views of a distributed taken and are defined in Figure I.

data base are

Query optimization is to successfully reduce a query requiring data from several sites into a sequence of local queries. Wong aims at taking the User's View and repeatedly refining its corresponding Distribution View until only local processing remains. This refining is done with data transfers between local processing steps all

The quality of the distribution strategy derived by the optimization algorithm is measured by response time and total processing time of the query. Response time is the time from the start of the schedule of transmission until the relation,

238

the while trying to achieve a minimal communication and local processing cost.

"VI:

V2:

V3:

combined

The User View This consists of the data model, possibly some or all of distribution information.

is found. distribution.

plus the

I.

View one local view per site, of all the relations of the at that site" [WONG77J.

Figure I Views of A Data Base

The overall plan of query processing can be separated into the following steps: I.

CONVERSION

Determine strategy.

multivariable V2 query ....... > one-variable V2 queries

2.

The second step is to try to find subparts of the query that can be processed at a single site (one-variable) or minimal data transfer that could achieve greater local processing. 3.

~ECONVERSION

4.

DECOMPOSITION

multi-variable V3 query one-variable V3 queries

5.

L O C A L ~

In step 2, the problem reduction of distributed query

of optimizing the into a local query

Process clauses.

locally

d.

Identify

the fragments at each site.

e.

Determine M(Q) by computing of moving the fragments to a destination site with all its values. M(Q) is then the set of the initial fragments to a site.

all

V2-one-variable

Node splitting in the strategy successive refinement of M(Q).

the cost selected possible of moves selected

tree - a

a°

Each node owns a proposed set of fragments QI.

b.

For every element m of M a set of moves Rm which would reduce the fragment indicated by m is developed.

c.

Take the union m ~ and eliminate redundancy. The resulting set is identified by R.

d.

A set MI is designed which contains (I) any move in R which reduces more than it costs and (2) any move in the original set, M unaffected by requirement (I).

e.

M is replaced by MI followed by 142 = {the remaining moves of M as changed by MI}. If M = MI, the splitting stops.

f.

Q2 then becomes the modification of QI by MI.

g.

The node (M, QI) is replaced (MI,QI), (M2,Q2) [WONG77].

(MI ,QI)

239.

distribution

c.

OUERY PROCESSING

Then finally, all local processing is completed so that a minimal set of data is all that must be transferred. After transferring, the process starts again with step 2 until the required query answer reaches the result node [WONG77].

initial

Close Q under transitivity. Any clause which is transitively implied by other clauses and at a single site is a local operation.

.... >

Step four analyzes the available relations to see how many of the queries can be answered by a single relation or how the data comparison can be reduced by single relation processing.

operates in the the following two

b.

one-variable V2 query ....... > multi-variable V3 query

The third step looks at how a query must be answered at a local site and converts the query into subqueries for the various relations found at that site (multi-variable V3 query).

-

in

optimizing

Put Q, the query, in conjuctive form. In this condition any clause, relational algebra statement, which is one-variable (in V2) represent local processing.

VI query ........ > V2 query

pISTRIBUTION

M(Q)

this

a.

The first step is to convert what the user asks for from his data model to a query that accounts for where the data is located in the entire database. 2.

terms

The algorithm that distribution is summarized basic components.

The Distribution View This view consists of collection of relations, one per site, each being the cartesian product of all the relations at one site. The Local There is consisting data model

Wong

V2-query, moves M

(M2, ~9.)

QI and a for the

query

from

by

Thus, Wong optimizes a query by first doing all possible local processing and then searching for data transmissions that will reduce any initial strategy moves to a given site. This reduction is recursively computed until the set of minimal cost moves has been defined.

What is involved in local processing? The satisfaction of a query, locally, consists of checking the validity and authorization of the request, processing the commands to locate and retrieve the data from storage (such as restrict, project, and join applied to relations to retrieve the desired information), and includes the resource utilization monitoring of the entire process. The processing of any query must include the cost and speed of the processor, of primary memory, of secondary storage, and of internal data paths [KIMB75].

Wong intends to conduct all initial local processing then define a set of data transfers on the portions of the query that are not one-varlable. With this set, he recursively searches for possible optimal moves that will reduce the amount of data being transferred. These new optimized moves and the initial ones unaffected by these new moves become the distribution strategy by which the query will be processed. Any initial moves affected by the newly defined ones will have to be specially handled to insure their complete inclusion in the processing of the query. Again, the volume of data transferred is the governing factor in the optimization algorithm. Hevner and Yao minimized the volume of data to be transferred in the query; whereas, Wong bases data transfer decisions on careful study of the data reduction benefits such a transfer could produce.

There is an unique usage charge associated with individual processors [STON78a]. Therefore, if a query must be processed at two nodes, its total processing costs will be the sum of the costs associated with the processors at those nodes and the total processing time will be the sum of the times or the greater of the two times depending on whether the processing is done in parallel. If, however, the query has a choice of processors (nodes) at which it may be handled, then the optimization algorithm should select the one with the least total resource expenditure or the least resource expenditure which is considered critical to the continued operation of the system. The speed and cost of the processor is not the sole contributor to this decision.

The authors would like to extend this research by defining a general topology and then distinguishing it from a user topology, by delineating the restrictions a user query may place on the general topology, and by developing a model of query processing in which an optimization algorithm can be developed.

The processor may use both a main memory and a secondary memory in its operations. When handling a query request, the required data may have to be retrieved from secondary storage. The characteristics of this secondary storage determines how quickly a processor can handle a request. The various nodes in the network will have an individual secondary storage characteristic dependent on the devices present at the node, similarly for main memory.

The distributed data base configuration consists of the data node locations, the communication paths, the available hardware and software and the distribution of the data management system components, e.g., the directory. The pattern of interconnection of the nodes and the data located at those nodes form the general • topology of the network. There are two basic components of a topology, local processing resources and communication resources. Local processing resources refer to any aspect of the data base that is needed to perform the query processing at a node, i.e., data, file devices, or processor. Communication resources refer to any device or means that is needed to transfer data among the nodes for the processing, i.e., communication channels.

A network seldom has equally utilized nodes no matter how well designed the distribution. A temporal profile, a graph of the features at a particular point in time, of the node utilization can be made and used as an input to the query optimization algorithm. For example, a node which is overloaded, but has the faster processor and memories, may not give the most time optimum retrieval if compared to a node with slower resources but which is less overloaded. Thus, the profile must include all of the features of processor and memory speeds and node utilization rate.

A user topology is a subset of the general topology that contains the system based upon user characteristics of the query. The description from a homogeneous perspective is not real world.

Local Processing

In a similar manner, the factors of file organization, queuing techniques and search algorithms needed by the query all affect the resource utilization at a local node (see Figure 2). Thus, the node's particular resources must be identified and tagged with temporal cost and time profiles.

of these resources will be perspective; however, that totally satisfactory for the

Resources

Characteristics of communication paths such as speed and distance are simpler to model than local processing resource usage. Wong, whose research centers on the communication component of a query processing model, comments that one of the remaining problems to be solved is "estimating the costs of local operations" [WONG77].

I

Processor

Memories

File Organization

Queuing Techniques

Search Algorithm

Utilization

Figure 2 Local Processing Resources

240

Rate

The total node resource utilization function of several costs and times.

NODEc =

and whether the line is dedicated or shared. With a dedicated line, the cost is higher than a shared line and generally the faster the speed, the higher the cost. A profile for a line then must include the standard line rate based on the number of possible users and speed. Since a network can be formed from a variety of types of lines, the choice of a particular path would determine to a large part the cost and time of a query retrieval.

a

I (PC, MMC, SMC, FRC)

where PC ~C SMC FRC

NODEt =

is

= = = =

processor cost main memory cost secondary memory coat file retrieval cost

These factors, volume of traffic, distance, and type of transmission facility, combined form a cost and time profile for a communication link in a network. The distance and type of line are established when the network's topology is designed. The remaining factors are ascertained when a specific query is processed. The combination of influences these factors provide can determine the communication resource utilization cost and time. The cost and time of a particular transmission can be accomplished with the following functions:

2 (PS, MM~, SMS, FRS, UR)

where PS ~MS S~i~ FRS UR

= = = = =

processor speed and queuing wait main memory speed secondary memory speed file retrieval speed utilization rate

When a query enters the system, the cost of local processing resources of each of the nodes in the set of nodes that could possibly respond to the query are calculated and used as one factor in the optimization algorithm. For a more accurate and realistic optimum retrieval time and cost, the local processing resources must be included in the calculation of an optimization algorithm.

COMMc =

3 (volume, distance, line transmission facility)

COMet =

4 (volume, distance, line transmission facility)

cost, type of

speed,

type of

As in the calculation of the local processing resources for a query, a subset of the topology to satisfy the query's communications requirements could be selected. The communication links in that subset would already be identified with resource utilization rates and an estimate of the volume of data would provide the optimization algorithm with appropriate information.

Resources A distributed data base concept could not function without the help of communication links. The use of the communication links, though, adds considerable resources usage for both time and cost of a query because "typical bandwidths available on high-speed communication links are still a factor of 10 to 100 lower than memory bandwidths" [STON78a]. The communication cost and time are not static factors and may vary based on a number of influences, time of day, security, volume of traffic, distance and type of transmission.

Thus, the optimization algorithm could operate given all of the possible local processing and communication resource parameters, COMM^, COMMt, NODEc, and NODE t. We express this abstractly as the minimization of the resource parameters of the topology T: ~ n i m i z e T (COMM c, COMM t, NODE c, NODE t)

New communications methods are now commercially available including satellite, microwave, and laser communication. Performance and cost of these will be forthcoming as research continues, e.g., recently identified is a measurable delay by satellite communication. As with processor and memory resource, utilization rates based upon a temporal profile must be established for each communication link.

Within an office envirorgnent, the nodes may be connected by a local area network (LAN) which would result in removing distance as a factor.

U~@F TODolo~v A configuration or general topology was defined as the pattern of intereonnection by communication links of nodes. The nodes consist of processors, data storage, data base model, and data base management system components. The links can represent either a LANS or an open network and have associated with them temporal cost and processing characteristics. A general topology has certain processing cost and temporal profiles fixed for the nodes and the communication links (see Figure 3). Two types of records are proposed to represent this information; let records of type X represent node information and type Y represent the link information.

With present technology, the distance of the transmission influences the rate that will be charged. There is speculation, though, that the new technology will eliminate this concern [HEVNS0]. Presently and in the foreseeable future, a transmission that must travel a longer distance is charged a higher total rate as opposed to one which travels a shorter distance. The features identified so far for the profile are additive costs to a standard line rate. The standard line rate varies upon the type of line employed in the transmission. Primarily, distinctions among types of lines are line speed

241

time bounds. Since all of this processing could be done with intersection of sets perhaps stored as bits, it should occur very rapidly and would provide to the node a graph of potential sources of data which meet the users profile for all considered factors, e.g., time and cost.

xc 2 ., y x5

Ouerv Processin~ Model 12

Proposed is a model of query processing that encompasses the selection of a user topology, its restriction by query constraints and its provision of appropriate nodes and links to an optimization algorithm for optimization. The model consists of the following three steps.

x8

l

~

/

Y17

KIO

Ii

I.

Based upon the data needs of the query, a set of nodes and links in the network which can satisfy the data request are selected. A careful consideration of all the possible data element groups (relations) at implementation time can produce a set of stored tables of these user topologies (recall this paper is restricted to static data distribution).

where Y = a record of

X : a record of NODE

(node cost)

NODE~ (node time) Language DBMS Model Processor Security Provisions Processor Speed

Selection of User Topology

COMMc (comm. cost) COMM t (comm. time) Security Provisions Line Speed 2.

Restriction of User Topology Based upon certain user defined constraints, as given in this query constraint tuple below, the nodes and links of the user topologies which cannot meet these constraints are eliminated to give a restricted user topology.

Figure 3 General Topology

A user topology is defined as that subset of the nodes and links of the general topology that is available to satisfy the data request needs of the query being processed. Defining user topologies can be viewed as identifying the nodes and links which can be used to satisfy the data requests of the queries. These user topologies can be further restricted or layered based on the constraints of the query, e.g., time. These constraints are predetermined, chosen by the end user or Data Base Administrator (DBA). Considerations such as the security needed, the type of hardware on which a query can be processed, or the language in which it must communicate allow the the determination of constraints. This layering provides an ability to optimize successively with these further constraints.

Qres (Security, Time, Languagei, DBMS Modelj, Processor k) where i:I,..., max. no. of languages j=1,..., max. no. of DBMS models k=1,..., max. no. of processors 3-

Application of the Optimization

Algorithm

The restricted user topology, with its associated cost and time profiles for both the nodes and links, is given to the optimization algorithm for selection of an optimum retrieval pattern. The optimization algorithm can now be applied to final constrained user topology. In a system of small computers (e.g., PCs) in an office enviroement, the algorithm might even be so simple as to broadcast a request to all nodes for the needed data. However, our current work indicates great savings can be accomplished by having subpart of the request shipped to appropriate nodes, processing done at the remote node(s) and the result of that subrequest shipped back to the requesting node.

The creation of the user topologies within an office system would be quite feasible. Each group (record or relation) of data could be considered as an entity consisting of a series of attributes. Each node is capable of responding to requests for data from some subset of all the records or relations. The creation of data topologies consists of those nodes which can answer requests for data within a given group. When an actual request for data is encountered, the union of those data topologies which provide any of the attributes can be accomplished easily and this union will be called the user topology.

Summarv Thus, this model tries to consider more thoroughly the factors which influence the cost and time of operation for both the nodes and links. It goes on to provide for the restricting influence of

Once created, this can be intersected with the constraints on the request, like response time which could be created by dividing the general topology into topologies with appropriate response

242

Third ~erkelev Workshop on Distributed ~ a n d Computer Networks, August 29-31, 1978.

the user constraints which raise cost and time expenditures. Then having considered these factors outside the optimization algorithm, it provides the algorithm with a more complete and concise selection of nodes and links from which the algorithm can optimize. This resource utilization and query processing model forms an umbrella under which much further research is needed. For instance, it is not clear how the time variant factors such as resource utilization would be made available to nodes. It basically defines the components that affect an optimization algorithm, how those component's values are interrelated and how they could be supplied to the optimization algorithm.

SELECTED BIBLIOGRAPHY

APER83

BALD79

BERN81

CASE72

CHU69

CHU79

Apers, P. M. G., A. R. Hevner, and S. B. Yao. "Optimization Algorithm for Distributed Queries." IEEE Trans. on Software En~., Vol. 9, No. I (Jan. 1983) pp. 57-68. Baldissera, C., G. Bracchi, and S. Ceri. "A Query Processing Strategy for Distributed Databases." Proc. EURP-IFIP79, 1979, PP. 667-678. Bernstein, P. A., N. Goodman, E. Wong, C. L. Reeve, and J. Rothnie. "Query Processing in a System for Distributed Databases (SDD-I)." ACM Trans. on Database~y_s_~, Vol. 6, December 1981. Casey, R. G. "Allocation of Copies of a File in an Information Network." Proc. AFIPS. 2972, SJCC, Vol. 40. AFIPS Press, Montvale, N.J., 1972. Chu, W. W. "Optimal File Allocation in a Multicomputer Information System." IEEE Trans. ComPuters, C-18, 10 (Oct. 1969) pp. 885-889. Chu, W. W. and P. Hurley. "A Model for Optimal Processing for Distributed Databases." Proc. 18th IEEE COMPCON, Spring 1979, pP. 116-122.

CON80

Convis, D. B. "Method for Dynamic Optimization of Relational Tuple Search Sequence for Query by Example." IBM Technical Disclosure Bulletin, Vol. 22, No. I, April 1980.

EPST78

Epstein, R., M. R. Stonebraker, and E. Wong. "Distributed Query Processing in a Relational Data Base System." Proc. ACM SIGMOD, May 1978, pP. 169-180.

EPST80

Epstein, R. and M. Stonebraker. "Analysis of Distributed Database Processing Strategies." Proc. Int. Conf. Very Large Data Bases, Montreal, P. Q., Canada, 1980

HEVN78

Hevner, A. R. and S. B. Yao. "Query Processing on a Distributed Database."

243

HEVN79

Hevner, A. R. and S. B. Yao. "Query Processing in Distributed Database Systems." IEEE Transactions on Software Engineering, VoI. SE-5, No. 3 (May 1979).

HEVNS0

Hevner, A. R. and S. B. Yao. "Query Optimization in Distributed Database Systems." Private Communication (1980).

HEVN83

Hevner, A. R. "Data Allocation and Retrieval in Distributed Systems." Advances in Data base ~ , Vol. II, E. A. Unger, Ed., New York: Wiley 1983 •

KIM82

Kim, W. "On Optimizing an SQL-like Nested Query." ACM Transactions on ~ Base Systems, Vol. 7, No. 3, (1982) p. 443-69.

KIMB75

Kimbleton, S. R. and G. M. Schneider. "Computer Communication Network: Approaches, Objectives, and Performance Considerations." ~ ~urvevs, Vol. 7, No. 3 (Sept. 1979) pp. 129-173.

LEVI75

Levin, K. D. and H. L. Morgan. "Optimizing Distributed Data Bases - A Framework for Research." Proc. AFIPS 1975, NCC. Vol. 44, AFIPS Press, Montvale, N.J., pp. 473-478.

l~RY77

Maryanski, F. J., et al. "Distributed Data Base Management Using Minicomputers." Dept. of Computer Science, Kansas State University, Manhattan, KS (Oct. 1977).

MILL78

Miller, M. "A Survey of Distributed Data Base Management." ~ and Management, I, North Holland Published Co. (1978) pp. 243-264.

MORG77

Morgan, N. L. and K. D. Levin. Program and Data Location in Networks." ~ . ~ A K ~ 2 ~ o f t h e A C M , 20, No. 5 (May 1977).

POPE79

Popek, G. J. and C. S. Kline. "Encryption and Secure Computer Networks." Surveys, Vol. 11, No. 4 (Dec. 1979).

ROTH77

Rothnie, J. B. and N. Goodman. "A Survey of Research and Development in Distributed Database Management." ~roeeedin~sof the Third ~Dternational Conference on Very Large Data Bases, Tokyo, Japan (Oct. 1977).

SCHW77

Schwartz, M. ComPuter Network Design Analysis. Prentice-Hall, Inc., Englewood Cliffs, N.J. (1977).

SHAR80

Scharf, J. D. "Department of Defense Computer Network Security: An Assessment of the State of the Art." Master's Report, Dept. of Computer Science, Kansas State University, Manhattan, KS (1980).

"Optimal Compuer Vol.

SLON79

Slonlm, J., et al. "Data Base Management System Environments Present and Future." Dept. of Computer Science, Kansas State University, Manhattan, KS (May 1979).

UNG E79

Unger, E. A., et al. "Integration of a DBMS into a Network Enviromnent." Dept. of Computer Science, Kansas State University, Manhattan, KS (April 1979).

SMAL79

Small, D. and W. W. Chu. "A Distributed Database Architecture for Processing in a Dynamic Enviromnent." Proc. COMPCON, March 1979.

WONG76

Wong, E. and K. Youssefi. ,Decomposition -- Strategy for Query Processing." ACM Transactions on Database Systems, (Sept. 1976).

STON78a

Stone, H. S. and S. H. Bokhari. "Control of Distributed Proeesses."ComDuter, Vol. 11, No. 7 (July 1978).

WONG77

STON78b

Stonebraker, M. "Concurrency Control and Consistency of Multiple Copies of Data in Distributed Ingres." Memorandum No. USB/ERL M78/24. Electronics Research Laboratory~ University of California, Berkeley (May 24, 1978).

Wong, E. "Retrieving Dispersed Data from SDD-I: A System for Distributed Databases." Proceedings of the Second Berkeley Workshov on Distributed Data and ~etworks. Lawrence Berkeley Laboratory, Univ. of California (May 1977).

YAO79

Yao, S. B. "Optimization of Query Evaluation Algorithms." ACM Transactions on patabase Systems, Vol. 4, No. 2 (June 1979) •

TAKI80

Takizawa, M. "Operational Query Decomposition Algorithm in Distributed Databases." Japan Information Proo. Dev. Cert. Rep. TR80/2, 1980.

244