article

Free access

Estimating block accesses in database organizations: a closed noniterative formula

Authors:

Kyu-Young Whang,

Gio Wiederhold,

Daniel SagalowiczAuthors Info & Claims

Communications of the ACM, Volume 26, Issue 11

Pages 940 - 944

https://doi.org/10.1145/182.358452

Published: 01 November 1983 Publication History

PDF eReader

References

[1]

Astrahan, M.M. et al. Performance of the System R access path selection mechanism. Information Processing, IFIP, North-Holland Publishing Co., 1980, pp. 487-491.

Google Scholar

[2]

Berstein, P.A., et al. Query processing in a system for distributed databases (SDD-1). ACM Trans. Database Syst. 6, 4 (December 1981), 602-625.

Digital Library

Google Scholar

[3]

Cardenas, A.F. Analysis and performance of inverted database structures. Comm. ACM 18, 5 (May 1975), 253-263.

Digital Library

Google Scholar

[4]

DEC system-10/DECSYSTEM-20 Hardware Reference Manual-Central Processor. Digital Equipment Corporation, 1978.

Google Scholar

[5]

Hammer, M. and Chan, A. Index selection in a self-adaptive database management system. Proc. Intl. Conf. on Management of Data, Washington, DC, ACM SIGMOD, June, 1976, pp. 1-8.

Crossref

Google Scholar

[6]

IBM, System 360 Scientific Subroutine Package. 1970.

Google Scholar

[7]

Luk, W.S. On Estimating Block Accesses in Database Organizations. Comm. ACM, this issue.

Digital Library

Google Scholar

[8]

Rothnie, J.B. and Lozano, T. Attribute-based file organization in a paged memory environment. Comm. ACM 17, 2 (February 1974), 63- 69.

Digital Library

Google Scholar

[9]

Severance, D.G. Some generalized modeling structures for use in design of file organizations. Ph.D. Thesis, University of Michigan, Ann Arbor, Michigan, 1972.

Digital Library

Google Scholar

[10]

Siler, K.F. A stochastic evaluation model for database organizations in data retrival systems. Comm. ACM 19, 2 (February 1976), 84-95.

Digital Library

Google Scholar

[11]

Waters, S.J. File design fallacies. Comput. J. 15,1 (1972), 1-4.

Crossref

Google Scholar

[12]

Waters, S.l. Estimating magnetic disc seeks. Comput. J. 18, 1 (1975), 12-17.

Crossref

Google Scholar

[13]

Waters, S.J. Hit ratios. Comput. I. 19,' (1976), 21-24.

Google Scholar

[14]

Whang, K., Wiederhold, G., and Sagalowicz, D. Separability: an approach to physical database design. Proc. Intl. Conf. on Very Large Databases, Cannes, France, IEEE, September, 1981, pp. 320-332.

Google Scholar

[15]

Whang, K., Wiederhold, G., Sagalowicz, D. Separability as an approach to physical database design. Tech. Rept. STAN-CS-81-898, Stanford University, October 1981 (also numbered as CSL TR-222).

Google Scholar

[16]

Wiederhold, G. Database Design. McGraw-Hill, New York 1977.

Digital Library

Google Scholar

[17]

Yao, S.B. Approximating block accesses in database organizations. Comm. ACM 20, 4 (April 1977), 260-261.

Digital Library

Google Scholar

[18]

Yao, S.B. Optimization of query evaluation algorithm. ACM Trans. Database Syst. 4, 2 (June 1979), 133-155.

Digital Library

Google Scholar

[19]

Yue, P.C. and Wong, C.K. Storage cost considerations in secondary index selection. Int. J. Comput. Inf. Sci. 4, 4 (1975), 307-327.

Crossref

Google Scholar

Cited By

View all

Hamirwasia VKarlapalem KValluri S(2019)FASTProceedings of Real-Time Business Intelligence and Analytics10.1145/3350489.3350490(1-10)Online publication date: 26-Aug-2019
https://dl.acm.org/doi/10.1145/3350489.3350490
NØrvåg KBratbergsengen K(2006)An analytical study of object identifier indexingDatabase and Expert Systems Applications10.1007/BFb0054466(38-49)Online publication date: 26-May-2006
https://doi.org/10.1007/BFb0054466
Nørvåg K(2004)Buffer performance modeling in the context of unclustered index accesses with non-uniform access patternInformation Sciences: an International Journal10.1016/j.ins.2003.12.006167:1-4(239-262)Online publication date: 2-Dec-2004
https://dl.acm.org/doi/10.1016/j.ins.2003.12.006
Show More Cited By

