=Paper=
{{Paper
|id=Vol-1350/paper-36
|storemode=property
|title=On
the Utility of CFDI
|pdfUrl=https://ceur-ws.org/Vol-1350/paper-36.pdf
|volume=Vol-1350
|dblpUrl=https://dblp.org/rec/conf/dlog/TomanW15
}}
==On
the Utility of CFDI==
https://ceur-ws.org/Vol-1350/paper-36.pdf
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.