Database Reference
In-Depth Information
T
Eval(t
RA
)
Eval
t
RA
=
∪
Eval
t
RA
.
=
Eval(t
RA
)
⊕
5.3
Relational Algebra and Database Schema Mappings
In what follows, we will demonstrate that all relational algebra operations over the
databases correspond to a specific subclass of inter-schema mappings, and hence
every update of a given database schema can be equivalently represented as a com-
posed inter-schema mapping.
Proposition 26
Every term t
R
∈
T
RE
with the relational symbols
(
i
.
e
.,
the vari-
ables
)
of a given database schema
A
such that it is an update of a given relation or
an extraction of a view of this database can be represented by a composed database
schema mapping
M
={
Φ
}:
A
→
A
.
Proof
From the completeness of
RA
(Proposition
23
), we obtained the reduction
Rd
RE
:
T
RE
→
Mor
RA
such that, for a given schema
A
=
(S
A
,Σ
A
)
,aterm
t
R
∈
T
RE
is reduced to the arrow
f
:
t
RA
→
f(t
RA
)
such that
t
R
#
=
f(t
RA
)
#
, where
t
RA
=
t
1
⊗···⊗
t
m
with
t
i
∈
r
i
,
...
r
i
a
i
1
, name
i
1
,e
i
1
...
a
ik
, name
ik
,e
ik
,
i
∈
S
A
,
for 1
≤
i
≤
m
. Each term
t
i
=
(...(r
i
a
i
1
, name
i
1
,e
i
1
)...)
a
ik
, name
ik
,e
ik
can
be represented by the SOtgd
Ψ
i
equal to
x
i
r
i
(
x
i
)
r
i
x
i
&
e
i
1
(
x
i
),...,e
ik
(
x
i
)
,
∀
⇒
where each
e
ij
(
x
i
)
,for1
k
, is an expression (i.e., a function, usually
nullary function (constant)) with the variables in
x
i
=
(x
i
1
,...,x
il
)
, and
ar(r
i
)
=
l,ar(r
i
)
=
l
+
k
.
Hence,
≤
j
≤
r
i
|
ar(r
i
)
A
1
=
{
r
i
|
t
i
=
r
i
∈
t
RA
}∪{
=
we
define
the
schema
(
+
k,
for
t
i
=
(...(r
i
a
i
1
, name
i
1
,e
i
1
a
ik
, name
ik
,e
ik
∈
t
RA
}
∅
ar(r
i
)
)...)
,
)
, and
the schema
Σ
r
∈
A
1
ar(r)
, so that the construction of
t
RA
is defined by the composition of schema mappings:
B
0
=
(
{
r
t
0
}
,
∅
)
with
ar(r
t
0
)
=
M
A
1
B
0
◦
M
AA
1
:
A
→
B
0
,
(5.4)
(
r
i
∈
A
1
Ψ
i
)
(
r
i
∈
A
i
∀
M
AA
1
={
∧
⇒
}:
A
→
A
1
and
where
x
i
(r
i
(
x
i
)
r
i
(
x
i
)))
M
A
1
B
0
={
where
Φ
is the SOtgd for the Cartesian product of the relations in
A
1
(see point 2 in Sect.
5.1
).
Let
f
Φ
}
k
the unary algebraic operators in
Σ
RA
.
Then, from the proof of Proposition
24
, each
o
i
can be expressed by an SOtgd
Φ
i
,
thus by an inter-schema mapping
=
o
k
◦···◦
o
2
◦
o
1
, with
o
i
,
1
≤
i
≤
M
B
i
−
1
B
i
:
B
i
−
1
→
B
i
, with
B
i
=
(
{
r
t
i
}
,
∅
)
and
ar(r
t
i
)
≥
1 is the arity of the relation
o
i
(r
t
i
−
1
)
#
,for
i
=
1
,...,k
. Consequently,