Database Reference
In-Depth Information
3.
σ
(
y
i
) is a constant, for every 1
≤
i
≤
m
,and
4.
σ
(
u
i
)
=
σ
(
v
i
),forevery1
≤
i
≤
n
.
The operator
is used to define the semantics of constant-inequality Datalog programs.
More precisely, define
T
0
Π
• T
(
I
) :=
I
,and
n
+1
Π
n
Π
n
Π
• T
(
I
) :=
T
(
T
(
I
))
∪T
(
I
),forevery
n
≥
0.
(
I
)=
n
≥
0
T
T
Π
n
Π
Then the evaluation of
Π
over
I
is defined as
(
I
).
A constant-inequality Datalog program
Π
is said to be defined over a relational schema
R if R =
Pred
(
). Intuitively, A
NSWER
is a dis-
tinguished predicate that is used to define the evaluation of a D
ATALOG
C(
=)
program over
an instance. Given an instance
I
of R and a tuple
t
in D
OM
(
I
)
n
,where
n
is the arity of
A
NSWER
, we say that
t
Π
)
−
IPred
(
Π
) and A
NSWER
∈
IPred
(
Π
A
NSWER
T
Π
(
I
0
)
,where
I
0
is the extension of
I
defined
(
I
) if
t
∈
Π
∈
as:
R
I
0
=
R
I
R and
R
I
0
= /0for
R
for
R
∈
∈
IPred
(
Π
).
Computing certain answers of
D
ATALOG
C(
=)
programs
The reason that explains why certain answers of unions of conjunctive queries can be
obtained by means of naıve evaluation is that these queries are preserved under homomor-
phisms. Recall that this means that if
Q
is a union of conjunctive queries over R
t
,and
T
and
T
are two target instances such that there is a homomorphism from
T
to
T
, then a tuple
a
of constants that belongs to the evaluation of
Q
over
T
also belongs to the evaluation of
Q
over
T
.
It is well-known that D
ATALOG
programs are also preserved under homomorphisms,
and, therefore, that their certain answers can be obtained by means of naıve evaluation.
Unfortunately, extending D
ATALOG
programs (or even conjunctive queries) with inequal-
ities destroys preservation under homomorphisms. For example, assume that we have an
instance
T
that only contains the fact
R
(
a
,
⊥
),where
a
∈
C
ONST
and
⊥∈
V
AR
.Let
Q
be
the following conjunctive query with one inequality:
=
Q
but
T
|
=
Q
,where
T
is the homomorphic image of
T
witnessed by the homomorphism
h
(
∃
x
∃
y
(
R
(
x
,
y
)
∧
x
=
y
). Clearly,
T
|
)=
a
.
But as we mentioned before, the homomorphisms in data exchange are not arbitrary;
they are the identity on the constants. Thus, given that inequalities are witnessed by con-
stants in D
ATALOG
C(
=)
programs, we have that these programs are preserved under homo-
morphisms. From this we conclude that the certain answers of a D
ATALOG
C(
=)
program
Π
⊥
over a universal solution and then discard-
ing those tuples that contain nulls. Since the data complexity of evaluating D
ATALOG
C(
=)
programs is in P
TIME
, we conclude the following:
can be computed by directly evaluating
Π
Proposition 7.7
Σ
t
)
be a mapping such that
Σ
t
consists of a set of
egds and a weakly acyclic set of tgds, and let
Π
be a
D
ATALOG
C(
=)
program over
R
t
.Then
CERTAIN
Let
M
=(R
s
,
R
t
,
Σ
st
,
(
Π
)
can be solved in
P
TIME
.
M