Databases Reference
In-Depth Information
A
But let us assume that we can manipulate the given ABox
.Inthiscase,a
T
A
natural question would be: why cannot we first apply
to
andthenevaluate
q
OWL 2 QL
over the resulting canonical model? However, many
TBoxes are of
infinite depth, and so the canonical model of
K
=(
T
,
A
) can be infinite; even if
T
is of bounded depth, the canonical model of
K
can be of exponential size.
Example 13.
Consider the
OWL 2 QL
TBox
T
−
R
−
T
=
{
A
∃
T,
∃
B, B
∃
R,
∃
A
}
.
The infinite canonical model of
C
K
,for
K
=(
T
,
{
A
(
a
)
}
), looks as follows:
A
a
B
aw
[
T
]
A
aw
[
P
]
w
[
R
]
B
aw
[
T
]
w
[
R
]
w
[
T
]
T
R
T
C
K
But what if we fold the infinite chain of alternating
R
-and
T
-arrows in a simple
cycle such as in the picture below?
T
A
a
B
w
[
T
]
A
w
[
R
]
G
K
T
R
Note that
G
K
is still a model of
K
.Now,considertheCQ
q
(
x
)=
∃
y,z
(
T
(
x, y
)
∧
R
(
y,z
)
∧
T
(
z,y
))
.
Clearly, we have
(
a
). Observe, however, that to get rid
of this spurious answer
a
, it is enough to slightly modify
G
K
|
=
q
(
a
), but
C
K
|
=
q
q
by adding to it the
'filtering conditions' (
z
=
w
[
R
]
), (
y
=
w
[
R
−
]
), (
y
=
w
[
T
]
)and(
z
=
w
[
T
−
]
)as
conjuncts (in the scope of
have
no tree witnesses, and so the variables
y
and
z
cannot be mapped anywhere in
the anonymous part of the canonical model.
∃
y,z
). Indeed, it is not hard to see that
q
and
T
It turns out that this idea works perfectly well at least for the case when
OWL 2 QL
TBoxes
do not contain role inclusions
. Suppose
T
is such a TBox
and
A
an arbitrary ABox. We define the
generating model
G
K
of
K
=(
T
,
A
)by
taking:
Δ
G
K
=
Δ
C
K
}
{
tail
(
σ
)
|
σ
∈
,
a
G
K
=
a,
for all
a
∈
ind
(
A
)
,
A
G
K
=
A
C
K
}
{
tail
(
σ
)
|
σ
∈
,
for all concept names
A,
P
G
K
=
(
tail
(
σ
)
,
tail
(
σ
))
(
σ, σ
)
P
C
K
}
{
|
∈
,
for all role names
P,
where
C
K
is the standard canonical model of
K
. It is not hard to see that the
map
tail
:
Δ
C
K
→
Δ
G
K
is a homomorphism from
C
K
onto
G
K
,and
C
K
can be
viewed as the 'unraveling' of
G
K
. The generating model
G
K
can be constructed
in polynomial time in
. As positive existential queries are preserved under
homomorphisms, we obtain:
|K|
