ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Estimating block accesses in database organizations: a closed noniterative formula
Full text PdfPdf (432 KB)
Source
Communications of the ACM archive
Volume 26 ,  Issue 11  (November 1983) table of contents
Pages: 940 - 944  
Year of Publication: 1983
ISSN:0001-0782
Authors
Kyu-Young Whang  Stanford Univ., Stanford, CA
Gio Wiederhold  Stanford Univ., Stanford, CA
Daniel Sagalowicz  SRI International, Menlo Park, CA
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 6,   Downloads (12 Months): 33,   Citation Count: 24
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/182.358452
What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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.
2
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 Transactions on Database Systems (TODS), v.6 n.4, p.602-625, Dec. 1981  [doi>10.1145/319628.319650]
3
Alfonso F. Cárdenas, Analysis and performance of inverted data base structures, Communications of the ACM, v.18 n.5, p.253-263, May 1975  [doi>10.1145/360762.360766]
 
4
DEC system-10/DECSYSTEM-20 Hardware Reference Manual-Central Processor. Digital Equipment Corporation, 1978.
5
Michael Hammer , Arvola Chan, Index selection in a self-adaptive data base management system, Proceedings of the 1976 ACM SIGMOD international conference on Management of data, June 02-04, 1976, Washington, D.C.
 
6
IBM, System 360 Scientific Subroutine Package. 1970.
7
W. S. Luk, On estimating block accesses in database organizations, Communications of the ACM, v.26 n.11, p.945-947, Nov. 1983  [doi>10.1145/182.358456]
8
James B. Rothnie, Jr. , Tomas Lozano, Attribute based file organization in a paged memory environment, Communications of the ACM, v.17 n.2, p.63-69, Feb. 1974  [doi>10.1145/360827.360831]
 
9
Dennis Gordon Severance, Some generalized modeling structures for use in design of file organizations., 1972
10
Kenneth F. Siler, A stochastic evaluation model for database organizations in data retrieval systems, Communications of the ACM, v.19 n.2, p.84-95, Feb. 1976  [doi>10.1145/359997.360010]
 
11
Waters, S.J. File design fallacies. Comput. J. 15,1 (1972), 1-4.
 
12
Waters, S.l. Estimating magnetic disc seeks. Comput. J. 18, 1 (1975), 12-17.
 
13
Waters, S.J. Hit ratios. Comput. I. 19,' (1976), 21-24.
 
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.
 
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).
 
16
Gio C. Wiederhold, Database Design, McGraw-Hill, Inc., New York, NY, 1977
17
S. B. Yao, Approximating block accesses in database organizations, Communications of the ACM, v.20 n.4, p.260-261, April 1977  [doi>10.1145/359461.359475]
18
S. Bing Yao, Optimization of query evaluation algorithms, ACM Transactions on Database Systems (TODS), v.4 n.2, p.133-155, June 1979  [doi>10.1145/320071.320072]
 
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.

