Database Reference
In-Depth Information
homomorphism from
G
to
K
3
, the clique of size 3. Thus,
G
is 3-colorable if and only if the
core of the disjoint union of
G
and
K
3
is
K
3
itself. This shows that there is a polynomial
time reduction from the problem of 3-colorability to the problem of computing the core of
a graph. It follows that the latter is NP-hard. In fact, checking if a
fixed
graph
G
0
is the
core of an input graph
G
is an NP-complete problem; if both
G
and
G
0
are inputs, then the
complexity is even higher (more precisely, in the class DP, studied in complexity theory).
However, in data exchange we are interested in computing the core of a universal so-
lution and not of an arbitrary instance. And the intractability of the general problem does
not mean bad news in our case. In fact, we are about to see that computing the core of
the universal solutions under the class of mappings with a weakly acyclic set of tgds is a
tractable problem.
Let us consider first a simple class of relational mappings: those without tgds. Then
there is a simple greedy algorithm that computes the core of the universal solutions (under
the assumption that universal solutions exist, i.e., that the chase does not fail). Moreover,
it does so in polynomial time. The algorithm C
OMPUTE
C
ORE
(
M
) for a mapping
M
=
(R
s
,
R
t
,
Σ
st
,
Σ
t
) without tgds in
Σ
t
is shown below.
Algorithm 6.1 C
OMPUTE
C
ORE
(
M
)
Require: A source instance
S
Ensure: If
S
has a universal solution under
,then
T
∗
is a target instance that is a core
M
for
S
.Otherwise,
T
∗
=
fail
1:
let
T
be the result of a successful chase sequence for
S
under
M
2:
if
T
=
fail
then
3:
T
∗
=
fail
4:
else
5:
T
∗
:=
T
for all fact
R
(
a
) in
T
∗
do
6:
let
T
∗,−
be an instance obtained from
T
∗
by removing fact
R
(
a
)
7:
if (
S
,
T
∗,−
) satisfies
Σ
st
then
8:
9:
T
∗
:=
T
∗,−
10:
end if
11:
end for
12:
end if
M
=(R
s
,
R
t
,
st
,
Theorem 6.17
t
. If the chase
computing the canonical universal solution does not fail, then
C
OMPUTE
C
ORE
(
Let
Σ
Σ
t
)
be a mapping without tgds in
Σ
)
out-
puts the core of the universal solutions for S. Furthermore, this algorithm runs in polyno-
mial time in the size of S.
M
Proof
It is clear that the algorithm runs in polynomial time in the size of
S
, since com-
puting
T
is done in polynomial time, and checking whether
T
∗,−
is a solution for
S
can be
done in polynomial time as well.
