Database Reference
In-Depth Information
Notice that, as opposed to the case of LAVmappings,
n
-modularity is used in the charac-
terization of GAV mappings. We conclude this section by presenting an example showing
that
n
-modularity is indeed needed in this characterization.
Example 21.8 Assume that
is a mapping from a source schema R
s
consisting of a
binary relation
E
to a target schema R
t
consisting of a binary relation
G
. Moreover, assume
that
M
M
is defined by the following
infinite
set of st-tgds:
Σ
st
=
{
E
(
x
1
,
x
2
)
∧···∧
E
(
x
n
−
1
,
x
n
)
→
G
(
x
1
,
x
n
)
|
n
≥
2
}
.
It is not hard to see that
is closed under target homomorphisms, admits universal solu-
tions, reflects source homomorphisms and is closed under target intersection (see
Exercise
22.3
). On the other hand,
M
cannot
be defined by a finite set of GAV st-tgds (by
Theorem 21.6
). To see why this is the case,
notice that if
S
,
T
are instances of R
s
and R
t
, respectively, then (
S
,
T
)
M
is not
n
-modular for any
n
>
0, which implies that
M
∈M
if and only if
D
OM
(
S
) such that (
a
,
b
) belongs to the transitive closure of
E
S
, it holds
for every
a
,
b
∈
G
T
. Thus, if
S
n
,
T
n
are the following instances of R
s
and R
t
:
that (
a
,
b
)
∈
E
S
n
=
{
(
i
,
i
+1)
|
1
≤
i
≤
n
}
,
G
T
n
=
{
(
i
,
j
)
|
1
≤
i
<
j
≤
n
+1
}
{
(1
,
n
+1)
}
,
since (1
,
n
+1) is in the transitive closure of
E
S
n
and
then we have that: (1) (
S
n
,
T
n
)
∈M
G
T
n
, and (2) for every instance
S
n
of R
s
such that
S
n
⊆
D
OM
(
S
n
)
(1
,
n
+1)
∈
S
n
and
|
|≤
n
,
since (1
,
n
+1) is not in the transitive closure of
E
S
n
.
it holds that (
S
n
,
T
n
)
∈M
21.3 An application: simplifying schema mappings
In this section, we study the problem of transforming a mapping given by st-tgds into an
equivalent mapping specified by simpler dependencies. More specifically, we apply the
characterizations presented in the previous section to pinpoint the exact computational
complexity of this problem for GAV and LAV st-tgds.
We start by considering the following problem:
P
ROBLEM
: G V-E
QUIVALENCE
I
NPUT
: Mapping
M
given by st-tgds
M
given by GAV st-tgds?
Q
UESTION
: s
M
equivalent to a mapping
GAV mappings are particularly easy, as they essentially provide queries that compute the
target. Thus, if we get a positive answer to the equivalence question, it is well worth trans-
forming the mapping and operating with a simpler one. Of course by equivalence of
M
M
we mean
M
and
M
=
or, equivalently, that for every source
S
, solutions under
M
are the same.
A priori we do not even know whether GAV-E
QUIVALENCE
is decidable. However, the
characterizations presented in the previous section give us a way of analyzing the problem:
M
and solutions under
