Database Reference
In-Depth Information
Example 7.3 ( Example 4.1 continued) Consider the source instance
S =
{ FLIGHT ( Paris , Santiago , AirFrance , 2320) ,
FLIGHT ( Paris , Santiago , LAN , 2200)
}
.
Notice that every universal solution for S under
M
must contain as a subinstance a copy
of the following target instance T :
{ ROUTES ( 1 , Paris , Santiago ) , INFO FLIGHT ( 1 , 2320 ,⊥ 2 , AirFrance )
ROUTES (
3 , Paris , Santiago ) , INFO FLIGHT (
3 , 2200 ,
4 , LAN )
}
.
It is not hard to see that T is a canonical universal solution for S .
The FO-query
( x , z ) in (7.2) must return the pair ( Paris , Santiago ) over any universal
solution for S . On the other hand, the certain answer of
ϕ
ϕ
( x , z ) over S is the empty set. This
is because T defined as
{ ROUTES (
1 , Paris , Santiago ) , INFO FLIGHT (
1 , 2320 ,
2 , AirFrance ) ,
INFO FLIGHT (
1 , 2200 ,
2 , LAN )
}
( x , z ) returns the empty set when evaluated over it. (Notice that T
is not a universal solution for S as there is no homomorphism from T into T ). Intuitively,
this means that the set of solutions for S does not imply that there is more than one flight
from Paris to Santiago in the target.
is a solution for S and
ϕ
Thus, certain answers of conjunctive queries with inequalities cannot be obtained by
naıve evaluation over a materialized universal solution. However, this does not exclude the
possibility that certain answers to conjunctive queries with inequalities can be efficiently
computed.
We show next that this is unfortunately not the case. In particular, we prove that the
problem of computing certain answers for the class of conjunctive queries with inequalities
remains decidable, but it can be intractable even in the absence of target dependencies.
Theorem 7.4
Σ t consists of a set of egds and a weakly
acyclic set of tgds, and let Q be a union of conjunctive queries with inequalities. Then
CERTAIN
1. Let
M
be a mapping such that
( Q ) is in CO NP .
2. There is a Boolean conjunctive query Q with inequalities and a L AV mapping
M
M
,such
that CERTAIN M ( Q ) is CO NP -hard.
Proof We first prove 1. We show that if there is a solution T for a source instance S
such that t
Q ( T ), then there is a solution T of polynomial size such that t
Q ( T ).
Suppose that T is a solution for S such that t
Q ( T ).Let T can be a canonical universal
solution for S . (Notice that T can exists since S has at least one solution). Then there is a
homomorphism h : T can
T . We denote by h ( T can ) the homomorphic image of T under h .
It is not hard to prove that h ( T can ) is a solution for S .Furthermore, h ( T can ) is of polynomial
size in
). We claim that t
S
(since T can is also of polynomial size in
S
Q ( h ( T can )).
Search WWH ::




Custom Search