Querying the Guarded Fragment with Transitivity

Georg Gottlob, Andreas Pieris, Lidia Tendera

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish
Title of host publicationAutomata, Languages, and Programming
Subtitle of host publication40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II
EditorsFedor V. Fomin, Rusis Freivalds, Marta Kwiatkowska, David Peleg
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages12
ISBN (Electronic)978-3-642-39212-2
ISBN (Print)978-3-642-39211-5
Publication statusPublished - 2013

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Querying the Guarded Fragment with Transitivity'. Together they form a unique fingerprint.

Cite this