Enumerating Answers to Ontology Mediated Queries

Speaker(s)

Marcin Przybyłko

Affiliation

University of Leipzig

Date

Dec. 21, 2022, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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

---