Database Reference
In-Depth Information
c,d,r
+
,
)
1
k
Lemma 7.
In a completion forest of , the maximal number of non-isomorphic
k
-trees is
T
k
= 2
(
p
where
p
(
c, d, r
is some polynomial w.r.t.
c, d
, and
r
.
)
⊆ ∪ × ≥ × ∪ , there are at most 2
c
d
node labels in a
k
-complete clash free completion forest of . Each successor of such a node
v
may be a root node of
a (
Proof.
Since
L
( )
x
(
sub
(
K
)
sub C
(
))
{ }
(
N
A
N
q
)
q
2 ,
S n
, the
∃
≥
-rule or ³
³
-rule is triggered and new nodes are added. The generating rules can be applied to each node
at most
c
times. Each time it is applied, it generates at most two
R
-successors (if the label of the node con-
tains 〈≥
k
- -tree. If a node label of a
k
-tree contains some tripes of the form 〈∃
1)
R C
.
,
≥ 〉
, or 〈≥
n
≥ 〉
2 ,
S n
) for each role
R
. This gives a bound of 2
c R
-successors for each role, and a bound of 2
cr
successors for each node. Since
L
≥ 〉
R
, there are at most 2
r
d
different
edge labels, and thus can link a node to one of its successor in 2
r
d
ways. Hence, there can be at most 2
r
d
combinations from a single node in a completion forest to its successors. Thus, the upper bound of the num-
ber of non-isomorphic
k
-trees is
T
A
N
q
(
〈
x y
,
〉 ⊆
)
× ≥ ×
{ }
(
N
∪
)
K
c
r
2
cr
= 2
d
(2
d
T
)
. Let
y
= 2
cr
,
x
=
c
+ , then
y
k
k
-
1
x
1
+
y
y
x
1
+
y
x
1
+
y
y
y
T
= 2
d
(
T
) = 2
d
(2
d
(
T
) ) =
k
k
−
1
k
−
2
y
k
−
1
y
k
y
k
x
1
+
y
1
+ + +
y
x
1
+
y
= (2
d
)
(
T
)
≤
(2
d
T
)
.
0
0
Since
T
0
= 2
c
d
, we have for
y
³ 2 (It also holds for
y
= 1) that
k
k
2
2
c 2cr
+
1 2
+
cr
c
(2
cr
)
2
c 2cr
+
+ +
(1 2cr)d
(
2cr
)
T
k
≤
(2
d
2 )
≤
(2
)
k
+
1
2
2 3
2 2
2
c
+
4c r
+
4c r d
k
+
1
p
(
c,d,r
)
≤
(2
)
= 2
2
2 3
2 2
where
p
(
c, d, r
) = 2
c
+
4c r
+
4c r d
.
d
+
1
Lemma 8.
The upper bound of the number of nodes in is O (
I
((
cr
)
))
, where
d
= (
T
1+ .
k
k
Proof.
By Lemma 7, there are at most
T
k
non-isomorphic
k
-trees. If there exists a path from
v
to
v
with its length greater than (
k
+ , then
v
would appear after a sequence of
T
k
+1 non-overlapping
k
-trees, and one of them would have been blocked so that
v
would not be generated. The number of nodes
in a
k
-tree is bounded by (
T
1)
k
cr
d
+
. The number of nodes in a is bounded by |
)
1
I
| (2 )
cr
d
+
.
1
Corollary 1.
If
k
is linear in the size of ||
q
, then the number of nodes in is at most triple ex-
,
||
ponential in the size of ||
q
; if the size of
q
, TBox , and RBox is fixed, and
k
is a constant,
then the number of nodes in is polynomial in the size of .
,
||
Theorem 3.
(Termination) The expansion of
into a complete and clash free completion forest Î
ccf
k
(
q
, and in polynomial time w.r.t. | if the
size of
q
, TBox , and RBox is fixed, and
k
is a constant.
terminates in triple exponential time w.r.t. ||
)
,
||
