Database Reference
In-Depth Information
Furthermore, those restrictions are, in a sense, optimal, since by lifting any one of them
the problem becomes intractable.
Let
Σ st ) be a mapping. Then for every n -ary relation symbol T in R t ,
we say that the i -th attribute of T (1
M
=(R s , R t ,
i n ) can be nullified under
M
,ifthereisanst-
tgd
α
in
Σ st such that the i -th attribute of T is existentially quantified in the right-hand
side of
α
. Notice that for each mapping
M
and source instance S ,ifthe i -th attribute
of T cannot be nullified under
, then for every tuple T ( c 1 ,..., c n ) in the canonical
universal solution for S , it holds that c i is a constant. Moreover, if Q is a conjunctive
query with inequalities over R t and x is a variable in Q , then we say that x can be
nullified under Q and
M
,if x appears in Q as the i -th attribute of a target relation T ,
and the i -th attribute of T can be nullified under
M
.
Let Q be a conjunctive query with two inequalities over a target schema R t . Assume
that the quantifier free part of Q is of the form ϕ( x 1 ,..., x m ) u 1 = v 1 u 2 = v 2 ,where
ϕ
M
is a conjunction of relational atoms over R t and u 1 , v 1 , u 2 and v 2 are all mentioned
in the set of variables x 1 , ... , x m . Then:
Q has almost constant inequalities under
M
,if u 1 or v 1 cannot be nullified under Q
and
. Intuitively, this means that
to satisfy Q in the canonical universal solution of a source instance, one can only
make comparisons of the form c
M
,and u 2 or v 2 cannot be nullified under Q and
M
= c ,where c , c are constants and
=
and c
is
a null value.
Q has constant joins under
M
, if for every variable x that appears at least twice in
M
ϕ
. Intuitively, this means that to
satisfy Q in the canonical universal solution of a source instance, one can only use
constant values when joining relations.
,thevariable x cannot be nullified under Q and
Prove that the two syntactic restrictions mentioned above yield tractable computa-
tion of certain answers for conjunctive queries with two inequalities, at least in the
absence of target dependencies. That is, let
M
=(R s , R t ,
Σ st ) be a mapping with-
out target dependencies, and let Q be a conjunctive query with two inequalities. Then
CERTAIN
( Q ) can be solved in polynomial time, if Q has constant joins and almost
constant inequalities.
Then prove that by lifting any of the two syntactic restrictions the problem be-
comes intractable, even under L AV mappings. That is, prove that there exists Boolean
conjunctive query Q with two inequalities, such that Q does not have almost con-
stant inequalities (or does not have constant joins), and a LAV mapping
M
M
, such that
( Q ) is CO NP-complete.
16. (Source: Arenas et al. ( 2011c ))
Prove the following stronger version of Theorem 7.8 .Let
CERTAIN
M
M
=(R s , R t ,
Σ st ,
Σ t ) be
a mapping such that
Σ t consists of a set of egds, and let Q be a union of con-
junctive queries with at most one inequality or negated relational atom per disjunct.
Then there exists a D ATALOG C( =) program
Π Q such that for every source instance S ,
certain M ( Q , S )= certain M (
Π Q , S ).
Search WWH ::

Custom Search