Report Number: CS-TR-81-898
Institution: Stanford University, Department of Computer Science
Title: Separability as a physical database design methodology
Author: Whang, Kyu-Young
Author: Wiederhold, Gio
Author: Sagalowicz, Daniel
Date: October 1981
Abstract: A theoretical approach to the optimal design of large multifile physical databases is presented. The design algorithm is based on the theory that, given a set of join methods that satisfy a certain property called "separability," the problem of optimal assignment of access structures to the whole database can be reduced to the subproblem of optimizing individual relations independently of one another. Coupling factors are defined to represent all the interactions among the relations. This approach not only reduces the complexity of the problem significantly, but also provides a better understanding of underlying mechanisms. A closed noniterative formula is introduced for estimating the number of block accesses in a database organization, and the error analyzed. This formula, an approximation of Yao's exact formula, has a maximum error of 3.7%, and significantly reduces the computation time by eliminating the iterative loop. It also achieves a much higher accuracy than an approximation proposed by Cardenas.
http://i.stanford.edu/pub/cstr/reports/cs/tr/81/898/CS-TR-81-898.pdf