Approximating the Number of Accesses in Database Organizations.

@article{DBLP:journals/cacm/Yao77,
  author    = {S. Bing Yao},
  title     = {Approximating the Number of Accesses in Database Organizations},
  journal   = {Commun. ACM},
  volume    = {20},
  number    = {4},
  year      = {1977},
  pages     = {260-261},
  ee        = {db/journals/cacm/Yao77.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1977 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

• 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/An4-1 or /cdrom

• 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/aDVD2 or /dvd

Online Edition: ACM Digital Library

Referenced by

1. Zhe Li, Kenneth A. Ross: Fast Joins Using Join Indices. VLDB J. 8(1): 1-24(1999)
2. Cheng Hian Goh, Beng Chin Ooi, D. Sim, Kian-Lee Tan: GHOST: Fine Granularity Buffering of Indexes. VLDB 1999: 339-350
3. Danièle Gardy, Laurent Némirovski: Urn Models and Yao's Formula. ICDT 1999: 100-112
4. Ladjel Bellatreche, Kamalakar Karlapalem, Qing Li: Derived Horizontal Class Partitioning in OODBs: Design Strategies, Analytical Model and Evaluation. ER 1998: 465-479
5. Matteo Golfarelli, Stefano Rizzi: Methodological Framework for Data Warehouse Design. DOLAP 1998: 3-9
6. Ming-Syan Chen, Hui-I Hsiao, Philip S. Yu: On Applying Hash Filters to Improving the Execution of Multi-Join Queries. VLDB J. 6(2): 121-131(1997)
7. Uday R. Kulkarni, Richard G. Ramirez: Independently Updated Views. IEEE Trans. Knowl. Data Eng. 9(5): 798-812(1997)
8. Michael Gesmann: A Cost Model for Parallel Navigational Access in Complex-Object DBMSs. DASFAA 1997: 1-10
9. Chi-Wai Fung, Kamalakar Karlapalem, Qing Li: Cost-Driven Evaluation of Vertical Class Partitioning in Object-Oriented Databases. DASFAA 1997: 11-20
10. Wan-Sup Cho, Seung-Sun Lee, Kyu-Young Whang, Yong-Ik Yoon: Query Optimization Techniques Utilizing Path Indexes in Object-Oriented Database Systems. DASFAA 1997: 21-29
11. John Mylopoulos, Vinay K. Chaudhri, Dimitris Plexousakis, Adel Shrufi, Thodoros Topaloglou: Building Knowledge Base Management Systems. VLDB J. 5(4): 238-263(1996)
12. Georges Gardarin, Jean-Robert Gruser, Zhao-Hui Tang: Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases. VLDB 1996: 390-401
13. Praveen Seshadri, Joseph M. Hellerstein, Hamid Pirahesh, T. Y. Cliff Leung, Raghu Ramakrishnan, Divesh Srivastava, Peter J. Stuckey, S. Sudarshan: Cost-Based Optimization for Magic: Algebra and Implementation. SIGMOD Conference 1996: 435-446
14. Boris Shidlovsky, Elisa Bertino: A Graph-Theoretic Approach to Indexing in Object-Oriented Databases. ICDE 1996: 230-237
15. Arun N. Swami, K. Bernhard Schiefer: Estimating Page Fetches for Index Scans with Finite LRU Buffers. VLDB J. 4(4): 675-701(1995)
16. Salvatore T. March, Sangjyu Rho: Allocating Data and Operations to Nodes in Distributed Database Design. IEEE Trans. Knowl. Data Eng. 7(2): 305-317(1995)
17. Elisa Bertino, Paola Foscoli: Index Organizations for Object-Oriented Database Systems. IEEE Trans. Knowl. Data Eng. 7(2): 193-209(1995)
18. Georges Gardarin, Jean-Robert Gruser, Zhao-Hui Tang: A Cost Model for Clustered Object-Oriented Databases. VLDB 1995: 323-334
19. Adel Shrufi, Thodoros Topaloglou: Query Processing for Knowledge Bases Using Join Indices. CIKM 1995: 158-166
20. Eric Hughes, Marianne Winslett: The Index Suggestion Problem for Object Database Applications. CIKM 1995: 50-57
21. Elisa Bertino, S. Salerno, Boris Shidlovsky: Enhanced Nested-Inherited Index for OODBMS. CIKM 1995: 58-65
22. Elisa Bertino: Index Configuration in Object-Oriented Databases. VLDB J. 3(3): 355-399(1994)
23. Claudio Sartori, Maria Rita Scalas: Partial Indexing for Nonuniform Data Distributions in relational DBMS's. IEEE Trans. Knowl. Data Eng. 6(3): 420-429(1994)
24. Edward Omiecinski, Liehuey Lee, Peter Scheuermann: Performance Analysis of a Concurrent File Reorganization Algorithm for Record Clustering. IEEE Trans. Knowl. Data Eng. 6(2): 248-257(1994)
25. Patrick Martin, Per-Åke Larson, Vinay Deshpande: Parallel Hash-Based Join Algorithms for a Shared-Everything. IEEE Trans. Knowl. Data Eng. 6(5): 750-763(1994)
26. George Diehr, Aditya N. Saharia: Estimating Block Accesses in Database Organizations. IEEE Trans. Knowl. Data Eng. 6(3): 497-499(1994)
27. Zhaohui Xie, Jiawei Han: Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases. VLDB 1994: 522-533
28. Arun N. Swami, K. Bernhard Schiefer: Estimating Page Fetches for Index Scans with Finite LRU Buffers. SIGMOD Conference 1994: 173-184
29. Sunil Choenni, Elisa Bertino, Henk M. Blanken, Thiel Chang: On the Selection of Optimal Index Configuration in OO Databases. ICDE 1994: 526-537
30. Boris Novikov: Indices for Set-Theoretical Operations in Object Bases. ADBIS 1994: 208-216
31. Gultekin Özsoyoglu, Aladdin Hafez: Near-Optimum Storage Models for Nested Relations Based on Workload Information. IEEE Trans. Knowl. Data Eng. 5(6): 1018-1038(1993)
32. Paolo Ciaccia: Block Access Estimation for Clustered Data. IEEE Trans. Knowl. Data Eng. 5(4): 712-718(1993)
33. Ming-Syan Chen, Philip S. Yu: Combining Join and Semi-Join Operations for Distributed Query Processing. IEEE Trans. Knowl. Data Eng. 5(3): 534-542(1993)
34. Ming-Syan Chen, Hui-I Hsiao, Philip S. Yu: Applying Hash Filters to Improving the Execution of Bushy Trees. VLDB 1993: 505-516
35. Bernhard Seeger, Per-Åke Larson, Ron McFadyen: Reading a Set of Disk Pages. VLDB 1993: 592-603
36. Alfons Kemper, Guido Moerkotte, Klaus Peithner: A Blackboard Architecture for Query Optimization in Object Bases. VLDB 1993: 543-554
37. Chung-Min Chen, Nick Roussopoulos: Adaptive Database Buffer Allocation Using Query Feedback. VLDB 1993: 342-353
38. Wei Sun, Yibei Ling, Naphtali Rishe, Yi Deng: An Instant and Accurate Estimation Method for Joins and Selection in a Retrieval-Intensive Environment. SIGMOD Conference 1993: 79-88
39. Oliver Günther: Efficient Computation of Spatial Joins. ICDE 1993: 50-59
40. Pai-Cheng Chu: Estimating Block Selectivities for Physical Database Design. IEEE Trans. Knowl. Data Eng. 4(1): 89-98(1992)
41. Yu-Wang Wang, Eric N. Hanson: A Performance Comparison of the Rete and TREAT Algorithms for Testing Database Rule Conditions. ICDE 1992: 88-97
42. Jenn-Yang Tien, Wei-Pang Yang: Comments on 'Hash-Based and Index-Based Join Algorithms for Cube and Ring Connected Multicomputers'. IEEE Trans. Knowl. Data Eng. 3(3): 387-389(1991)
43. Christos Faloutsos, Raymond T. Ng, Timos K. Sellis: Predictive Load Control for Flexible Buffer Allocation. VLDB 1991: 265-274
44. Raymond T. Ng, Christos Faloutsos, Timos K. Sellis: Flexible Buffer Allocation Based on Marginal Gains. SIGMOD Conference 1991: 387-396
45. Arie Segev, J. Leon Zhao: Evaluation of Rule Processing Strategies In Expert Databases. ICDE 1991: 404-412
46. William Perrizo, James Gustafson, Daniel Thureen, David Wenberg: Domain Vector Accelerator for Relational Operations. ICDE 1991: 491-498
47. Sivarama P. Dandamudi, Siu-Lun Au: Locking Granularity in Multiprocessor Database Systems. ICDE 1991: 268-277
48. Edward Omiecinski, Peter Scheuermann: A Parallel Algorithm for Record Clustering. ACM Trans. Database Syst. 15(4): 599-624(1990)
49. Fazli Can, Esen A. Ozkarahan: Concepts and Effectiveness of the Cover-Coefficient-Based Clustering Methodology for Text Databases. ACM Trans. Database Syst. 15(4): 483-517(1990)
50. Hongjun Lu, Kian-Lee Tan, Ming-Chien Shan: Hash-Based Join Algorithms for Multiprocessor Computers. VLDB 1990: 198-209
51. Frank Olken, Doron Rotem: Random Sampling from Database Files: A Survey. SSDBM 1990: 92-111
52. Himawan Gunadhi, Arie Segev: A Framework for Query Optimization in Temporal Databases. SSDBM 1990: 131-147
53. Alfons Kemper, Guido Moerkotte: Access Support in Object Bases. SIGMOD Conference 1990: 364-374
54. Arie Segev, Weiping Fang: Currency-Based Updates to Distributed Materialized Views. ICDE 1990: 512-520
55. José A. Blakeley, Nancy L. Martin: Join Index, Materialized View, and Hybrid-Hash Join: A Performance Analysis. ICDE 1990: 256-263
56. Elisa Bertino: Optimization of Queries using Nested Indices. EDBT 1990: 44-59
57. Yannis Manolopoulos, John G. Kollias: Performance of a Two-Headed Disk System when Serving Database Queries Under the Scan Policy. ACM Trans. Database Syst. 14(3): 425-442(1989)
58. Lothar F. Mackert, Guy M. Lohman: Index Scans Using a Finite LRU Buffer: A Validated I/O Model. ACM Trans. Database Syst. 14(3): 401-424(1989)
59. Sheau-Dong Lang, James R. Driscoll, Jiann H. Jou: A Unified Analysis of Batched Searching of Sequential and Tree-Structured Files. ACM Trans. Database Syst. 14(4): 604-618(1989)
60. Jaideep Srivastava, Jack S. Eddy Tan, Vincent Y. Lum: TBSAM: An Access Method for Efficient Processing of Statistical Queries. IEEE Trans. Knowl. Data Eng. 1(4): 414-423(1989)
61. Arie Segev, Jooseok Park: Updating Distributed Materialized Views. IEEE Trans. Knowl. Data Eng. 1(2): 173-184(1989)
62. Edward Omiecinski, Eileen Tien Lin: Hash-Based and Index-Based Join Algorithms for Cube and Ring Connected Multicomputers. IEEE Trans. Knowl. Data Eng. 1(3): 329-343(1989)
63. Elisa Bertino, Won Kim: Indexing Techniques for Queries on Nested Objects. IEEE Trans. Knowl. Data Eng. 1(2): 196-214(1989)
64. Frank Olken, Doron Rotem: Random Sampling from B+ Trees. VLDB 1989: 269-277
65. Eugene J. Shekita, Michael J. Carey: Performance Enhancement Through Replication in an Object-Oriented DBMS. SIGMOD Conference 1989: 325-336
66. Silvio Salza, Mario Terranova: Evaluating the Size of Queries on Relational Databases with non Uniform Distribution and Stochastic Dependence. SIGMOD Conference 1989: 8-14
67. Elena Barcucci, Alessandra Chiuderi, Renzo Pinzani, M. Cecilia Verri: Index Selection in Relational Databases. MFDBS 1989: 24-36
68. Arie Segev, Jooseok Park: Maintaining Materialized Views in Distributed Databases. ICDE 1989: 262-270
69. Michael V. Mannino, Paicheng Chu, Thomas Sager: Statistical Profile Estimation in Database Systems. ACM Comput. Surv. 20(3): 191-221(1988)
70. Jaideep Srivastava, Doron Rotem: Analytical Modeling of Materialized View Maintenance. PODS 1988: 126-134
71. Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987)
72. Ron Sacks-Davis, Alan J. Kent, Kotagiri Ramamohanarao: Multikey Access Methods Based on Superimposed Coding Techniques. ACM Trans. Database Syst. 12(4): 655-696(1987)
73. Jane Fedorowicz: Database Performance Evaluation in an Indexed File Environment. ACM Trans. Database Syst. 12(1): 85-110(1987)
74. Giovanni Maria Sacco: Index Access with a Finite Buffer. VLDB 1987: 301-309
75. Jianzhong Li, Harry K. T. Wong: Batched Interpolation Searching on Databases. ICDE 1987: 18-24
76. Bao-Chyuan Jenq, Walter H. Kohler, Donald F. Towsley: A Queueing Network Model for a Distributed Database Testbed System. ICDE 1987: 62-71
77. Giovanni Maria Sacco, Mario Schkolnick: Buffer Management in Relational Database Systems. ACM Trans. Database Syst. 11(4): 473-498(1986)
78. Brad T. Vander Zanden, Howard M. Taylor, Dina Bitton: Estimating Block Accessses when Attributes are Correlated. VLDB 1986: 119-127
79. Patrick Valduriez, Setrag Khoshafian, George P. Copeland: Implementation Techniques of Complex Objects. VLDB 1986: 101-110
80. Frank Olken, Doron Rotem: Simple Random Sampling from Relational Databases. VLDB 1986: 160-169
81. K. H. Pun, Geneva G. Belford: Optimal Granularity and Degree of Multiprogramming in a Distributed Database System. ICDE 1986: 13-20
82. Alle IJbema, Henk M. Blanken: Estimating Bucket Accesses: A Practical Approach. ICDE 1986: 30-37
83. Ilsoo Ahn: Towards An Implementation of Database Management Systems with Temporal Support. ICDE 1986: 374-381
84. Clement T. Yu, Cheing-Mei Suen, K. Lam, M. K. Siu: Adaptive Record Clustering. ACM Trans. Database Syst. 10(2): 180-204(1985)
85. Y. C. Tay, Nathan Goodman, Rajan Suri: Locking Performance in Centralized Databases. ACM Trans. Database Syst. 10(4): 415-462(1985)
86. Mario Schkolnick, Paolo Tiberio: Estimating the Cost of Updates in a Relational Database. ACM Trans. Database Syst. 10(2): 163-179(1985)
87. Prashant Palvia: Expressions for Batched Searching of Sequential and Hierarchical Files. ACM Trans. Database Syst. 10(1): 97-106(1985)
88. Rakesh Agrawal, David J. DeWitt: Integrated Concurrency Control and Recovery Mechanisms: Design and Performance Evaluation. ACM Trans. Database Syst. 10(4): 529-564(1985)
89. Hong-Tai Chou, David J. DeWitt: An Evaluation of Buffer Management Strategies for Relational Database Systems. VLDB 1985: 127-141
90. Salvatore T. March, Gary D. Scudder: On the Selection of Efficient Record Segmentations and Backup Strategies for Large Shared Databases. ACM Trans. Database Syst. 9(3): 409-438(1984)
91. Toshihide Ibaraki, Tiko Kameda: On the Optimal Nesting Order for Computing N-Relational Joins. ACM Trans. Database Syst. 9(3): 482-502(1984)
92. Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984)
93. Clement T. Yu, C. C. Chang: Distributed Query Processing. ACM Comput. Surv. 16(4): 399-433(1984)
94. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
95. Y. C. Tay, Rajan Suri: Choice and Performance in Locking for Databases. VLDB 1984: 119-128
96. Gregory Piatetsky-Shapiro, Charles Connell: Accurate Estimation of the Number of Tuples Satisfying a Condition. SIGMOD Conference 1984: 256-276
97. Huei-Huang Chen, Sharon McCure Kuck: Combining Relational and Network Retrieval Methods. SIGMOD Conference 1984: 131-142
98. Giovanni Maria Sacco: Distributed Query Evaluation in Local Area Networks. ICDE 1984: 510-516
99. Salvatore T. March: Techniques for Structuring Database Records. ACM Comput. Surv. 15(1): 45-79(1983)
100. Clement T. Yu, C. C. Chang: On the Design of a Query Processing Strategy in a Distributed Database Environment. SIGMOD Conference 1983: 30-39
101. Stavros Christodoulakis: Estimating Block Transfers and Join Sizes. SIGMOD Conference 1983: 40-54
102. Larry Kerschberg, Peter D. Ting, S. Bing Yao: Query Optimization in Star Computer Networks. ACM Trans. Database Syst. 7(4): 678-711(1982)
103. Don S. Batory, C. C. Gotlieb: A Unifying Model of Physical Databases. ACM Trans. Database Syst. 7(4): 509-539(1982)
104. Jo-Mei Chang: A Heuristic Approach to Distributed Query Processing. VLDB 1982: 54-61
105. Arnon Rosenthal, David S. Reiner: An Architecture for Query Optimization. SIGMOD Conference 1982: 246-255
106. 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)
107. Kenneth C. Sevcik: Data Base System Performance Prediction Using an Analytical Model (Invited Paper). VLDB 1981: 182-198
108. Daniel R. Ries, Michael Stonebraker: Locking Granularity Revisited. ACM Trans. Database Syst. 4(2): 210-227(1979)
109. Don S. Batory: On Searching Transposed Files. ACM Trans. Database Syst. 4(4): 531-544(1979)
110. Clement T. Yu, K. Lam, M. K. Siu, Z. Meral Özsoyoglu: Performance Analysis of three Related Assignment Problems. SIGMOD Conference 1979: 82-92
111. Giuseppe Pelagatti, Fabio A. Schreiber: Evaluation of Transmission Requirements in Distributed Database Access. SIGMOD Conference 1979: 102-108
112. Michael Hammer, Bahram Niamir: A Heuristic Approach to Attribute Partitioning. SIGMOD Conference 1979: 93-101
113. S. Bing Yao, D. DeJong: Evaluation of Database Access Paths. SIGMOD Conference 1978: 66-77
114. S. Bing Yao: An Attribute Based Model for Database Access Cost Analysis. ACM Trans. Database Syst. 2(1): 45-67(1977)