Dynamic and Order Preserving Data Partitioning for Database Machines.

Esen A. Ozkarahan, Aris M. Ouksel: Dynamic and Order Preserving Data Partitioning for Database Machines. VLDB 1985: 358-368
  author    = {Esen A. Ozkarahan and
               Aris M. Ouksel},
  editor    = {Alain Pirotte and
               Yannis Vassiliou},
  title     = {Dynamic and Order Preserving Data Partitioning for Database Machines},
  booktitle = {VLDB'85, Proceedings of 11th International Conference on Very
               Large Data Bases, August 21-23, 1985, Stockholm, Sweden},
  publisher = {Morgan Kaufmann},
  year      = {1985},
  pages     = {358-368},
  ee        = {db/conf/vldb/OzkarahanO85.html},
  crossref  = {DBLP:conf/vldb/85},
  bibsource = {DBLP,}


The I/O bottleneck represents a major problem in architectures hat have been pro- posed to implement hard database operations such as join and projection. It is recognized that solutions to this problem cannot be based on new database machine architectures alone if satisfactory performance goals are to be atteined. A case in point is illustrated by the comparison of cellular/associative and in- stream pipeline based architectures.A metho- dology based on a global order preserving and dynamic partitioning is presented. The relevance of this approach to the solution of the I/O bottleneck problem is demonstrated through the efficient parallel processing of the join and projection operations. Finaly, this methodology is incorporatated into a specific database machine architecture; namely, the RAP.3 database machine. The partitioning strategy has been previously proven to be supe- rior to he other known methods.

Copyright © 1985 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Alain Pirotte, Yannis Vassiliou (Eds.): VLDB'85, Proceedings of 11th International Conference on Very Large Data Bases, August 21-23, 1985, Stockholm, Sweden. Morgan Kaufmann 1985
Contents BibTeX


[Banerjee, Hsiao, and Kannan, 1979]
[Burkhard, 1983]
Walter A. Burkhard: Interpolation-Based Index Maintenance. PODS 1983: 76-89 BibTeX
[DeWitt, 1979]
[Kitsuregewa, Tanaka, and Mot-Oka, 1983]
Masaru Kitsuregawa, Hidehiko Tanaka, Tohru Moto-Oka: Application of Hash to Data Base Machine and Its Architecture. New Generation Comput. 1(1): 63-74(1983) BibTeX
[Kung and Lehman, 1980]
H. T. Kung, Philip L. Lehman: Systolic (VLSI) Arrays for Relational Database Operations. SIGMOD Conference 1980: 105-116 BibTeX
[Nievergelt, Hinterberger, and Sevcik, 1984]
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX
[Ouksel, 1983a]
[Ouksel, and Scheuermann, 1983b]
Aris M. Ouksel, Peter Scheuermann: Storage Mappings for Multidimensional Linear Dynamic Hashing. PODS 1983: 90-105 BibTeX
[Ouksel, 1985a]
Aris M. Ouksel: The Interpolation-Based Grid File. PODS 1985: 20-27 BibTeX
[Ouksel, 1985b]
[Ozkarahan, 1982]
[Ozkarahan, 1983]
[Ozkarahan, 1985]
[Tanaka, 1984]

Referenced by

  1. Thomas A. Mück, Manfred J. Schauer: Optimizing Sort Order Query Execution in Balanced and Nested Grid Files. IEEE Trans. Knowl. Data Eng. 7(2): 246-260(1995)
  2. Manuel A. Penaloza, Esen A. Ozkarahan: Parallel Algorithms for Executing Joins on Cube-Conneced Multicomputers. ICDE 1992: 20-27
  3. Aris M. Ouksel, Otto Mayer: The Nested Interpolation Based Grid File. MFDBS 1991: 173-187
  4. Lilian Harada, Miyuki Nakano, Masaru Kitsuregawa, Mikio Takagi: Query Processing for Multi-Attribute Clustered Records. VLDB 1990: 59-70
  5. Masaru Kitsuregawa, Lilian Harada, Mikio Takagi: Join Strategies on KB-Tree Indexed Relations. ICDE 1989: 85-93
  6. Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269
  7. Doron Rotem, Arie Segev: Physical Organization of Temporal Data. ICDE 1987: 547-553
  8. Jean-Pierre Cheiney, Pascal Faudemay, Rodolphe Michel, Jean-Marc Thévenin: A Reliable Backend Using Multiattribute Clustering and Select-Join Operator. VLDB 1986: 220-227
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:25 2009