A Scan-Driven Sort Facility for a Relational Database System.

Theo Härder: A Scan-Driven Sort Facility for a Relational Database System. VLDB 1977: 236-244

@inproceedings{DBLP:conf/vldb/Harder77,
  author    = {Theo H{\"a}rder},
  title     = {A Scan-Driven Sort Facility for a Relational Database System},
  booktitle = {Proceedings of the Third International Conference on Very Large
               Data Bases, October 6-8, 1977, Tokyo, Japan},
  publisher = {IEEE Computer Society},
  year      = {1977},
  pages     = {236-244},
  ee        = {db/conf/vldb/Harder77.html},
  crossref  = {DBLP:conf/vldb/77},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper the design and implementation aspects of an integrated sort package are described which was implemented by the author as a part of an experimental relational database system called System R. The sort facility developed for variable length sort keys and tuples is discussed with regard to its anticipated use in relational database systems. It is considered to be a powerful tool to implement complex relational operations like join and projection and to support the dynamic creation of access paths and the loading and reorganizing of data clustered by field values. The input loop of the sort can be driven by various scans which allow the filtering of qualified tuples according to disjunctive normal forms of simple search arguments. Various aspects of the integration with storage and transaction management, locking and logging components are described. A number of design decisions for the sort facility concerning sorting, peerage, and merging techniques are discussed. Finally, some implementation aspects for sorting variable length keys consisting of a number of distributed fields are pointed out.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb7588 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Proceedings of the Third International Conference on Very Large Data Bases, October 6-8, 1977, Tokyo, Japan. IEEE Computer Society 1977
Contents

References

[1]: Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976)
[2]: Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972)
[3]: Mike W. Blasgen, Richard G. Casey, Kapali P. Eswaran: An Encoding Method for Multifield Sorting and Indexing. Commun. ACM 20(11): 874-878(1977)
[4]: ...
[5]: ...
[6]: Laurent Hyafil, F. Prusker, Jean Vuillemin: Design of Optimal Merge on Direct Access Devices. IFIP Congress 1974: 979-982
[7]: ...
[8]: Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley 1973
[9]: ...
[10]: John Miles Smith, Philip Yen-Tang Chang: Optimizing the Performance of a Relational Algebra Database Interface. Commun. ACM 18(10): 568-579(1975)
[11]: ...
[12]: ...