Database Reference
In-Depth Information
DB
category morphism
α
∗
(
M
AB
)
={
f
1
,...,f
n
,q
⊥
}:
A
→
B
, where
A
=
α(S
A
)
A
=
is an instance-database of the schema
,
B
α(S
B
)
is an instance-database of the
schema
α(q
i
)
are the functions obtained from the operads, with the
domain equal to the Cartesian product of a subset of relations in the instance
A
and
the codomain is a relation in the instance
B
.
The functors such that, for every operad's operation
q
i
=
v
i
·
q
A,i
in each sketch's
mapping, the function
α(v
i
)
is an inclusion (injection) will define a
model
of the
schema database mapping system expressed by this sketch.
This is the principal idea for the
categorical semantics
of the schema database
mapping systems and will be discussed with more details in next two chapters.
B
, and
f
i
=
2.5
Algorithm for Decomposition of SOtgds
In this section, we will present an algorithm for decomposition of a given SOtgd into
two SOtgds. This decomposition will be used for the demonstration of the extended
symmetry properties of the database mappings at the instance-level (Sect.
3.2.3
in
Chap.
3
). Let us define this algorithm that transforms an SOtgd
Φ
of a given schema
mapping into two SOtgds
Φ
E
and
Φ
M
such that the composition of them is equiva-
lent to the original SOtgd
Φ
:
Decomposition algorithm
DeCompose(
M
AB
)
Input.
A schema mapping
M
AB
:
A
→
B
given by a SOtgd
Φ
.
f
∀
ψ
B,
1
)
∧···∧
∀
ψ
B,n
)
.
∃
x
1
(φ
A,
1
⇒
x
n
(φ
A,n
⇒
Output.
The pair
(Φ
E
,Φ
M
)
of SOtgds.
1. (
Normalize the SOtgd
)
Initialize
S
,
S
E
and
S
M
to be the empty sets (
∅
). Let
M
AB
be the singleton set
∃
f
∀
ψ
B,
1
)
∧···∧
∀
ψ
B,n
)
.
x
1
(φ
A,
1
⇒
x
n
(φ
A,n
⇒
Put each of
n
implications
φ
A,i
⇒
ψ
B,i
,for1
≤
i
≤
n
,into
S
.
Each implication
χ
in
S
has the form
φ
A,i
(
x
i
)
⇒∧
1
≤
j
≤
k
r
j
(
t
j
)
where every
variable in
x
i
is universally quantified, and each
t
j
,for1
k
, is a sequence
(tuple) of terms with variables in
x
i
. We then replace each such implication
χ
in
S
with
k
implications:
φ
A,i
(
x
i
)
≤
j
≤
⇒
r
1
(
t
1
),...,φ
A,i
(
x
i
)
⇒
r
k
(
t
k
)
.
2. (
Transformation into two new SOtgds
)
Let
S
be the set of implications obtained in the previous step.
Then for each implication
χ
i
, equal to the formula
q
Ai
(
x
i
)
={
χ
1
,...,χ
m
}
⇒
r
i
(
t
i
)
,doasfol-
lows:
2.1. Let
y
i
be the subset of variables
x
l
∈
x
i
that appear in some atom in
q
Ai
(i.e., of a relational symbol in
t
i
(i.e., when
r
i
(...,x
l
,...)
). If
y
i
is not empty then we add the implication
q
Ai
(
x
i
)
A
) and in the atom
r
i
(
t
i
)
as a variable
x
l
∈
r
q
i
(
y
i
)
in
S
E
, by introducing a new fresh symbol
r
q
i
; otherwise
we add the implication
q
Ai
(
x
i
)
⇒
⇒
r
if
y
i
in
S
E
.
∅
