Some properties of optimal cartesian product files for orthogonal range queries
| Autor: | Wei-Pang Yang, Chin-Chen Chang, Annie Y. H. Chou |
|---|---|
| Rok vydání: | 1996 |
| Předmět: |
Information Systems and Management
Theoretical computer science Range query (data structures) Computer science Cartesian product File format Computer Science Applications Theoretical Computer Science symbols.namesake Search engine Artificial Intelligence Control and Systems Engineering symbols Software |
| Zdroj: | Information Sciences. 90:91-107 |
| ISSN: | 0020-0255 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect