Database Reference
In-Depth Information
logic-syntax of (composed) schema mappings by SOtgds. However, we need a new
semantics for the mappings in order to define the (strict) equality between two map-
pings, different from the logical equivalence [ 5 ] used in data-exchange settings. The
data-exchange setting is only a particular case of our more general setting. Thus, in
our setting two logically equivalent schema-mappings are always equal at instance-
level as well. However, we can have equal mappings (at instance level) which are
not logically equivalent at schema level as it was presented by Example 2 . Thus,
in what follows, we will investigate this equality of mappings at the instance-level
between instance-databases, and the first step is to pass from logic to algebras and
hence to functorial semantics of database mappings.
2.4
Logic versus Algebra: Categorification by Operads
We consider that logical syntax for composition of schema mappings, represented
by SOtgds introduced in [ 5 ], is well suited for consideration of the logical syntax
and semantics of schema mappings, and we explained how SOtgds hide the rela-
tions of 'intermediate' databases by substituting them with existentially quantified
characteristic functions of such relations.
Another way, more closed to the functorial categorial representation, is to assume
an algebraic point of view for the representation of atomic and composed mappings.
It is possible because each conjunctive formula (a view) used on the left-hand side of
the implication forms of tgds can be equivalently represented by a term of SPJRU-
relational algebra. Any elementary (or atomic) mapping may be represented by a set
of these algebraic terms, while the composition of atomic mappings may be repre-
sented algebraically by the term-trees, or formally, by using the algebraic theory of
operads.
In what follows, we will use this algebraic point of view based on the oper-
ads, which is a more convenient than a standard Lindenbaum-like translation of the
second-order tgds logic into the algebraic categorial setting.
In what follows, we will work with the typed operads, first developed for ho-
motopy theory [ 1 , 3 , 7 ], having a set
of types (each finitary relation symbol is a
type), or “R-operads” for short. The basic idea of an R-operad O is that, given types
r 1 ,...,r k ,r
R
∈R
, there is a set O(r 1 ,...,r k ,r) of abstract k -ary “operations” with
inputs of type r 1 ,...,r k and output of type r . In short, an operad describes a family
of composable operations with multiple inputs and one output, satisfying several in-
tuitive properties like associativity of composition and permutability of the inputs.
The main difference from the universal algebra approach where R would be a car-
rier set and the operad's operations would compose the signature of such an algebra,
here we emphasize just the “operations” by treating them as a carrier set so that the
symbol of their composition '
' is just an operator of the R-operads signature.
Categorification is a process of finding category-theoretic analog of set-theoretic
concepts by introducing ' n -categories', i.e., algebraic structures having objects,
morphisms between objects, 2-morphisms between morphisms, and so on up to n -
morphisms. In [ 2 ], the existence of a close relation between n -categories and the
·
Search WWH ::




Custom Search