SOME PROPERTIES OF OPTIMAL CARTESIAN PRODUCT FILES FOR ORTHOGONAL RANGE QUERIES

Cartesian product file (CPF) has bren proposed as a good multi-attribu te 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 P MQs may not be beneficial for orthogonal range queries (ORQs). Therefo re, 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 opt imal CPF for ORQs is related to the problem of finding a minimal-f N-t uple. We will also show some theories of minimal-f N-tuples and develo p a method for generating a minimal-f N-tuple. Finally, we will presen t some properties of the optimal CPF for ORQs from the theories of min imal-f N-tuples.