Relational data management implementation techniques

ABSTRACT

The use of relations as a model of information stored in large data bases has several significant advantages over other methods of data description. It is often, however, criticized as difficult to implement efficiently. In this paper, some of the pros and cons of the relational model are discussed. The concepts of modeling information structures with data is illustrated with the CODASYL DBTG and the relational models. Then the main concepts of a relational data management system are presented based on current implementations. The advantages and disadvantages of the relational model is discussed in the light of these implementations. By presenting the theories of relational data management in a context of specific system implementations, the advantages and disadvantages of this data organization will be more clearly understood.

REFERENCES

• 1: Bjorner, D., Codd, E.F., Decker, K.L., Traiger, I.L., "The Gamma Zero n-ary Relational Data Base Interface: Specifications of Objects and Operations," IBM San Jose Research Report RJ1200, April 1973. (Detailed description of a low-level interface to a relational data base. Practical.)
• 2: R. F. Boyce , D. D. Chamberlin , M. M. Hammer , W. F. King, Specifying queries as relational expressions, Proceedings of the 1973 meeting on Programming languages and information retrieval, p.31-47, November 04-06, 1973, Gaithersburg, Maryland
• 3: Bracchi, G., "A Language for a Relational Data Base Management System," Proceedings of Sixth Annual Princeton Conference on Information Science and Systems, March 1972, pp. 84-92. (The COLARD language is based on the predicate calculus.)
• 4: Canning, R.G., "/Introduction to/ 1973 ACM Turing Award Lecture," Communications of the ACM, Vol. 16, No. 11, November 1973, p. 653.
• 5: Childs, D.L., "Feasibility of a Set Theoretic Data Structure," Proceedings of the IFIP Congress, 1968. (Theoretical development of a data structure model using a modification of set theory which incorporates sequencing. Mathematical.)
• 6: Childs, D.L., "Description of a Set Theoretic Data Structure," Proceedings of the Fall Joint Computer Conference, 1968.
• 7: Childs, D.L., "Extended Set Theory: A Formalism for the Design, Implementation, and Operation of Information Systems," submitted to IFIP-74. (Revised theoretical basis for a set-theoretical data structure. Good discussion of data structures as models for information structures. Mathematical.)
• 8: CODASYL, "Report of the DATA BASE TASK GROUP," April 1969 and October 1971, available from ACM. (Language specifications for a data description language and COBOL enhancements for data manipulation. Based on a network organization of information.)
• 9: CODASYL Development Committee, "An Information Algebra," Communications of the ACM, V, 4, April 1962, p. 190-204. (The information algebra, mainly the work of R. Bozak, is a calculus language for describing data manipulation. Abstract, concise. Mathematical.)
• 10: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 11: Codd, E.F., "Normalized Data Base Structure: A Brief Tutorial," Proceedings of the 1971 ACM SIGFIDET Workshop, p. 1-18, available from ACM, New York. (Examples showing the reduction of data base structures to the Third Normal Form by the removal of repeating groups, hierarchic and plex structures, and cross-referencing structures.)
• 12: Codd, E.F., "A Data Base Sublanguage founded on the Relational Calculus," Proceedings of the 1971 ACM SIGFIDET Workshop, available from ACM, New York. (A non-procedural calculus-oriented language is introduced with many clear examples.) It is contrasted with algebraic languages. Practical.)
• 13: Codd, E.F., "Further Normalization of the Data Base Relational Model," Courant Computer Science Symposia 6, "Data Base Systems," New York City, May 24-25, 1971, Prentice-Hall. (Theoretical development of Third-Normal Form. Mathematical.)
• 14: Codd, E.F., "Relational Completeness of Data Base Sublanguages," in Data Base Systems, R. Rustin, Ed., Prentice-Hall, 1972. ("This paper attempts to provide a theoretical basis which may be used to determine how complete a selection capability is provided in a proposed data sublanguage.....The selection is a basic non-statistical one." Mathematical.)
• 15: Codd, E.F., "Seven Steps to Rendezvous with the Casual User," to be presented at IFIP TC-2 Working Conference on Data Base Management Systems, Cargese, Corsica, 1-5 April 1974; also available as IBM San Jose Research Report RJ 1333. (Fascinating description of an already partially implemented system for a two-way dialog between a casual user and a relational data base query system. Practical.)
• 16: Date, C.J. & Hopewell, P., "File Definition and Logical Data Independence," Proceedings of the 1971 ACM SIGFIDET Workshop, available from ACM, New York. (Describes a data management system architecture similar to the DBTG approach and discusses how the relational model fits into the architecture. Discusses the minimal required features of a file definition language.)
• 17: Date, C.J. & Hopewell, P., "Storage Structure and Physical Data Independence," Proceedings of the 1971 ACM SIGFIDET Workshop, available from ACM, New York. (Discussion of the problems with efficiently accessing data stored as relations in Third Normal Form. Indexing, inverting, and other techniques for improving the access speed are discussed. Good examples. Describes many DBTG structures in their relational form.
• 18: Date, C.J., "Relational Database Systems: A Tutorial," Proceedings of the COINS-72 Symposium, December 1972. (Excellent tutorial on the relational model for information structure with special emphasis on the advantages of the relational model over the DBTG and the hierarchical models. Discussion of both calculus and algebraic languages.)
• 19: Earley, J., "On the Semantics of Data Structures," in Data Base Systems, R. Rustin, Ed., Prentice-Hall, 1972. (A clear argument for a three level data base description.)
• 20: Goldstein, R.C., & Strnad, A.J., "The MacAIMS Data Management System," Proceedings of the 1970 ACM SIGFIDET Workshop, available from ACM, New York. (A relational data base system implemented in PL/1 on the MULTICS computer. Relations are stored as chained tuples. Some implementation details. Practical.)
• 21: Heath, I.J., "Unacceptable File Operations in a Relational Data Base," Proceedings of the 1971 ACM SIGFIDET Workshop, available from ACM, New York. (When a data base is maintained in Third Normal Form, certain undesirable side-effects of data manipulation can automatically be avoided. Mathematical.)
• 22: IBM, "Information Management System IMS/360, Application Description Manual (Version 2)," Form GH20-0765-1. (Describes the IMS/2 hierarchical data base management system.)
• 23: Lorie, R.A., "XRM-An Extended (N-ary) Relational Memory," IBM Cambridge Scientific Center Technical Report 320-2096, January 1974. ("This paper presents a low level interface for handling n-ary relations....Operators are supplied to create and drop a relation, to add or delete tuples in a relation, to scan a relation..." Practical.)
• 24: McIntosh, S. & Griffel, D., "Data Management for a Penny A Byte," Computer Decisions, May 1973. (ADMINS, a relational data manager, is implemented on a mini-computer. It may be used as a flexible inquiry processor or a collection of routines callable from a COBOL program. Advocates use of data compression to reduce data storage requirements. Practical.)
• 25: Nijssen, G.M., "Present and Future Possibilities of Database Technology," Proceedings of the IFIP Congress, Stockholm, 1974. (Quite general, stresses the need for user education.)
• 26: Notley, M.G., "The Peterlee IS/1 System," IBM UK Scientific Centre report UKSC-0018, March 1972. (The IS/1 system is a prototype general purpose information system based on a relational model of data. It is a query system with a high degree of generality, efficiency, estensibility, and consistency. An application of this system is the subject of item 28 in this reference list. Practical.)
• 27: Palermo, F.P., "A Data Base Search Problem," Proceedings of the (COINS-72) Symposium, December 1972; also IBM San Jose Research Report RJ 1072. (A method for translating a propositional calculus expression into a sequence of algebraic operations of a relational data manager. Mathematical.)
• 28: Soop, K., Svensson, P., & Wiktorin, L., "An Experiment with a Relational Data Base System in Environmental Research," Proceedings of the COINS-72 Symposium, December 1972. ("This paper lists certain characteristics of environmental data and their uses, maps those characteristics onto requirements on the software tools, and describes how the final system attempts to meet these requirements." Uses the Peterlee IS/I system described in item 26 above. Practical.)
• 29: T. B. Steel, Jr., Beginnings of a theory of information handling, Communications of the ACM, v.7 n.2, p.97-103, Feb. 1964 [doi>10.1145/363921.363937]
• 30: Strnad, A.L., "The Relational Approach to the Management of Data Bases," Proceedings of the IFIP Congress, 1971. (Descriptions of an implementation of a relational system, MacAIMS, with an emphasis on the operations available to the user of the system. Practical.)
• 31: Whitney, V.K.M., "A Relational Data Management System (RDMS)," Proceedings of the COINS-72, December, 1972. (Describes some experiences with an algebraic relational data management system used for interactive data analysis. Some implementation details for a large, virtual memory computer provided. Practical.)
• 32: Whitney, V.K.M., "Fourth Generation Data Management Systems," Proceedings of the National Computer Conference, 1973. (Trends in the architecture of data management systems include a three level descriptive structure, increased modularity, a relational information structure, and better theoretical foundations.)
• 33: Wilkes, M.V., "Associative Tabular Data Structures," Proceedings of a Symposium on Data Structures in Programming Languages, February 1971, pp. 337-345. (Wilkes's tables are relations. A macro implementation of the basic data manipulations was used to illustrate formal differentiation of expressions. Practical.)

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

General Terms:
Design, Management