Databases Reference
In-Depth Information
3.
Each
i
is a conjunction of atomic formulas T.t
1
;:::;t
l
/,whereT is an l-ary
relation symbol of schema
T
and t
1
;:::;t
l
are terms based on
x
i
and
f
.
4.
Each variable in
x
i
appears in some atomic formula of
i
.
Composition algorithm for SO tgds.
We now illustrate the steps of the composition
algorithm using the schema mappings
M
0
in this section. For the complete
details of the algorithm, we refer the reader to
Fagin et al.
[
2005b
]. The first step of
the algorithm is to transform
M
and
M
0
into schema mappings that are specified
by SO tgds (if they are not already given as SO tgds). Each GLAV constraint can be
transformed into an SO tgd by skolemization, that is, by replacing each existentially
quantified variable by a Skolem term. For our example, we transform
M
and
M
into a
schema mapping specified by the following SO tgd:
9f.8e.
Emp
.e/ !
Reports
.e;f.e////:
Here, f is an existentially quantified function and the term f.e/replaces the earlier
existentially quantified variable M. The second mapping
M
0
needs no skolemiza-
tion since there are no existentially quantified variables. The corresponding SO tgd
for
M
0
is simply one with no existentially quantified functions and consisting of the
conjunction of the two constraints that specify
M
0
.
S
S
0
, to consist of all the implications of
After this, we initialize two sets,
and
M
M
0
.
the SO tgds in
and, respectively,
S
W
Emp
.e
0
/ !
Reports
.e
0
;f.e
0
//
S
0
W
Reports
.e;m/ !
Manager
.e;m/;
Reports
.e;e/ !
SelfMgr
.e/
Observe that the existential quantifiers of function symbols as well as the universal
quantifiers in front of the implications are omitted, for convenience. Additionally,
we have renamed the variables in
S
so that they are disjoint from the variables used
S
0
.
Next, for each implication in
in
S
0
, we consider each relational atom on the left-
hand side of the implication and replace that atom based on all the implications
in
whose right-hand side have an atom with the same relation symbol. For our
example, we will replace
Reports
(e,m) of the first implication in
S
S
0
using the sole
implication in
S
, whose right-hand side also has a
Reports
atom. Replacement
proceeds by equating the terms in corresponding positions of
Reports
e
0
, f.e
0
/
and
Reports
(e,m), and then adding the left-hand side of the implication in
.In
this case, we obtain the equalities e
0
D e and f.e
0
/ D m and we add the relational
atom
Emp
(e
0
). Hence, the first implication of
S
S
0
becomes:
1
W
Emp
.e
0
/ ^ .e
0
D e/ ^ .f.e
0
/ D m/ !
Manager
.e;m/:
S
23
Similarly, the second implication of
becomes:
2
W
Emp
.e
0
/ ^ .e
0
D e/ ^ .f.e
0
/ D e/ !
SelfMgr
.e/:
