Database Reference
In-Depth Information
if an instance satisfies a formula then every isomorphic instance also satisfies that
formula.
This is a mild condition that is true for all standard logical formalisms, such as
first-order logic, second-order logic, fixed-point logics, and infinitary logics.
Thus, such formulae represent the queries in the sense of Chandra and Harel
[
12
]. An immediate consequence of this property is that
Inst(
M
)
is closed under
isomorphism.
Remark 1
Differently from [
22
,
43
,
64
], each formula in
contains the relational
symbols of both source and target schema (the integrity constraints are contained
in their schemas), in order to represent an inter-schema mapping graphically as a
graph edge
M
M
AB
:
A
→
B
as in standard mathematical denotation of a mapping.
The problem of computing semantic mappings [
5
,
22
,
23
,
43
,
63
,
67
], given a
semantic mapping
M
AB
between data schemas
A
and
B
, and
M
BC
between
B
and
C
, generally was to answer if it is possible to generate a direct semantic mapping
M
AC
(possibly in the same logic language formalism) between
that is
“equivalent” to the original mappings. Here “equivalent” means that for any query
in a given class of queries
Q
and for any instance of data sources, using the direct
mapping yields exactly the same answer that would be obtained by the two original
mappings [
43
].
The semantics of the composition of the schema mappings proposed by Mad-
havan and Halevy [
43
] was a significant first step. However, it suffers from certain
drawbacks that are caused by the fact that this semantics is given relative to a class
of queries. In this setting, the set of formulae specifying a composition
A
and
C
M
AC
of
M
AB
and
M
BC
relative to a class
Q
of queries need not be unique up to logical
equivalence, even when the class
Q
of queries is held fixed.
It was shown [
22
] that this semantics is rather fragile because a schema mapping
M
AC
may be a composition of
M
BC
when
Q
is the class of conjunctive
queries, but may fail to be a composition of these two (inter-)schema mappings
when
Q
is the class of conjunctive queries with inequalities.
Using these results, a proper theory of composition of schema mappings, based
on Second-Order tgds, will be developed in Chap.
2
.
M
AB
and
1.5
Basic Category Theory
Category theory is an area of mathematics that examines in an abstract way the
properties of particular mathematical concepts, by formalizing them as collections
of objects and arrows (also called morphisms, although this term also has a specific,
non-category-theoretic sense), where these collections satisfy certain basic condi-
tions. Many significant areas of mathematics can be formalized as categories, and
the use of category theory allows many intricate and subtle mathematical results in
these fields to be stated, and proved, in a much simpler way than without the use of
categories.
