Various modelling features of DLs affect the complexity of conjunctive query (CQ) entailment in a rather strong sense. For the most popular basic description logic (DL), ALC, the complexity of CQ entailment is known to be ExpTimecomplete, as is that of knowledge-base satisfiability. It was first shown in [9, Thm. 2] that CQ entailment becomes exponentially harder when ALC is extended with inverse roles (I), while the complexity of satisfiability remains the same. Shortly after, a combination of transitivity and role-hierarchies (SH) was shown to be another culprit of higher worst-case complexity of reasoning [5, Thm. 1]. Finally, also nominals (O) turned out to be equally problematic [10, Thm. 9]. On the other hand, there are “benign” DL constructs that do not affect the complexity of CQ entailment. Examples are counting (Q) [9, Thm. 4] (the complexity stays the same even for expressive arithmetical constraints [1, Thm. 21]), role-hierarchies alone (H) [6, Cor. 3], or even a tamed use of higher-arity relations [2, Thm. 20]. Our result. We study CQ entailment in ALCSelf , an extension of ALC with the Self operator, i.e. a modelling feature that allows us to specify the situation when an element is related to itself by a binary relationship. Among other things, this allows us to formalise the concept of a “narcissist”, e.g. Narcissist ≡ ∃loves.Self. The Self operator is supported by the OWL 2 Web Ontology Language and the DL SROIQ [7]. Due to its simplicity (it only refers to one element), it is easy to handle by automata techniques [4] or consequence-based methods [11] and thus, so far, there has been no real indication that the added expressivity provided by Self may change anything, complexity-wise. Arguably, this impression is further corroborated by the observation that Self features in two profiles of OWL 2 (EL/RL), without harming tractability [8]. However, we present a rather counter-intuitive result, namely that CQ entailment for ALCSelf is exponentially harder than for ALC, thus placing the seemingly innocuous Self operator among the “malign” modelling features.
Bartosz Bednarczyk, Sebastian Rudolph Our proof goes via encoding of computational trees of alternating Turing machines working in exponential space and follows a general hardness-proof-scheme by Lutz [9, Section 4]. However, to adjust the schema to ALCSelf , novel ideas are required: the ability to speak about self-loops is exploited to produce a single query that traverses trees in a root-to-leaf manner and to simulate disjunction inside CQs, useful to express that certain paths are repeated inside the tree.
To illustrate our proof technique, assume that the structures under consideration are two full binary trees of height n with their roots connected via the next role. The crucial task of the to-be-constructed query is to “synchronise” the two trees, which requires to identify and connect leaves in corresponding positions. To this end, the structures are axiomatised to satisfy a few additional properties: (a) each node is labelled with a unique Lvli concept (meaning that its distance from its root is equal to i), (b) every node from the (i−1)-th level is connected to its left (resp. right) child by `i (resp. ri) role, (c) every node has a `i- and a ri-self-loop for all 1 ≤ i ≤ n, and (d) all leaves (and only they) have a next-self-loop. The case of n = 2 is depicted below.
Then, one can produce a single CQ q with distinguished variables x, y such that
the set of pairs (π(x), π(y)) over all matches π of q over the above-depicted
structure is equal to the set of all leaf-leaf pairs between two trees of the same
addresses (when numbered from left to right). A quick check can ensure the
reader that, for n = 2, the following conjunctive query does the job:3
(Lvl2?; r2−; `2−; r1−; `1−; Lvl0?; next; Lvl0?; `1; r1; `2; r2; Lvl2?)(x, y)
∧ (r2−; `2−; `1−; next; `1; `2; r2; Lvl2?; r2−; `2−; r1−; next; r1; `2; r2)(x, y)
∧ (`2−; r1−; `1−; next; `1; r1; `2; Lvl2?; r2−; r1−; `1−1; next; `1; r1; r2)(x, y)
The first line of the query is responsible for selecting a leaf x in the left tree
and a leaf y in the second tree. The second (resp. third) line ensures that the
first (resp. second) bits of their addresses coincide. In the full paper [