Optimal file designs and reorganization points
ACM Transactions on Database SystemsPublished 1 March 1982Open access
Don Batory
Citations44
SJR quartileQ1
SJR score0.91
SNIP1.85
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A model for studying the combined problems of file design and file reorganization and applications to hash-based and indexed-sequential files reveal important relationships between initial loading factors and reorganization frequency.
Abstract
A model for studying the combined problems of file design and file reorganization is presented. New modeling techniques for predicting the performance evolution of files and for finding optimal reorganization points for files are introduced. Applications of the model to hash-based and indexed-sequential files reveal important relationships between initial loading factors and reorganization frequency. A practical file design strategy, based on these relationships, is proposed.
Keywords
Computer Science
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
ACM Transactions on Database SystemsAn attribute based model for database access cost analysis
104 Citations1977S. Bing Yao
The model provides a general design framework in which the distinguishing properties of database organizations are made explicit and their performances can be compared.
ACM Computing SurveysDatabase Reorganization—Principles and Practice
76 Citations1979Gary H. Sockut, Robert P. Goldberg
Communications of the ACMOptimum data base reorganization points
65 Citations1973Ben Shneiderman
This paper examines strategies for selecting the optimum reorganization points in data base organization schemes and concludes that the high cost of a reorganization prohibits frequent reorganizations.
ACM Transactions on Database SystemsA dynamic database reorganization algorithm
51 Citations1976S. Bing Yao, Kapotaksha Das +1 more
A dynamic reorganization algorithm which makes the reorganization decision by measuring the database search costs is presented, which is shown to be near optimum for constant reorganization cost and is superior for increasing reorganizationcost.
Communications of the ACMA practitioner's guide to addressing algorithms
48 Citations1976Dennis G. Severance, Ricardo Duhne
This paper consolidates a number of popular rules of thumb which have been suggested for the design of record addressing algorithms, and discusses the applicability of these rules to large commercial databases.
ACM Transactions on Database SystemsOptimal policy for batch operations
46 Citations1977Guy M. Lohman, John A. Muckstadt
A general model for determining the optimal frequency of database maintenance operations in batches is presented and optimal backup, checkpointing, batch updating, and reorganization policies are derived.
ACM Transactions on Database SystemsOptimum reorganization points for linearly growing files
34 Citations1978William G. Tuel
The problem of finding optimal reorganization intervals for linearly growing files is solved and an approximate reorganization policy, independent of file lifetime, is obtained.
Very Large Data BasesAn analysis of storage utilization factor in block split data structuring scheme
33 Citations1978Toshiyuki Nakamura, Tetsuo Mizoguchi
The Storage Utilization Factor (SUF) of Block Split Data Structuring (BSDS) scheme (e.g. IBM's VSAM) is analyzed and some experimental results indicate that the analysis of expected SUF is sufficiently adequate.
B+ trees and indexed sequential files
23 Citations1981Don Batory
An analytic method for comparing the performance of B+ trees and indexed sequential files is proposed and preliminary results indicate that indexed Sequential files may be more efficient than B- trees in certain applications.
IBM Journal of Research and DevelopmentOptimum Storage Allocation for a File in Steady State
18 Citations1973John-Rob Pool
A file of fixed-length records in auxiliary storage using a key-to-address transformation to assign records to addresses is considered and the loading factors that minimize file maintenance costs in terms of storage space and additional accesses are computed.
An analytic model of physical databases
4 Citations1981Don Batory
The simple file, linkset, transaction, and file evolution models collectively define an analytic model of physical databases and this composite model is shown to unify and generalize many former works.
Efficient algorithms for selecting efficient data storage structures
4 Citations1980Raul Javier Ramirez Inurrigarro
Algorithms based on dynamic programming for selecting efficient composite storage structures are presented, and pseudo-polynomial algorithms that select the most efficient implementations for each data type occurrence are presented and discussed.