Document Server@UHasselt >
Research >
Research publications >

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

Title: Deciding Termination of Query Evaluation in Transitive-Closure Logics for Constraint Databases.
Authors: GEERTS, Floris
Issue Date: 2003
Publisher: Springer-Verlag
Citation: DATABASE THEORY ICDT 2003, PROCEEDINGS. p. 190-206
Abstract: We study extensions of first-order logic over the reals with different types of transitive-closure operators as query languages for constraint databases that can be described by Boolean combinations of polynomial inequalities over the reals. We are in particular interested in deciding the termination of the evaluation of queries expressible in these transitive-closure logics. It turns out that termination is undecidable in general. However, we show that the termination of the transitive closure of a continuous function graph in the two-dimensional plane, viewed as a binary relation over the reals, is decidable, and even expressible in first-order logic over the reals. Based on this result, we identify a particular transitive-closure logic for which termination of query evaluation is decidable and which is more expressive than first-order logic over the reals. Furthermore, we can define a guarded fragment in which exactly the terminating queries of this language are expressible.
URI: http://hdl.handle.net/1942/634
ISI #: 000181548600013
ISBN: 0302-9743
ISSN: 0302-9743
Category: A1
Type: Journal Contribution
Validation: ecoom, 2004
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A175.3 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.