The hierarchical grid file(HGF) was proposed by Whang and Krishnamurthy as a multidimensional dynamic hashed file organization. In this thesis, we implement the HGF and prove its characteristics through experiments. They are linear growth of the directory proportional to the number of records and the number of disk accesses for a exact match query. The results show that the HGF is a practically usable multidimensional dynamic file structure and solves many problems associated with the directory of the grid file proposed by Nievergelt et al. Next, we propose a new scheme for estimating data distribution using the information contained in the directory of the HGF. This scheme gives a very accurate estimation of the selectivity for a given query. A good estimation of the selectivity is essential for a query optimization and a physical database design. Experimental results show that our scheme is indeed accurate. Finally, we propose a new join algorithm that uses the directory of the HGF as abstract databases. The notion of the abstract database has been formalized by Whang and Krishnamurthy. This algorithm adopts an incremental evaluation strategy for queries and has an advantage of reducing disk accesses.
