Database Reference
In-Depth Information
Starting with an
f
-SHIF (
D
KB
K
= 〈
T R A
, , , the completion forest
F
K
is initialized such that it
〉
contains (
i
) a root node
o
, with
L
( ) = {
o
〈 ≥ 〉
C
,
,
n C o
|
( )
≥ ∈
n
A
}
, for each abstract individual name
o
occurring in , (
ii
) a leaf node
v
, with
L
( ) = { ,
v
〈 ≥ 〉
d
,
n
|
d v
( )
≥ ∈
n
A
}
, for each concrete individual
′
〉
′
〉
′
≥ 〉 ∈
name
v
occurring in , (
iii
) an abstract edge 〈
o o
, with
L
(
〈
o o
,
) = {
〈 ≥ 〉 〈
R
,
,
n
|
R o o
( ,
)
n
A
}
, for
′
〉
′
≥ ∈ is non-empty, and (
iv
) a
each pair 〈
o o
, of individual names for which the set {
R R o o
|
( ,
)
n
}
concrete edge 〈
o v
, with
L
〉
(
〈
o v
,
〉
) = { ,
〈 ≥ 〉 〈
T
,
n
|
T o v
( ,
)
≥ 〉 ∈
n
A
}
. We initialize the relation ¹ as
′
〉 ≠
′
∈
{ ,
〈
o o o o
, and the relation » to be empty.
|
}
Example 3.
In our running example,
F
K
contains only one node
o
labelled with
( ) = {
o
〈 ≥
,
, 0.8 }
〉
.
Now we can formally define a new blocking condition, called
k -blocking
, for fuzzy query entailment
depending on a depth parameter
k
> 0 .
Definition 4.
(
k
-tree equivalence) The
k
-tree of a node
v
in
T
, denoted as
T
v
k
, is the subtree of
T
rooted at
v
with all the descendants of
v
within distance
k
. We use
Nodes T
v
( ) to denote the set of
nodes in
T
v
k
. Two nodes
v
and
w
in
T
are said to be
k
-tree equivalent in
T
, if
T
v
k
and
T
w
k
are iso-
morphic, i.e., there exists a bijection y:
Nodes T
(
k
)
®
Nodes T
(
k
)
such that (i) y( ) =
v
w
, (iii) for every
v
w
node
o Nodes T
v
k
o
y , (iii) for every edge connecting two nodes
o
and
o
in
T
v
k
,
Î
(
) ,
( ) = (
o
( ))
′
〉
′
〉
(
〈
o o
,
) = (
〈
ψ
( ),
o
ψ
(
o
) )
.
Definition 5.
(
k
-witness) A node
w
is a
k
-witness of a node
v
, if
v
and
w
are
k
-tree equivalent in
T
,
w
is an ancestor of
v
in
T
and
v
is not in
T
w
k
. Furthermore,
T
w
k
tree-blocks
T
v
k
and each node
o
in
T
w
k
tree-blocks node ψ
−1
(
o
in
T
v
k
.
Definition 6.
(
k
-blocking) A node
o
is
k
-blocked in a completion forest iff it is not a root node
and it is either directly or indirectly
k
-blocked. Node
o
is directly
k
-blocked iff none of its ancestors
is
k
-blocked, and
o
is a leaf of a tree-blocked
k
-tree. Node
o
is indirectly
k
-blocked iff one of its
ancestors is
k
-blocked or it is a successor of a node
o
and (
〈
′
o o
,
〉 ∅
) =
.
An initial completion forest is expanded according to a set of
expansion rules
that reflect the con-
structors in
f
-SHIF (
D
. The expansion rules, which syntactically decompose the concepts in node
labels, either infer new constraints for a given node, or extend the tree according to these constraints
(see Table 1). Termination is guaranteed by
k
-blocking. We denote by
the set of all completion
forests obtained this way.
For a node
o
, (
o
is said to contain a
clash
, if it contains one of the followings: (
i
) a pair of triples
〈 ≥ 〉
C
, , and 〈¬ ≥ 〉
n
C
, ,
m
with
n
+ > 1, (
ii
) one of the triples: 〈⊥ ≥ 〉
, ,
n
with
n
> 0, 〈 ≥ 〉
C
, , with
n
, with
n
+
′
> 1 and
o
n
> 1, (
iii
) some triple 〈≤
1 ,
S
≥ 〉
,
n
, and
o
has two
R
≥ ′
-neighbors
o o
1
/» .
o
,
1
2
Definition 7.
(
k
-complete and clash-free completion forest) A completion forest is called
k
-complete
and clash-free if under
k
-blocking no rule can be applied to it, and none of its nodes and edges contains
a clash. We denote by ccf
k
(
the set of
k
-complete and class-free completion forests in
.
)