One of the problems which confront designers, implementers, and users of database management systems is the very large amounts of space often required to store a database in a computer system. In general, that space is used for two purposes: to represent certain atomio units of data and to represent certain relationships among those atomic units. This paper investigates the second aspect of the problem, the storage requirements of relationship representations. The class of navigational representations is defined, and several relationship representation techniques commonly used in database management systems are shown to be navigational. Two additional techniques for constructing relationship representations are presented. The first produces more compact representations than the standard techniques by taking advantage of a property of relationships called companionship. The second technique, called the powerset representation, always achieves a worst-case lower bound on the size of navigational relationship representations.

Supporting multiple user views of databases is currently an important problem area in database management system development. An interesting facet of this problem arises whenever a user needs an integrated view of several distinct databases. Using traditional database concepts, an aggregate schema facility has been developed to address this problem. The basic functions of an aggregate schema facility are discussed, as well as their implementation in a CODASYL/DBTG-like environment. Interest in an aggregate schema facility grew out of a problem in restructuring large databases. The application of this facility to restructuring is discussed, as well as potential applications to dynamic translation and distributed databases.

The Access Path Specification Language (APSL) is a high-level essentially nonprocedural language for specifying restructuring transformations of network databases. It does so in terms of application-oriented concepts such as access strategies and selection criteria. APSL's approach to restructuring emphasizes description of the source structures from which target data is to be retrieved, rather than the operations needed to convert source constructs to target constructs. The latter approach is used by most current systems to restructure hierarchical data.APSL is based on the Relational Interface Model (RIM) of data, which permits a suitably restricted network database to be viewed simultaneously as a relational database in first normal form. Any restructuring of a RIM database which can be performed by the relational algebra operations Join, Select, Project, and Union can be described in APSL.APSL has been implemented as the restructuring specifications language in the Michigan Data Translator.