Database Reference
In-Depth Information
•
If
S
is a source instance without nulls, then the set of universal representatives for
S
coincides with the set of universal solutions for
S
.
•
There exists a mapping
Σ
st
) and a naıve database over R
s
, such that
no naıve database over R
t
is a universal representative for
S
under
M
=(R
s
,
R
t
,
M
.
•
The latter result states that naıve databases are not expressive enough to act as uni-
versal representatives in data exchange when source instances contain null values.
Here we present an extension of the class of naıve databases, called
conditional
databases (see
Abiteboul et al.
(
1995
);
Imieli nski and Lipski
(
1984
)), that allows
defining universal representatives for source instances given as naıve databases (and,
in fact, even for source instances given as conditional databases).
A
conditional database T
extends a naıve database with a
condition
ρ
t
attached to
each fact
t
T
. Each such condition is a Boolean combination of formulae of the
form
x
=
y
with
x
,
y
∈
∈
C
ONST
∪
V
AR
. Given a valuation
ν
:V
AR
∪
C
ONST
→
C
ONST
that is the identity on C
ONST
, we denote by
(
T
) the instance that is obtained from
T
by replacing each fact
W
(
u
1
,...,
u
n
) in
T
with
W
(
ν
ν
(
u
1
)
,...,
ν
(
u
n
)),andthen
removing the resulting facts of the form
ρ
t
(in the
usual sense). The set
Rep
(
T
) is defined as all those instances
T
, without nulls, such
that
ν
(
t
) such that
ν
does not satisfy
T
, for some mapping
ν
(
T
)
⊆
ν
:V
AR
∪
C
ONST
→
C
ONST
that is the identity
on C
ONST
.
As before, a conditional database
T
over R
t
is a universal representative for condi-
tional database
S
over R
s
under
,if
Rep
(
T
)=
S
∈
M
S
OL
M
(
S
)
.
Rep
(
S
)
Σ
st
) and conditional database
S
over
R
s
, there is a conditional database
T
over R
t
that is a universal representative for
S
under
M
. Moreover, prove that the same property holds if one restricts to the
case of
positive
conditional databases, which are obtained by disallowing the use
of negation in the conditions attached to the facts in conditional databases. Thus,
we say that conditional databases, and positive conditional databases, form a
strong
representation system
for the class of mappings specified by st-tgds (this problem
has also been studied by
Grahne and Onet
(
2012
)).
31. In this exercise, you will provide another justification for the mapping languages used
in this topic, which is inspired by the notion of instance-completeness that was used
to justify relational languages. More precisely, say that a pair (
S
,
T
) of instances is
admissible
if: (1) the schemas of
S
and
T
are disjoint, (2) every constant mentioned in
T
is also mentioned in
S
, and (3) every isomorphism from
S
to itself (which is not nec-
essarily the identity on constants) can be extended to an isomorphism from
T
to itself.
Moreover, say that a class
Prove that for every mapping
M
=(R
s
,
R
t
,
of mappings is
instance-complete
if for every admissible
pair (
S
,
T
), there exists a mapping
C
M ∈C
such that
T
is a universal solution for
S
un-
der
. In this exercise, you have to prove that the class of mappings defined by finite
sets of st-tgds including inequalities in the source formulae is instance-complete.
M
