Database Reference
In-Depth Information
Assume otherwise; then
t
Q
(
h
(
T
can
)).But
h
(
T
can
) is a subinstance of
T
, and, therefore,
since unions of conjunctive queries with inequalities are
monotone
(i.e., if
t
∈
∈
Q
(
T
1
) then
t
Q
(
T
2
),forevery
T
2
such that
T
1
is a subinstance of
T
2
), it is the case that
t
also belongs
to
Q
(
T
), which is a contradiction.
With this observation, it is easy to construct a
CO
NP algorithm for the problemof certain
answers of
Q
and
∈
.Infact,a
CO
NP algorithm for checking
t
M
∈
certain
M
(
Q
,
S
) is the
same as an NP algorithm for checking
t
certain
M
(
Q
,
S
). By the above observation, for
the latter it simply suffices to guess a polynomial-size instance
T
and check, in polynomial
time, that
T
is a solution, and that
t
∈
Q
(
T
).
We now prove 2. The L
AV
mapping
∈
st
) is as follows. The source schema
R
s
consists of two relations: a binary relation
P
and a ternary relation
R
. The target schema
R
t
also consists of two relations: a binary relation
U
and a ternary relation
V
.Theset
M
=(R
s
,
R
t
,
Σ
Σ
st
contains the following source-to-target dependencies:
P
(
x
,
y
)
→∃
z
(
U
(
x
,
z
)
∧
U
(
y
,
z
))
R
(
x
,
y
,
z
)
→
V
(
x
,
y
,
z
)
.
The Boolean query
Q
is defined as:
∃
x
1
∃
y
1
∃
x
2
∃
y
2
∃
x
3
∃
y
3
(
V
(
x
1
,
x
2
,
x
3
)
∧
U
(
x
1
,
y
1
)
∧
U
(
x
2
,
y
2
)
∧
U
(
x
3
,
y
3
)
∧
x
1
=
y
1
∧
x
2
=
y
2
∧
x
3
=
y
3
)
.
Next we show that
CERTAIN
M
(
Q
) is
CO
NP-hard.
The
CO
NP-hardness is established from a reduction from 3SAT to the complement of
the problemof certain answers for
Q
and
M
. More precisely, for every 3CNF propositional
formula
ϕ
, we construct in polynomial time an instance
S
ϕ
of R
s
such that
ϕ
is satisfiable
iff
certain
M
(
Q
,
S
ϕ
)=
false
.
Given a propositional formula
ϕ
≡
1
≤
j
≤
m
C
j
in 3CNF, where each
C
j
is a clause, let
S
ϕ
be the following source instance:
•
The interpretation of
P
in
S
ϕ
contains the pair (
q
,
¬
q
), for each propositional variable
q
mentioned in
ϕ
;and
•
the interpretation of
R
in
S
ϕ
contains all tuples (
α
,
β
,
γ
) such that for some 1
≤
j
≤
m
it
is the case that
C
j
=(
α
∨
β
∨
γ
).
Clearly,
S
ϕ
can be constructed in polynomial time from
.
It is not hard to see that the unique canonical universal solution
T
for
S
ϕ
ϕ
is as follows,
where we denote by
⊥
q
the null generated by applying the st-tgd
P
(
x
,
y
)
→∃
z
(
U
(
x
,
z
)
∧
U
(
y
,
z
)) to
P
(
q
,
¬
q
):
•
The interpretation of the relation
U
in
T
contains the tuples (
q
,
⊥
q
) and (
¬
q
,
⊥
q
),for
each propositional variable
q
mentioned in
ϕ
;and
•
the interpretation of the relation
V
in
T
is just a copy of the interpretation of the relation
R
in
S
ϕ
.
