Database Reference
In-Depth Information
20.4 Inverses under extended semantics
So far we have assumed that source instances do not contain null values. However, null
values in the source may naturally arise when using inverses of mappings to exchange
data. Indeed, we apply inverses to databases containing exchanged data, which, of course,
contains nulls. Thus, when we handle inverse operators, it seems natural to let databases
contain both constants and nulls, i.e., values from C
ONST
∪
V
AR
.
In this section, we introduce two appropriate notions for the scenario of whether source
instances may contain nulls, namely
extended recovery
and
maximum extended recovery
,
and compare them with the previously proposed notions of recovery and maximum recov-
ery.
The first observation to make is that since null values are intended to represent
missing
or
unknown
information, they should not be treated naıvely as constants. In fact, if null values
are treated as constants when verifying the satisfaction of a set of dependencies, then the
existence of maximum recoveries for mappings given by tgds is no longer guaranteed.
Proposition 20.40
If null values are treated as constants, then there exists a mapping
specified by a finite set of tgds and containing null values in sources instances that does
not admit a maximum recovery.
Proof
Let
),whereR
1
is a schema consisting of unary relations
A
and
B
,
R
2
is a schema consisting of a unary relation
E
and
M
=(R
1
,
R
2
,
Σ
Σ
is a set consisting of the following
tgds:
A
(
x
)
→
E
(
x
)
B
(
x
)
→∃
yE
(
y
)
.
Moreover, assume that the instances of R
1
may contain null values. Next we show that
M
does not admit a maximum recovery if nulls are treated as constants when verifying the
satisfaction of
.
For the sake of contradiction, assume that
Σ
M
admits a maximum recovery, and let
S
1
be
an instance of R
1
such that
A
S
1
= /0and
B
S
1
=
,where
a
is a constant. Then we have
from
Theorem 20.25
that
S
1
has a witness solution under
{
a
}
M
, say instance
T
1
of R
2
.Given
,wehavethat
E
T
1
that the empty instance of R
2
is not a solution for
S
1
under
M
= 0. Thus,
we have to consider two cases.
•
Assume first that there exists a constant
b
such that
E
(
b
) is a fact in
T
1
,andlet
S
2
be
an instance of R
1
such that
A
S
2
=
and
B
S
2
= 0. Then we have that (
S
2
,
T
1
)
{
b
}
|
=
Σ
and, therefore
T
1
∈
S
OL
M
(
S
2
). Thus, from the fact that
T
1
is a witness for
S
1
under
M
,
we conclude that S
OL
M
(
S
1
)
S
OL
M
(
S
2
). But this leads to a contradiction since the
instance of R
2
consisting of fact
E
(
c
),where
c
⊆
=
b
is a constant, is a solution for
S
1
under
M
, but it is not a solution for
S
2
under
M
.
•
Second, suppose that there exists a null value
n
such that
E
(
n
) is a fact in
T
1
,andlet
S
3
be an instance of R
1
such that
A
S
3
=
and
B
S
3
= 0 (notice that
S
3
is an instance of
R
1
containing null values). Then given that we are treating null values as constants, we
{
n
}
