Article

Free access

Evaluation of database access paths

Authors:

David DeJongAuthors Info & Claims

SIGMOD '78: Proceedings of the 1978 ACM SIGMOD international conference on management of data

Pages 66 - 77

https://doi.org/10.1145/509252.509273

Published: 31 May 1978 Publication History

Abstract

An evaluation system which estimates the performance of database access paths is presented. The system is based on a generalized model of access paths and is applicable to most access paths for searching a database system. The study brings to light many subtle but important parameters which can have a significant effect on the performance of the access paths, and which, then, must be taken into consideration in the selection of such paths.

References

[1]

Astrahan, M. M. and D. D. Chamberlin, "Implementation of a structured English query language," Comm. ACM, Vol. 18, No. 10 (Oct.1975), pp. 580-588.

Digital Library

[2]

Astrahan, M. M. et al, "System R: A relational approach to data base management," ACM Trans. on Database Systems, Vol. 1, No. 2 (June 1976). pp. 97-137.

Digital Library

[3]

Blasgen, M. W. and K. P. Eswaren, On the evaluation of queries in a data base system, IBM Research Report FJ 1945, IBM Research Laboratory, San Jose, California, 95193 (April 1976).

[4]

Blasgen, M. W. and K. P. Eswaren, "Storage access in relational data bases," IBM Systems J., No. 4, 1977, pp. 363-377.

[5]

Cardenas, A. F., "Analysis and performance of inverted data base structures," Comm. ACM, Vol. 18, No. 5 (May 1975), pp. 253-263.

Digital Library

[6]

Codd, E. F., "A relational model of data for large shared data banks," Comm. ACM, Vol. 13, No. 6 (June 1970), pp. 377-387.

Digital Library

[7]

Date, C. J., An Introduction to Database Systems, Addison-Wesley, 1977.

Digital Library

[8]

Gotleib, L., "Computing joins of relations." Proc. ACM-SIGMOD Conf., San Jose, California, May 1975, New York: ACM, pp. 53-63.

Digital Library

[9]

Hsiao, D. and F. Harary, "A formal system for information retrieval from files," Comm. ACM, Vol. 13. No. 2 (Feb 1970), pp. 67-73; "Corrigendum," Comm. ACM, Vol. 13, No. 4 (April 1970), p. 266.

Digital Library

[10]

Information Management System, General Information Manual, Form GH20-0765, IBM Corp., Data Processing Division, White Plains,NY 10604.

[11]

Knuth, D. E., The Art of Computer Programming, Vol. 3 Sorting and Searching, Addison-Wesley, 1973.

Digital Library

[12]

Palermo, E. P., "A data base search problem," Proc. 4th Int'l Symposium of Computers and Information Science, Miami Beach, Fla., Dec. 1972.

[13]

Pecherer, R. M., "Efficient evaluation of expressions in a relational algebra," Proc. ACM Pacific 75 Conf., April 1975, pp. 44-49.

[14]

Rothnie, J. B., "Evaluating inter-entry retrieval expressions in a relational data base management system," Proc. AFIPS 1975 NCC, Vol. 44, Montvale, NJ; AFIPS, pp. 417-423.

[15]

Severance, D. G., "Some generalized modeling structures for use in design of file organizations," Ph.D.Diss,U of Mich/Ann Arbor,1975.

Digital Library

[16]

Smith, J. M., and P. Y. T. Chang, "Optimizing the performance of a relational algebra and database interface," Comm. ACM, Vol. 18, No. 10 (October 1975), pp. 568-579.

Digital Library

[17]

Stonebraker, M., E. Wong, P. Kreps and G. Held, "The Design and Implementation of INGRES," ACM Transactions on Database Systems, Vol. 1, No. 3 (Sept. 1976). pp. 189-222.

Digital Library

[18]

