Database Reference
In-Depth Information
I
F
D
{ ( ),
〈
π
x
π
(
y
)
〉 ∈
∆
×
∆
|
T x y
( ,
)
≥ ∈
n
q
}
.
V G
(
p
is divided into
Vr G
(
p
and
Vn G
(
p
, i.e.,
V G
and
Vr G
∅
,
(
) =
Vr G
(
)
∪
Vn G
(
)
(
)
∩
Vn G
(
) =
π
π
π
π
π
where
Vr G
(
) = {[
v
/ is a root node in }.
v
] |
v
p
Definition 14.
(Maximal
q
-distance) For any
x y
,
Î
Terms q
( )
, if π
( ),
x
π
(
y
)
∈
Vn G
(
)
, then we use
π
p
( ,
d
x y
) to denote the length of the shortest path between p(
x
and p(
y
in
G
p. If p(
x
and p(
y
π
( ,
are in two different connected components respectively, then
d
x y
) = − . We define maximal
q
-distance
d
π
=
{
d
π
( ,
x y
)}
.
max
x y Terms q
,
∈
(
)
q
Example 7.
Consider a mapping p such that p
( ) =
x
p
,
p
(
y
) =
p
,
p
( ) =
z
p
, and p(
y
) =
v
. The
6
7
8
c
5
mapping graph
G
p
contains the nodes
p
6
,
p
7
and
p
8
, where
Vr G
(
) =
∅,
Vn G
(
) = {
p p p v
,
,
, }
,
π
p
6
7
8
5
p
(
p
(
p
(
and
E G
(
) = {
〈
p p
,
〉 〈
,
p p
,
〉 〈
,
p v
,
〉 . Moreover,
d
}
p p
,
) = 1
,
d
p p
,
) = 1
,
d
p p
,
) = 2
,
π
6
7
7
8
7
5
6
7
7
8
6
8
p
(
p
(
, thus
d
q
p
= 2 .
d
p v
,
) = 2
, and
d v p
,
) = 2
6
5
5
8
We use
n
q
to denote the number of fuzzy role atoms in a fuzzy query
q
. We only consider fuzzy
role atoms
R x y
π
≤ . We show provided the
k
in the
k
-blocking condition is greater than or equal to
n
q
, it suffices to find a mapping from
q
to .
p
( ,
( ,
) ³ with
R
a simple role, so
d
n
x y
) = 1 and
d
n
q
q
Lemma 6.
Let
F
Î
ccf
k
(
)
with
k
n
³ , and I
F
is the canonical model of . If I
q
, then
K
F
q
F
.
D
such that p( )
a a
I
F
Proof.
Since I
F
q
, then there exists a mapping π :
Terms q
( )
→
∆
∪
∆
F
I
F
( ( ))
I
F
( ( ),
π
′
≥
for each
a
Î ( ) ,
C
Ind q
π
t
≥ for each fuzzy concept atom
C t
n
( ) ≥ ∈ ,
R
n
q
π
t
( ))
t
n
I
F
( ( ),
π
′
≥ ) for each fuzzy role atom
R t t
′
≥ (resp.
T t t
′
≥ ) Î
q
.
(resp.
T
π
t
( ))
t
n
( ,
n
( ,
n
Terms q Node
→ from the mapping p. First, we consider
G
, a
subgraph of
G
p
, which is obtained by eliminating the vertices of the form [
We construct the mapping µ :
( )
(
)
a
/ with
a
a individual
name and the arcs that enter or leave these vertices.
G
consists of a set of connected components- written
as
G
]
1
,
,
. We define
Blocked Gi(
i
G
m
(
) as the set of all the vertices
p
such that
Tails p
(
)
¹
Tails p
'(
)
.
Then, for every ancestor
p
of
p
in
G
i
,
Tails p
(
) =
Tails p
'(
) . We use
AfterBlocked Gi
i
(
) to denote the
set of the descendants of the vertices in
Blocked Gi(
( ).
Recalling the definition of
Nodes
( , since is
k
-blocked, if there are two node pairs
v
/
¢
and
w
/
¢
in a path (also a vertex)
p
with
v
≠
′
and
w
≠
′
, then the distance between these two node
pairs must greater than
k
. A path
p
always begins with
v
/ , if it contains a node pair
w
/
¢
with
w
≠
′
, then the distance between
v
/ and
w
/
¢
must greater than
k
.
We prove two properties of
G
i
as follows.
