Database Reference
In-Depth Information
1.
h
Υ
(
⊥
)
=⊥∈
Υ
∈
Ob
DB
(for each object in
DB
, the empty relation is an element
0
).
2.
h
Υ
(α
#
(t),i)
=
α
#
(o
i
(t))
, where
o
i
(t)
∈
T
P
X
.
3.
h
Υ
((α
#
(t
1
),α
#
(t
2
)),
of it, with
⊥
={⊥}
−
1
)
=
α
#
(t
1
TIMES
t
2
)
,
and
h
Υ
((α
#
(t
1
),α
#
(t
2
)),
0
)
=
otherwise.
Thus,
α
#
is the unique epic inductive extension of
h
Υ
along the assignment
α
:
X
→
Υ
, to all terms with variables in
α
#
(t
1
UNION
t
2
)
if
α
#
(t
1
)
and
α
#
(t
2
)
are union compatible;
⊥
T
P
X
(the mapping
α
#
is equal to
α
for the variables
in
X
⊆
T
P
X
). (The injections
inl
X
and
inr
X
are defined at the end of Sect.
5.1.1
.)
Heaving defined this schema
Υ
=
(
R
,
∅
)
, the instance database
α
∗
(Υ)
is an ob-
ject in
DB
for each R-algebra
α
. Let us show that
α
∗
(Υ)
⊆
Υ
.
From the fact that
Υ
is defined as a set of all
n
-ary relations (for finite
n
≥
0) with
values in a fixed universe
U
, it means that, for any
n
-ary relational symbol
r
∈R
,the
relation
α(r)
is an element in
Υ
. Thus,
α
∗
(Υ)
∈
Υ
={
|
}={
|
∈R}⊆
α(r)
r
α(r)
r
Υ
. Consequently,
Υ
α
=
α
0
α
0
(Υ)
α
=
α
0
α
∗
(Υ)
α
∗
(Υ)
α
∗
(Υ)
Υ
=
=
=
=
A
α
A
∈
S
⊆
Ob
DB
α
∗
(Υ)
where
S
={
∈
Ob
DB
|
α
=
α
0
}⊆{
A
|
A
is simple object in
DB
}=
Υ
.
Remark
Notice that the top simple object
Υ
is the set of all finitary relations (i.e.,
with a finite number of columns
n
ar(R)
, but some of them can have also infinite
sets of tuples) that can be obtained from a fixed universe
=
U
=
dom
∪
SK
, where
={
}
SK
ω
0
,ω
1
,...
is an infinite set of indexed Skolem constants and
dom
is a fixed
domain of values.
As specified in the introduction (Sect.
1.4
) for any relation
R
∈
Υ
with an infinite
number of tuples,
SK
⊆
val(
{
R
}
)
and
val(
{
R
}
)
∩
dom
is always
finite
(because a
domain
dom(a)
att
of a relation is finite). Consequently,
the infinite relations can have only finite sets of values of
dom
and become infinite
only because they have
all
Skolem constants: it happens only when we have the
cyclic tgds with existentially quantified right-hand side of implication (the case of
database mappings with incomplete information, as explained in Example
27
in
Sect.
4.2.4
):
⊂
dom
of any attribute
a
∈
R
1
=
r
can(
I
,
D
)
R
2
=
s
can(
I
,
D
)
a,b
b,ω
0
b,ω
1
ω
1
,ω
2
ω
1
,ω
3
ω
3
,ω
4
ω
3
,ω
5
ω
5
,ω
6
...
...
with
π
2
(R
2
)
={
w
i
|
w
i
∈
SK
}
the infinite unary relations composed of the infinite
set of all Skolem constants.