Please use this identifier to cite or link to this item:
Title: On the Decidability of Termination of Query Evaluation in Transitive-Closure Logics for Polynomial Constraint Databases
Authors: GEERTS, Floris 
Issue Date: 2005
Publisher: Elsevier
Source: THEORETICAL COMPUTER SCIENCE, 336(1). p. 125-151
Abstract: The formalism of constraint databases, in which possibly infinite data sets are described by Boolean combinations of polynomial inequality and equality constraints, has its main application area in spatial databases. The standard query language for polynomial constraint databases is first-order logic over the reals. Because of the limited expressive power of this logic with respect to queries that are important in spatial database applications, various extensions have been introduced. We study extensions of first-order logic with different types of transitive-closure operators and 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:
ISSN: 0304-3975
e-ISSN: 1879-2294
DOI: 10.1016/j.tcs.2004.10.034
ISI #: 000229422600006
Category: A1
Type: Journal Contribution
Validations: ecoom 2006
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
onthedecidability.pdf269.97 kBAdobe PDFView/Open
Show full item record


checked on Sep 2, 2020


checked on May 13, 2022

Page view(s)

checked on May 16, 2022


checked on May 16, 2022

Google ScholarTM



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