When is Ontology-Mediated Querying Efficient?

Pablo Barceló, Cristina Feier, Carsten Lutz, Andreas Pieris

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

In ontology-mediated querying, description logic (DL) ontologies are used to enrich incomplete data with domain knowledge which results in more complete answers to queries. However, the evaluation of ontology-mediated queries (OMQs) over relational databases is computationally hard. This raises the question when OMQ evaluation is efficient, in the sense of being tractable in combined complexity or fixed-parameter tractable. We study this question for a range of ontology-mediated query languages based on several important and widely-used DLs, using unions of conjunctive queries as the actual queries. For the DL ELHI⊥, we provide a characterization of the classes of OMQs that are fixed-parameter tractable. For its fragment ELH dr⊥ , which restricts the use of inverse roles, we provide a characterization of the classes of OMQs that are tractable in combined complexity. Both results are in terms of equivalence to OMQs of bounded tree width and rest on a reasonable assumption from parameterized complexity theory. They are similar in spirit to Grohe’s seminal characterization of the tractable classes of conjunctive queries over relational databases. We further study the complexity of the meta problem of deciding whether a given OMQ is equivalent to an OMQ of bounded tree width, providing several completeness results that range from NP to 2EXPTIME, depending on the DL used. We also consider the DL-Lite family of DLs, including members that, unlike ELHI⊥, admit functional roles.

Original languageEnglish
Title of host publicationProceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages28
ISBN (Electronic)978-1-7281-3608-0
ISBN (Print)978-1-7281-3609-7
Publication statusPublished - 5 Aug 2019
EventThirty-Fourth Annual ACM/IEEE Symposium on Logic in Computer Science - Vancouver, Canada
Duration: 24 Jun 201927 Jun 2019


ConferenceThirty-Fourth Annual ACM/IEEE Symposium on Logic in Computer Science
Abbreviated titleLICS 2019
Internet address


Dive into the research topics of 'When is Ontology-Mediated Querying Efficient?'. Together they form a unique fingerprint.

Cite this