On the interdependencies between record structure and access path design

The physical organization of data within a database has two major components: record structures and access paths. Record structures specify the grouping of data items into data records that are physically stored and accessed together. Access paths specify the algorithms and system data used to determine the physical location of data records and to efficiently support content-dependent searching. Choosing efficient record structures and access paths is complicated by the fact that they are interdependent. This paper formalizes these interdependencies and proposes an approach to solving the combined record structure-access path design problem. This work extends an existing database design system in four ways: (1) record segmentation is extended to include redundantly stored data in any number of independently processed segments; (2) dependent access paths are added allowing us to design multiple, interrelated file organizations at the same time; (3) new methods are proposed to assist in the generation of potentially useful record structures; and (4) inter-file organization performance constraints can be specified.