The Evaluation of Abstract Data Types as an Implementation Tool for Database Management Systems

Abstract

This dissertation examines the application of current research on abstract data types and on generic procedures to the implementation of a network model database management system. The data manipulation routines are examples of generic procedures. The data manipulation routines utilize the descriptors of the record and set types in the schema and subschema to determine the functions which are to be performed for a given actual parameter. A generic procedure model of a database management system is presented and used to describe the techniques used in current systems to provide these descriptors to the data manipulation routines. To preserve data independence, an approach employing run-time interpretation is commonly used. The generic procedure model is extended to represent the schema and subschema as a shared collection of abstract data types. The data manipulation routines are implemented in terms of the data attributes and procedures associated with the abstract data types. When coupled with environment control mechanisms based on SIMULA 67, the abstract data type model is shown to support data independence, sharing of the schema and subschema, and access control to the schema through the subschema, while eliminating run-time interpretation. The abstract data types representing the schema and subschema are generated by extending the concept of generalization developed by Smith and Smith. Generalization is used to define generic objects which represent the network data model. These objects are used as tenmplates to translate the schema and subschema into the equivalent declarations of abstract data types which implement the generic ogbjects. A simulation model is developed to compare the abstract data type model with the interpretive approach. The simulation model is used in combination with analytic modeling to study the locality of references to schema descriptors, the effect of multiprogramming on system overhead, and the effect of mass storage I/O time on system performance.