|
|||||
|
|
Some properties of optimal cartesian product files for orthogonal range queries |
|
| Authors: | Annie Y H Chou Wei-Pang YangChin-Chen Chang |
| Affiliation: | Department of Computer and Information Science, National Chiao Tung University, Hsinchu, Taiwan 300, Republic of China Department of Computer Science and Information Engineering, National Chung Cheng University, Hsinchu, Taiwan 621, Republic of China |
| Abstract: | Cartesian product file (CPF) has been proposed as a good multi-attribute file structure. Although designing an optimal CPF for partial match queries (PMQs) has been proven to be NP-hard, some useful properties have been studied for PMQs to help the work. However, a good CPF for PMQs may not be beneficial for orthogonal range queries (ORQs). Therefore, in this paper, we intend to study properties that help the design of a good CPF for ORQs. We found that the problem of designing the optimal CPF for ORQs is related to the problem of finding a minimal-f N-tuple. We will also show some theories of minimal-f N-tuples and develop a method for generating a minimal-f N-tuple. Finally, we will present some properties of the optimal CPF for ORQs from the theories of minimal-f N-tuples. |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ | |