www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/633

Title: Constraint Databases, Data Structures and Efficient Query Evaluation
Authors: Heintz, Joos
KUIJPERS, Bart
Issue Date: 2004
Publisher: Springer-Verlag
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:
URI: http://hdl.handle.net/1942/633
ISI #: 000222323700001
ISBN: 3-540-22126-3
ISSN: 0302-9743
Category: A1
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.