Description Logics (DLs) are a family of languages for knowledge representation, popular for writing ontologies that describe domain-specific knowledge. As fragments of classical first-order logic, DLs make the open-world assumption. That is, the semantics of a knowledge base (KB) is given by the set of all its models. This view naturally supports modeling of incomplete knowledge. However, it is not always fully adequate, as in many applications of DLs, incomplete knowledge interacts with complete information. For example, in the popular paradigm of ontology-based data access, DL ontologies are advocated as a means to leverage domain knowledge when querying data sources. These sources often stem from traditional relational databases, which have a closedworld view and are assumed to fully describe the instances included in a relation. E.g., a municipality-provided table of bus routes can be assumed complete. Query answering algorithms should exploit this to exclude irrelevant models and infer more answers.
Combining open and closed world reasoning is not a new topic in DLs [
Most work considering closed predicates has focused on the problem of evaluating
a query (usually a conjunctive query) under the standard certain answer semantics, and
on data complexity, i.e. the complexity measured in the size of the data instance to be
queried, while both the ontology and the query are assumed to be fixed. E.g., Franconi
et at. ([
The data complexity is an important indicator of whether algorithms can scale to
large amounts of data. However, it is also fundamental to understand the combined
complexity, which takes the size of the ontology and the query along with the data into
account, as the size of these two components often has a big impact on the performance
of query answering algorithms. Indeed, ontologies can be very large [
We use NC, NR and NI for concept names, role names and individual names, respectively. DL knowledge bases (KB) take the form K = (T ; ; A). The TBox T is a set of axioms , which usually include concept inclusions C v D and role inclusions r v s. The specific syntax of concepts C; D, roles r; s and other possible axioms depends on the DL in question. is a set of concept and role names, called the closed predicates of K. Finally, the ABox A is a finite set of assertions of the forms A(b) and r(a; b) with A 2 NC, r 2 NR and a; b 2 NI.
The notion of an interpretation I = ( I ; I ) is as usual. We make the standard name assumption (SNA), i.e., aI = a for all I and individuals a. Concepts C are interpreted as sets of objects CI I and roles r as binary relations rI I I in the standard way. The notions of TBox and ABox satisfaction I j= T and I j= A are also as usual. We say that I respects a given NC [ NR if: (a) for all A 2 \ NC, if d 2 AI , then A(d) 2 A, and (b) for all r 2 \ NR, if (d; d0) 2 rI , then r(d; d0) 2 A.
We call I a model of a KB K = (T ; ; A), and write I j= K, if I j= T , I j= A, and I respects the closed predicates in .
The main problem we study here is query answering, which is a generalization of standard reasoning tasks such as consistency testing and instance checking. Let NV be a countably infinite set of variables. Boolean conjunctive queries (BCQs), take the form q = 1 ^ : : : ^ n, where each j is an atom of the form A(t) or r(t; t0) with A 2 NC, r 2 NR, and ft; t0g NI [ NV. Queries are given the standard first order semantics, where all variables are existentially quantified: we write I j= q0 if there is an assignment from the variables in q to objects in I that makes all atoms true. A Boolean union of conjunctive queries (BUCQ) is of the form q0 = q1 _ : : : _ qn, where each qi is a BCQ. Given an interpretation I, we write I j= q0 if there is i 2 f1; : : : ; ng such that I j= qi, and given a KB K we write K j= q if I j= q holds for every model I of K. Given K and a B(U)CQ q as above, the query entailment problem is to decide whether K j= q.All results below apply also to query answering (as a decision problem) for queries with answer variables using the standard reduction to query entailment. 3
In the presence of complete data, already consistency checking and instance query entailment in the basic DL-Litecore are NP-complete. For the hardness, it is not hard to reduce 3-colorability to deciding consistency of a DL-Litecore KB with closed concepts.
Without closed predicates
With closed predicates Instance queries B(U)CQs
Instance queries
B(U)CQs DL-Litecore DL-LiteR EL ALCO SHOQ, SHOI
NL
[
For the membership, we provide an algorithm that shows an NP upper bound even for rich DL-Lite dialects with Boolean combinations of concepts, role inclusions, and nominals, and for UCQs without existentially quantified variables.
In E L we can use DBoxes to express disjunction, atomic negation, and nominals, making E L as expressive as ALCO, and causing consistency testing to require exponential time in the worst case. Tight upper bounds for instance queries and quantifier free UCQs for any DL containing E L can then be inferred by a reduction to standard reasoning in well-known expressive DLs with nominals.
For more expensive queries, we show that entailment of UCQs is 2EXPTIME-hard
for DL-LiteR and E L based on a reduction from the word problem for Alternating
Turing machines (ATMs) with exponential work space [
A similar reduction allows us to prove 2EXPTIME-hardness of CQ entailment in the standard DL ALCO (with no DBox). This closes an open problem and singles out nominals as a previously unidentified source of complexity when answering queries over expressive DLs. A summary of our result and its comparison to the case without DBox is provided in Table 1.
In the light of these negative results, we also looked for classes of queries for which the query answering problem has lower complexity. In particular, we considered a restriction on variables called K-safety which guarantees that it is sufficient to consider assignments of the variable to individuals in the KB, and there is no need to consider other objects in the interpretation domain . A query is called K-safe if all its variables are K-safe. We also generalize K-safe queries to K-acyclic by allowing for variables that are not K-safe, but requiring that they induce only acyclic subqueries in the original query. 4
Closed predicates seem to have a great potential in applications of DLs, but as our results show, they are computationally costly. It remains a challenge to identify useful restricted settings with better complexity, and to explore other ways for effectively supporting partial completeness at a lower computational cost.
We note that all hardness proofs in the paper are given for KBs (T ; ; A) where contains only a constant number of concept names (which can be further reduced to a single one in DLs that can express disjointness). Moreover, they also apply to KBs (T ; ;; A) with no closed predicates, but where axioms A v fa; bg with the so-called one-of or enum are allowed. Hence our results also shed light on the effect of nominal enumerations in lightweight DLs.
Some interesting questions remain open for the DL-Lite family, like the precise complexity of (U)CQs in DL-Litecore. We remark that inverses play a very limited role in the hardness results here. They all apply to 1-way DL-Lite KBs, where only role names r occur in the right-hand side of axioms, and inverse roles r on the left-hand side; these KBs have directed models in the style of E L and ALC.
This work was partially supported by the Austrian Science Fund (FWF) projects T515, P25207, and the project ORMiE from the Free University of Bozen-Bolzano.