Expressions for Batched Searching of Sequential and Hierarchical Files.

Prashant Palvia: Expressions for Batched Searching of Sequential and Hierarchical Files. ACM Trans. Database Syst. 10(1): 97-106(1985)

@article{DBLP:journals/tods/Palvia85,
  author    = {Prashant Palvia},
  title     = {Expressions for Batched Searching of Sequential and Hierarchical
               Files},
  journal   = {ACM Trans. Database Syst.},
  volume    = {10},
  number    = {1},
  year      = {1985},
  pages     = {97-106},
  ee        = {http://doi.acm.org/10.1145/3148.3326, db/journals/tods/Palvia85.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

Batching yields significant savings in access costs in sequential, tree-structured, and random files. A direct and simple expression is developed for computing the average number of records/pages accessed to satisfy a batched query of a sequential file. The advantages of batching for sequential and random files are discussed. A direct equation is provided for the number of nodes accessed in unbatched queries of hierarchical files. An exact recursive expression is developed for node accesses in batched queries of hierarchical files. In addition to the recursive relationship, good, closed-form upper- and lower-bound approximations are provided for the case of batched queries of hierarchical files.

Copyright © 1985 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" 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/An3-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" 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/aDVD2 or /dvd

BibTeX

References

[1]: Don S. Batory, C. C. Gotlieb: A Unifying Model of Physical Databases. ACM Trans. Database Syst. 7(4): 509-539(1982) BibTeX
[2]: Alfonso F. Cardenas: Analysis and Performance of Inverted Data Base Structures. Commun. ACM 18(5): 253-263(1975) BibTeX
[3]: To-Yat Cheung: Estimating Block Accesses and Number of Recorde in File Management. Commun. ACM 25(7): 484-487(1982) BibTeX
[4]: ...
[5]: ...
[6]: Prashant Palvia, Salvatore T. March: Approximating Block Accesses in Database Organizations. Inf. Process. Lett. 19(2): 75-79(1984) BibTeX
[7]: ...
[8]: Dennis G. Severance, John V. Carlis: A Practical Approach to Selecting Record Access Paths. ACM Comput. Surv. 9(4): 259-272(1977) BibTeX
[9]: Ben Shneiderman, Victor Goodman: Batched Searching of Sequential and Tree Structured Files. ACM Trans. Database Syst. 1(3): 268-275(1976) BibTeX
[10]: S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) BibTeX
[11]: S. Bing Yao: An Attribute Based Model for Database Access Cost Analysis. ACM Trans. Database Syst. 2(1): 45-67(1977) BibTeX

Referenced by

Bernhard Seeger, Per-Åke Larson, Ron McFadyen: Reading a Set of Disk Pages. VLDB 1993: 592-603
Frank Olken, Doron Rotem: Random Sampling from Database Files: A Survey. SSDBM 1990: 92-111
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)
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)
Frank Olken, Doron Rotem: Random Sampling from B+ Trees. VLDB 1989: 269-277
Jaideep Srivastava, Doron Rotem: Analytical Modeling of Materialized View Maintenance. PODS 1988: 126-134
Jaideep Srivastava, C. V. Ramamoorthy: Efficient Algorithms for Maintenance of Large Database. ICDE 1988: 402-408
Jane Fedorowicz: Database Performance Evaluation in an Indexed File Environment. ACM Trans. Database Syst. 12(1): 85-110(1987)
Jianzhong Li, Harry K. T. Wong: Batched Interpolation Searching on Databases. ICDE 1987: 18-24

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]