Databases Reference
In-Depth Information
3.1 Canonical Model
All types of FO-rewritings are based on the fact that, if an
OWL 2 QL
KB
K
T
,
A
K
, called a
canonical
=(
) is consistent, then there is a special model of
model
and denoted
C
K
, such that
K|
q
a
C
K
|
q
a
q
x
)
and any
a
⊆
ind
(
A
). We have already seen one canonical model in Example 1.
Intuitively, the construction of
C
K
is pretty straightforward: we start with
A
and then apply to it recursively the axioms of
T
wherever possible. The only
nontrivial case is when we apply an axiom of the form
B
=
(
)iff
=
(
), for any CQ
(
B
.
Then either we already have an
R
-arrow starting from
w
, in which case we do
not have to do anything, or such an
R
-arrow does not exist, and then we create a
fresh
individual, say
w
R
, in the model under construction and draw an
R
-arrow
from
w
to
w
R
.
Formally, let
∃
R
to some
w
∈
[
R
]=
{
S
|T|
=
R
S
and
T|
=
S
R
}
.
We write [
R
]
≤
T
[
S
]if
T|
=
R
S
;thus,
≤
T
is a partial order on the set of
equivalence classes [
R
], for roles
R
in
T
.Foreach[
R
], we introduce a
witness
w
[
R
]
and define a
generating relation
K
on the set of these witnesses together
with
ind
(
A
) by taking:
a
K
w
[
R
]
if
a
∈
ind
(
A
)and[
R
]is
≤
T
-minimal such that
K|
=
∃
R
(
a
)and
K|
=
R
(
a, b
) for any
b
∈
ind
(
A
);
w
[
S
]
K
w
[
R
]
if [
R
]is
≤
T
-minimal with
T|
∃
S
−
∃
R
and [
S
−
]
=[
R
].
=
A
K
-
path
is a finite sequence
aw
[
R
1
]
···
w
[
R
n
]
,
n
≥
0, such that
a
∈
ind
(
A
) and,
if
n>
0, then
a
K
w
[
R
1
]
and
w
[
R
i
]
K
w
[
R
i
+1
]
,for
i<n
.Denoteby
tail
(
σ
)the
last element in the path
σ
. The canonical model
C
K
=(
Δ
C
K
,·
C
K
) is defined by
taking
Δ
C
K
to be the set of all
K
-paths and setting:
a
C
K
=
a,
for all
a ∈
ind
(
A
)
,
A
C
K
=
{
a
∈
ind
(
A
)
|K|
=
A
(
a
)
}∪
R
−
{
σ
·
w
[
R
]
|T|
=
∃
A
}
,
for all concept names
A,
P
C
K
=
{
(
a, b
)
∈
ind
(
A
)
×
ind
(
A
)
|
R
(
a, b
)
∈A
with [
R
]
≤
T
[
P
]
}∪
{
(
σ, σ
·
w
[
R
]
)
|
tail
(
σ
)
K
w
[
R
]
,
[
R
]
≤
T
[
P
]
}∪
≤
T
[
P
−
]
{
(
σ
·
w
[
R
]
,σ
)
|
tail
(
σ
)
K
w
[
R
]
,
[
R
]
}
,
for all role names
P.
C
K
,and
Δ
C
K
\
We call
ind
(
A
)the
ABox part
of
ind
(
A
)the
anonymous part
.
Example 6.
Consider the KB
K
=(
T
,
A
), where
Q
−
S
−
∃
R
−
∃
T
=
{
A
∃
Q,
∃
B, Q
S,
∃
R,
∃
R, B
∃
P
}
,
A
=
{
A
(
a
)
,B
(
b
)
,P
(
b,a
)
,S
(
d, b
)
}
.
