Databases Reference
In-Depth Information
Theorem 13 ([36]).
For any consistent
OWL 2 QL
KB
K
T
,
A
)
, which does
=(
not contain role inclusion axioms, any CQ
q
x
)
and any tuple
a
⊆
ind
(
A
)
,if
(
C
K
|
q
a
)
then
G
K
|
q
a
)(
but not the other way round
)
.
=
(
=
(
Suppose now that we are given a CQ
q
(
x
)=
∃
y
ϕ
(
x
,
y
). Our aim is to rewrite
q
†
(
q
†
(
q
to an FO-query
x
) in such a way that
C
K
|
=
q
(
a
)iff
G
K
|
=
a
), for any
q
†
is polynomial in the size of
tuple
a
⊆
ind
(
A
), and the size of
q
and
T
.(Note
that the rewriting given in [36,37] does not depend on
T
because of a different
q
†
as a conjunction
definition of tree witness.) We define the rewriting
q
†
(
x
)=
∃
y
(
ϕ
∧
ϕ
1
∧
ϕ
2
∧
ϕ
3
)
,
where
ϕ
1
,
ϕ
2
and
ϕ
3
are Boolean combinations of equalities
t
1
=
t
2
,andeach
of the
t
i
is either a term in
q
or a constant of the form
w
[
R
]
. The purpose of the
conjunct
=
x∈
x
ϕ
1
(
x
=
w
[
R
]
)
R
arolein
T
is to ensure that the answer variables
)only.
The conjunct
ϕ
2
implements the matching dictated by the tree witnesses.
Suppose
x
receive their values from
ind
(
A
generated by
R
.If
R
(
t, t
)
t
=(
t
r
,
t
i
) is a tree witness for
q
and
T
∈
q
and
t
is mapped to
w
[
R
]
, then all the variables in
t
r
are to be mapped to the
same point as
t
:
(
t
=
w
[
R
]
)
(
s
=
t
)
.
ϕ
2
=
→
R
(
t,t
)
s∈
t
r
∈
q
there is a tree witness
t
with
R ∈ Ω
t
,then
t
cannot be mapped to the witness
w
[
R
]
at all. This is ensured by the conjunct
generated by
R
and such that
R
(
t, t
)
Ifthereisnotreewitness
t
∈
q
t
t
=
w
[
R
]
.
ϕ
3
=
R
(
t,t
)
∈
q
no tree witness
t
with
R ∈ Ω
t
exists
Theorem 14 ([36]).
For any consistent
OWL 2 QL
KB
K
=(
T
,
A
)
containing
no role inclusion axioms, any CQ
q
(
x
)
and any tuple
a
⊆
ind
(
A
)
, we have
q
†
(
C
K
|
=
q
(
a
)
iff
G
K
|
=
a
)
.
q
†
can be computed in polynomial time in
The rewriting
q
and
T
and is of size
O
(
).
A slightly different idea was proposed in [46] to extend the combined approach
to unrestricted
|
q
|·|T|
OWL 2 QL
TBoxes. As before, given a CQ
q
(
x
), an
OWL 2 QL
TBox
T
andanABox
A
, we first construct a polynomial-size interpretation
G
K
G
K
representing the (possibly infinite) canonical model
C
K
(in fact,
is more
involved than
G
K
). Then we use an RDBMS to compute the answers to the
G
K
original
CQ
stored in the RDBMS. As we saw above, some of
the answers can be spurious. To eliminate them, instead of
ϕ
1
,ϕ
2
and
ϕ
3
,one
can use a 'filtering procedure' that is installed as a user-defined function in the
q
(
x
)over
