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/945

Title: On the Decidability of Termination of Query Evaluation in Transitive-Closure Logics for Polynomial Constraint Databases
Authors: GEERTS, Floris
KUIJPERS, Bart
Issue Date: 2005
Publisher: Elsevier
Citation: 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.
URI: http://hdl.handle.net/1942/945
DOI: 10.1016/j.tcs.2004.10.034
ISI #: 000229422600006
ISSN: 0304-3975
Category: A1
Type: Journal Contribution
Validation: ecoom, 2006
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A269.97 kBAdobe PDF

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