Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/945
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | GEERTS, Floris | - |
dc.contributor.author | KUIJPERS, Bart | - |
dc.date.accessioned | 2006-05-09T13:48:15Z | - |
dc.date.available | 2006-05-09T13:48:15Z | - |
dc.date.issued | 2005 | - |
dc.identifier.citation | THEORETICAL COMPUTER SCIENCE, 336(1). p. 125-151 | - |
dc.identifier.issn | 0304-3975 | - |
dc.identifier.uri | http://hdl.handle.net/1942/945 | - |
dc.description.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. | - |
dc.format.extent | 276446 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.language.iso | en | - |
dc.publisher | Elsevier | - |
dc.title | On the Decidability of Termination of Query Evaluation in Transitive-Closure Logics for Polynomial Constraint Databases | - |
dc.type | Journal Contribution | - |
dc.bibliographicCitation.bvolume | 336 | - |
dc.identifier.epage | 151 | - |
dc.identifier.issue | 1 | - |
dc.identifier.spage | 125 | - |
dc.identifier.volume | 336 | - |
local.bibliographicCitation.jcat | A1 | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
dc.bibliographicCitation.oldjcat | A1 | - |
dc.identifier.doi | 10.1016/j.tcs.2004.10.034 | - |
dc.identifier.isi | 000229422600006 | - |
item.fullcitation | GEERTS, 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.fulltext | With Fulltext | - |
item.validation | ecoom 2006 | - |
item.contributor | GEERTS, Floris | - |
item.contributor | KUIJPERS, Bart | - |
item.accessRights | Open Access | - |
crisitem.journal.issn | 0304-3975 | - |
crisitem.journal.eissn | 1879-2294 | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
onthedecidability.pdf | 269.97 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
3
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
6
checked on Sep 26, 2024
Page view(s)
88
checked on Jul 31, 2023
Download(s)
168
checked on Jul 31, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.