Database Reference
In-Depth Information
a schema consisting of binary relations
coloring
and
edge
,andR
3
a schema consisting
of a binary relation
error
and a unary relation
color
. Moreover, let
12
=(R
1
,
R
2
,
M
Σ
12
)
23
=(R
2
,
R
3
,
and
M
Σ
23
),where
Σ
12
consists of the following st-tgds:
node
(
x
)
→∃
y
coloring
(
x
,
y
)
,
(19.1)
edge
(
x
,
y
)
,
edge
(
x
,
y
)
→
and
Σ
23
consists of the following st-tgds:
edge
(
x
,
y
)
∧
coloring
(
x
,
u
)
∧
coloring
(
y
,
u
)
→
error
(
x
,
y
)
,
(19.2)
coloring
(
x
,
u
)
→
color
(
u
)
.
(19.3)
Next we show that C
OMPOSITION
(
23
) is NP-hard by reducing from the graph 3-
coloring problem. Intuitively, relations
node
and
edge
in R
1
store a graph
G
, and relation
edge
in R
2
is a copy of
edge
. Moreover, st-tgd
(19.1)
indicates that a color must be
assigned to each node in the graph and, thus, relation
coloring
in R
2
stores a possible
coloring of graph
G
. Finally, st-tgd
(19.3)
indicates that relation
color
in R
3
stores the
colors used in the coloring of
G
, and st-tgd
(19.2)
indicates that
error
stores any incorrect
assignment of colors, that is,
error
(
x
,
y
) holds if
x
,
y
are adjacent nodes in
G
and the same
color is assigned to them.
Formally, let
G
=(
N
,
E
) be a graph, and define instances
S
1
of R
1
and
S
3
of R
3
as
follows:
M
12
,
M
node
S
1
=
N
,
color
S
3
=
{
red
,
green
,
blue
}
,
edge
S
1
=
E
,
error
S
3
= 0.
23
if and only if graph
G
is 3-colorable. This con-
cludes the proof of the theorem, as it shows that the graph 3-coloring problem can be
reduced in polynomial time to C
OMPOSITION
(
12
Then it holds that (
S
1
,
S
3
)
∈M
◦M
12
,
23
).
M
M
Let us see now that FO is not expressive enough to define compositions of mappings
defined by st-tgds. We claim that the composition of
23
cannot be defined by
a finite set of FO formulae. Towards a contradiction, suppose that it is defined by a finite set
Σ
M
12
and
M
23
) reduces immediately to the problemof
verifying whether a pair of instances (
S
1
,
S
3
) satisfies
of FO formulae. Then C
OMPOSITION
(
M
12
,
M
Σ
. But this means that the complexity
23
) is in AC
0
, as the complexity of the problem of verifying
whether a fixed set of FO formulae is satisfied by an instance is in this complexity class.
Recall that AC
0
is the class of “constant parallel time” problems, i.e., languages that can
be accepted by a family of constant-depth, unbounded-fanin circuits with AND, OR, and
NOT gates. Its uniform version, which contains FO, is a subclass of L
OGSPACE
, and thus
P
TIME
.By
Theorem 19.3
,C
OMPOSITION
(
of C
OMPOSITION
(
M
12
,
M
12
,
23
) is NP-hard, which contradicts the
M
M
well-known fact that AC
0
NP (see
Section 2.4
for a discussion about these complexity
classes).
Theorem 19.3
not only shows that FO is not the right language to express the compo-
sition of mappings given by st-tgds, but also gives a good insight into what needs to be
