Database Reference
In-Depth Information
23. Generalize the P
TIME
-algorithm for certain answers given in
Part THREE
so that it
handles mappings in SM
nr
(
↓
,
=
,
F
UN
) and queries in CTQ(
↓
,
=).
24. (Source:
Fagin et al.
(
2008b
))
Prove that the mapping
M
specified by the set
{
P
(
x
)
→
T
(
x
)
,
R
(
x
)
→
T
(
x
)
}
of st-tgds
does not have a Fagin-inverse.
25. (Source:
Fagin et al.
(
2008b
))
Prove that the mapping
M
specifiedbyst-tgd
P
(
x
,
y
,
z
)
→
R
(
x
,
y
)
∧
T
(
y
,
z
) does not
have a Fagin-inverse.
26. (Source:
Fagin and Nash
(
2010
))
Prove that the problem of verifying, given a mapping
M
specifiedbyasetofst-tgds,
is Fagin-invertible is
CO
NP-hard.
27. (Source:
Fagin et al.
(
2008b
))
Let
whether
M
M
be an arbitrary mapping. Prove that if
M
is quasi-invertible, then
M
satisfies
∼
M
)-subset property.
28. (Source:
Fagin et al.
(
2008b
))
Let
the (
∼
M
,
M
specifiedbytgd
M
be the mapping in
Exercise 22.3
. Prove that the mapping
R
(
x
,
y
)
∧
T
(
y
,
z
)
→
P
(
x
,
y
,
z
) is a quasi-inverse of
M
.
29. (Source:
Fagin et al.
(
2008b
))
Find a quasi-inverse for the mapping in
Exercise 22.3
.
30. (Source:
Arenas et al.
(
2009b
))
Show that in
Example 20.20
, mapping
M
2
is not a maximum recovery of mapping
.
31. Find a quasi-inverse of the mapping
M
M
specified by st-tgd
P
(
x
,
y
,
z
)
→
R
(
x
,
y
)
∧
T
(
y
,
z
)
that is neither a recovery nor a maximum recovery of
M
.
32. Let
M
be the mapping in
Example 20.31
and
Q
be the target query
T
(
x
,
y
). Prove that
∧
∨
R
(
x
,
y
) is a source rewriting of
Q
under
M
(
P
(
x
)
x
=
y
)
.
33. Prove
that
the
formula
α
(
u
)
computed
in
line
8
of
algorithm
M
AXIMUM
R
ECOVERY
F
ULL
is a source rewriting of
target query
P
(
u
).Use
this fact to conclude that this algorithm is correct.
34. Use algorithm M
AXIMUM
R
ECOVERY
F
ULL
to find a maximum recovery for the map-
ping
M
specified by st-tgd
P
(
x
,
y
,
z
)
→
R
(
x
,
y
)
∧
T
(
y
,
z
).
35. Let
is a finite set of tgds, and assume that the instances of
R
1
can contain null values. Prove that every instance of R
1
has a universal solution
under
e
(
M
=(R
1
,
R
2
,
Σ
),where
Σ
M
). Use this fact to conclude that
e
(
M
) admits a maximum recovery.
36. (Source:
Arenas et al.
(
2009a
))
This exercise is about recoveries under the universal solution semantics. For a
mapping
M
=(R
1
,
R
2
,
Σ
),let
u
(
M
) be defined as the set of pairs:
{
(
S
,
T
)
|
))
−
1
=
T
is a universal solution for
S
under
M}
. Prove that
the mapping (
u
(
M
{
(
T
,
S
)
|
(
S
,
T
)
∈
u
(
M
)
}
is a maximum recovery of
u
(
M
).
37. (Source:
ten Cate and Kolaitis
(
2009
))
Let
M
be a mapping specified by a finite set of st-tgds. Prove that
M
reflects source
homomorphisms.
