Journal article icon

Journal article

Querying the Guarded Fragment with Transitivity.

Abstract:

We study the problem of answering a union of Boolean conjunctive queries q against a database Δ, and a logical theory φ which falls in the guarded fragment with transitive guards (GF + TG). We trace the frontier between decidability and undecidability of the problem under consideration. Surprisingly, we show that query answering under GF2 + TG, i.e., the two-variable fragment of GF + TG, is already undecidable (even without equality), whereas its monadic fragment is decidable; in fact, it is ...

Expand abstract
Publication status:
Published

Actions


Access Document


Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author

Contributors

Role:
Editor
Role:
Editor
Role:
Editor
Role:
Editor
Publisher:
Springer
Journal:
ICALP (2) More from this journal
Volume:
7966
Issue:
PART 2
Pages:
287-298
Publication date:
2013-01-01
DOI:
EISSN:
1611-3349
ISSN:
0302-9743
Language:
English
Pubs id:
pubs:415436
UUID:
uuid:e9110d87-fc61-40c9-a346-c5fa8d4cfb86
Local pid:
pubs:415436
Source identifiers:
415436
Deposit date:
2013-11-17

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP