Database Reference
In-Depth Information
(b) For the associative composition '
·
',
α
q
(q
1
,...,q
k
)
=
α(q)
α(q
1
)
α(q
k
)
·
×···×
(c) For any
q
∈
O(r
1
,...,r
k
,r)
and a permutation
σ
∈ R
k
,
α(qσ)
=
α(q)σ
,
where
σ
acts on the function
α(q)
on the right by permuting its arguments.
3. We introduce two functions
∂
0
and
∂
1
such that for any
α(q)
,
q
∈
O(r
1
,...,r
k
,r)
,
∂
0
(q)
={
r
1
,...,r
k
}
,
∂
0
(α(q))
=
α
∗
(∂
0
(q))
={
α(r
1
),...,α(r
k
)
}
,
∂
1
(q)
={
r
}
,
and
∂
1
(α(q))
=
α
∗
(∂
1
(q))
={
α(r)
}
.
α
∗
(S
A
)
of a schema
=
A
=
Remark
In what follows, an instance database
A
(S
A
,Σ
A
)
will be denoted by
α
∗
(
A
)
as well. The empty schema is denoted by
0
α
∗
(
A
∅
=
{
r
∅
}
∅
⊥
=
A
∅
)
=
(
,
)
so that for any
α
, from point 1 of this definition,
α
∗
(S
A
∅
)
={
}={⊥}
α(r
∅
)
is the empty instance-database.
Note that this empty database is the zero object of the
DB
category defined in
the next chapter, and this is the reason that in the computation of
α
∗
in point 1
of this definition we added
α(r
)
as well, so that we will have for each schema
∅
α
∗
(S
A
)
α
∗
(
A
=
)
.
Consequently, we can think of an operad as a simple sort of theory, used to define
a schema mapping between databases, and its R-algebras as models of this theory
used to define the mappings between instance-databases, where an R-algebra
α
is
considered as an interpretation of relational symbols of a given database schema.
For the empty operation 1
r
∅
∈
M
AB
of a mapping
(S
A
,Σ
A
)
that
α(r
)
=⊥∈
=
A
∅
M
AB
, we have, by Definition
10
,
that its interpretation is prefixed by the empty function
q
⊥
:⊥→⊥
, while for the
rest of operad's operations in
M
AB
we have to define their formal semantics. What
we need is to specify the subsets of R-algebras that contain well defined
mapping-
interpretations
for the operad's operations obtained from schema mappings by the
MakeOperads
algorithm. They are particular extensions of Tarski's interpretations
of the database mappings (when we eliminate the existential quantifiers over func-
tions from SOtgds of a given schema database mapping system then we obtain the
FOL with its Tarski's interpretations
I
T
, and their extensions
I
T
to all formulae
introduced in Sect.
1.3
) as follows:
Definition 11
Let
φ
Ai
(
x
)
⇒
r
B
(
t
)
be an implication
χ
in a normalized SOtgd
∃
f
(Ψ )
(where
Ψ
is an FOL formula) of the mapping
M
AB
,let
t
be a tuple of
terms with variables in
x
MakeOperads(
M
AB
)
be the
operad's operation of this implication obtained by
MakeOperads
algorithm, equal
to the expression
(e
⇒
(
_
)(
t
))
∈
O(r
1
,...,r
k
,r
B
)
, where
q
i
=
v
i
·
q
A,i
with
q
A,i
∈
O(r
1
,...,r
k
,r
q
)
and
v
i
∈
O(r
q
,r
B
)
such that for a new relational symbol
r
q
,
ar(r
q
)
=
=
x
1
,...,x
m
, and
q
i
∈
1.
Let
S
be an empty set and
e
[
(
_
)
n
/r
n
]
1
≤
n
≤
k
be the formula obtained from ex-
pression
e
where each place-symbol
(
_
)
n
is substituted by the relational symbol
r
n
for 1
ar(r
B
)
≥
≤
n
≤
k
. Then do the following as far as possible: For each two relational sym-
bols
r
j
,r
n
in the formula
e
[
(
_
)
n
/r
n
]
1
≤
n
≤
k
such that the
j
h
th
free variable
(which
