Distributed query processing and optimization techniques for a hierarchically structured computer network. (English) Zbl 0712.68028
This work deals with distributed query processing and optimization techniques in the three level hardware and software environment. The bottom level consists of a number of basic database servers (BDAS) which are implemented on computers which control the low level factory devices. The BDAS computers form subnetworks according to their manufacturing functions. The distributed database control and management functions within each subnetwork are handled by a distributed data administration system (DDAS). One of the DDAS is designated as the master data administration system (MDAS) to handle the functions like factory network initialization, global dictionary management, error recovery.
Four distributed query optimization techniques are presented which are suitable for query processing strategies based on data flow and pipelining concepts. The general query optimization procedure for a hierarchically structured network is developed. A recursive method for computing the response time and the execution time, and cost formulas for query tree evaluation have been developed. The tools should be applicable to any hierarchically structured network system using pipeline and data flow query processing strategies.
Four distributed query optimization techniques are presented which are suitable for query processing strategies based on data flow and pipelining concepts. The general query optimization procedure for a hierarchically structured network is developed. A recursive method for computing the response time and the execution time, and cost formulas for query tree evaluation have been developed. The tools should be applicable to any hierarchically structured network system using pipeline and data flow query processing strategies.
Reviewer: E.Kostolansky
MSC:
| 68P15 | Database theory |
| 68M10 | Network design and communication in computer systems |
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 68W15 | Distributed algorithms |
References:
| [1] | Apers, P. M.G.; Hevner, A. R.; Yao, S. B., Optimization algorithm for distributed queries, IEEE Trans. Software Enrg., SE-9, 1, 57-68 (Jan. 1983) |
| [2] | Barkmeyer, E.; Michell, M.; Mikkilineni, K. P.; Su, S. Y.W.; Lam, H., A Distributed Data Management Architecture for Computer Integrated Manufacturing, National Bureau of Standards Report (1985) |
| [3] | Bernstein, P. A., Query processing in a system for distributed database (SDD-1), ACM Trans. Database Systems, 6, 602-625 (Dec. 1981) · Zbl 0465.68060 |
| [4] | Bic, L.; Herendeen, M., An architecture for a relational dataflow database machine, (Joint Proceedings of SIGMOD Symposium on Small Systems and Workshop on Small Database Systems (Oct. 1981)), 42-49 |
| [5] | Boral, H.; DeWitt, D. J., Design considerations for a dataflow database machine, (Proceedings of ACM-SIGMOD (1980)), 94-104 |
| [6] | Boral, H.; DeWitt, D. J., Processor allocation strategies for a multiprocessor database machine, ACM Trans. Database Systems, 6, 2, 92-114 (June 1981) |
| [7] | Boral, H., On the Use of Dataflow Techniques in Database Machines, (Computer Science Technical Report 432 (May 1981), Univ. of Wisconsin) |
| [8] | Brill, D.; Templeton, M.; Yu, C., Distributed query processing strategies in mermaid—a frontend to data management systems, (Proceedings of COMDEC (Apr. 1984)), 182-196 |
| [9] | Chakravarty, U. S.; Minker, J., Processing multiple queries in database systems, IEEE Trans. Database Engrg., 5, 3, 38-43 (Sept. 1982) |
| [10] | Chen, A. P.; Li, V. K., Optimizing star queries in a distributed database system, (Proceedings of VLDB (1984)), 209-215 |
| [11] | Chin, D.; Bernstein, P. A.; Yu, C., Optimizing chain queries in a distributed database system, Siam J. Comput., 13, 1, 116-134 (Feb. 1984) · Zbl 0582.68061 |
| [12] | Chu, W. W.; Hurley, P., Optimal query processing for distributed database systems, IEEE Trans. Comput., C-31, 9, 835-840 (Sept. 1982) · Zbl 0488.68070 |
| [13] | Dayal, U.; Landers, T.; Edwab, L., Global Query Optimization in Multibase, (Technical Report (Oct. 1982), Computer Corp. of America: Computer Corp. of America Cambridge, Mass) |
| [14] | Epstein, R.; Stonebraker, M.; Wong, E., Distributed query processing in a relational database system, (Proceedings of ACM-SIGMOD (May 1978)), 169-180 |
| [15] | Finkelstein, S., Common expression analysis in database applications, (Proceedings of ACM-SIGMOD (1982)), 235-245 |
| [16] | Fishman, D.; Lai, M. Y.; Wilkinson, W. K., Overview of the jasmine database machine, (Proceedings of ACM-SIGMOD (1984)), 234-239 |
| [17] | Gajski, D., (cedar Project Reports (Dec. 1983), Univ. of Illinois: Univ. of Illinois Urbana-Champaign) |
| [18] | Gajski, K.; Kim, W., A Parallel Pipeline Relational Query Processor: An Architectural Overview, (IBM Research Report RJ 4087 (Oct. 1983), IBM Research Center: IBM Research Center San Jose, Calif) |
| [19] | Hee, J., A Query Optimization Strategy for an Integrated Manufacturing Database Administration System, (M.S. Thesis (1985), Univ. of Florida) |
| [20] | Hevner, A. R., The Optimization of Query Processing on Distributed Database Systems, (Ph.D Thesis (Dec. 1979), Univ. of Maryland) |
| [21] | Hevner, A. R., A Survey of Data Allocation and Retrieval Methods for Distributed Systems, (Working Paper MS/S 81-036 (Oct. 1981), College of Business and Management, Univ. of Maryland: College of Business and Management, Univ. of Maryland College Park) |
| [22] | Hong, Y. C., A pipelined architecture for relational database operations, (Proceedings of COMDEC (1984)), 215-221 |
| [23] | Keller, R., A loosely coupled applicative multiprocessing system, (Proceedings of NCC (1979)), 613-622 |
| [24] | Kim, W.; Reiner, D.; Batory, D., Query Processing in Database Systems (1985), Springer-Verlag: Springer-Verlag New York · Zbl 0581.68070 |
| [25] | Kooi, R., The Optimization of Queries in Relational Databases, (Ph.D. Thesis (1980), Dept. of Computer and Information Sciences, Case Western Reserve Univ) |
| [26] | Mikkilineni, K. P.; Su, S. Y.W., A Dynamic Inter-query Optimization Methodology for Achieving Data Sharing Among Concurrent Queries, (Technical Report TR-85-12 (1985), Database System Research and Development Center, Univ. of Florida) |
| [27] | Mitchell, M.; Barkmeyer, E. J., Data distribution in the NBS automated manufacturing facility, (Proceedings of IPAD II. Proceedings of IPAD II, NASA Conference Publication 2301 (Apr. 1984)), 189-198 |
| [28] | Treleaven, P. C., Data-driven and demand-driven computer architecture, ACM Comput. Surveys, 14, 1, 93-144 (Mar. 1982) |
| [29] | Sellis, T.; Shapiro, L., Optimization of extended database query language, (Proceedings of ACM-SIGMOD (May. 1985)), 424-436 |
| [30] | Smith, J. M.; Chang, P. T., Optimizing the performance of a relational algebra database interface, Comm. ACM, 1, 3, 189-222 (Sept. 1975) |
| [31] | Su, S. Y.W., A distributed query processing strategy using decomposition, pipelining and intermediate result sharing techniques,, (presented at International Conference on Data Engineering. presented at International Conference on Data Engineering, Los Angeles (Feb. 1986)) |
| [32] | Su, S. Y.W.; Lam, Herman, The architecture and prototype implementation of an integrated manufacturing database administration system, (Spring COMPCON Proceedings. Spring COMPCON Proceedings, Los Angeles (1986)), 67-71 |
| [33] | Wong, E.; Youssefi, K., Decomposition—a strategy for query processing, ACM Trans. Database Systems, 1, 3, 223-241 (Sept. 1976) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