Index Terms

Estimating block accesses in database organizations: a closed noniterative formula
1. Information systems

Recommendations

On estimating block accesses in database organizations
Approximating block accesses in database organizations

When data records are grouped into blocks in secondary storage, it is frequently necessary to estimate the number of blocks X_D accessed for a given query. In a recent paper [1], Cardenas gave the expression X_D = m(1 - (1 - 1/m)^k), (1) assuming that ...
Towards the Maturity of Object-Relational Database Technology: Promises and Reality

Object-relational technology provides a significant increase in scalability and flexibility over the traditional relational databases. The additional object-relational features are particularly satisfying for advanced database applications that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 26, Issue 11

Nov. 1983

203 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/182

Editor:
Peter J. Denning
NASA Ames Research Center, Moffett Field, CA

Issue’s Table of Contents

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 1983

Published in CACM Volume 26, Issue 11

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
568
Total Downloads

Downloads (Last 12 months)100
Downloads (Last 6 weeks)14

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hamirwasia VKarlapalem KValluri S(2019)FASTProceedings of Real-Time Business Intelligence and Analytics10.1145/3350489.3350490(1-10)Online publication date: 26-Aug-2019
https://dl.acm.org/doi/10.1145/3350489.3350490
NØrvåg KBratbergsengen K(2006)An analytical study of object identifier indexingDatabase and Expert Systems Applications10.1007/BFb0054466(38-49)Online publication date: 26-May-2006
https://doi.org/10.1007/BFb0054466
Nørvåg K(2004)Buffer performance modeling in the context of unclustered index accesses with non-uniform access patternInformation Sciences: an International Journal10.1016/j.ins.2003.12.006167:1-4(239-262)Online publication date: 2-Dec-2004
https://dl.acm.org/doi/10.1016/j.ins.2003.12.006
Kim JChang J(2000)Vertically-partitioned parallel signature file methodJournal of Systems Architecture: the EUROMICRO Journal10.1016/S1383-7621(99)00035-146:8(655-673)Online publication date: 1-Jun-2000
https://dl.acm.org/doi/10.1016/S1383-7621%2899%2900035-1
Gündem T(1999)Near optimal multiple choice index selection for relational databasesComputers & Mathematics with Applications10.1016/S0898-1221(98)00256-937:2(111-120)Online publication date: Jan-1999
https://doi.org/10.1016/S0898-1221(98)00256-9
Kim JChang J(1998)Horizontally divided signature files on a parallel machine architectureJournal of Systems Architecture: the EUROMICRO Journal10.1016/S1383-7621(97)00015-544:9-10(723-735)Online publication date: 1-Jun-1998
https://dl.acm.org/doi/10.1016/S1383-7621%2897%2900015-5
Maamir AGrosky W(1997)Estimating block accesses in a B+-tree whose leaf records are of arbitrary sizeInformation Systems10.1016/S0306-4379(97)00018-522:5(325-331)Online publication date: 1-Jul-1997
https://dl.acm.org/doi/10.1016/S0306-4379%2897%2900018-5
Simha RMajumdar A(1997)An urn model with applications to database performance evaluationComputers and Operations Research10.1016/S0305-0548(96)00063-924:4(289-300)Online publication date: 1-Apr-1997
https://dl.acm.org/doi/10.1016/S0305-0548%2896%2900063-9
Kim JLee CChang J(1997)Two-dimensional dynamic signature file method using extendible hashing and frame-slicing techniquesInformation Sciences: an International Journal10.1016/S0020-0255(96)00188-098:1-4(1-26)Online publication date: 1-May-1997
https://dl.acm.org/doi/10.1016/S0020-0255%2896%2900188-0
Cho WPark CWhang KSon S(1996)A new method for estimating the number of objects satisfying an object-oriented query involving partial participation of classesInformation Systems10.1016/0306-4379(96)00014-221:3(253-267)Online publication date: 1-May-1996
https://dl.acm.org/doi/10.1016/0306-4379%2896%2900014-2
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

References

Cited By

Index Terms

Recommendations

On estimating block accesses in database organizations

Approximating block accesses in database organizations

Towards the Maturity of Object-Relational Database Technology: Promises and Reality

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations