Databases Reference
In-Depth Information
where each
γ
i
is an atom
P
(
x
1
,...,x
l
) with
x
i
∈
x
(see e.g., [1]). The atom
γ
0
is
called the
head
of the clause, and
γ
1
,...,γ
m
its
body
. In the datalog literature, a
standard agreement is to omit the universal quantifiers, replace
∧
with a comma,
and put the head before the body; thus, the rule above is written as
γ
1
,...,γ
m
.
All variables occurring in the head must also occur in the body. We will also
assume that the heads do not contain constant symbols. A predicate
P depends
on a predicate
Q
in
Π
if
Π
contains a clause whose head is
P
and whose body
contains
Q
.
Π
is called
nonrecursive
if this dependence relation for
Π
is acyclic.
For example, we can define the
ext
predicates (1) and (2) by a nonrecursive
datalog program with the following rules:
ext
A
(
x
)
γ
0
←
A
(
x
)
,
=
A
←
for a concept name
A
with
T|
A,
(9)
ext
A
(
x
)
←
R
(
x, y
)
,
for a concept name
A
with
T|
∃
R
A,
=
(10)
ext
P
(
x, y
)
←
R
(
x, y
)
,
for a role name
P
with
T|
=
R
P.
(11)
(Note that
∀
x, y
(
R
(
x, y
)
→
ext
A
(
x
)) is equivalent to
∀
x
(
∃
yR
(
x, y
)
→
ext
A
(
x
)).)
Let
q
(
x
)beaCQand
T
an
OWL 2 QL
TBox. For a nonrecursive datalog
q
(
q
)isan
NDL-rewriting of
program
Π
andanatom
x
), we say that (
Π,
q
(
x
)
q
(
and
T
(over H-complete ABoxes) in case (
T
,
A
)
|
=
q
(
a
)iff
Π,
A|
=
a
), for any
(H-complete) ABox
). An NDL-rewriting over arbitrary
ABoxes can clearly be obtained from an NDL-rewriting over H-complete ABoxes
by plugging in the
ext
rules above (at the price of a polynomial blowup).
Let us see how the tree-witness PE-rewriting (8) will look like if we represent
it as an NDL-rewriting over H-complete ABoxes. Suppose
A
and any
a
⊆
ind
(
A
t
t
r
,
t
i
)isatree
=(
witness for
q
and
T
with
t
r
=
{
t
1
,...,t
k
}
,
k
≥
0. We associate with
t
a
k
-ary
predicate
tw
t
defined by the following set of rules:
tw
t
(
x,...,x
)
Ω
t
.
(12)
If
t
r
=
∅
then (12) makes all the arguments of
tw
t
equal; otherwise,
t
r
=
∅
and
tw
t
is a propositional variable, with
x
being existentially quantified in the body
of (12). As the arguments of
tw
t
play identical roles, we can write
tw
t
(
←
A
R
(
x
)
,
for
R
∈
t
r
) without
specifying any order on the set
t
r
. We obtain an NDL-rewriting (
Π,
q
tw
(
x
)) of
q
over H-complete ABoxes by taking
Π
to be the nonrecursive datalog
program containing the rules of the form (12) together with the rules
q
tw
(
(
x
)and
T
1
k
1
k
r
x
←
q
\
q
Θ
)
,
tw
t
1
(
t
r
)
,...,
tw
t
k
(
t
r
)
,
for consistent
Θ
=
{
t
r
,...,
t
}
.
(13)
)
(
Example 10.
Let
q
and
T
be the same as in Example 9. Denote by
Π
the datalog
program given below:
q
tw
(
x
1
,x
4
)
←
R
(
x
1
,y
2
)
,R
(
y
3
,y
2
)
,R
(
y
3
,x
4
)
,
q
tw
(
x
1
,x
4
)
←
R
(
y
3
,x
4
)
,
tw
t
1
(
x
1
,y
3
)
,
q
tw
(
x
1
,x
4
)
←
R
(
x
1
,y
2
)
,
tw
t
2
(
y
2
,x
4
)
,
tw
t
1
(
x, x
)
←
A
R
(
x
)
,
tw
t
2
(
x, x
)
←
A
R
−
(
x
)
.
