An analytic model of physical databases
Don S. Batory · 1981
Physical databases are decomposable into a collection of simple files and linksets. Simple files are structures that organize records of a file. Linksets are structures that link records of one file to those of another. Classical simple files include hash based, unordered, and indexed sequential files; classical linksets include inverted lists, ring lists, and parent pointers. Using classical structures as a basis, unifying models of simple files and linksets are developed. Together these models serve as powerful tools for describing a wide spectrum of physical databases. Primitive file and linkset operations are identified and cost equations for these operations are developed. These operations are then augmented with Pidgin ALGOL constructs so that database transactions can be modeled. By applying simple statement-expression translation rules to a transaction, an expression estimating the cost of processing the transaction can be derived. In this way, the task of analyzing transactions may be simplified. To supplement the above, a unifying model of file evolution is proposed. The model explains and predicts the evolution of certain file statistics, such as the average length of an overflow chain, as records are inserted and deleted from a file. Such statistics are indispensable when accurate estimates of a file's performance over extended periods of time are desired. Applications of the model to hash based, indexed sequential, and B+ tree files, among others, have been validated by simulation studies. The simple file, linkset, transaction, and file evolution models collectively define an analytic model of physical databases. This composite model is shown to unify and generalize many former works. Specifically, new results concerning the problems of structure selection and index selection are presented. Also, a new method is proposed for solving the combined problems of file design and file reorganization.