Implementing a generalized access path structure for a relational database system

ABSTRACT

A new kind of implementation technique for access paths connecting sets of tuples qualified by attribute values is described. It combines the advantages of pointer chain and multilevel index implementation techniques. Compared to these structures the generalized access path structure is at least competitive in performing retrieval and update operations, while a considerable storage space saving is gained. Some additional features of this structure support m-way joins and the evaluation of multirelation queries, and allow efficient checks of integrity assertions and simple reorganization schemes.

REFERENCES

• 1: M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
• 2: BACHMAN, C.W. Implementation techniques for data structure sets. In Data Base Management Systems, D.A. Jardine, Ed., North-Holland Pub. Co., Amsterdam, 1974, pp. 147-157.
• 3: BAYER, R., AND MCCREIGHT, E. Organization and maintenance of large ordered indexes. Acta
• 4: BAYER, R., AND SCHKOLNICK, M. Concurrency of operations on B-Trees. IBM Res. Rep. RJ 1791, IBM Res. Lab., San Jose, Calif., May 1976. To appear in Acta Informatica.
• 5: BLASGEN, M.W., CASEY, R.G., AND ESWARAN, K.P. An encoding method for multi-field sorting and indexing. IBM Res. Rep., RJ 1753, IBM Res. Lab., San Jose, Calif., March 1976.
• 6: BLASGEN, M.W., AND ESWARAN, K.P. On the evaluation of queries in a relational database system. IBM Res. Rep. RJ 1745, IBM Res. Lab., San Jose, Calif., 1976.
• 7: CADIOU, J.M. On semantic issues in the relational model of data. Proc. 5th Symp. on Math. Foundations of Compt. Sci. 1976, Gdansk, Poland, Lecture Notes in Computer Science 45, Springer-Verlag, pp. 23-38.
• 8: CODASYL DATA BASE TASK GROUP (DBTG) Report, April 1971 (available from ACM, New York).
• 9: 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]
• 10: CODD, E.F., AND DATE, C.J. Interactive support for nonprogrammers: The relational and network approaches. IBM Res. Rep. RJ 1400, IBM Res. Lab., San Jose, Calif., June 1974.
• 11: ESWARAN, K.P., AND CHAMBERLIN, D.D. Functional specifications of a subsystem for data base integrity. Proc. Int. Conf. on Very Large Data Bases, Framingham, Mass., Sept. 1975, pp. 48-68 (available from ACM, New York).
• 12: HAERDER, T. An implementation technique for a generalized access path structure. IBM Res. Rep. RJ 1837, IBM Res. Lab., San Jose, Calif., Oct. 1976.
• 13: WEDEKIND, H. On the selection of access paths in a data base system. In Data Base Management, J.W. Klimbie and K.L. Koffeman, Eds., North-Holland Pub. Co., Amsterdam, 1974, pp. 385-397.

INDEX TERMS

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

General Terms:
Design

Keywords:
B-trees, access path structures, database, index structures, relational model