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