|
 
|
[GRS99] On the Orthographic Dimension of Constraint Databases
Conférence Internationale avec comité de lecture : Intl. Conf. on Database Theory (ICDT), January 1999,
motcle:
Résumé:
One of the most important advantages of constraint data\-bases is their ability
to represent and to manipulate data in arbitrary dimension within a uniform
framework. Although the complexity of querying such databases by standard
means such as first-order queries has been shown to be tractable for reasonable
constraints (e.g. polynomial), it depends badly (roughly speaking
exponentially) upon the dimension of the data. A precise analysis of the
trade-off between the dimension of the input data and the complexity of the
queries reveals that the complexity strongly depends upon the
use the input makes of
its dimensions. We introduce the concept of orthographic dimension, which,
for a convex object $O$, corresponds to the dimension of the (component)
objects $O_1,...,O_n$, such that $O=O_1\times\cdots\times O_n$.
We study properties of databases with bounded orthographic dimension in a general
setting of o-minimal structures, and provide a syntactic characterization of
first-order orthographic dimension preserving queries.
The main result of the paper concerns linear constraint databases. We prove that orthographic dimension preserving Boolean combination of conjunctive queries can be evaluated independently of the global dimension, with operators limited to the orthographic dimension, in parallel on the components. This results in an extremely efficient optimization mechanism, very easy to use in practical applications.
BibTeX
| @inproceedings { | |||
| GRS99, | |||
| title | = | "{On the Orthographic Dimension of Constraint Databases}", | |
| author | = | " S. Grumbach and P. Rigaux and L. Segoufin ", | |
| booktitle | = | "{Intl. Conf. on Database Theory (ICDT)}", | |
| year | = | 1999, | |
| month | = | "January", | |
| } | |||
