Database Reference
In-Depth Information
4
Functorial Semantics for Database Schema
Mappings
4.1
Theory: Categorial Semantics of Database Schema
Mappings
A relational database schema
is generally specified by a pair
(S
A
,Σ
A
)
, where
S
A
is a set of
n
-ary relation symbols,
Σ
A
=
A
Σ
eg
A
with a set of the database in-
tegrity constraints expressed by
equality-generating dependencies
(egds)
Σ
egd
A
Σ
tg
A
∪
and
a set of the
tuple-generating dependencies
(
tgds
)
Σ
tgd
A
introduced by Definition
2
.
Note that any atomic inter-schema database
mapping
from a schema
A
into a
schema
B
is represented by a
set
of general tgds
∀
x
(φ
A
(
x
))
⇒∃
z
(ψ
B
(
y
,
z
))
where
⊆
∀
y
x
from the head of each tgd
sentence, that is, by the open (with free variables)
view mapping
formulas
q
A
(
x
)
x
, with elimination of the universal quantification
⇒
q
B
(
y
)
where
q
A
(
x
)
(equivalent to
φ
A
(
x
)
) is a conjunctive query over the schema
A
and
q
B
(
y
)
(equivalent to
(
.
In Sect.
2.6
, we explained what the models of the schema mappings based on tgds
and of the integrity-constraint schema mappings are. We have demonstrated that a
set of tgds can be equivalently represented by a single SOtgd (by Skolemization of
existential quantifiers on the right-hand side implications of tgds) and how the set
of integrity constraints of a database schema can be equivalently represented by a
single SOtgd (by the algorithms
TgdsToConSOtgd
and
EgdsToSotgd
in Sect.
2.2
).
Moreover, in order to translate this particular second-order logic (based on SOt-
gds sentences) into the categorial setting, we explained how we can translate the
SOtgds into the set of abstract operad's operations that specify a mapping between
database schemas, and hence to use the functorial semantics for database mappings
based on R-algebras for operads (in Sect.
2.4
).
Based on this translation into operads, we have seen that each operad's opera-
tion
q
i
∈
∃
z
ψ
B
(
y
,
z
))
) is a conjunctive query over the schema
B
O(r
1
,...,r
m
,r)
, obtained from an
atomic
mapping (introduced in Defini-
tion
7
), is an algebraic specification for an implication conjunct in a normalized
SOtgd such that
∂
0
(q
i
)
={
r
1
,...,r
m
}⊆
S
A
is a subset of relations of a source
schema
A
=
(S
A
,Σ
A
)
and
∂
1
(q
i
)
={
r
}
is a singleton set with a relation
r
∈
S
B
of a target schema
B
=
(S
B
,Σ
B
)
. Consequently, the representation of a database
