Implementing a generalized access path structure for a relational database system

Abstract

A new kind of implementation technique for access paths connecting sets of tuples qualified by attribute values is described. It combines the advantages of pointer chain and multilevel index implementation techniques. Compared to these structures the generalized access path structure is at least competitive in performing retrieval and update operations, while a considerable storage space saving is gained. Some additional features of this structure support m -way joins and the evaluation of multirelation queries, and allow efficient checks of integrity assertions and simple reorganization schemes.