  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
extended with the bottom concept, we provide a characterization of the classes
of OMQs that are fixed-parameter tractable. For its fragment EL extended with
domain and range restrictions and the bottom concept (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 admit functional roles.
