Using grid files for a relational database management system

In the grid file storage organization a relation with k attributes is represented as an m-dlmensional grid file, where m is the length of a grid file and k the number of attributes.

Abstract

In the grid file storage organization a relation with k attributes is represented as an m-dlmensional grid file, where m<=k. During the query evaluation the extent of each relation scan can be defined very precisely by considering the constraints on all attributes simultaneously. We describe some implementations of the grid directory and of query evaluation algorithms. We first introduce the concepts of useful boundaries and manually inserted boundaries to reduce the size of the grid directory and to adapt the grid partition to the actual data distribution. Next we describe the process of restricting the search region of individual relations and three different two-variable join algorithms. Finally, we introduce appropriate cost formulae to find the optimal join order of n relations.