We consider the description logic CF DI8nc , a feature-based dialect that allows capturing value restrictions, a variety of identi cation constraints, and unquali ed feature inverses. We introduce PTIME algorithms for various reasoning tasks in this logic, such as knowledge base consistency and logical implication and discuss the necessity of restrictions over CF DI8nc to maintain tractability. We then show how CF DI8nc 's modeling capabilities make it suitable for capturing relational and object-relational data sources (including of n-ary relations) in a natural way. In addition, we show that CF DInc can simulate reasoning in 8 DL-LitecFore. We also discuss an approach to capturing a limited variant of role hierarchies within CF DI8nc .
We have been developing the CF D family of feature-based description logic (DL) dialects that are designed primarily to support e cient PTIME reasoning services about object relational data sources. The dialects are notable for their ability to support terminological cycles with universal restrictions over functional 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 rst member of this family, initially proposed in
[
The dialect CF Dnc was subsequently introduced in which negation on
righthand-sides of inclusion dependencies replaced the ability to have conjunction on
left-hand-sides [
An earlier version of this paper has appeared as [19]. 8 8
In this paper, we consider the dialect CF DInc which extends CF Dnc with an ability to have unquali ed inverse features in inclusion dependencies, and 8 8 also introduce a less general dialect CF DInc in which a given CF DInc 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 8 concerning reasoning in CF DInc , in particular PTIME algorithms for both 8 logical consequence and for knowledge base consistency for CF DInc knowledge bases.
For the remainder the paper, we give an overview of a number of applications of CF DI8nc , starting with how it can be used to address issues relating to relational data sources over database schema that can include arbitrary combinations of functional dependencies and unary inclusion dependencies. We also show how the task of evaluating instance queries over RDF data sources based 8 on a DL-LitecFore entailment regime can be reduced to reasoning about CF DInc knowledge base consistency. Note that the DL dialect DL-LitecFore is of particular relevance to the W3C OWL 2 QL pro le. A discussion of related work and future directions then follow in Section 6. 2
The Description Logics CF DI nc and CF DI nc 8 8 All members of the CF D family of DLs are fragments of FOL with underlying 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 rei cation of n-ary predicates. Thus, e.g., a role R can be rei ed as a primitive concept RC and two features domR and ranR in CF DInc or CF DI8nc , and an inclu8 sion dependency A v 8R:B can then be captured as an inclusion dependency 8domR:A v 8ranR:B.
De nition 1 (CF DInc Knowledge Bases) Let F, PC and IN be disjoint sets 8 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 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).
8 Metadata and data in a CF DInc 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 C ::= A j 8 Pf :C j 9f 1
Semantics: \( )I " AI 4 fx j PfI (x) 2 CI g fx j 9y 2 4 : f I (y) = xg consists of a nite set of facts in the form of concept assertions A(a), and path function assertions Pf1(a) = Pf2(b). Any PFD occurring in T must also satisfy a regularity condition by adhering to one of the following two forms: C : Pf : Pf1; Pf2; : : : ; Pfk ! Pf or
C : Pf : Pf1; Pf2; : : : ; Pfk ! Pf :g: (1)
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, 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 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 , 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. 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 [
8
Finally, note that CF DInc 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.
8 Lemma 2 (CF DInc KB Normal Form) For every KB (T ; A), there is an equi-satis able KB (T 0; A0) in which subsumptions in T 0 adhere to the following
A v B; A v 8f:B; 8f:A v B; A v 9f 1; or A v A0 : Pf1; : : : ; Pfk ! 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
using auxiliary names for intermediate concept descriptions and individuals. For
further details, see the de nition of simple concepts in [
Hereon, we identify :8 Pf :A with 8 Pf ::A, and say that 8 Pf :A and 8 Pf ::A are complementary for Pf 2 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 unquali ed inverse features make reasoning about logi8 cal consequence over an arbitrary CF DInc KB K intractable [19]. To recover PTIME reasoning for both logical implication and KB consistency, K will need to satisfy additional syntactic restrictions.
8 8 De nition 3 (CF DInc Knowledge Bases) A CF DInc KB K = (T ; A) is a 8 CF DInc KB in normal form that satis es the following two conditions. 1. (inverse feature and value restriction interaction) If fA v 9f 1; 8f:A0 v
Bg T then (a) A v A0 2 T , (b) A0 v A 2 T or (c) A v :A0 2 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 : Pf1; Pf2; : : : ; Pfk ! Pf or C : Pf :f; Pf2; : : : ; Pfk ! 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 8 to impact the modeling utility of CF DInc in relation to keys and functional constraints. Indeed, we show that arbitrary functional dependencies in relational schema are easily captured. 3
CF DI 8nc TBoxes and Concept Satis ability
8 It is easy to see that every CF DInc TBox T is consistent (by setting all primitive concepts to be interpreted as the empty set). To test for (primitive) concept satis ability we use the following construction: 8 De nition 4 (TBox Closure) Let T be a CF DInc TBox in normal form. We de ne Clos(T ) to be the least set of subsumptions that contains T and is closed under the following ve inference rules: 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 jT j. It is also easy to verify that each inclusion added to Clos(T ) by the inferences (1-4) in De nition 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 9f 1, nor it is needed in the case A0 v :A since, in this case, the value restriction in the rule is satis ed vacuously.
Given Clos(T ), an object o, and a primitive concept A, we de ne the following family of subsets of PC indexed by paths of features (and their inverses), starting from o, as follows: 1. So = fB j A v B 2 Clos(T )g; 2. Sf(x) = fB j A v 8f:B 2 Clos(T ) and A 2 Sxg, when f 2 F and x not of the form \f (y)"; and 3. Sf (x) = fB j 8f:A v B and A 2 Sxg, when A0 v 9f 1 2 Clos(T ), A0 2 Sx, and x not of the form \f (y)".
We say that Sx is de ned if it conforms to one of the three above cases, and that it is consistent if, whenever fA; A0g Sx, A v :A0 62 Clos(T ). 8 Theorem 5 (Primitive Concept Satis ability) Let T be a CF DInc TBox in normal form and A a primitive concept description. Then A is satis able with respect to T if and only if A v :A 62 Clos(T ).
We build a model of T in which o 2 AI for some o 2 4 as Proof (sketch): follows: { 4 = fx j Sx is de nedg; { f I = f(x; f (x)) j Sf(x) is de nedg [ f(f (x); x) j Sf (x) is de nedg; and { AI = fx j Sx is de ned; A 2 Sxg.
It is easy to see that, due to closure rules in De nition 4, all the de ned sets Sx must be consistent. Otherwise, A (2 S0) must be inconsistent, implying in turn that A v :A 2 Clos(T ), a contradiction. Hence, I = (4; :I ) is a model of T (it satis es all dependencies in Clos(T )) such that o 2 AI . 2 Note that the model witnessing satis ability of A does not contain any identical path agreements (beyond the trivial id = id ) and hence vacuously satis es all PFDs in T .
The above theorem can be used to check satis ability of complex (non-PFD) concepts; e.g., satis ability of 8 Pf :B w.r.t. T can be tested by checking satis ability of a new primitive concept A w.r.t. T [ fA v 8 Pf :Bg. It also provides a technique for checking satis ability of nite conjunctions of primitive concepts with respect to T : Corollary 6 Let T be a CF DI8nc TBox in normal form and A1; : : : ; Ak primitive concepts. Then A1 u : : : u Ak is satis able with respect to T if and only if A is satis able with respect to T [ fA v A1; : : : ; A v Akg, 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 DI8nc knowledge base is consistent. This is resolved in a straightforward way with the following notion of an interesting path function and the subsequent de nition of an ABox completion procedure.
De nition 7 Let T be a CF DI8nc TBox. We say that a path function Pf is interesting in T if it is a common pre x of all Pfi in a PFD A v B : Pf1; : : : ; Pfk ! Pf 2 T . 2 De nition 8 Let (T ; A) be a CF DI8nc knowledge base. We de ne 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 mem8 bers of primitive concepts. Thus, a CF DInc ABox alone cannot lead to inconsistency. 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 DI8nc KB consistency) Let K = (T ; A) be a CF DI8nc KB (in normal form). Then K is consistent if and only if fA j A(a) 2 completionT (A)g is satis able 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 jKj, 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 DI8nc knowledge bases is complete for PTIME. 2 ABox Equality Rules: 1. If fa = b; b = cg A, then a = c 2 A. 2. If ff (a) = b; b = cg A, then f (a) = c 2 A. 3. If fa = b; f (b) = cg A, then f (a) = c 2 A. 4. If ff (a) = b; f (a) = cg A, then b = c 2 A.
5. If fa = b; A(a)g A, then A(b) 2 A.
ABox{TBox Interactions: 6. If A(a) 2 A and A v B 2 Clos(T ), then B(a) 2 A. 7. If fA(a); f (a) = bg A and A v 8f:B 2 Clos(T ), then B(b) 2 A. 8. If fA(a); f (b) = ag A and 8f:A v B 2 Clos(T ), then B(b) 2 A. ABox{Inverse Interactions: 9. If Pf = f1f2 fk is interesting in T , A0(a0) 2 A, a0 is an object in the original ABox A, and fAi 1 v 9fi 1; 8fi:Ai 1 v Aig Clos(T ) for 0 < i k, then fAi(ai); fi(ai 1) = aig A.
ABox{PFD Interactions: 10. If fA(a); B(b)g A, fPf0i(a) = ci; Pf0i(b) = cig A for 0 < i k, and A v B : Pf1; : : : ; Pfk ! Pf 2 T such that Pf0i is a pre x of Pfi, then (a) fPf0(a) = c; Pf0(b) = cg A for Pf0 a pre x of Pf, (b) If fPf(a) = c; Pf(b) = dg A, then c = d 2 A, or (c) If Pf is of the form Pf00 :f and fPf00(a) = c; Pf00(b) = dg A, then f (c) = e and f (d) = e to A for a new individual e.
Fig. 2. ABox Completion Rules. 8 It is also straightforward to reduce logical implication for a CF DInc TBox T to knowledge base consistency. Indeed, subsumptions between literals are directly present in Clos(T ). Logical implication involving more general concept descriptions, such as PFDs, is reduced to knowledge base (in)consistency by encoding a counterexample as an ABox. We now introduce two major applications for CF DI8nc : capture of relational (and object-relational) database schemas and its ability to fully simulate DLLitecFore. We also show how role hierarchies can be partially accommodated by CF DI8nc . There are a number of applications of CF DI8nc 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 DI8nc 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 rei ed by mapping to the following inclusion dependencies in T(S; ): CR v CR : aR:A1 ; : : : ; aR:Ak ! id and
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 elds in such tuples, and (c) Di are primitive concepts standing for the domains of the features. In addition, for each pair of R; R0 2 S, add to T(S; )
CR v :CR0 :
inclusion dependency: is then mapped to an
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 8aR:A:A;
A v 9aR0:A0 1; and 8aR0:A0 :A v CR0 : BCNF diagnosis then translates to logical consequence in CF DI8nc in a straightforward fashion: Theorem 12 (Diagnosing BCNF for Relational Data Sources) Each relation R in (S; ) is in BCNF i there is no set of features faR:Ai0 ; : : : ; aR:Aik g in T(S; ) such that
T(S; ) j= CR v CR : aR:Ai1 ; : : : ; aR:Aik ! aR:A0 but where
T(S; ) 6j= 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
generalization of binary decompositions called pivoting is the means of repairing violations
of BCNF [
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 [
Our reduction is based on mapping a given DL-LitecFore knowledge base K to 8 a CF DInc 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 de ne the mapping of each inclusion dependency in K (in
normal form [
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 rei ed roles are captured by the feature dom and ran (common to both the rei ed roles). Then we can capture subsumption and disjointness of these roles as follows:
R v S R u S v ? 7! 7! assuming that the rei ed role R (and analogously S) also satis es the key constraint CR v CR : dom; ran ! id . Role typing is achieved in a way analogous to DL-LitecFore.
CR v CS ; CR v CS : dom; ran ! id ;
CR v :CS ; CR v CS : dom; ran ! id ; Note, however, that such a reduction does not lend itself to capturing role hierarchies between roles and inverses of roles: this is due to xing the (names of the) features dom and ran. Moreover, the condition introduced in De nition 3(1), that governs the interactions between inverse features and value restrictions, introduces 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 concepts CR1 and CR2 , respectively, and associated constraints that declare typing for the roles,
CR1 v 8dom:A1; CR1 v 8ran:B1; CR1 v CR1 : dom; ran ! id
CR2 v 8dom:A2; CR2 v 8ran: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 9Ri in DL-Lite). This leads to the following constraints:
A1 v 9dom 1; 8dom:A1 v CR1 and A2 v 9dom 1; 8dom:A2 v CR2 :
A1 v A2; A2 v A1; or A1 v :A2 are present in the TBox. The rst (and second) conditions imply that CR1 v CR2 (CR2 v CR1 , respectively). The third condition states that the domains of (the rei ed 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 DI8nc are as follows: 1 Unlike DL-Lite(cHorFe), 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 rst restriction originates in the way (binary) roles are rei ed|by assigning canonically-named features. This prevents modeling constraints such as R v R (which would seem to require simple equational constraints for feature renaming). The second condition is essential to maintaining tractability of reasoning [19]. Note, however, that no such restriction is needed for roles that do not participate 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 [
DRi v 9dom 1; 8dom:DRi v CRi ; and CRi v 8DRi::
Then, instead of asserting A v DRi (which immediately leads to inconsistency
due to our PTIME restrictions on roles) we assert A v 8fRi :DRi where the fRi
images of an A object are the delegates used to participate in the roles Ri.
Last, the CF DI8nc-based approach to role hierarchies can easily be extended to
handling hierarchies of non-homogeneous relationships (again, via rei cation and
appropriate naming of features) that originate, e.g., from relating the aggregation
constructs via inheritance in the EER model [
Toman and Weddell have also proposed the DLF family of feature-based
Booleancomplete DL dialects obtained by allowing arbitrary use of negation in concepts
[
A variety of path based identi cation constraints have been proposed [