On Finite Entailment of Non-Local Queries in Description Logics

06/30/2020
by   Tomasz Gogacz, et al.
0

We study the problem of finite entailment of ontology-mediated queries. Going beyond local queries, we allow transitive closure over roles. We focus on ontologies formulated in the description logics ALCOI and ALCOQ, extended with transitive closure. For both logics, we show 2EXPTIME upper bounds for finite entailment of unions of conjunctive queries with transitive closure. We also provide a matching lower bound by showing that finite entailment of conjunctive queries with transitive closure in ALC is 2EXPTIME-hard.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset