BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-81-898
       ENTRY:: June 05, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Separability as a physical database design methodology
        TYPE:: Technical Report
      AUTHOR:: Whang, Kyu-Young
      AUTHOR:: Wiederhold, Gio
      AUTHOR:: Sagalowicz, Daniel
        DATE:: October 1981
       PAGES:: 64
    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.
       NOTES:: [Adminitrivia V1/Prg/19950605]
         END:: STAN//CS-TR-81-898