Data reduction algorithms for distributed query processing
Jia-shinn Wang · ThinkTech (Texas Tech University) · 1984
Recent advances in computer and communciation technologies, coupled with explosion in size and complexity of application areas, have led to design of large computer communication complexes.For instance, the ARPANET currently supports communication among more than one hundred computer systems.The network is under continual development and is used by thousands of users daily.Computer networks have capability to bring computing power to the people who need it, and provide access to a wider variety of resources dispersed among several computers which are linked by a communication facility to provide the basis for "distributed" computing services.In general, the notion of "distributed systems" varies in character and scope with different people [KAR80].So far, there is no accepted definition and basis for classifying these systems.Basically, at least four physical components of a system might be distributed: hardware or processing logic, data, the processing itself, and control.Some speak of a system that has any one of these components distributed as being a "distributed system."However, Enslow [ENS78] pointed out that a ^ distributed system should include: a multiplicity of general purpose resource components, a physical distribution of these physical and logical components, a high level operating system that unifies and integrates the control of the distributed components, system transparency, and cooperative autonomy.Evolution of modern computer network technology and rise of common carrier packet switched networks have provided motivation to develop distributed information networks.In addition, due to increasing geographic dispersion of end users within an organization, pressures are generated or data processing and corporate management to distribute data processing and storage capabilities at the location of data origin and/or end use of the data.The Distributed Data Base Management System (DDBMS) provides faster, easier access and more reliability to data than is feasible in traditional, centralized Data Base Management System (EBMS).According to the CODASYL systems committee [NCC78], the major benefits derived of distributions focus on increased data availablity and reduced exposure of total system failure due to hardware/software failure to end users.There are currently three favored approches to the data base model: the hierarchical model, the network model, and the relational model £DAT31].The hierarchical model and the network model present to the user a navigational interface with which the user must determine the data access path.The relational model was later proposed to achieve a high level of data independence.Users perceieve the data base as a collection of relations (or tables), regardless of actual physical data structures used for stroage.Each relation is composed of a set of homogeneous records (called tuples) , which in turn are subdivided into an ordered set of fields call attributes.This simple data representation allows access of data by specifying the properties of data to be retrieved, rather than specifying how data are to he accessed.A component of the data base called the query optimizer determines ah efficient access plan.Distributed data base systems are considerably more complex than centralized ones [SWA81, SMA79, SMI81, RAM79].These additional complexities are due to some problems inherent to distribution, such as synchronization, heterogeneity, and geographical dispersion.Major areas of current research are query optimization, distributed concurrency control, failure recovery, distributed data base design, and distributed architectures for data base machines [SAC82].The present thesis focuses on the problem of guery optimization in distributed data base systems.The query optimizer is a difficult component of a data base system ^ [ROT80], because the cost of almost all interactions with the data base depends on the quality of plans which are determined by the query optimizer.This component is invoked not only for retrival operations but also for replace and remove operations.In [SAC82], the authors have presented an excellent review of this area.