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 
KUIJPERS, Bart 
Issue Date: 2003
Publisher: Springer-Verlag
Source: DATABASE THEORY ICDT 2003, PROCEEDINGS. p. 190-206
Series/Report: LECTURE NOTES IN COMPUTER SCIENCE
Series/Report no.: 2572
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.
Document URI: http://hdl.handle.net/1942/634
ISBN: 0302-9743
ISSN: 0302-9743
ISI #: 000181548600013
Category: A1
Type: Journal Contribution
Validations: ecoom 2004
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
sdcql3.pdf175.3 kBAdobe PDFView/Open
Show full item record

WEB OF SCIENCETM
Citations

2
checked on May 22, 2022

Page view(s)

52
checked on May 28, 2022

Download(s)

152
checked on May 28, 2022

Google ScholarTM

Check

Altmetric


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