Enumerating Answers to Ontology Mediated Queries

Prelegent(ci)

Marcin Przybyłko

Afiliacja

University of Leipzig

Termin

21 grudnia 2022 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

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

---