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  .
)
Search WWH ::




Custom Search