We consider the consequences on basic reasoning problems of allowing negated primitive concepts on left-hand-sides of inclusion dependencies in the description logic dialect CF Dnc. Although earlier work has shown that this makes CQ answering coNP-complete, we show that TBox consistency and concept satis ability remain in PTIME. We also show that knowledge base consistency and instance retrieval remain in PTIME if a CF Dnc knowledge base satis es a number of additional conditions, and that failing any one of these conditions will alone lead to intractability for these problems.
Dialects of description logic (DLs) with PTIME complexity of reasoning services
have become an important tool in addressing scalability issues in the semantic
web, in particular with regard to SPARQL query evaluation in the context of the
OWL 2 direct semantics entailment regime. Indeed, the W3C has adopted two
DL fragments of OWL 2 that are designed to ensure PTIME data complexity
for the key services of checking for knowledge base (KB) consistency and for
conjunctive query (CQ) answering. Called pro les, the DLs are E L++ [
Toman and Weddell have proposed an alternative CF D family of DLs with
PTIME complexity of various reasoning services [
One member of this family, CF Dnc, has PTIME complexity with respect
to the size of a knowledge base for checking KB consistency, and PTIME data
complexity for CQ answering [
In this paper, we consider the consequences of relaxing a number of syntactic restrictions in CF Dnc on KB consistency checking and other reasoning tasks. In particular, we consider the DL CF D8n;c: which now allows value restrictions and negated primitive concepts to occur on the left-hand-sides of inclusion depen8;: KB. dencies that comprise the \metadata", called a TBox, of a given CF Dnc Our results, in the order established, are as follows.
{ We show that TBox consistency for CF D8n;c: is no longer trivial, unlike the case for CF Dnc and many other lightweight logics, but remains in NLOGSPACE. { fWraegmsheonwtstohfaCtFCFDD8n;c:8n;c:whKeBre cKoBnsicsotnesnicsyteinscyNPre-mcoaminpslettreacatnadbleid.eInnttiefryesptrinecgilsye, when negated concepts are allowed on the left-hand side of inclusion dependencies, this boundary is tied to the structure of keys and to the unique name assumption (UNA).
We begin in the next section by introducing the syntax and semantics of CF D8n;c:, and talk about some of its key features and limitations. In Section 3, we consider the problem of TBox consistency, and then more general KB consistency in Section 4. A review of related work and summary comments then follows in Section 5. 2 8;:
A formal de nition of CF D8n;c: knowledge bases and the above reasoning problems now follows. Observe that the logic is based on attributes or features denoting unary functions instead of the more common case of roles denoting arbitrary binary relations. However, this is not really an issue; CF D8n;c: is ideal for expressing rei cation for predicates of any arity (see comments following).
8;: Knowledge Bases) Let F, PC and IN be disjoint sets
De nition 1 (CF Dnc
of (names of) attributes, primitive concepts and individuals, respectively. A path
function Pf is a word in F with the usual convention that the empty word
is denoted by id and concatenation by \:". Concept descriptions C and D are
de ned by the grammars on the left-hand-side of Figure 1 in which occurrences of
\A" denote primitive concepts. A concept \C : Pf1; : : : ; Pfk ! Pf" produced by
the last production of the grammar for D is called a path functional dependency
(PFD). To avoid undecidability [
Metadata and data in a CF D8n;c: knowledge base K are respectively de ned by a TBox T and an ABox A. Assume A 2 PC, C and D are arbitrary concepts given by the grammars in Figure 1, fPf1; Pf2g F and that fa; bg IN. Then T consists of a nite set of inclusion dependencies of the form C v D, and A consists of a nite set of facts in the form of concept assertions A(a), basic function assertions f (a) = b and path function assertions Pf1(a) = Pf2(b). C ::= A j :C j 8 Pf :C D ::= A
Semantics: \( )I " AI
4 4 n CI fx : PfI (x) 2 CI g j :A j 8 Pf :D j C : Pf1; : : : ; Pfk ! Pf
AI
4 4 n AI fx : PfI (x) 2 DI g fx : 8 y 2 CI : Vik=1 PfiI (x) = PfiI (y)) ) PfI (x) = PfI (y)g
A is called a primitive ABox if it consists only of concept and basic function assertions.
Semantics is de ned in the standard way with respect to an interpretation I = (4; ( )I ), where 4 is a domain of \objects" and ( )I an interpretation function that xes the interpretation of primitive concepts A to be subsets of 4, attributes f to be total functions on 4, and individuals a to be elements of 4. The interpretation function is extended to path expressions by interpreting id , the empty word, as the identity function x:x, concatenation as function composition, and to derived concept descriptions C or D as de ned in Figure 1. An interpretation I satis es an inclusion dependency C v D if CI DI , a concept assertion A(a) if aI 2 AI , a basic function assertion f (a) = b if f I (aI ) = bI and a path function assertion Pf1(a) = Pf2(b) if Pf1I (aI ) = Pf2I (bI ). I satis es a knowledge base K if it satis es each inclusion dependency and assertion in K, and also satis es UNA if, for any individuals a and b occurring in K, aI 6= bI . 2 As usual, allowing conjunction (resp. disjunction) on the right-hand (resp. lefthand) sides of inclusion dependencies is a simple syntactic sugar.
The conditions imposed on PFDs in (1) distinguish, e.g., PFDs of the form
C : f ! id and C : f ! g from PFDs of the form C : f ! g:h, and are
necessary to retain PTIME complexity for reasoning problems [
The grammar for CF D8n;c:, unlike CF Dnc, allows an unrestricted use of concept constructors for value restrictions and concept negation on left-hand-sides of inclusion dependencies. To see that this constitutes a genuine enhancement of modeling utility, consider an enrollment relation for a hypothetical relational data source about students and courses. In a CF Dnc TBox, the relation would be rei ed as the ENROLLMENT primitive concept with Student and Course features \typed" as follows:
ENROLLMENT v (8Student:STUDENT) u (8Course:COURSE): With the added exibility of value restrictions in CF D8n;c:, it is now straightforward to further restrict who may enroll in graduate courses:
8Course:GRADCOURSE v 8Student:GRADSTUDENT: The added exibility relating to negation can be used, e.g., to introduce a \top" concept, say THING, by asserting the following:
Such a concept can then be used, e.g., to enforce general range restrictions for attributes:
For reasoning tasks, such as TBox and more general KB consistency, it is 8;: convenient to assume by default, and without loss of generality, that CF Dnc knowledge bases are given in a normal form.
Lemma 2 (CF D8n;c: KB Normal Form) For every KB (T ; A), there is an equi-satis able KB (T 0; A0) in which T 0 adheres to the following (more limited) grammar for CF D8n;c: concept descriptions:
C ::= A j :A j 8f:A
D ::= A j :A j 8f:A j A : Pf1; : : : ; Pfk ! Pf;
and also where ABox A0 contains only assertions of the form f (a) = b and a = b.
2
Obtaining T 0 and A0 from an arbitrary knowledge base K that are linear in the
size of K is easily achieved by a straightforward conservative extension using
auxiliary names for intermediate concept descriptions and individuals (e.g., see
defn. of simple concepts in [
fA0 v 8f:A; :A0 v 8f::A; A0 v Bg:
Finally note that, when the UNA is assumed, it becomes necessary to distinguish the individuals that appear in the original ABox from those introduced during the normalization and for which, technically, the UNA does not apply. 8;: KB K can In particular, occurrences of path function assertions in a CF Dnc indeed in uence the computational properties of reasoning problems for K, see Section 4. 3
Unlike the case for CF Dnc and many other lightweight logics, it is possible for a CF D8n;c: TBox T to be inconsistent. In this section, we introduce a NLOGSPACE procedure for deciding TBox consistency for CF D8n;c:.
De nition 3 Let PC and F be nite sets of primitive concepts and features, respectively. We de ne an implication graph over PC and F to be a node and edge labeled graph G = (N; E) whose nodes are N = PC [ f:A j A 2 PCg [ f8f:A j A 2 PC; f 2 Fg [ f:8f:A j A 2 PC; f 2 Fg :8f:A !f :A are among the edges occurring in E. and whose edges are labeled by F [ f g and such that L ! L, 8f:A !f A, and In the following, the nodes of implication graphs are identi ed with their labels. We call the pairs (A; :A) and (8f:A; :8f:A) complementary, and, if L is a node in an implication graph G, write :L to denote the node of G for the concept label that is complementary to L. We call a node L in the implication graph G = (N; E) an empty node if L ! :L 2 E. We consider paths in G to be synonymous with words in a nite automaton based on G in which denotes the empty transition. Thus we identify, e.g., f with f with f , etc. De nition 4 Let G = (N; E) be an implication graph. We say that G is closed under consequences if L1 ! :L2 2 E whenever for nodes L1, L2, and L there is a path Pf E such that L1 !Pf L and L2 !Pf :L. 2 It is easy to see from the above that it is su cient to consider paths of the form and f to obtain the same result.
De nition 5 (Implication Graph for T ) Let T be a CF D8n;c: TBox in normal form. We de ne an implication graph for T to be the least graph G = (N; E) over the primitive concepts and features occurring in T such that 2 2 { if C v D 2 T then C ! D 2 E, and { G is closed under consequences.
The implication graph for T makes all implications between literals implied by T explicit : for T j= L1 v L2 it cannot be the case that L1 ! L2 62 E since L1 u :L2 must be empty, and this can only be enforced in the case where two paths traversing the same features and originating in L1 and :L2, respectively, end in a complementary pair of concepts. This yields the following theorem: Theorem 6 Let T be a CF D8n;c: TBox in normal form. Then T is consistent if and only if no two complementary nodes are empty in the implication graph G for T .
Proof (sketch): If two complementary nodes, e.g., A and :A, are empty then T j= A v :A and T j= :A v A; a contradiction.
If no such pair exists then there must be at least one non-empty node. We de ne an interpretation I for T to be a complete F-tree whose nodes form the domain 4 and whose edges provide the interpretation for features in F. We label the nodes of the tree by sets of literals as follows. First, initialize all labels to be empty, and then repeat the following: let n be a node that has not been Data: A CFD8n;c: TBox T initialize N and E as in De nition 3; E := E [ fC ! D j C v D 2 T g; repeat for L1; L2; L 2 N and Pf 2 f ; f g do if L1 !Pf L; L2 !Pf :L 2 E and L1 ! :L2 62 E then end
E := E [ fL1 ! :L2g; end until E is unchanged ;
Algorithm 1: Construction of Implication Graph for T labeled by neither A nor :A for some primitive concept A, but whose ancestors have already been labeled by all primitive concepts or their negations. Then either A or :A must be non-empty (since T is consistent) and neither of the two literals is implied by any of the existing labels of n (since, otherwise, the label n would already contain such a literal). Assume A is non-empty. We add a literal L to the label of the node m if Pf(n) = m (i.e., m is a Pf-descendant of n) and there is a path Pf from A to L in G (note that the edges behave as empty transitions in the construction of the path; hence, e.g., the node n is labeled by A). The construction of G for T guarantees that no node will be labeled by complementary literals. Hence, since every node is labeled either by a primitive concept or by its negation and the labeling respects all constraints implied by T , it can serve as the interpretation of primitive concepts, completing the construction. 2 Observe that, since the above interpretation is a tree, all PFDs in T are satis ed vacuously and are therefore not taken into account in the above construction (nor in the de nition of an implication graph). It is easy to see that Algorithm 1 constructs an implication graph for TBox T and runs in PTIME since there are only jT j2 edges that can be added to E. A straightforward but tedious modi cation of Algorithm 1 that (repeatedly) recomputes consequences as additional edges in the graph on the y, instead of materializing all consequences as additional edges in the graph, can be shown to be in NLOGSPACE; the need to explore paths in G then yields the following: Corollary 7 Consistency of CF D8n;c: TBoxes is NLOGSPACE-complete. Whenever T is consistent, the implication graph for T also records which primitive concepts (and/or their negations) are empty in every model, those for which A ! :A 2 E.
Corollary 8 Concept satis ability with respect to CF D8n;c: TBoxes is NLOGSPACE-complete.
The complexity landscape for ABox reasoning, in particular for knowledge base consistency, depends crucially on the occurrence of non-key PFDs in T , on path function assertions in A that are not equivalent to basic function assertions, and on whether UNA is assumed. 4.1
The Tractable Cases We rst consider KB consistency for primitive ABoxes and TBoxes without PFDs.
De nition 9 (2-CNF for an ABox) Let T be a consistent TBox without any mention of the PFD concept constructor and A a primitive ABox. We de ne 2-CNF(T ; A) to be the union of each of the following sets of clauses over the propositions A(a) and 8f:A(a), where a is an ABox individual, A a primitive concept, and f a primitive feature, and where Li stand for propositions or their negations.
{ fA(a) : A(a) 2 Ag { fL1(a) ! L2(a) : T j= L1 v L2g { fL1(a) ! L2(b) : f (a) = b 2 A; T j= L1 v 8f:L2g { fL1(b) ! L2(a) : f (a) = b 2 A; T j= 8f:L1 v L2g Recall that we have shown in Section 3 that any implication questions of the form T j= L1 v L2 can be read directly from the implication graph G for T since all implications of this form are explicit in G. Thus, we have the following. Theorem 10 Let T be a CF D8n;c: TBox without any mention of the PFD concept constructor and A a primitive ABox. Then the knowledge base K = (T ; A) is consistent if and only if T is consistent and 2-CNF(T ; A) is satis able. Proof (sketch): The satisfying assignment for 2-CNF(T ; A) yields an interpretation for the ABox of K: aI 2 AI if the proposition A(a) is true in the assignment. To complete this interpretation, since ABox individuals may be missing some features, we follow the construction from Theorem 6.
Conversely, if K is consistent, the class membership of ABox objects yields a satisfying assignment for 2-CNF(T ; A). 2 Note that the theorem can be slightly strengthened by allowing general ABoxes since, without PFD constraints, there is never a need to equate ABox objects and thus reasoning under UNA is the same as reasoning without UNA. Corollary 11 CF D8n;c: knowledge base consistency is NLOGSPACE-complete. Adding Keys under UNA. We say that a PFD key constraint L1 v L2 : Pf1; : : : ; Pfk ! Pf is potentially violated by an ABox A with respect to two distinct individuals a and b if for all 0 < i k the path functions Pf0i(a) and Pf0i(b) reach the same object in A, where Pf0i are the shortest pre xes of Pfi with that property but where Pf0i is not a pre x of Pf. Under UNA, such potentially violated PFDs can only be satis ed if the objects a and b do not simultaneously belong to descriptions L1 and L2, respectively, since UNA prevents us from repairing the violation by equating the objects Pf(a) and Pf(b). Consequently, one can simply add the following 2-CNF clauses, { L1(a) ! :L2(b) and L2(b) ! :L1(a), for all pairs of individuals a; b in A and key PFDs L1 v L2 : Pf1; : : : ; Pfk ! Pf in T for which the latter is potentially violated by the former w.r.t. a and b, called KEY-2-CNF(T ; A), to the set of clauses 2-CNF(T ; A) to account for this situation (recall De nition 9 above for the latter): Theorem 12 Let T be a CF D8n;c: TBox with arbitrary occurrences of key PFDs and let A be a primitive ABox. Then, assuming UNA, the knowledge base K = (T ; A) is consistent if and only if T is consistent and 2-CNF(T ; A) [ KEY-2-CNF(T ; A) is satis able.
Proof (sketch): The proof is essentially the same as for Theorem 10 since the interpretation of the ABox makes all PFDs in T satis ed (the KEY-2-CNF(T ; A) clauses guarantee that) and since the additional anonymous objects cannot violate PFDs since corresponding parts of the interpretation are tree shaped. 2 The theorem assumes that the ABox is primitive. However, this condition can be relaxed without harm to allow path assertions of the form \f (a) = g(b)" for which the same construction and proof argument would apply.
Corollary 13 CF D8n;c: knowledge base consistency is NLOGSPACE-complete for knowledge bases with primitive ABoxes, key-PFDs, and assuming unique names. 4.2
The Intractable Cases Unfortunately, relaxing any of the above conditions leads to intractability. For each of the cases, we show a reduction of 3-SAT to knowledge base consistency. Figure 2 illustrates the ABox widgets used to capture the behavior of 3-clauses in the three respective cases.
The Keys without UNA Case. We reduce 3-CNF satis ability to KB consistency as follows: let ' be a propositional formula in 3-CNF with clauses C1; : : : ; Ck and propositional variables x1; : : : ; xn. We de ne a CF D8n;c: knowledge base K' = (T ; A) as follows: 1. For each propositional variable xi in ', introduce an A individual xi. lj;1 aj f bj :B g aj f :B aj g lj;2 f
f cj lj;3 bj g :B The Key w/o UNA Case
The General FD Case
The Non-unit Paths Case 2. For each clause Cj introduce individuals aj, bj, and cj. 3. For the variables xi1 , xi2 , and xi3 that appear in a clause Cj, include the following basic function assertions in A: lj;1(xi1 ) = aj, lj;2(xi2 ) = aj, and lj;3(xi3 ) = bj. 4. Add assertions f (aj) = cj and f (bj) = cj to A. 5. Add concept assertion B(bj) to A. 6. Add the following inclusion dependencies to T : { T v 8lj;1::A and :T v 8lj;1:A when xi1 appears positively in Cj, and
T v 8lj;1:A and :T v 8lj;1::A when xi1 appears negatively in Cj; { T v 8lj;2:B and :T v 8lj;2::B when xi2 appears positively in Cj, and
T v 8lj;2::B and :T v 8lj;2:B when xi2 appears negatively in Cj; and { T v 8lj;3::A and :T v 8lj;3:A when xi3 appears positively in Cj, and
T v 8lj;3:A and :T v 8lj;3::A when xi3 appears negatively in Cj. 7. Finally, add the key PFD A v A : f ! id to T .
A truth assignment to the propositions xi occurring in ' is then encoded by an interpretation I of K': xI 2 T I is where xi is true, and xI 2 :T I is i i where xi is false. With this in mind, it is straightforward to con rm that any interpretation of K' will only encode a satisfying truth assignment and that, in turn, an interpretation of K' can always be constructed by a satisfying truth assignment (see the proof sketch to Lemma 14 below).
The General Functional Dependencies Case. Allowing functional dependencies (i.e., non-key PFDs) even under UNA also leads to intractability. The reduction shares the rst four steps with the previous case:
6. Add the following to T : { T v 8lj;1::A and :T v 8lj;1:A when xi1 appears positively in Cj, and
T v 8lj;1:A and :T v 8lj;1::A when xi1 appears negatively in Cj. { T v 8lj;2:8g:B and :T v 8lj;2:8g::B when xi2 appears positively in Cj, and T v 8lj;2:8g::B and :T v 8lj;2:8g:B when xi2 appears negatively in Cj; and { T v 8lj;3::A and :T v 8lj;3:A when xi3 appears positively in Cj, and
T v 8lj;3:A and :T v 8lj;3::A when xi3 appears negatively in Cj. 7. A v A : f ! g 2 T .
The Non-unit Path Agreements Case. Similarly, allowing non-primitive ABoxes with path function assertions even under UNA leads to intractability. The reduction again shares the rst three steps with the previous cases: 4. Add g:f (aj) = cj, g:f (bj) = cj. 5. Add 8g:B(bj) to A. 6. Add the following to T : { T v 8lj;1:8g::A and :T v 8lj;1:8g:A when xi1 appears positively in Cj, and T v 8lj;1:8g:A and :T v 8lj;1:8g::A when xi1 appears negatively in Cj. { T v 8lj;2:8g:B and :T v 8lj;2:8g::B when xi2 appears positively in Cj, and T v 8lj;2:8g::B and :T v 8lj;2:8g:B when xi2 appears negatively in Cj; and { T v 8lj;3:8g::A and :T v 8lj;3:8g:A when xi3 appears positively in Cj, and T v 8lj;3:8g:A and :T v 8lj;3:8g::A when xi3 appears negatively in Cj. 7. Finally, add the key PFD A v A : f ! id to T .
Note the use of paths of length 2 to in step 4 to construct anonymous objects that evade UNA. In all three cases it is easy to con rm that: Lemma 14 Let ' be a propositional formula in 3-CNF. Then ' is satis able if and only if K' is consistent.
Proof (sketch): It is easy to verify that a satisfying assignment for ' can be used to create a model for K, essentially by assigning the class membership of the individuals xij to the primitive concepts T and :T and then extending this assignment to the aj, bj and cj individuals as dictated by the constraints in T . On the other hand, a model for K (when restricted to each widget representing a clause) guarantees that at least one of the xi1 , xi2 , and xi3 will belong to the concept T : the concept B is used to make the widget corresponding to a 3-CNF clause unsatis ed exactly when the clause itself is unsatis ed: an interpretation assigning all of xi1 , xi2 , and xi3 to :T forces the two individuals connected by the dashed lines in the widgets in Figure 2 to be equal as a consequence of the PFD and to belong to B and :B at the same time, thus disqualifying such interpretations as models of K. 2 Hence, knowledge base consistency without assuming UNA or when allowing functional dependencies in T or non-primitive path equalities in A is NP-complete: membership in NP is established by guessing primitive classes and equalities for ABox individuals.
Instance Retrieval. Since CF D8n;c: is closed under negation, instance retrieval, the question K j= C(a) reduces naturally to knowledge base (in)consistency, i.e., K j= C(a) if and only if (T ; A [ f:C(a)g) is inconsistent (for K = (T ; A)) and therefore inherits the computational properties of testing for consistency: { CF D8n;c: instance retrieval is NLOGSPACE-complete for primitive ABoxes and key PFDs under UNA, and { coNP-complete in all other cases.
The instance retrieval result cannot, however, be extended to conjunctive queries.
In particular, it is a straightforward consequence of results of Schaerf that
allowing negated primitive concepts on left-hand-sides of inclusion dependencies
in CF Dnc alone makes CQ answering coNP-complete [
PFD-based constraints were rst introduced and studied in the context of
graphoriented data models (similar to RDF) and its re nements [
Logics in the CF D family that allow conjunctions on left of subsumptions
[
{ Allowing conjunction \u" yields the logic CF D? and therefore makes
reasoning PSPACE-complete [
In this paper, we have considered extensions to the logic CF Dnc and their 8;: and its various reimpact on the complexity of reasoning problems. CF Dnc stricted fragments introduced in this paper have served as vehicles for this study. Most signi cantly, we have shown that instance retrieval remains in PTIME for 8;: under UNA, provided that ABoxes are primitive and that PFDs ocCF Dnc curring in TBoxes are keys. Thus, basic graph pattern (BGP) evaluation over CF D8n;c: knowledge bases satisfying these conditions is also in PTIME.