Database Reference
In-Depth Information
We illustrate the concept of CWA solutions with the following example.
Example 8.9 Consider the mapping
M
=(R
s
,
R
t
,
Σ
st
) such that
Σ
st
consists of the fol-
lowing st-tgds:
R
(
x
,
y
)
→∃
z
∃
w
(
P
(
x
,
y
,
z
)
∧
U
(
w
,
z
))
N
(
x
,
y
)
→∃
uP
(
x
,
y
,
u
)
.
{
R
(
a
,
b
)
,
N
(
a
,
b
)
}
Let
S
be the source instance
. Then, with respect to
S
, both its canonical
universal solution
T
=
{
P
(
a
,
b
,
⊥
1
)
,
P
(
a
,
b
,
⊥
2
)
,
U
(
⊥
3
,
⊥
1
)
}
and the core of its universal
solutions
T
=
are CWA solutions.
On the other hand, the solution
T
1
=
{
P
(
a
,
b
,⊥
1
)
,
U
(
⊥
1
,⊥
1
)
}
is not a CWA solution,
simply because it is not a universal solution for
S
(as there is no homomorphism from
T
1
into
T
). The solution
T
2
=
{
P
(
a
,
b
,
⊥
1
)
,
U
(
⊥
3
,
⊥
1
)
}
is a universal
solution for
S
that is not a homomorphic image of
T
. Thus,
T
2
is not a CWA solution.
{
P
(
a
,
b
,
⊥
1
)
,
P
(
a
,
b
,
⊥
2
)
,
P
(
a
,
b
,
⊥
4
)
,
U
(
⊥
3
,
⊥
1
)
}
To connect the definition of CWA solutions with a proper intuition behind the CWA,
we will show that these are the solutions that “satisfy” the requirements below (once we
properly formalize them):
(A1) Each fact in the solution is
justified
by the source instance and the st-tgds in
Σ
st
.
(A2)
Justifications
for facts are not overused; that is, justifications for facts do not justify
more facts than necessary.
(A3) Each “statement” that holds in the solution can be explained by the contents of the
source instance and the st-tgds in
Σ
st
only.
We now formalize these requirements. Start with requirement (A1). Consider a mapping
M
=(R
s
,
R
t
,
Σ
st
) and a source instance
S
.A
justification
in
S
under
M
is a tuple of the
form (
σ
,
a
),where:
•
σ
is an st-tgd in
Σ
st
of the form
ϕ
(
x
)
→∃
y
ψ
(
x
,
y
),and
•
a
is a tuple of elements in D
OM
(
S
) such that
|
a
|
=
|
x
|
and
S
|
=
ϕ
(
a
).
This justification states that any solution
T
for
S
under
M
must satisfy
∃
y
ψ
(
a
,
y
). Intu-
itively, it can be used to
justify
any fact
P
(
u
) that appears in
ψ
(
a
,
w
),where
w
is a tuple
of elements in D
OM
(
T
) such that
|
w
|
=
|
y
|
. If that is the case, we say that the justification
,
a
) is
suitable
for
P
(
u
).
Let
T
be a solution for
S
under
(
σ
M
. Then the first requirement can be properly formalized
as follows:
(A1) Each fact in
T
can be assigned to some suitable justification in
S
under
M
.
In other words, we require that for each fact
P
(
v
) in
T
there is:
•
a justification (
σ
,
a
) in
S
, with
σ
of the form
ϕ
(
x
)
→∃
y
ψ
(
x
,
y
),and
•
an assignment
ν
:V
AR
(
y
)
→
D
OM
(
T
) where V
AR
(
y
) is the set of variables mentioned
in
y
,