Wong, E. and K. Youssefi, "Decomposition--a strategy for query processing," ACM Trans. on Database Systems, Vol. 1, No. 3 (Sept 1970, pp. 223-241.

Digital Library

[19]

Yao, S. B., "An attribute-based model for database access cost analysis," ACM Transactions on Database Systems, Vol. 2, No. 1 (March 1977). pp. 45-67.

Digital Library

[20]

Yao, S. B., "Approximating block accesses in data base organizations," Comm. ACM, Vol. 20, No. 4 (April 1977), pp. 260-261.

Digital Library

[21]

Yao, S. B., "Optimization of query evaluation algorithms," January 1978 (submitted for publication).

Cited By

Tang LFu YZeng YLi ZLi S(2021)Flow entry conflict detection and resolution scheme for software-defined networkingInternational Journal of Electrical Engineering & Education10.1177/0020720921998237Online publication date: 3-Mar-2021
https://doi.org/10.1177/0020720921998237
Idreos SZoumpatianos KHentschel BKester MGuo DDas GJermaine CBernstein P(2018)The Data CalculatorProceedings of the 2018 International Conference on Management of Data10.1145/3183713.3199671(535-550)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3183713.3199671
March SRho S(1995)Allocating Data and Operations to Nodes in Distributed Database DesignIEEE Transactions on Knowledge and Data Engineering10.1109/69.3822997:2(305-317)Online publication date: 1-Apr-1995
https://dl.acm.org/doi/10.1109/69.382299
Show More Cited By

Evaluation of database access paths
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory

Recommendations

Conceptual database security access permissions
EC'09: Proceedings of the 10th WSEAS international conference on evolutionary computing

High-level conceptual database design is a widespread method in database built with conceptual models we will illustrate the "mini world" of the database via Database Management System (DBMS) in an independent form. The form will be mapped by the use of ...
Improved algorithms for the k simple shortest paths and the replacement paths problems

Given a directed, non-negatively weighted graph G=(V,E) and s,t@?V, we consider two problems. In the k simple shortest paths problem, we want to find the k simple paths from s to t with the k smallest weights. In the replacement paths problem, we want ...
Role-Based Access Control for Grid Database Services Using the Community Authorization Service

In this paper, we propose a role-based access control (RBAC) method for Grid database services in Open Grid Services Architecture-Data Access and Integration (OGSA-DAI). OGSA-DAI is an efficient Grid-enabled middleware implementation of interfaces and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '78: Proceedings of the 1978 ACM SIGMOD international conference on management of data

May 1978

180 pages

ISBN:9781450373425

DOI:10.1145/509252

Conference Chair:
John Lyon
Colonial Penn Group Data Corporation, Philadelphia, PA
,
General Chairs:
Alfred G. Dale
University of Texas at Austin, Austin, Texas
,
Nell B. Dale
University of Texas at Austin, Austin, Texas
,
Program Chair:
Eugene I. Lowenthal
MRI Systems Corporation, Austin, Texas

Copyright © 1978 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 May 1978

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
404
Total Downloads

Downloads (Last 12 months)62
Downloads (Last 6 weeks)15

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tang LFu YZeng YLi ZLi S(2021)Flow entry conflict detection and resolution scheme for software-defined networkingInternational Journal of Electrical Engineering & Education10.1177/0020720921998237Online publication date: 3-Mar-2021
https://doi.org/10.1177/0020720921998237
Idreos SZoumpatianos KHentschel BKester MGuo DDas GJermaine CBernstein P(2018)The Data CalculatorProceedings of the 2018 International Conference on Management of Data10.1145/3183713.3199671(535-550)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3183713.3199671
March SRho S(1995)Allocating Data and Operations to Nodes in Distributed Database DesignIEEE Transactions on Knowledge and Data Engineering10.1109/69.3822997:2(305-317)Online publication date: 1-Apr-1995
https://dl.acm.org/doi/10.1109/69.382299
Omiecinski E(1989)Heuristics for Join Processing Using Nonclustered IndexesIEEE Transactions on Software Engineering10.1109/32.2172215:1(18-25)Online publication date: 1-Jan-1989
https://dl.acm.org/doi/10.1109/32.21722
Lu HCarey M(1985)Some experimental results on distributed join algorithms in a local networkProceedings of the 11th international conference on Very Large Data Bases - Volume 1110.5555/1286760.1286787(292-304)Online publication date: 21-Aug-1985
https://dl.acm.org/doi/10.5555/1286760.1286787
DeWitt DKatz ROlken FShapiro LStonebraker MWood D(1984)Implementation techniques for main memory database systemsACM SIGMOD Record10.1145/971697.60226114:2(1-8)Online publication date: 1-Jun-1984
https://dl.acm.org/doi/10.1145/971697.602261
DeWitt DKatz ROlken FShapiro LStonebraker MWood DSmith DYormark B(1984)Implementation techniques for main memory database systemsProceedings of the 1984 ACM SIGMOD international conference on Management of data10.1145/602259.602261(1-8)Online publication date: 18-Jun-1984
https://dl.acm.org/doi/10.1145/602259.602261
Ibaraki TKameda T(1984)On the optimal nesting order for computing N-relational joinsACM Transactions on Database Systems10.1145/1270.14989:3(482-502)Online publication date: 1-Sep-1984
https://dl.acm.org/doi/10.1145/1270.1498
Sevcik K(1981)Data base system performance prediction using an analytical model (invited paper)Proceedings of the seventh international conference on Very Large Data Bases - Volume 710.5555/1286831.1286850(182-198)Online publication date: 9-Sep-1981
https://dl.acm.org/doi/10.5555/1286831.1286850
Kim WSprowls RChen P(1980)A new way to compute the product and join of relationsProceedings of the 1980 ACM SIGMOD international conference on Management of data10.1145/582250.582278(179-187)Online publication date: 14-May-1980
https://dl.acm.org/doi/10.1145/582250.582278
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents