Database Reference
In-Depth Information
Tail
'( ( )p is tree-blocked by ψ
y
(
Tail
'( (
π
y
. If
Tail
)))
'( ( )p is a
R
n
y
³,
-successor of
Tail
( ( )p ,
x
then µ
(
y
) = (
ψ
Tail
'( (
π
y
is a
R
n
)))
³,
-successor of µ
( ) = (
x
ψ
Tail
'( ( )))
π
x
.
(c) If π( )
x
∉
AfterBlocked G
i
(
)
and π(
y
)
∈
AfterBlocked G
i
(
)
, then
Tail
( ( ))
π
x
≠
Tail
'( ( ))
π
x
and
Tail
( ( )) = (
π
x
ψ
Tail
'( ( )))
π
x
. If
Tail
'( ( )p is a
R
n
y
³,
-successor of
Tail
( ( )p , then
x
µ
(
y
) =
Tail
'( (
π
y
is a
R
n
))
³,
-successor of µ
( ) = (
x
ψ
Tail
'( ( )))
π
x
.
The proof for case (2) is in a similar way with case (1).
Since m has the Property 1-3,
q
F
holds.
Example 8.
Since
Vr G
(
) =
∅ and
G
p
is connected, the only connected component of
G
p
is itself. We
π
have
Blocked G
(
) = { }
6
p
, and
AfterBlocked G
(
) = {
p p v
,
, }
. We obtain the mapping m
1
from p
p
p
7
8
5
by setting µ
( ) = (
x
ψ
Tail p
'(
)) =
o
, m
1
(
y
) =
Tail p
'(
) =
o
, m
1
( ) =
z
Tail p
'(
) =
o
, and m
1
(
y
) =
v
.
1
6
3
7
4
8
5
c
5
By Definition 9,
q
1
F
.
1
Theorem 2.
Let
k
n
³ . Then
K
q
iff for each Î ccf
k
(
, it holds that
q
F
.
)
,
F
q
. Then, by Theorem1,
K
q
. For the converse side, by Theorem 1,
F
q
for each Î ccf
k
(
Proof.
The if direction is easy. By Lemma 3, for each Î ccf
k
(
)
. By Lemma 6,
q
F
.
We can, from the only if direction of Theorem 2, establish our key result, which reduce query entail-
ment
K
q
to finding a mapping of
q
into every in ccf
k
(
)
.
)
TERMINATION AND COMPLEXITY
For the standard reasoning tasks, e.g., knowledge base consistency, the combined complexity is measured
in the size of the input knowledge base. For query entailment, the size of the query is additionally taken
into account. The size of a knowledge base or a query
q
is simply the number of symbols needed
to write it over the alphabet of constructors, concept, role, individual, and variable names that occur in
or
q
, where numbers are encoded in binary. As for data complexity, we consider the ABox as the
only input for the algorithm, i.e., the size of the TBox, the role hierarchy, and the query is fixed. When
the size of the TBox, role hierarchy, and query is small compared to the size of the ABox, the data com-
plexity of a reasoning problem is a more useful performance estimate since it tells us how the algorithm
behaves when the number of assertions in the ABox increases.
Let
K
q
the string length of encoding and
q
, | the sum of the numbers of fuzzy assertions and inequal-
ity assertions, |
= 〈
T R A
, , a
f
-SHIF (
〉
D
KB and
q
a fuzzy conjunctive query, we denote by ||
,
||
the number of role inclusion axioms, | the number of fuzzy GCIs,
c
the
sub
(
È
)
sub C
q
(
)
, where
C
q
is the set of concepts occurring in
q
,
r
the cardinality of
R
,
+ . Note that, when the size of
q
, TBox , and RBox is fixed,
c
,
d
, and
r
is
linear in the size of ||
d
=|
N
|
|
N
q
|
q
, and is constant in .
,
||
