Document Type

Dissertation

Publication Date

1975

Abstract

This thesis claims that contemporary data structures can be understood and studied with an intelligible model which captures their essential differences and similarities and, further, that such a model is an appropriate basis for a top-down description method for data structures. To define the scope of the model, the data structures included in 21 programming languages and data base management systems have been tabulated. Each individual data structure is illustrated with an example drawn from a published paper or a working computer program. This mélange of data structures is divided into three classes (aggregates, associations , and files) and each class is modeled with a set of questions . Each question delineates one significant characteristic of the data structure and can be viewed as one axis of a n-dimensional universe of data structures. To demonstrate the clarity and generality of the model numerous existing examples, including several CODASYL Data Base Task Group and Feature Analysis data organizations, are described with the model. Additionally, a “completeness” exercise demonstrates that the model can represent all of the data structures identified in the survey of 21 programming languages and data base management systems.

The top-down data structure design method is based upon the model and is particularly suited to both the design and documentation of large data bases. Two special features, restatement and redefinition, allow the designs to remain intellectually manageable throughout a large number of conceptual levels. To show the utility of these methods a practical data base design for a software development system is presented. The requirements for this data base are drawn from the typical situation in which a number of individual programmers cooperate to create a software system which is used and modified over a long time period. This design proffers a general solution to a common programming problem and is thus a “software engineering" approach to data base design.

In order to compare and contrast the model of this thesis with existing work, 11 other data structure models are surveyed and divided into four groups: semantic, prototype, analysis, and information models. The data structure model of this thesis is an analysis model; such models provide a compilation of all possible variations among a collection of data structures. To aid the comparison, a common example is expressed in terms of each data structure model.

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.

Download

Share

COinS