Database Reference
In-Depth Information
8.3 Closed-world semantics and target constraints
So far we considered CWA data exchange in the absence of target dependencies. Here we
extend it to general mappings with egds and tgds. The basic idea is to characterize the class
of solutions that satisfy requirements (A1), (A2) and (A3), as formalized in the previous
section, under mappings that have target dependencies.
Unlike the case without target dependencies, for the class of mappings with target con-
straints it is not so simple to provide a characterization of the class of CWA solutions in the
spirit of
Definition 8.8
(which states that CWA solutions are precisely the universal solu-
tions that are homomorphic images of the canonical universal solution). Hence, we present
a more procedural version now. This version continues the idea from the previous section
that facts and true statements in CWA solutions must be justified (but not overjustified) by
the source instance and the dependencies only. However, in this case it will be necessary
to consider not just the dependencies in
Σ
st
but also those in
Σ
t
. As expected, involving
dependencies in
Σ
t
has an associated cost in the technical complexity of the definition. The
procedural characterization of CWA solutions under target dependencies that we provide
in this section is based on a suitably “controlled” modification of the chase.
Our initial goal is to redefine the notion of CWA presolution in the presence of target
dependencies; that is, those solutions that satisfy the requirements:
(A1) Each fact in the solution is justified by the source instance and the st-tgds in Σ
st
∪
Σ
t
.
(A2) Justifications for facts are not overused; that is, justifications for facts do not justify
more facts than necessary.
Let us start with requirement (A1). Informally, a fact in a solution
T
for
S
under
M
=
(R
s
,
R
t
,
Σ
st
,
Σ
t
) is justified, if either:
•
It can be obtained from
S
by applying an st-tgd in
Σ
st
,or
•
it can be obtained by applying a tgd in
Σ
t
to already justified facts.
We have not yet considered egds; these will be incorporated later.
One has to be careful with “cyclic” justifications: for instance, a tgd
ϕ
(
x
)
→∃
y
ψ
(
x
,
y
)
together with a tuple
a
such that
|
a
|
=
|
x
|
maybeusedtojustifyfactsin
ψ
(
a
,
v
), while, at
the same time, another tgd may use the atoms in
(
a
).In
order to avoid this problem, we make use of a “controlled” version of the chase, in which
each tgd can only be applied to facts already obtained by another tgd in the chase sequence.
As in the case with no target dependencies, in order to satisfy requirement (A2) we force
every (st-)tgd
ψ
(
a
,
v
) to justify the atoms in
ϕ
ϕ
(
x
)
→∃
y
ψ
(
x
,
y
) in
Σ
st
∪
Σ
t
to be applied at most once with each tuple
a
such that
. We formalize these intuitions below.
We start by redefining the notion of justification in the new setting. Let
|
a
|
=
|
x
|
M
=
(R
s
,
R
t
,
Σ
t
consists of a set of tgds only, and
S
a source in-
stance. That is, for the time being we do not consider egds, although we will incorporate
them later. A
potential
justification under
Σ
st
,
Σ
t
) be a mapping, where
M
is a tuple of the form (
σ
,
a
),where
σ
is an
st-tgd in
Σ
st
or a tgd in
Σ
t
of the form
ϕ
(
x
)
→∃
y
ψ
(
x
,
y
),and
a
is a tuple of elements
