PERFORMANCE IMPLICATIONS OF USING HIGHER ORDER INVERSION STRUCTURES FOR REDUCTION OF NATURAL QUANTIFIER EXPRESSIONS
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.
Description
Keywords
Computer Science