Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/945
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGEERTS, Floris-
dc.contributor.authorKUIJPERS, Bart-
dc.date.accessioned2006-05-09T13:48:15Z-
dc.date.available2006-05-09T13:48:15Z-
dc.date.issued2005-
dc.identifier.citationTHEORETICAL COMPUTER SCIENCE, 336(1). p. 125-151-
dc.identifier.issn0304-3975-
dc.identifier.urihttp://hdl.handle.net/1942/945-
dc.description.abstractThe 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.-
dc.format.extent276446 bytes-
dc.format.mimetypeapplication/pdf-
dc.language.isoen-
dc.publisherElsevier-
dc.titleOn the Decidability of Termination of Query Evaluation in Transitive-Closure Logics for Polynomial Constraint Databases-
dc.typeJournal Contribution-
dc.bibliographicCitation.bvolume336-
dc.identifier.epage151-
dc.identifier.issue1-
dc.identifier.spage125-
dc.identifier.volume336-
local.bibliographicCitation.jcatA1-
local.type.refereedRefereed-
local.type.specifiedArticle-
dc.bibliographicCitation.oldjcatA1-
dc.identifier.doi10.1016/j.tcs.2004.10.034-
dc.identifier.isi000229422600006-
item.fulltextWith Fulltext-
item.validationecoom 2006-
item.contributorKUIJPERS, Bart-
item.contributorGEERTS, Floris-
item.fullcitationGEERTS, Floris & KUIJPERS, Bart (2005) On the Decidability of Termination of Query Evaluation in Transitive-Closure Logics for Polynomial Constraint Databases. In: THEORETICAL COMPUTER SCIENCE, 336(1). p. 125-151.-
item.accessRightsOpen Access-
crisitem.journal.issn0304-3975-
crisitem.journal.eissn1879-2294-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
onthedecidability.pdf269.97 kBAdobe PDFView/Open
Show simple item record

SCOPUSTM   
Citations

3
checked on Sep 2, 2020

WEB OF SCIENCETM
Citations

6
checked on Jun 29, 2022

Page view(s)

60
checked on Jul 1, 2022

Download(s)

120
checked on Jul 1, 2022

Google ScholarTM

Check

Altmetric


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