CITED BY  24
Lothar F. Mackert , Guy M. Lohman, Index scans using a finite LRU buffer: a validated I/O model, ACM Transactions on Database Systems (TODS), v.14 n.3, p.401-424, Sept. 1989
Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984
Giovanni Maria Sacco , Mario Schkolnick, Buffer management in relational database systems, ACM Transactions on Database Systems (TODS), v.11 n.4, p.473-498, Dec. 1986
R. Sacks-Davis , A. Kent , K. Ramamohanarao, Multikey access methods based on superimposed coding techniques, ACM Transactions on Database Systems (TODS), v.12 n.4, p.655-696, Dec. 1987
M. Schkolnick , P. Tiberio, Estimating the cost of updates in a relational database, ACM Transactions on Database Systems (TODS), v.10 n.2, p.163-179, June 1985
W. S. Luk, On estimating block accesses in database organizations, Communications of the ACM, v.26 n.11, p.945-947, Nov. 1983
Kyu-Young Whang , Ravi Krishnamurthy, Query optimization in a memory-resident domain relational calculus database system, ACM Transactions on Database Systems (TODS), v.15 n.1, p.67-95, March 1990
Kyu-Young Whang , Brad T. Vander-Zanden , Howard M. Taylor, A linear-time probabilistic counting algorithm for database applications, ACM Transactions on Database Systems (TODS), v.15 n.2, p.208-229, June 1990
Jeong-Ki Kim , Jae-Woo Chang, A new parallel signature file method for efficient information retrieval, Proceedings of the fourth international conference on Information and knowledge management, p.66-73, November 29-December 02, 1995, Baltimore, Maryland, United States
G. Diehr , A. N. Saharia, Estimating Block Accesses in Database Organizations, IEEE Transactions on Knowledge and Data Engineering, v.6 n.3, p.497-499, June 1994
C. Sartori , M. R. Scalas, Partial Indexing for Nonuniform Data Distributions in Relational DBMS's, IEEE Transactions on Knowledge and Data Engineering, v.6 n.3, p.420-429, June 1994
Yannis Manolopoulos , J. G. Kollias, Expressions for Completely and Partly Unsuccessful Batched Search of Sequential and Tree-Structured Files, IEEE Transactions on Software Engineering, v.15 n.6, p.794-799, June 1989
P. Ciaccia, Block Access Estimation for Clustered Data, IEEE Transactions on Knowledge and Data Engineering, v.5 n.4, p.712-718, August 1993
F. Grandi , M. R. Scalas, Block Access Estimation for Clustered Data Using a Finite LRU Buffer, IEEE Transactions on Software Engineering, v.19 n.7, p.641-660, July 1993
Michael V. Mannino , Paicheng Chu , Thomas Sager, Statistical profile estimation in database systems, ACM Computing Surveys (CSUR), v.20 n.3, p.191-221, Sept. 1988
P. -C. Chu, Estimating Block Selectivities for Physical Database Design, IEEE Transactions on Knowledge and Data Engineering, v.4 n.1, p.89-98, February 1992
Gregory Piatetsky-Shapiro , Charles Connell, Accurate estimation of the number of tuples satisfying a condition, ACM SIGMOD Record, v.14 n.2, June 1984
Kjetil Nørvåg, Buffer performance modeling in the context of unclustered index accesses with non-uniform access pattern, Information Sciences—Informatics and Computer Science: An International Journal, v.167 n.1-4, p.239-262, 2 December 2004
Sheau-Dong Lang , James R. Driscoll , Jiann H. Jou, A unified analysis of batched searching of sequential and tree-structured files, ACM Transactions on Database Systems (TODS), v.14 n.4, p.604-618, Dec. 1989
Rafiul Ahad , K. V. Bapa , Dennis McLeod, On estimating the cardinality of the projection of a database relation, ACM Transactions on Database Systems (TODS), v.14 n.1, p.28-40, March 1989
Bernhard Seeger , Per-Åke Larson , Ron McFayden, Reading a Set of Disk Pages, Proceedings of the 19th International Conference on Very Large Data Bases, p.592-603, August 24-27, 1993
Kyu-Young Whang , Gio Wiederhold , Daniel Sagalowicz, Physical Design of Network Model Databases Using the Property of Separability, Proceedings of the 8th International Conference on Very Large Data Bases, p.98-107, September 08-10, 1982
Giovanni Maria Sacco, Index Access with a Finite Buffer, Proceedings of the 13th International Conference on Very Large Data Bases, p.301-309, September 01-04, 1987
Pavel Zezula , Paolo Ciaccia , Paolo Tiberio, Key-based partitioned bit-sliced signature file, ACM SIGIR Forum, v.29 n.2, p.20-34, Fall 1995

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models; Selection process


General Terms:
Performance


Keywords:
blocking factor, conditional probability, database, database access cost, database performance, information processing, number of block access, page, performance, query-processing, records

Collaborative Colleagues:
Kyu-Young Whang: colleagues
Gio Wiederhold: colleagues
Daniel Sagalowicz: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player