Database Reference
In-Depth Information
We briefly mention some other extensions that have not been treated in detail in this
part. First, we viewed data exchange as unidirectional (from source to target); an extension
of schema mappings that works in a bidirectional way (peer data exchange) was given by
Fuxman et al.
(
2006
).
Giacomo et al.
(
2007
) proposed a setting that reconciled peer data ex-
change with both data exchange and data integration settings. Approximate data exchange
settings, which do not require targets to follow all constraints precisely, were proposed
by
de Rougemont and Vieilleribiere
(
2007
). Data exchange in a probabilistic setting was
studied by
Fagin et al.
(
2010
). Techniques for implementing general data exchange using
mappings without target constraints are studied by
Marnette et al.
(
2010
). Practical aspects
of computing cores are discussed in
Mecca et al.
(
2009
)and
ten Cate et al.
(
2009
). Learning
schema mapping from data exchange examples is studied in
ten Cate et al.
(
2012
).
9.3 Exercises
1. Find the exact complexity of computing the canonical universal solution. Also prove
that the canonical universal solution can be constructed in DL
OGSPACE
if the mapping
is fixed.
2. Show that the set of tgds constructed in the proof of
Theorem 5.3
is not weakly acyclic.
3. (Source:
Deutsch et al.
(
2008
))
In this exercise we prove that efficient chase procedures can be pushed beyond weak
acyclicity. Let
d
1
:=
y
2
ψ
2
(
x
2
,
y
2
) be tgds
over the schema R.Then
d
1
triggers d
2
if there are instances
T
1
and
T
2
over R,and
tuples
a
ϕ
1
(
x
1
)
→∃
y
1
ψ
1
(
x
1
,
y
1
) and
d
2
:=
ϕ
2
(
x
2
)
→∃
D
OM
(
T
1
)
|
x
1
|
and
b
D
OM
(
T
2
)
|
x
2
|
, respectively, such that:
∈
∈
b
does not belong to D
OM
(
T
1
),or
T
1
|
ϕ
2
(
b
)
•
either some element of
=
→
y
2
ψ
2
(
b
,
y
2
).Thatis,
d
2
is not applicable in
T
2
for tuple
b
;
•
T
1
d
1
,
a
∃
−−→
T
2
, i.e.,
T
2
is obtained from
T
1
by applying a chase step on
d
1
with tuple
a
;
and
ϕ
2
(
b
)
y
2
ψ
2
(
b
,
y
2
), i.e.,
T
2
violates
d
2
, and this is witnessed by tuple
b
.
•
T
2
|
∧¬∃
=
Let
Σ
be a set of tgds. We define the
chase graph
of
Σ
as the undirected graph whose
nodes are the tgds in
and such that there is an edge between tgds
d
1
and
d
2
if and
only if
d
1
triggers
d
2
.Theset
Σ
is
stratified
if the set of constraints in every cycle of
its chase graph is weakly acyclic.
Σ
(i) Prove that the notion of stratification properly extends the notion of weak acyclic-
ity. That is, prove that each weakly acyclic set of tgds is stratified, but there is a
stratified set of tgds that is not weakly acyclic.
(ii) Prove that the chase is guaranteed to terminate, in at most polynomially many
steps, for stratified sets of tgds. That is, prove that there exists a polynomial
p
such that the length of every chase sequence for an instance
T
under a stratified
set of tgds is bounded by
p
(
T
).
