Prelegent: Marcin Przybyłko

A known dichotomy states that for conjunctive queries (CQs) with no self-joins the set of answers can be enumerated with linear preprocessing* and constant delay* if and only** if the query is both acyclic and free-connex. I will show how to lift those results to the enumeration of certain answers to ontology mediated queries in the form of CQs enhanced by guarded tuple generating dependencies (GTGD) -- a formalism commonly used in knowledge representation. *data complexity **lower bounds depend on some common conjectures: triangle detection, clique detection, matrix multiplication