Data Complexity of Answering Ontology-Mediated Queries with a Covering Axiom

In this paper, we work with an application of specific ontologies to facilitate access to various types of data sources that is known as ontology-based data access (OBDA) where an ontology is used to support query answering for distributed and heterogeneous data sources. For this approach to work, one has to carefully choose the ontology language. We considered ontologies formulated in terms of a suitable description logic. The OWL 2 Web Ontology Language is an ontology language for the Semantic Web recently designed ad standardised by the W3C. We use the OWL 2 QL profile designed specifically for OBDA via query rewriting. Unfortunately, OWL 2 QL does not contain many concept and role constructs that are useful in many OBDA applications such as disjunction (or union) on the right-hand side of concept inclusions. In order to implement OBDA to the data with a complex structure, we could adapt first-order (FO) rewritability to the concrete query and ontology somehow interested for a user. We study one simple fixed non-Horn ontology O_A = {A -> T⊔ F} and face difficult problem. Ultimately aiming at a complete classification of CQs q according to the data complexity of answering OMQs Q = (O,q), we obtained some preliminary results on this problem. In particular, we study the data complexity of this task when the ontology and the CQ are fixed and an arbitrary data is considered. We obtained a few results about NL, P and coNP classes as a continuation of our previous research. We defined a new subclass of F-tree OMQs (q_T1T^n,O_\top), which are NL-complete. We also analysed the plain 2T+2F queries, classified them by constructed gadgets and identified interesting queries, which may be in P.