Low level structures in the implementation of the relational algebra

We present storage organization schemes and a tuple density model of a relation, for the efficient processing of information in a relational database. The underlying concept used in the design of the storage schemes and the density model is that of a multidimensional array. These organizational schemes are: Multidimensional Paging, Dynamic Multipaging, and two dynamic multidimensional hashing schemes, DMHL and DMHE. The DMHL and DMHE schemes are the respective extensions of linear hashing and extendible hashing for multidimensional data organization. Storage mapping functions for extendible arrays are developed as the page addressing functions in the dynamic multidimensional structures. Performance of the multipaging schemes are examined through empirical studies.We show how relations are structured with these organizational methods to provide symmetric access to the data on any combination of attributes. Further we derive size estimation formulae for the result of the various relational operations using the density model