Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Teoria Automatów


Enumerating Answers to Ontology Mediated Queries

Prelegent: Marcin Przybyłko

2022-12-21 14:15

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