Language:

Deciding Termination of Query Evaluation in Transitive-Closure Logics for Constraint Databases

Geerts, Floris ; Kuijpers, Bart Lenzerini, Maurizio ; Motwani, Rajeev ; Calvanese, Diego

Database Theory — ICDT 2003, 2003, p.190-206 [Peer Reviewed Journal]

Berlin, Heidelberg: Springer Berlin Heidelberg

Full text available

Citations Cited by

Actions
1. Add to e-Shelf
2. Remove from e-Shelf
3. E-mail
4. Print
5. Permalink
6. Citation
7. EasyBib
8. EndNote
9. RefWorks
10. Delicious
11. Export RIS
12. Export BibTeX

Title:
Deciding Termination of Query Evaluation in Transitive-Closure Logics for Constraint Databases
Author: Geerts, Floris ; Kuijpers, Bart
Lenzerini, Maurizio ; Motwani, Rajeev ; Calvanese, Diego
Subjects: Applied sciences ; Binary Relation ; Computer science; control theory; systems ; Decision Procedure ; Exact sciences and technology ; Information systems. Data bases ; Logical, boolean and switching functions ; Memory organisation. Data processing ; Periodic Point ; Query Language ; Software ; Theoretical computing ; Transitive Closure
Is Part Of: Database Theory — ICDT 2003, 2003, p.190-206
Notes: The research presented here was done while this author was at the University of Limburg.
Description: 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.
Related Titles: Lecture Notes in Computer Science
Publisher: Berlin, Heidelberg: Springer Berlin Heidelberg
Language: English

Links

View record in Pascal Francis

Back to results list

Result 1 Next Go to Next page

Implemented by: Social Network Logos:

Deciding Termination of Query Evaluation in Transitive-Closure Logics for Constraint Databases

Geerts, Floris ; Kuijpers, Bart Lenzerini, Maurizio ; Motwani, Rajeev ; Calvanese, Diego

Berlin, Heidelberg: Springer Berlin Heidelberg

Searching Remote Databases, Please Wait