Querying the Guarded Fragment with Transitivity.

Journal article

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.

Authors: Gottlob, G; Pieris, A; Tendera, L

• Publication status: Published
• Publisher: Springer
• Journal: ICALP (2)
• Volume: 7966
• Issue: PART 2
• Pages: 287-298
• Publication date: 2013-01-01
• DOI: 10.1007/978-3-642-39212-2_27
• EISSN: 1611-3349
• ISSN: 0302-9743
• Language: English