Database Reference
In-Depth Information
represents complete instances
T
(without nulls) such that there is a homomorphism
h
:
T
T
. The set of such instances is denoted by
Rep
(
T
) (see
Section 2.3
).
There appear to be three different ways to state that a solution
T
is more general than
other solutions, explained below.
→
1. Solutions that describe all others: A most general solution
T
must describe the set of
all other complete solutions, i.e., every complete solution must be represented by
T
:
{
T
∈
|
T
is over C
ONST
UnivSol
1
(
T
) :
S
OL
M
(
S
)
}⊆
Rep
(
T
)
.
2. Solutions that are as general as others: A seemingly slightly weaker condition says
that if a solution
T
is universal, it cannot describe fewer complete instances than another
solution, i.e.
Rep
(
T
)
Rep
(
T
) for every
T
∈
⊆
S
OL
M
(
S
)
.
UnivSol
2
(
T
) :
3. Solutions that map homomorphically into others: This more technical, and yet very
convenient definition, is inspired by the algebraic notion of a universal object, that has a
homomorphism into every object in a class. Recall that a homomorphism
h
:
T
T
is a
mapping from the domain of
T
into the domain of
T
, that is the identity on constants, and
such that
t
=(
t
1
,...,
t
n
)
→
implies
h
(
t
)=(
h
(
t
1
)
,...,
h
(
t
n
)) is in
W
T
for all
W
in R
t
.
W
T
∈
Our third condition then is:
T
for each
T
∈
UnivSol
3
(
T
) :
there is a homomorphism
h
:
T
→
S
OL
M
(
S
)
.
So, which definition should we adopt? It turns out that we can take any one, as they are
equivalent.
Proposition 6.1
If
Σ
t
)
is a mapping, and T is a solution for some source
instance S, then conditions
UnivSol
1
(
T
)
,
UnivSol
2
(
T
)
and
UnivSol
3
(
T
)
are equivalent.
Proof
We first observe the following. Let
T
∈
M
=(R
s
,
R
t
,
Σ
st
,
n
enumerate
the nulls in D
OM
(
T
). Then clearly any instance
T
c
that can be obtained from
T
by re-
placing each
S
OL
M
(
S
),andlet
⊥
1
,...,
⊥
≤
i
≤
n
), such that
c
i
does not appear in
T
,
belongs to
Rep
(
T
). We prove below that it also belongs to S
OL
M
(
S
).
Assume otherwise; that is,
T
c
∈
⊥
i
with a distinct constant
c
i
(1
S
OL
M
(
S
).Then
T
c
|
Σ
t
. Suppose first that
T
c
violates
=
a tgd of the form
ϕ
(
x
)
→∃
y
ψ
(
x
,
y
) in
Σ
t
. That is, assume that there exists a tuple
a
of
elements in D
OM
(
T
c
) such that
(
a
,
y
).Let
a
be the tuple
of elements in D
OM
(
T
) that is obtained from
a
by replacing each occurrence of
c
i
with
⊥
i
,for
i
,
T
c
|
(
a
),but
T
c
|
|
x
|
=
|
a
|
=
ϕ
=
∃
y
ψ
n
. Then it is not hard to see that
T
|
(
a
) and
T
|
(
a
,
y
). This is because
≤
=
ϕ
=
∃
y
ψ
both
(
x
,
y
) are conjunctive queries, which are closed under homomorphisms,
and there is a one-to-one homomorphism from
T
into
T
c
that sends each
ϕ
(
x
) and
∃
y
ψ
⊥
i
to a distinct
n
) that does not occur in
T
or in
constant
c
i
(1
≤
i
≤
Σ
t
. But this contradicts the fact that
T
∈
S
OL
M
(
S
). The case when
T
c
violates an egd in
Σ
t
is completely analogous. With this
observation, we can now easily prove the proposition.
