NEAR-OPTIMUM STORAGE MODELS FOR NESTED RELATIONS BASED ON WORKLOAD INFORMATION

We consider the problem of choosing a storage model for a nested relat ion (i.e., a relation containing relations). We introduce a technique that uses the workload information of the database system under consid eration to obtain a ''better'' storage model (i.e., one with a lower q uery cost) for a given nested relation. The nested relation scheme is first represented as a tree called the scheme tree. By using the workl oad information and by performing a series of merges in the nodes of t he scheme tree, a near-optimum scheme tree is produced, and file organ ization types are assigned to each node (file) in the scheme tree. We apply our methodology by using a specific nested relational algebra an d three file organization types, namely, sequential, heap, and dense i ndex files. However, the methodology can be used with other nested rel ational algebra languages and other file organization types. In all of our experiments, the proposed methodology has located the optimum sto rage model and the optimum file organization techniques for the extern al and internal relations of the tested nested relations.