Document Server@UHasselt >
Research publications >
Please use this identifier to cite or link to this item:
|Title: ||Constraint Databases, Data Structures and Efficient Query Evaluation|
|Authors: ||Heintz, Joos|
|Issue Date: ||2004|
|Citation: ||CONSTRAINT DATABASES, PROCEEDINGS. p. 1-24|
|Series/Report: ||LECTURE NOTES IN COMPUTER SCIENCE, 3074|
|Abstract: ||Constraint databases that can be described by boolean combinations of polynomial inequalities over the reals have received ample research attention. In particular, the expressive power of first-order logic over the reals, as a constraint database query language, has been studied extensively. The difficulty of the effective evaluation of first-order queries, usually involving some form of quantifier elimination, has been largely neglected.
The contribution of this paper is a discussion of various aspects that influence the efficiency of the evaluation of queries expressible in first-order logic over the reals. We emphasize the importance of data structures and their effect on the complexity of quantifier-elimination. We also propose a novel data model that supports data exploration and visualization as well as efficient query evaluation. In this context, we introduce the concept of sample point query. Finally, we show that a particular kind of sample point query cannot be evaluated in polynomial sequential time by means of branching-parsimonious procedures.
Research partially supported by the following Argentinian, Belgian, German and Spanish grants:|
|ISI #: ||000222323700001|
|Type: ||Journal Contribution|
|Validation: ||ecoom, 2005|
|Appears in Collections: ||Research publications|
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.