On the Utility of CF DI ∀− nc David Toman and Grant Weddell Cheriton School of Computer Science University of Waterloo, Canada {david,gweddell}@cs.uwaterloo.ca Abstract. We consider the description logic CFDI ∀− nc , a feature-based dialect that allows capturing value restrictions, a variety of identification constraints, and unqualified feature inverses. We introduce PTIME al- gorithms for various reasoning tasks in this logic, such as knowledge base consistency and logical implication and discuss the necessity of restrictions over CFDI ∀nc to maintain tractability. We then show how CFDI ∀−nc ’s modeling capabilities make it suitable for capturing relational and object-relational data sources (including of n-ary relations) in a nat- ural way. In addition, we show that CFDI ∀− nc can simulate reasoning in DL-LiteF core . We also discuss an approach to capturing a limited variant of role hierarchies within CFDI ∀− nc . 1 Introduction We have been developing the CF D family of feature-based description logic (DL) dialects that are designed primarily to support efficient PTIME reasoning ser- vices about object relational data sources. The dialects are notable for their ability to support terminological cycles with universal restrictions over func- tional roles together with a rich variety of functional constraints such as keys and functional dependencies over functional role paths. The dialect CF D was the first member of this family, initially proposed in [8]. In [16], the authors show that reasoning about logical consequence remains in PTIME when concept conjunction is allowed on left-hand-sides of inclusion dependencies, but that this is no longer the case should a variety of other concept constructors also be allowed. In particular, it was shown that adding inverse features in posed questions alone made reasoning about logical consequence in CF D intractable. The dialect CF Dnc was subsequently introduced in which negation on right- hand-sides of inclusion dependencies replaced the ability to have conjunction on left-hand-sides [17]. This allowed the capture of so-called disjointness constraints, and also made it possible to support additional reasoning services in PTIME, notably conjunctive query answering. These results generalize to CF D∀nc knowl- edge bases in which universal restrictions are also permitted on left-hand-sides of inclusion dependencies [18]. An earlier version of this paper has appeared as [19]. In this paper, we consider the dialect CF DI ∀nc which extends CF D∀nc with an ability to have unqualified inverse features in inclusion dependencies, and also introduce a less general dialect CF DI ∀− ∀ nc in which a given CF DI nc TBox is presumed to satisfy additional syntactic restrictions. The restrictions relate to combinations of value restrictions and inverses and to combinations of value restrictions and path functional dependencies. A Summary of our main results concerning reasoning in CF DI ∀− nc , in particular PTIME algorithms for both logical consequence and for knowledge base consistency for CF DI ∀− nc knowledge bases. For the remainder the paper, we give an overview of a number of applica- tions of CF DI ∀− nc , starting with how it can be used to address issues relating to relational data sources over database schema that can include arbitrary combi- nations of functional dependencies and unary inclusion dependencies. We also show how the task of evaluating instance queries over RDF data sources based ∀− on a DL-LiteF core entailment regime can be reduced to reasoning about CF DI nc F knowledge base consistency. Note that the DL dialect DL-Litecore is of particular relevance to the W3C OWL 2 QL profile. A discussion of related work and future directions then follow in Section 6. 2 The Description Logics CF DI ∀nc and CF DI ∀− nc All members of the CF D family of DLs are fragments of FOL with underly- ing signatures based on disjoint sets of unary predicate symbols called primitive concepts, constant symbols called individuals and unary function symbols called features. Note that incorporating features deviates from normal practice to use binary predicate symbols called roles. However, as we shall see, features make it easier to incorporate concept constructors suited to the capture of relational data sources that include various dependencies by a straightforward reification of n-ary predicates. Thus, e.g., a role R can be reified as a primitive concept RC and two features domR and ranR in CF DI ∀nc or CF DI ∀− nc , and an inclu- sion dependency A v ∀R.B can then be captured as an inclusion dependency ∀domR.A v ∀ranR.B. Definition 1 (CF DI ∀nc Knowledge Bases) Let F, PC and IN be disjoint sets of (names of) features, 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 defined by the grammars on the left-hand-side of Figure 1 in which occurrences of “A” denote primitive concepts. A concept “C : Pf 1 , . . . , Pf k → Pf” produced by the last production of the grammar for D is called a path functional dependency (PFD). Metadata and data in a CF DI ∀nc knowledge base K are respectively defined by a TBox T and an ABox A. Assume A ∈ PC, C and D are arbitrary concepts given by the grammars in Figure 1, {Pf 1 , Pf 2 } ⊆ F∗ and that {a, b} ⊆ IN. Then T consists of a finite set of inclusion dependencies of the form C v D, and A Syntax Semantics: “(·)I ” C ::= A AI ⊆ 4 | ∀ Pf .C {x | Pf I (x) ∈ CI } | ∃f −1 {x | ∃y ∈ 4 : f I (y) = x} D ::= C CI ⊆ 4 | ¬C 4 \ CI | ∀ Pf .D {x | Pf I (x) ∈ DI } | ∃f −1 {x | ∃y ∈ 4 : f I (y) = x} Vk | C : Pf 1 , . . . , Pf k → Pf {x | ∀y ∈ CI : ( i=1 Pf Ii (x) = Pf Ii (y)) ⇒ Pf I (x) = Pf I (y)} Fig. 1. CFDI ∀nc Concepts. consists of a finite set of facts in the form of concept assertions A(a), and path function assertions Pf 1 (a) = Pf 2 (b). Any PFD occurring in T must also satisfy a regularity condition by adhering to one of the following two forms: C : Pf . Pf 1 , Pf 2 , . . . , Pf k → Pf or C : Pf . Pf 1 , Pf 2 , . . . , Pf k → Pf .g. (1) A PFD is a key if it adheres to the first of these forms. Semantics is defined 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 fixes the interpretation of primitive concepts A to be subsets of 4, features 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 defined in Figure 1. An interpretation I satisfies an inclusion dependency C v D if CI ⊆ DI , a concept assertion A(a) if aI ∈ AI , and a path function assertion Pf 1 (a) = Pf 2 (b) if Pf I1 (aI ) = Pf I2 (bI ). I satisfies a knowledge base K if it satisfies each inclusion dependency and assertion in K. 2 Condition (1) on occurrences of the PFD concept constructor 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 on CF D alone to avoid both intractability of reasoning about logical consequence [9] and undecidability of reasoning about KB consistency [15]. Conversely, and as usual, allowing conjunction (resp. disjunction) on the right-hand-sides (resp. left-hand-sides) of inclusion dependencies is a simple syn- tactic sugar. Finally, note that CF DI ∀nc does not assume the unique name assumption, but that its ability to express disjointness enables mutual inequality between all pairs of n individuals to be captured by introducing O(n) new atomic concepts, concepts assertions and inclusion dependencies in a straightforward way. Lemma 2 (CF DI ∀nc KB Normal Form) For every KB (T , A), there is an equi-satisfiable KB (T 0 , A0 ) in which subsumptions in T 0 adhere to the following forms: A v B, A v ∀f.B, ∀f.A v B, A v ∃f −1 , or A v A0 : Pf 1 , . . . , Pf k → Pf, where A and A0 are primitive concepts and B is a primitive concept or a negation of a primitive concept, and where ABox A0 contains only assertions of the form A(a), 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 us- ing auxiliary names for intermediate concept descriptions and individuals. For further details, see the definition of simple concepts in [13, 15]. Hereon, we identify ¬∀ Pf .A with ∀ Pf .¬A, and say that ∀ Pf .A and ∀ Pf .¬A are complementary for Pf ∈ F∗ . Also, when a particular KB (T , A) is considered, we assume the sets PC and F contain symbols that appear in T and A only. Unfortunately, use unqualified inverse features make reasoning about logi- cal consequence over an arbitrary CF DI ∀nc KB K intractable [19]. To recover PTIME reasoning for both logical implication and KB consistency, K will need to satisfy additional syntactic restrictions. Definition 3 (CF DI ∀− ∀− nc Knowledge Bases) A CF DI nc KB K = (T , A) is a ∀ CF DI nc KB in normal form that satisfies the following two conditions. 1. (inverse feature and value restriction interaction) If {A v ∃f −1 , ∀f.A0 v B} ⊆ T then (a) A v A0 ∈ T , (b) A0 v A ∈ T or (c) A v ¬A0 ∈ T . 2. (inverse feature and PFD interaction) Any PFD occurring in T must also satisfy a stronger regularity condition by adhering to one of the following two forms: C : Pf . Pf 1 , Pf 2 , . . . , Pf k → Pf or C : Pf .f, Pf 2 , . . . , Pf k → Pf .g. (2) Relaxing either of the conditions leads to EXPTIME and PSPACE completeness, respectively [19]. Note also, that the additional condition (2) imposed on PFDs applies only to non-key PFDs. Overall, however, such restrictions do not seem to impact the modeling utility of CF DI ∀nc in relation to keys and functional constraints. Indeed, we show that arbitrary functional dependencies in relational schema are easily captured. 3 CF DI ∀− nc TBoxes and Concept Satisfiability It is easy to see that every CF DI ∀− nc TBox T is consistent (by setting all primitive concepts to be interpreted as the empty set). To test for (primitive) concept satisfiability we use the following construction: Definition 4 (TBox Closure) Let T be a CF DI ∀− nc TBox in normal form. We define Clos(T ) to be the least set of subsumptions that contains T and is closed under the following five inference rules: 1. C1 v C1 ∈ Clos(T ); 2. If {C1 v C2 , C2 v C3 } ⊆ Clos(T ), then C1 v C3 ∈ Clos(T ); 3. If {C1 v D1 , C2 v D2 } ⊆ Clos(T ) and D1 and D2 are complementary, then C1 v ¬C2 ∈ Clos(T ); 4. If A v B ∈ Clos(T ), then ∀f.A v ∀f.B ∈ Clos(T ); and 5. If {A v ∃f −1 , ∀f.A0 v ∀f.B, A v A0 } ⊆ Clos(T ), then A v B ∈ Clos(T ), where A is a primitive concept, B is a primitive concept or its negation, and where C1 , C2 , D1 , and D2 are subconcepts of concepts in T or their negations. 2 Note that Clos(T ) is at most quadratic in |T |. It is also easy to verify that each inclusion added to Clos(T ) by the inferences (1-4) in Definition 4 is logically implied by T . Also, a variant of the closure rule (5) is not needed for the case A0 v A since we also have A0 v ∃f −1 , nor it is needed in the case A0 v ¬A since, in this case, the value restriction in the rule is satisfied vacuously. Given Clos(T ), an object o, and a primitive concept A, we define the following family of subsets of PC indexed by paths of features (and their inverses), starting from o, as follows: 1. So = {B | A v B ∈ Clos(T )}; 2. Sf (x) = {B | A v ∀f.B ∈ Clos(T ) and A ∈ Sx }, when f ∈ F and x not of the form “f − (y)”; and 3. Sf − (x) = {B | ∀f.A v B and A ∈ Sx }, when A0 v ∃f −1 ∈ Clos(T ), A0 ∈ Sx , and x not of the form “f (y)”. We say that Sx is defined if it conforms to one of the three above cases, and that it is consistent if, whenever {A, A0 } ⊆ Sx , A v ¬A0 6∈ Clos(T ). Theorem 5 (Primitive Concept Satisfiability) Let T be a CF DI ∀− nc TBox in normal form and A a primitive concept description. Then A is satisfiable with respect to T if and only if A v ¬A 6∈ Clos(T ). Proof (sketch): We build a model of T in which o ∈ AI for some o ∈ 4 as follows: – 4 = {x | Sx is defined}; – f I = {(x, f (x)) | Sf (x) is defined} ∪ {(f − (x), x) | Sf − (x) is defined}; and – AI = {x | Sx is defined, A ∈ Sx }. It is easy to see that, due to closure rules in Definition 4, all the defined sets Sx must be consistent. Otherwise, A (∈ S0 ) must be inconsistent, implying in turn that A v ¬A ∈ Clos(T ), a contradiction. Hence, I = (4, .I ) is a model of T (it satisfies all dependencies in Clos(T )) such that o ∈ AI . 2 Note that the model witnessing satisfiability of A does not contain any identical path agreements (beyond the trivial id = id ) and hence vacuously satisfies all PFDs in T . The above theorem can be used to check satisfiability of complex (non-PFD) concepts; e.g., satisfiability of ∀ Pf .B w.r.t. T can be tested by checking satisfi- ability of a new primitive concept A w.r.t. T ∪ {A v ∀ Pf .B}. It also provides a technique for checking satisfiability of finite conjunctions of primitive concepts with respect to T : Corollary 6 Let T be a CF DI ∀− nc TBox in normal form and A1 , . . . , Ak primi- tive concepts. Then A1 u . . . u Ak is satisfiable with respect to T if and only if A is satisfiable with respect to T ∪ {A v A1 , . . . , A v Ak }, for A a fresh primitive concept. 2 4 Knowledge Base Consistency and Logical Implication We start with the problem of determining if a given CF DI ∀−nc knowledge base is consistent. This is resolved in a straightforward way with the following no- tion of an interesting path function and the subsequent definition of an ABox completion procedure. Definition 7 Let T be a CF DI ∀− nc TBox. We say that a path function Pf is in- teresting in T if it is a common prefix of all Pf i in a PFD A v B : Pf 1 , . . . , Pf k → Pf ∈ T . 2 Definition 8 Let (T , A) be a CF DI ∀− nc knowledge base. We define an ABox completionT (A) to be the least ABox A0 such that A ⊆ A0 and A0 is closed under the rules in Figure 2. 2 Note that since A is in normal form, individuals can only be declared to be mem- bers of primitive concepts. Thus, a CF DI ∀− nc ABox alone cannot lead to incon- sistency. Only when combined with a TBox does it become possible that certain conjunctions of primitive concepts must interpret as empty in every model, thus leading to KB inconsistency. This observation combined with Corollary 6 yields the following theorem: Theorem 9 (CF DI ∀− nc KB consistency) Let K = (T , A) be a CF DI nc KB ∀− (in normal form). Then K is consistent if and only if {A | A(a) ∈ completionT (A)} is satisfiable with respect to Clos(T ) for all objects a in A. 2 It is easy to verify that constructing Clos(T ) and completionT (A) is polynomial in |K|, and that testing for consistency implicitly contains Horn-SAT due to the presence of PFDs. Thus, we have the following: Corollary 10 Consistency of CF DI ∀− nc knowledge bases is complete for PTIME. 2 ABox Equality Rules: 1. If {a = b, b = c} ⊆ A, then a = c ∈ A. 2. If {f (a) = b, b = c} ⊆ A, then f (a) = c ∈ A. 3. If {a = b, f (b) = c} ⊆ A, then f (a) = c ∈ A. 4. If {f (a) = b, f (a) = c} ⊆ A, then b = c ∈ A. 5. If {a = b, A(a)} ⊆ A, then A(b) ∈ A. ABox–TBox Interactions: 6. If A(a) ∈ A and A v B ∈ Clos(T ), then B(a) ∈ A. 7. If {A(a), f (a) = b} ⊆ A and A v ∀f.B ∈ Clos(T ), then B(b) ∈ A. 8. If {A(a), f (b) = a} ⊆ A and ∀f.A v B ∈ Clos(T ), then B(b) ∈ A. ABox–Inverse Interactions: 9. If Pf = f1 f2 · · · fk is interesting in T , A0 (a0 ) ∈ A, a0 is an object in the original ABox A, and {Ai−1 v ∃fi −1 , ∀fi .Ai−1 v Ai } ⊆ Clos(T ) for 0 < i ≤ k, then {Ai (ai ), fi (ai−1 ) = ai } ⊆ A. ABox–PFD Interactions: 10. If {A(a), B(b)} ⊆ A, {Pf 0i (a) = ci , Pf 0i (b) = ci } ⊆ A for 0 < i ≤ k, and A v B : Pf 1 , . . . , Pf k → Pf ∈ T such that Pf 0i is a prefix of Pf i , then (a) {Pf 0 (a) = c, Pf 0 (b) = c} ⊆ A for Pf 0 a prefix of Pf, (b) If {Pf(a) = c, Pf(b) = d} ⊆ A, then c = d ∈ A, or (c) If Pf is of the form Pf 00 .f and {Pf 00 (a) = c, Pf 00 (b) = d} ⊆ A, then f (c) = e and f (d) = e to A for a new individual e. Fig. 2. ABox Completion Rules. It is also straightforward to reduce logical implication for a CF DI ∀− nc TBox T to knowledge base consistency. Indeed, subsumptions between literals are directly present in Clos(T ). Logical implication involving more general concept descrip- tions, such as PFDs, is reduced to knowledge base (in)consistency by encoding a counterexample as an ABox. Theorem 11 Logical consequence for CF DI ∀− nc terminologies is complete for PTIME. 2 5 Applications We now introduce two major applications for CF DI ∀− nc : capture of relational (and object-relational) database schemas and its ability to fully simulate DL- LiteF core . We also show how role hierarchies can be partially accommodated by CF DI ∀− nc . 5.1 Relational Data Sources and BCNF There are a number of applications of CF DI ∀−nc in addressing issues that surface with relational data sources. To illustrate, we show how a relational schema (S, Σ) with relation symbols S and with functional dependencies and unary foreign keys Σ can be easily mapped to a CF DI ∀− nc terminology T(S,Σ) , and then exhibit a straightforward reduction of so-called Boyce-Codd normal form (BCNF) diagnosis to logical consequence over T(S,Σ) . First the mapping: each R(A1 : D1 , . . . , Ak : Dk ) in S (i.e., a relation of arity k) is reified by mapping to the following inclusion dependencies in T(S,Σ) : CR v CR : aR.A1 , . . . , aR.Ak → id and CR v ∀aR.Ai .Di , for each 0 < i ≤ k, where (a) CR is a primitive concept for which an interpretation will be the tuple objects that correspond to tuples in R, (b) aR.Ai are features that yield values of fields in such tuples, and (c) Di are primitive concepts standing for the domains of the features. In addition, for each pair of R, R0 ∈ S, add to T(S,Σ) CR v ¬CR0 . Each functional dependency R : Ai1 , . . . , Aik → Ai0 in Σ is then mapped to an inclusion dependency: CR v CR : aR.Ai1 , . . . , aR.Aik → aR.Ai0 , and each unary inclusion dependency R[A] ⊆ R0 [A0 ] in Σ to three inclusion dependencies, where A is a fresh primitive concept unique to R[A] ⊆ R0 [A0 ]: CR v ∀aR.A .A, A v ∃aR0 .A0 −1 , and ∀aR0 .A0 .A v CR0 . BCNF diagnosis then translates to logical consequence in CF DI ∀− nc in a straight- forward fashion: Theorem 12 (Diagnosing BCNF for Relational Data Sources) Each re- lation R in (S, Σ) is in BCNF iff there is no set of features {aR.Ai0 , . . . , aR.Aik } in T(S,Σ) such that T(S,Σ) |= CR v CR : aR.Ai1 , . . . , aR.Aik → aR.A0 but where T(S,Σ) 6|= CR v CR : aR.Ai1 , . . . , aR.Aik → id . 2 Note that this easily generalizes to the object-relational setting where the domain Di of an attribute may now refer directly to Ri -objects, and where a generaliza- tion of binary decompositions called pivoting is the means of repairing violations of BCNF [3, 4]. An application in query optimization over relational data sources relates to SQL distinct-keyword elimination, that is, detecting where operations in query plans to remove duplicates can be safely eliminated [8]. Such rewrites can be reduced to knowledge based consistency problems in CF DI ∀− nc by using an ABox to encode simple selection conditions in SQL queries [7]. 5.2 Encoding of DL-Lite Another application of CF DI ∀−nc in a different setting relates to the problem of evaluating basic graph patterns in SPARQL with a presumed entailment regime defined by DL-LiteF core , a DL dialect that is related to the W3C OWL 2 QL profile. Such tasks reduce fundamentally to instance checking problems which reduce, in turn, to knowledge base consistency problems in the standard way. Our reduction is based on mapping a given DL-LiteF core knowledge base K to a CF DI ∀− nc knowledge base MK as follows: for each role P in K, we reify P by introducing a new primitive concept CP and by adding the following key PFD to MK : CP v CP : domP, ranP → id . The following rules define the mapping of each inclusion dependency in K (in normal form [2]) and each ABox assertion in K to corresponding dependencies and assertions in MK : A1 v A2 7→ {A1 v A2 }, A1 v ¬A2 7→ {A1 v ¬A2 }, A1 v ∃P 7 → {A1 v ∃domP −1 , ∀domP.A1 v CP }, A1 v ∃P − 7 → {A1 v ∃ranP −1 , ∀ranP.A1 v CP }, ∃P v A1 7 → {CP v ∀domP.A1 }, ∃P − v A1 7→ {CP v ∀ranP.A1 }, (func P ) 7 → {CP v CP : domP → id }, (func P − ) 7→ {CP v CP : ranP → id }, a:A 7→ {a : A} and P (a, b) 7→ {cP P P a,b : CP , domP (ca,b ) = a, ranP (ca,b ) = b}. This mapping yields the following as a straightforward consequence: Theorem 13 (DL-LiteF F core Reasoning) Let K be a DL-Litecore KB. Then knowledge base consistency, logical implication, and instance checking with re- spect to K can be reduced to reasoning about KB consistency with respect to MK . 2 On Role Hierarchies The reduction above is only defined for DL-LiteF core . Indeed, it is well known that an (unrestricted) combination functionality with role hierarchies, e.g., DL-LiteHF core , leads to intractability [2]. On the other hand, the ability to reify roles seems to allow to capture a limited version of role hierarchies 1 . Example 14 Consider roles R and S and the corresponding primitive concepts CR and CS , respectively. In contrast to the development in the previous section, we assume that the domains and ranges of the reified roles are captured by the feature dom and ran (common to both the reified roles). Then we can capture subsumption and disjointness of these roles as follows: RvS 7→ CR v CS , CR v CS : dom, ran → id , RuS v⊥ 7→ CR v ¬CS , CR v CS : dom, ran → id , assuming that the reified role R (and analogously S) also satisfies the key con- straint CR v CR : dom, ran → id . Role typing is achieved in a way analogous to DL-LiteFcore . Note, however, that such a reduction does not lend itself to capturing role hierar- chies between roles and inverses of roles: this is due to fixing the (names of the) features dom and ran. Moreover, the condition introduced in Definition 3(1), that governs the interactions between inverse features and value restrictions, in- troduces additional interactions that interfere with (simulating) role hierarchies, in particular in cases when mandatory participation constraints are present. Example 15 Consider roles R1 and R2 and the corresponding primitive con- cepts CR1 and CR2 , respectively, and associated constraints that declare typing for the roles, CR1 v ∀dom.A1 , CR1 v ∀ran.B1 , CR1 v CR1 : dom, ran → id CR2 v ∀dom.A2 , CR2 v ∀ran.B2 , CR2 v CR2 : dom, ran → id originating, e.g., from an ER diagram postulating that entity sets Ai and Bi participate in a relationship Ri (for i = 1, 2). Now consider a situation where the participation of Ai in Ri is mandatory (expressed, e.g., as Ai v ∃Ri in DL-Lite). This leads to the following constraints: A1 v ∃dom−1 , ∀dom.A1 v CR1 and A2 v ∃dom−1 , ∀dom.A2 v CR2 . Condition (1) in Definition 3 then requires that one of A1 v A2 , A2 v A1 , or A1 v ¬A2 are present in the TBox. The first (and second) conditions imply that CR1 v CR2 (CR2 v CR1 , respectively). The third condition states that the domains of (the reified versions of) R1 and R2 are disjoint, hence the roles themselves must also be disjoint. Hence, in the presence of CR1 v CR2 : dom, ran → id , the concepts CR1 and CR2 must also be disjoint. In this setting role hierarchies can be mapped to CF DI ∀nc are as follows: 1 (HF ) Unlike DL-Litecore , that restricts the applicability of functional constraints in the presence of role hierarchies, we study what forms role hierarchies can be captured while retaining the ability to specify arbitrary keys and functional dependencies. 1. only primitive roles are supported, 2. for each pair of roles participating in the same role hierarchy, either one of the roles is a super-role of the other, or the roles’ domains/ranges are disjoint. The first restriction originates in the way (binary) roles are reified—by assigning canonically-named features. This prevents modeling constraints such as R v R− (which would seem to require simple equational constraints for feature renam- ing). The second condition is essential to maintaining tractability of reasoning [19]. Note, however, that no such restriction is needed for roles that do not par- ticipate in the same role hierarchy; this is achieved by appropriate choice of names for the features dom and ran similarly to the development in Section 5.2. One can, however, model object participation in sibling roles participating in a role hierarchy using delegation [1], leading to a more complex translation of role assertions to CF DI ∀−nc : Example 16 Consider roles R1 , R2 , and S involved in a role hierarchy R1 v S and R2 v S. To assert that A objects must participate in both the roles Ri , for i ∈ {1, 2}, we first explicitly establish the domains of the roles (the same applies for ranges of roles), DRi v ∃dom−1 , ∀dom.DRi v CRi , and CRi v ∀DRi .. Then, instead of asserting A v DRi (which immediately leads to inconsistency due to our PTIME restrictions on roles) we assert A v ∀fRi .DRi where the fRi images of an A object are the delegates used to participate in the roles Ri . Last, the CF DI ∀nc -based approach to role hierarchies can easily be extended to handling hierarchies of non-homogeneous relationships (again, via reification and appropriate naming of features) that originate, e.g., from relating the aggregation constructs via inheritance in the EER model [10, 11]. 6 Related Work and Future Directions Toman and Weddell have also proposed the DLF family of feature-based Boolean- complete DL dialects obtained by allowing arbitrary use of negation in concepts [12]. In particular, they have shown that allowing inverse features in such di- alects makes reasoning about logical consequence undecidable [14]. They have also shown that allowing negation on left-hand-sides of inclusion dependencies in CF DI ∀nc leads to intractability, but that PTIME algorithms exist for reason- ing about logical consequence and knowledge base consistency if a number of additional conditions are satisfied [20]. A variety of path based identification constraints have been proposed [5] together with analogous applications in relational schema diagnosis [6], although CF DI ∀− nc seems to provide a more natural and transparent approach to this problem. References 1. M. Aksit, J.W. Dijkstra, and A. Tripathi. Atomic delegation: object-oriented trans- actions. Software, IEEE, 8(2):84–92, March 1991. 2. Alessandro Artale, Diego Calvanese, Roman Kontchakov, and Michael Za- kharyaschev. The DL-Lite family and relations. J. AI Research, 36:1–69, 2009. 3. Joachim Biskup, Ralf Menzel, Torsten Polle, and Yehoshua Sagiv. Decomposition of Relationships through Pivoting. In Conceptual Modeling, pages 28–41, 1996. 4. Joachim Biskup and Torsten Polle. Decomposition of Database Classes under Path Functional Dependencies and Onto Constraints. In Foundations of Information and Knowledge Systems, pages 31–49, 2000. 5. Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. Path-based identification constraints in description logics. In Gerhard Brewka and Jérôme Lang, editors, KR, pages 231–241, 2008. 6. Diego Calvanese, Wolfgang Fischl, Reinhard Pichler, Emanuel Sallinger, and Man- tas Simkus. Capturing Relational Schemas and Functional Dependencies in RDFS. In to appear in Proc. Nat. Conf. on Artificial Intelligence (AAAI), 2014. 7. Vitaliy Khizder, David Toman, and Grant E. Weddell. Adding ABoxes to a De- scription Logic with Uniqueness Constraints via Path Agreements. In Proc. Inter- national Workshop on Description Logics DL2007, pages 339–346, 2007. 8. Vitaliy L. Khizder, David Toman, and Grant Weddell. Reasoning about Duplicate Elimination with Description Logic. In Rules and Objects in Databases (DOOD, part of CL’00), pages 1017–1032, 2000. 9. Vitaliy L. Khizder, David Toman, and Grant Weddell. On Decidability and Complexity of Description Logics with Uniqueness Constraints. In Int. Conf. on Database Theory ICDT’01, pages 54–67, 2001. 10. Il-Yeol Song and Peter P. Chen. Entity relationship model. In Ling Liu and M. Tamer Özsu, editors, Encyclopedia of Database Systems, volume 1, pages 1003– 1009. Springer, 2009. 11. Bernhard Thalheim. Extended entity relationship model. In Ling Liu and M. Tamer Özsu, editors, Encyclopedia of Database Systems, volume 1, pages 1083– 1091. Springer, 2009. 12. David Toman and Grant Weddell. On Attributes, Roles, and Dependencies in De- scription Logics and the Ackermann Case of the Decision Problem. In Description Logics 2001, pages 76–85. CEUR-WS vol.49, 2001. 13. David Toman and Grant Weddell. On Keys and Functional Dependencies as First- Class Citizens in Description Logics. In Proc. of Int. Joint Conf. on Automated Reasoning (IJCAR), pages 647–661, 2006. 14. David Toman and Grant E. Weddell. On the interaction between inverse features and path-functional dependencies in description logics. In Proc. Int. Joint Conf. on Artificial Intelligence (IJCAI), pages 603–608, 2005. 15. David Toman and Grant E. Weddell. On keys and functional dependencies as first-class citizens in description logics. J. Aut. Reasoning, 40(2-3):117–132, 2008. 16. David Toman and Grant E. Weddell. Applications and extensions of PTIME description logics with functional constraints. In Proc. Int. Joint Conf. on Artificial Intelligence (IJCAI), pages 948–954, 2009. 17. David Toman and Grant E. Weddell. Conjunctive Query Answering in CFDnc : A PTIME Description Logic with Functional Constraints and Disjointness. In Australasian Conference on Artificial Intelligence, pages 350–361, 2013. 18. David Toman and Grant E. Weddell. Answering Queries over CFD∀nc Knowl- edge Bases. Technical Report CS-2014-14, Cheriton School of Computer Science, University of Waterloo, 2014. 19. David Toman and Grant E. Weddell. On adding inverse features to the description logic CFD∀nc . In PRICAI 2014: Trends in Artificial Intelligence - 13th Pacific Rim International Conference on Artificial Intelligence, Gold Coast, QLD, Australia, December 1-5, 2014., pages 587–599, 2014. 20. David Toman and Grant E. Weddell. Pushing the CFDnc Envelope. In Interna- tional Workshop on Description Logics DL2014, 2014.