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
Search WWH ::




Custom Search