Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.11 No.4, pp.625-647 (December 1995)
Optimal Two-Attribute Cartesian Product Files for
Orthogonal Range Queries

Annie Y. H. Chou, Wei-Pang Yang and Chin-Chen Chang*
Department of Computer and Information Science
National Chiao Tung University
Hsinchu, Taiwan 300, R.O.C. *Department of Computer Science and Information Engineering
National Chung Cheng University
Hsinchu, Taiwan 621, R.O.C.

In the past, much research work has focused on designing optimal multi-attribute file systems for partial match queries (PMQs). However, prior works on designing a multi-attribute file system for orthogonal range queries (ORQs) were usually based on heuristic methods. In this paper, we particularly concentrate on designing the optimal two-attribute Cartesian product file (CPF) for ORQs. We present two important properties of the two-attribute CPF partition form for ORQs. The first property is that the closer the number of partitions of each domain is to the other, the better the performance the CPF will achieve. By this property, we can adjust the number of partitions of each domain of a partition from to obtain a better partition form. The second property is that the partition form with the larger number of partitions being assigned to the smaller domain will perform better than will the other partition form. By this property, we can change the order of numbers in a partition form to obtain better performance. Furthermore, we also show that the problem of designing the optimal two-attribute CPF for ORQs is partially related to the problem of finding a minimal 2-tuple with positive order. Based on these properties, an algorithm to find the optimal two-attribute CPF for ORQs is presented.

Keywords: multi-attribute file, Cartesian product file, partial match query, orthogonal range query

Received December 19, 1994; revised July 125, 1995.
Communicated by Shing-Tsaan Huang.