Querying the Guarded Fragment with Transitivity.
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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Journal article |
| Language: | English |
| Published: |
Springer
2013
|
| _version_ | 1797101412669194240 |
|---|---|
| author | Gottlob, G Pieris, A Tendera, L |
| author2 | Fomin, F |
| author_facet | Fomin, F Gottlob, G Pieris, A Tendera, L |
| author_sort | Gottlob, G |
| collection | OXFORD |
| description | 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 2exptime-complete in combined complexity and coNP-complete in data complexity. We also show that for a restricted class of queries, query answering under GF+TG is decidable. © 2013 Springer-Verlag. |
| first_indexed | 2024-03-07T05:51:33Z |
| format | Journal article |
| id | oxford-uuid:e9110d87-fc61-40c9-a346-c5fa8d4cfb86 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T05:51:33Z |
| publishDate | 2013 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:e9110d87-fc61-40c9-a346-c5fa8d4cfb862022-03-27T10:51:29ZQuerying the Guarded Fragment with Transitivity.Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:e9110d87-fc61-40c9-a346-c5fa8d4cfb86EnglishSymplectic Elements at OxfordSpringer2013Gottlob, GPieris, ATendera, LFomin, FFreivalds, RKwiatkowska, MPeleg, DWe 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 2exptime-complete in combined complexity and coNP-complete in data complexity. We also show that for a restricted class of queries, query answering under GF+TG is decidable. © 2013 Springer-Verlag. |
| spellingShingle | Gottlob, G Pieris, A Tendera, L Querying the Guarded Fragment with Transitivity. |
| title | Querying the Guarded Fragment with Transitivity. |
| title_full | Querying the Guarded Fragment with Transitivity. |
| title_fullStr | Querying the Guarded Fragment with Transitivity. |
| title_full_unstemmed | Querying the Guarded Fragment with Transitivity. |
| title_short | Querying the Guarded Fragment with Transitivity. |
| title_sort | querying the guarded fragment with transitivity |
| work_keys_str_mv | AT gottlobg queryingtheguardedfragmentwithtransitivity AT pierisa queryingtheguardedfragmentwithtransitivity AT tenderal queryingtheguardedfragmentwithtransitivity |