Database Reference
In-Depth Information
Fig. 2.1
Operations of an
R-operad
homotopy theory is demonstrated, based on theory of operads. As we will see in our
case of
DB
category used for denotational semantics of database mappings, this
DB
category is an
n
-category as well, but with a particular property that each arrow can
be equivalently represented by an object (i.e., a categorial symmetry) and hence the
higher-order arrows are represented just by ordinary 1-arrows in
DB
. Basically, the
work presented in this topic is a categorification of the logic theory of the schema
database mappings.
Remark
In our case, the input types are the relational symbols of the source database
of a given schema mapping (represented logically by an SOtgd) while the output
type is a relational symbol of the target database. Each single abstract “operation” is
derived from a logical implication, whose left-hand side is a conjunctive query over
the source database schema, into a particular relation of the target database schema.
Thus, it represents an SPJRU term of the relational algebra corresponding to the
left-hand side (a conjunctive query, possibly with negations (in the case of integrity
constraints), over the source schema) of this implication, labeled by a node
q
on the
left tree (an operation) in Fig.
2.1
. In what follows, we will provide an algorithm
MakeOperads
that transforms a given SOtgd (of a given mapping from a source to
a target schema database) into the set of such abstract operations with input types in
the source schema and output types in the target schema.
We can visualize such an operation as a tree with only one node (a relational
symbol of the target schema). In an operad, we can obtain new operations from
old ones by composing them; it can be visualized in terms of trees in Fig.
2.1
.We
can obtain the new operators from old ones by permuting arguments, and there is a
unary “identity” operation of each type. Finally, we insist on a few plausible axioms:
the identity operations act as identities for composition, permuting arguments is
compatible with composition, and
composition is associative
. Thus, formally, we
have the following:
Definition 8
of relational symbols with finite arity (the predicate
letters in Definition
1
) an R-operad
O
consists of:
1. A set
O(r
1
,...,r
k
,r)
for any
r
1
,...,r
k
,r
∈R
For any set
R
and an element 1
r
∈
O(r,r)
for
any
r
∈R
. We denote the empty type by
r
∅
(the truth propositional letter in FOL,
Definition
1
), with
ar(r
∅
)
=
0 and 1
r
∅
∈
O(r
∅
,r
∅
)
.
2. An element
f
·
(g
1
,...,g
k
)
∈
O(r
11
,...,r
1
i
1
,...,r
k
1
,...,r
ki
k
,r)
for any
f
∈
O(r
1
,...,r
k
,r)
and any
g
1
∈
O(r
11
,...,r
1
i
1
,r
1
),...,g
k
∈
O(r
k
1
,...,r
ki
k
,r
k
)
.
