A file definition facility for file structures

ABSTRACT

This paper describes a file definition facility (FDF) for defining files as graph structures. The structure of the file is explicitly declared in the file definition. Primitive functions (from graph theory), operators, and the format of the definition statements are given. The combination of functions and operators appear as directives to the programming system for structuring files. Several simple examples are given to illustrate the use of the FDF. The data organization for the implementation of this facility is described in detail. Problems of considerable importance that are treated are: (1) garbage collection, (2) template construction, and (3) runtime address calculation. The external definitions are represented internally by descriptors. The format of the descriptors is given and a discussion of the items in the descriptors is presented.

REFERENCES

• 1: Bachman, C.W. and Williams, S.B. "The Integrated Data Store—A General Purpose Programming System for Random Access Memories", AFIPS 1964 FJCC, Vol. 26, Spartan Books, N.Y., pp. 411-422.
• 2: Billy G. Claybrook, FOL: a language for implementing file organizations for information storage and retrieval systems, Proceedings of the 1973 meeting on Programming languages and information retrieval, p.101-112, November 04-06, 1973, Gaithersburg, Maryland
• 3: Claybrook, Billy G. "LPL: A Generalized List Processing Language", To appear in the 1974 Proceedings of the NCC&E.
• 4: 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]
• 5: Dodd, George D. "APL—A Language for Associative Data Handling in PL/1", AFIPS 1966 FJCC, Vol. 29, Spartan Books, N.Y., pp. 677-684.
• 6: Robert R. Fenichel, List tracing in systems allowing multiple cell-types, Communications of the ACM, v.14 n.8, p.522-526, Aug. 1971 [doi>10.1145/362637.362646]
• 7: Lefkovitz, David. File Structures for On-Line Systems, Spartan Books, New York, 1969.
• 8: McGee, William C. "File Structures for Generalized Data Management", Information Processing 68, North-Holland Publishing Company, Amsterdam, 1968, pp. 1233-1239.
• 9: J. E. L. Peck, ALGOL Sixty-Eight Implementation, Elsevier Science Inc., New York, NY, 1971
• 10: Standish, T. A. "A Data Definition Facility for Programming Languages", Dissertation, Department of Computer Science, Carnegie Institute of Technology, May 1967.
• 11: J. Weizenbaum, Symmetric list processor, Communications of the ACM, v.6 n.9, p.524-536, Sept. 1963 [doi>10.1145/367593.367617]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

General Terms:
Languages, Management

Keywords:
File structures, List structures, Programming languages