Abstract
A multidatabase system provides a logically integrated view of existing, distributed, possibly inconsistent, databases that may be stored under heterogeneous database systems. Query processing in a multidatabase system consists of four tasks. First, queries over the user’s integrated view must be modified into equivalent queries over the local schemas of the existing databases. Second, the modified queries must be globally optimized to produce an efficient global execution plan, which specifies local processing steps at individual sites, communication steps iii which data is moved between sites, postprocessing steps in which the results of local processing steps are combined, and the order in which these steps must be performed. Third, the single-site queries to be executed in the local processing steps must be locally optimized to select efficient access paths. Finally, the optimized single-site queries must be translated into the data languages of the host database management systems. This paper address the first three of these problems.
Logical database integration is achieved primarily through the use of generalization, which is modelled algebraically as a sequence of outerjoins and aggregation operations. Conventional query modification and distributed query processing techniques are inadequate for such views. Previous research on distributed query processing techniques has focused on joins, ignoring selections and projections because they are easy and inexpensive to process in a conventional distributed database system. However, even selection and projection queries over views defined by outer-joins and aggregates can be expensive to process. We develop solutions to this problem. We also solve the problem of local query optimization for navigational database systems such as CODASYL. The main problem here is to compile queries in a high-level query-language into programs that use efficient navigational access paths for evaluating the queries.
This research was jointly supported by the Defense Advanced Research Projects Agency of the Department of Defense and the Naval Electronic Systems Command and was monitored by the Naval Electronic Systems Command under Contract No. N00039-82-C-0226. The views and conclusions contained in this document are those of the author and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the DARPA, the NAVELÉX, or the U.S. Government.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Astrahan MM et al, “System R: A relational approach to database management”, ACM Transactions on Database Systems, 1,2, June 1976, 97–137
Bernstein PA, Chiù DM, “Using semi-joins to solve relational queries”, Journal of the ACM, 28,1, January 1981, 25–40
Bernstein PA, Goodman N, Wong E, Reeve CL, Rothnie JB, “Query processing in a system for distributed databases (SDD-1)”, ACM Transactions on Database Systems 6,4, December 1981,602–625
Chan A, Dayal U, Fox SA, Goodman N, Ries D, Skeen D, “Overview of an Ada-compatible distributed database manager (DDM)”, Proc. ACM SIGMOD Conference, June 1983, 228–237
Codd EF, “Extending the database relational model to capture more meaning”, ACM Transactions on Database Systems, 4,4, December 1979, 397–434
Daniels D, Seiinger PG, Haas LM, Lindsay BG, Mohan C, Walker A, Wilms P, “An introduction to distributed query compilation in R”, Proc. 2nd International Conference on Distributed Databases, Berlin, September 1982. Also available as IBM Research Laboratory RJ3497, San Jose, Calif.
Dayal U, Goodman N, Landers TA, Olson K, Smith JM, Yedwab L, “Local query optimization in MULTIBASE-a system for heterogeneous distributed databases”, Technical Report, CCA-81–11, Computer Corporation of America, Cambridge, MA, 1981
Dayal U, Landers TA, Yedwab L, “Global query optimization in MULTIBASE: a system for heterogeneous distributed databases”, Technical Report CCA-82–05, Computer Corporation of America, Cambridge, MA, 1982
Dayal U, Goodman N, “Query optimization for COD ASYL database systems”, Proc. ACM SIGMOD Conference, Orlando, June 1982, 138–150
Dayal U, Hwang HY, “View definition and generalization for database integration in MULTI-BASE: a system for heterogeneous distributed databases”, Proc. 6th Berkeley Workshop on Distributed Database Management and Computer Networks, February 1982, 203–238. (A revised version appeared in IEEE Transactions on Software Engineering, SE-10,6, November 1984, 628–644)
Dayal U, Goodman N, Katz RH, “An extended relational algebra with control over duplicate elimination”, Proc. ACM PODS Conference, 1982, 117–123.
Dayal U, “Processing queries over generalization hierarchies in a multidatabase system”, Proc. VLDB Conference, 1983, 342–353.
Dayal U, “Processing queries with quantifiers: a horticultural approach”, Proc. ACM PODS Conference, 1983, 125–136
Epstein R, Stonebraker M, Wong E, “Distributed query processing in a relational data base system”,Proc. ACM SIGMOD Conference, Austin, TX, May 1978, 169–180
Goldhirsh D, Yedwab L, “Processing read-only queries over views with generalization”, Proc. VLDB, 1984
Held GD, Stonebraker MR, Wong E, “INGRES: A relational database system”, Proc. AFIPS NCC, 1975, 409–416
Hevner AR, Yao SB, “Query processing in distributed database systems”, IEEE Transactions on Software Engineering, SE-5,3, May 1979, 177–187
Hwang HY, “Database integration and query optimization in multi-database systems”, Ph. D. Dissertation, Dept. of Computer Sciences, The University of Texas at Austin, Austin, TX., 1982
Hwang HY, Dayal U, “Using semi-outerjoins to process queries in a multidatabase system”, Proc. ACM PODS Conference, 1984
Katz R, Goodman N, “View processing in MULTIBASE-a heterogeneous database system”, Entity-Relationship Approach to Information Modelling and Analysis, Chen PP (ed.), ER Institute, Saugus, CA, 1981
Landers TA, Rosenberg RL, “An overview of MULTIBASE”, Distributed Databases, Schneider HJ (ed), North Holland, 1982,153–184
Motro A, Buneman P, “Constructing superviews”, Proc. ACM SIGMOD Conference, Ann Arbor, 1981, 56–64
Rothnie PA, Bernstein PA, Fox S, Goodman N, Hammer M, Landers T, Reeve C, Shipman DW, Wong E, “Introduction to a system for distributed databases (SDD-1)”, ACM Trans on Database Systems, 5,1, March 1980, 1–17
Ries D, Chan A, Dayal U, Fox SA, Lin WTK, Yedwab L, “Decompilation, and optimization for ADAPLEX: a procedural database language”, Technical Report CCA-82–04, Computer Corporation of America, 1982
Selinger PG, Adiba M, “Access path selection in distributed database management systems”, Proc. International Conference on Data Bases, Deen and Hammersly (eds), University of Aberdeen, July 1980, 204–215. Also available as IBM Research Laboratory RJ2883, San Jose, California
Shipman DW, “The functional data model and the data language DAPLEX”, ACM Transactions on Database Systems, 6,1, March 1981, 140–173
Smith JM, Bernstein PA, Dayal U, Goodman N, Landers TA, Lin KWT, Wong E, “MULTIBASE-integrating heterogeneous distributed database systems”, Proc. AFIPS National Computer Conference, 5, 1981, 487–499
Smith JM, Smith DCP, “Data base abstractions: aggregation and generalization”, ACM Transac-tions on Database Systems, 2,2, June 1977, 105–133
Stonebraker M, “A distributed database version of INGRES”, Proc. Berkeley Workshop, May 1977
Whang KY, Widerhold G, Sagalowicz D, “Separability-an approach to physical database design”, Proc. VLDB Conference, 1981, 320–332
Williams R, Daniels D, Haas L, Lapis G, Lindsay B, Ng P, Obermark R, Seiinger P, Walker A, Wilms P, Yost R, “R: An overview of the architecture”, Proc. International Conference on Databases: Improving Database Usability and Responsiveness, Jerusalem, Scheuermann P, (ed), Academic Press, New York, 1982,1–27. Also available as IBM Research Laboratory RJ3325, San Jose, California
Yao SB, “Approximating block access in database organizations”, Communications ACM, 20, April 1977, 260–261
Yu CT, Ozsoyoglu MZ, “An algorithm for tree-query membership of a distributed query”, IEEE COMPSAC, Chicago, November 1979, 306–312
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1985 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Dayal, U. (1985). Query Processing in a Multidatabase System. In: Kim, W., Reiner, D.S., Batory, D.S. (eds) Query Processing in Database Systems. Topics in Information Systems. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-82375-6_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-82375-6_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-82377-0
Online ISBN: 978-3-642-82375-6
eBook Packages: Springer Book Archive