Database Reference
In-Depth Information
There is an obvious inverse transformation of a given mapping-operad (a set of
k
-
ary operations)
M
AB
={
q
1
,...,q
n
,
1
r
∅
}:
A
→
B
, into the SOtgd of this mapping.
Inverse operads algorithm
InverseOperads(
M
AB
)
Input.
A mapping-operad
M
AB
={
q
1
,...,q
n
,
1
r
∅
}:
A
→
B
.
Output.
Mapping
represented by the SOtgd.
1. (
Transform operads into logical formulae
)
Initialize
S
to be the empty set
M
AB
from
A
into
B
.
For each
k
-ary mapping operad's operation
q
i
∈
∅
O(r
i,
1
,...,r
i,k
,r
)
,for1
≤
i
x
i
φ
i
where
x
i
is the tuple
of all variables in the expression of the operad's operation
q
i
and
φ
i
is the logical
formula where each labeled place symbol
(
_
)
m
,for1
≤
n
, such that
q
i
=
1
r
∅
, add in
S
the logical sentence
∀
k
, is replaced by
the relational symbol
r
i,k
and each unlabeled place symbol
(
_
)
is replaced by
r
∈
B
≤
m
≤
.
2. (
Elimination of relational symbols not in
A
)
r
(
t
i
)
,onthe
left-hand side of this implication
r
eplace each atom
r(
y
i
)
with
r/
In each formula
∀
x
i
φ
i
∈
S
where
φ
is an implication
φ
A,i
(
x
i
)
⇒
∈
A
, where
x
i
, by the equation
(f
r
(
y
i
)
.
y
i
⊆
=
1
)
, where
f
r
is the characteristic function of a
∈
A
hidden relational symbol
r/
.
3. (
Construct
SOtgd)
TheSOtgdisaformula
Φ
equal to
r
∅
⇒
r
∅
x
n
φ
n
)
otherwise, where
f
is the tuple of all functional symbols in the formulae in
S
.
Return
the logical mapping
if
S
is empty;
∃
f
(
∀
x
1
φ
1
∧···∧∀
M
AB
={
Φ
}:
A
→
B
.
Consequently, the algebraic formalism based on the mapping-operads is equiva-
lent to the logical formalism based on SOtgds.
Example 8
Let us consider the following example (corresponding to Example 4.3
in [
5
]) that explains in detail the transformation of the logic into R-algebras, that is,
the transformation of logical formulae used to define a schema mapping into the set
of abstract operad's operations and their R-algebras.
Schema
)
consists of a unary relation
EmpAcme
that represents the
employees of Acme, a unary relation
EmpAjax
that represents the employees of
Ajax, and a unary relation
Local
that represents employees that work in the local
office of their company. Schema
A
=
(S
A
,
∅
)
consists of a unary relation
Emp
that
represents all employees, a unary relation
Local1
that is intended to be a copy
of
Local
, and a unary relation
Over65
that is intended to represent people over
age 65. Schema
B
=
(S
B
,
∅
C
=
(S
C
,
∅
)
consists of a binary relation
Office
that associates
employees with office numbers and a unary relation
CanRetire
that represents
employees eligible for retirement. Consider now the following schema mappings:
M
AB
=
∀
x
e
EmpAcme
(x
e
)
⇒
Emp
(x
e
)
x
e
EmpAjax
(x
e
)
⇒
Emp
(x
e
)
∧∀
x
p
Local
(x
p
)
⇒
Local1
(x
p
)
,
∧∀