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.