
Chapter 17: Optimizing Datalog Programs 679
In order to show that r preserves τ nonrecursively, we will attempt to prove the
opposite by trying to construct a counterexample, and if we fail to do so, then
r preserves τ nonrecursively. A counterexample, in this particular case, is a
DB d Ε5ΑΓ(τ) such that (d,r
n
(d)) violates τ. The DB (d
9
r
n
(d)) violates τ if it
has a ground atom
G(JC
0
,Z
0
)
that exhibits a violation of τ, that is, a ground atom
G(JC
0
,Z
0
)
such that for all u>
0
, the DB (d,r
n
(d)) does not have a ground atom of
the form A(x
0
,w
0
). A ground atom G(x
0
,z
0
) of (d,r
n
(d)) that exhibits a viola-
tion of τ must be in r
n
(d) (it cannot be in d, ...