Abstract: The talk consists of two parts. In the first part, we present our recent theoretical results on the computational complexity of answering OWL 2 QL ontology-mediated queries (OMQs) with tree-shaped and bounded treewidth conjunctive queries (CQs) by means of query rewriting. In particular, we show that OMQs with bounded-depth ontologies have nonrecursive datalog (NDL) rewritings that can be constructed and evaluated in LOGCFL for combined complexity, even in NL if their CQs are tree-shaped with a bounded number of leaves. For OMQs with arbitrary ontologies and bounded-leaf CQs, NDL- rewritings are constructed and evaluated in LOGCFL. On the other hand, we show that answering OMQs with tree-shaped CQs is not fixed-parameter tractable if the ontology depth or the number of leaves in the CQs is regarded as the parameter, and that answering OMQs with a fixed ontology (of infinite depth) is NP-complete for tree-shaped and LOGCFL for bounded-leaf CQs.

In the second part, we report on our practical experience with the ontology-based data access platform Ontop. We concentrate on answering OMQs over the NPD FactPages ontology and argue that, for such real-world OMQs, the sources of theoretical intractability do not play a significant role in computing rewritings. On the other hand, compiling a large part of the ontology into mappings (known as T-mappings) with various optimisation techniques based, in particular, on the use of integrity constraints in the source database, allows Ontop to produce efficient SQL queries over the database.