  In many scenarios, complete and incomplete information coexist. For this
reason, the knowledge representation and database communities have long shown
interest in simultaneously supporting the closed- and the open-world views when
reasoning about logic theories. Here we consider the setting of querying
possibly incomplete data using logic theories, formalized as the evaluation of
an ontology-mediated query (OMQ) that pairs a query with a theory, sometimes
called an ontology, expressing background knowledge. This can be further
enriched by specifying a set of closed predicates from the theory that are to
be interpreted under the closed-world assumption, while the rest are
interpreted with the open-world view. In this way we can retrieve more precise
answers to queries by leveraging the partial completeness of the data.
  The central goal of this paper is to understand the relative expressiveness
of OMQ languages in which the ontology is written in the expressive Description
Logic (DL) ALCHOI and includes a set of closed predicates. We consider a
restricted class of conjunctive queries. Our main result is to show that every
query in this non-monotonic query language can be translated in polynomial time
into Datalog with negation under the stable model semantics. To overcome the
challenge that Datalog has no direct means to express the existential
quantification present in ALCHOI, we define a two-player game that
characterizes the satisfaction of the ontology, and design a Datalog query that
can decide the existence of a winning strategy for the game. If there are no
closed predicates, that is in the case of querying a plain ALCHOI knowledge
base, our translation yields a positive disjunctive Datalog program of
polynomial size. To the best of our knowledge, unlike previous translations for
related fragments with expressive (non-Horn) DLs, these are the first
polynomial time translations.
