Abstract
A series of storage-level inversions is presented. A record of a first
order inversion contains what has been termed a one-level dendrite,
a record of a second order inversion contains two-level dendrites, and so on.
A dendrite is a special hierarchy type employing record keys. The
well-known file inversion turns out to be the first order inversion in
the series, and a second order inversion becomes an inversion of an
owner-coupled set. A third order inversion becomes the inversion of
a pair of owner-coupled sets, and a fourth order inversion the inversion of
an owner-coupled set triplet, and so on. A first order inversion on a
given field is contained by the second order inversion on that field, and
this second order inversion is in turn contained by the third order
inversion on that field, and so on. Extensive tests of the performance
implications of particularly owner-coupled set inversions are described.
It is demonstrated that in most cases, algorithms using higher order
inversions at the storage level can perform complex retrievals with only
a few disk accesses. It is suggested that the updating and storage costs
associated with higher order inversions will in many cases be acceptable.
All the owner-coupled sets dealt with are implicit owner-coupled
sets, which are applicable to relational data bases.
Notes
We are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at digitize@ucalgary.ca