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
).
