Robert Epstein
Michael Stonebraker
ABSTRACT
In this paper we present a new algorithm for retrieving and updating data from a distributed relational data base. Within such a data base, any number of relations can be distributed over any number of sites. Moreover, a user supplied distribution criteria can optionally be used to specify what site a tuple belongs to.The algorithm is an efficient way to process any query by "breaking" the qualification into separate "pieces" using a few simple heuristics. The cost criteria considered are minimum response time and minimum communications traffic. In addition, the algorithm can optimize separately for two models of a communication network representing respectively ARPANET and ETHERNET like networks. This algorithm is being implemented as part of the INGRES data base system.
- {CHAM76} Chamberlin, D. D.; "Relational Data Base Management: A Survey," Computing Survey, Vol. 8, no. 1, March 1976. Google Scholar
Digital Library
- {CHU76} Chu, Wesley W.; "Performance of File Directory Systems for Data Bases in Star and Distributed Networks," AFIPS Conference Proceedings, vol. 45, 1976.Google Scholar
- {CODD70} Codd, E. F.; "A Relational Model of Data for Large Shared Data Banks," CACM vol. 13, no. 6, June 1970. Google ScholarDigital Library
- {HELD75} Held, G. D., M. R. Stonebraker, and E. Wong; "INGRES - A Relational Data Base System," Proc. NCC vol. 44, 1975.Google Scholar
- {LAMP76} Lamport, L.; "Time, Clocks and Ordering of Events in a Distributed System," Mass. Computer Associates Report CA-7603-2911, March 1976.Google Scholar
- {METC76} Metcalf, R. M. and D. R. Boggs, "Ethernet: Distributed Packet Switching for Local Computer Networks," CACM, vol. 19, no. 7, July 1976. Google ScholarDigital Library
- {ROBE70} Roberts, L. and Wessler, B., "Computer Network Development to Achieve Resource Sharing," Proc. SJCC, 1970, AFIPS Press.Google Scholar
- {ROTH77} Rothnie, J. B. and N. Goodman; "An Overview of the Preliminary Design of SDD-1: A System for Distributed Databases," 1977 Berkeley Workshop on Distributed Data Management and Computer Networks, Lawrence Berkeley Laboratory, May 1977.Google Scholar
- {STON75} Stonebraker, M. R.; "Implementation of Integrity Constraints and Views by Query Modification", University of California, Electronics Research Laboratory, Memorandum ERL-M514, March 1975.Google Scholar
- {STON76} Stonebraker, M. R., E. Wong, P. Kreps and G. D. Held; "Design and Implementation of INGRES," ACM Trans. Database Systems, vol. 1, no. 3, Sept. 1976. Google ScholarDigital Library
- {STON77} Stonebraker, M. R. and E. Neuhold; "A Distributed Database Version of INGRES," 1977 Berkeley Workshop on Distributed Data Management and Computer Networks, Lawrence Berkeley Laboratory, May 1977.Google Scholar
- {THOM75} Thomas, R. H.; "A Solution to the Update Problem for Multiple Copy Databases Which Use Distributed Control," BBN Report 3340, Bolt Beranek and Newman Inc., Cambridge, Mass., July 1975.Google Scholar
- {WONG76} Wong, E. and K. Youssefi; "Decomposition - A Strategy for Query Processing," ACM Trans. Database Systems, vol. 1, no. 3, Sept. 1976. Google ScholarDigital Library
- {WONG77} Wong, E.; "Retrieving Dispersed Data from SDD-1; A System for Distributed Databases," 1977 Berkeley Workshop on Distributed Data Management and Computer Networks, Lawrence Berkeley Laboratory, May 1977.Google Scholar
- {YOUS78} Youssefi, K.; "Query Processing for a Relational Database System," Ph.D Dissertation, University of California, Berkeley, 1978, Electronics Research Laboratory, Memorandum UCB/ERL M78/3, January 6, 1978. Google ScholarDigital Library
- Distributed query processing in a relational data base system
Recommendations
Query processing in a system for distributed databases (SDD-1)
This paper describes the techniques used to optimize relational queries in the SDD-1 distributed database system. Queries are submitted to SDD-1 in a high-level procedural language called Datalanguage. Optimization begins by translating each ...
Query Interoperation Among Object-Oriented and Relational Databases
ICDE '95: Proceedings of the Eleventh International Conference on Data EngineeringWe develop an efficient algorithm for the query interoperation among existing heterogeneous object-oriented and relational databases. Our algorithm utilizes a canonical deductive database as a uniform representation of object-oriented schema and data. ...
Query processing over object views of relational data
This paper presents an approach to object view management for relational databases. Such a view mechanism makes it possible for users to transparently work with data in a relational database as if it was stored in an object-oriented (OO) database. A ...
Comments