Near-optimum storage models for nested relations based on workload information

We consider the problem of choosing a storage model for a nested relation (i.e., a relation containing relations). We introduce a technique that uses the workload information of the database system under consideration to obtain a 'better' storage model (i.e., one with a lower query cost) for a given nested relation. The nested relation scheme is first represented as a tree called the scheme tree. By using the workload information and by performing a series of merges in the nodes of the scheme tree, a near-optimum scheme tree is produced, and file organization types are assigned to each node (file) in the scheme tree. We apply our methodology by using a specific nested relational algebra and three file organization types, namely, sequential, heap, and dense index files. However, the methodology can be used with other nested relational algebra languages and other file organization types. In all of our experiments, the proposed methodology has located the optimum storage model and the optimum file organization techniques for the external and internal relations of the tested nested relations.