Query Optimization for CODASYL Database Systems.

Umeshwar Dayal, Nathan Goodman: Query Optimization for CODASYL Database Systems. SIGMOD Conference 1982: 138-150

@inproceedings{DBLP:conf/sigmod/DayalG82,
  author    = {Umeshwar Dayal and
               Nathan Goodman},
  editor    = {Mario Schkolnick},
  title     = {Query Optimization for CODASYL Database Systems},
  booktitle = {Proceedings of the 1982 ACM SIGMOD International Conference on
               Management of Data, Orlando, Florida, June 2-4, 1982},
  publisher = {ACM Press},
  year      = {1982},
  pages     = {138-150},
  ee        = {http://doi.acm.org/10.1145/582353.582380, db/conf/sigmod/DayalG82.html},
  crossref  = {DBLP:conf/sigmod/82},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

One of the tasks of MULTIBASE, a system for integrated access to heterogeneous distributed databases, is to present a high-level query interface to navigational systems such as CODASYL. The interface compiles queries into efficient programs that implement the queries. The principal problem in constructing such an interface is access path optimization, i.e., the selection of an optimal sequence of access paths that must be traversed to process a given query. This paper identifies a class of queries for which efficient programs can be synthesized. It characterizes the strategies for processing a given query, and shows how to synthesize a program for implementing each strategy. It develops a model for estimating the cost of executing a program, and uses this model to find the optimal strategy for processing a given query.

Copyright © 1982 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod7592 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Mario Schkolnick (Ed.): Proceedings of the 1982 ACM SIGMOD International Conference on Management of Data, Orlando, Florida, June 2-4, 1982. ACM Press 1982

Contents

Online Edition: ACM Digital Library

References

[AHU74]: Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
[Bernstein et al.81]: Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie Jr.: Query Processing in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 6(4): 602-625(1981)
[BC81]: Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981)
[BE76]: ...
[BG80]: ...
[Chan et al. 81]: ...
[Collmeyer72]: Arthur J. Collmeyer: Implications of Data Independence on Architecture of Database Management Systems. SIGFIDET Workshop 1972: 307-321
[Dayal et al. 81]: ...
[DGK82]: Umeshwar Dayal, Nathan Goodman, Randy H. Katz: An Extended Relational Algebra with Control over Duplicate Elimination. PODS 1982: 117-123
[DL77]: ...
[Gerritsen75]: Rob Gerritsen: A Preliminary System for the Design of DBTG Data Structures. Commun. ACM 18(10): 551-557(1975)
[Gerritsen76]: ...
[Gerritsen77]: ...
[GG77]: Thomas J. Gambino, Rob Gerritsen: A Data Base Design Decision Support System. VLDB 1977: 534-544
[HD81]: Hai-Yann Hwang, Umeshwar Dayal: Using the Entity-Relationship Model for Implementing Multi-Model Database Systems. ER 1981: 235-256
[HS78]: Ellis Horowitz, Sartaj Sahni: Fundamentals of Computer Algorithms. Computer Science Press 1978
[JS80]: ...
[KG81]: Randy H. Katz, Nathan Goodman: View Processing in MULTIBASE, A Heterogeneous Database System. ER 1981: 257-277
[LA80]: Mary E. S. Loomis, Frank W. Allen: Paging Behaviour and Performance Optimization in a Codasyl DBMS. ICOD 1980: 119-134
[LOS72]: ...
[Selinger et al.79]: Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34
[Smith et al.81]: ...
[Wong77]: Eugene Wong: Retrieving Dispersed Data from SDD-1: A System for Distributed Databases. Berkeley Workshop 1977: 217-235
[Yao79]: S. Bing Yao: Optimization of Query Evaluation Algorithms. ACM Trans. Database Syst. 4(2): 133-155(1979)
[Zaniolo79]: ...