Database Reference
In-Depth Information
and we will define its complete signature
Σ
α
. Then we will demonstrate in Sect.
5.4
,
Theorem
9
and Corollary
19
, that such a
Σ
α
algebra (where
f
∈
O(r
1
,...,r
k
,r)
are
considered not as a carrier-set but as the set of composed operations in this algebra)
is computationally equivalent to the largest extension of the Codd's relational alge-
bra (which contains all update operations for the relations).
We consider an R-algebra in Definition
8
in the way where not the relations but
the operads
f
O(r
1
,...,r
k
,r)
constitute its carrier-set and hence it is similar to
the consideration of a category as a kind of algebra (see the introduction, Sect.
1.5.1
)
where the carrier set is composed of objects and arrows with the basic operation just
the associative composition '
∈
◦
' of the arrows, which is a partial function, as is the
·
associative operation '
' for the operads. This analogy (both with a composition with
the identity elements) is a natural justification for why we are using the interpreta-
tion of R-operads algebra in Definition
8
as a basis for the definition of the
DB
category for database-mappings.
Let us define the algorithm that transform an SOtgd into a set of abstract operads:
Operads algorithm
MakeOperads(
M
AB
)
M
AB
:
A
→
B
Input.
A schema mapping
givenbyanSOtgd
f
∀
ψ
B,
1
)
∧···∧
∀
ψ
B,n
)
.
∃
x
1
(φ
A,
1
⇒
x
n
(φ
A,n
⇒
Output.
Set of abstract operad's operations from
A
into
B
1. (
Normalize the SOtgd
)
Initialize
S
to be the empty set
∅
.Let
M
AB
be the singleton set
∃
f
∀
ψ
B,
1
)
∧···∧
∀
ψ
B,n
)
.
x
1
(φ
A,
1
⇒
x
n
(φ
A,n
⇒
For 1
ψ
B,i
into
S
if this implication is not a
ground formula. If
S
isemptygotostep4.
Each implication
χ
in
S
has the form
φ
A,i
(
x
i
)
≤
i
≤
n
, put the implication
φ
A,i
⇒
⇒∧
1
≤
j
≤
k
r
j
(
t
j
)
where every
member of
x
i
is a universally quantified variable and each
t
j
,for1
k
,isa
sequence (tuple) of terms over
x
i
. We then replace each such implication
χ
in
S
with
k
implications
φ
A,i
(
x
i
)
≤
j
≤
⇒
⇒
r
1
(
t
1
),...,φ
A,i
(
x
i
)
r
k
(
t
k
)
.
2. (
Reinsert the hidden relations
)
In each implication
φ
A,i
(
x
i
)
⇒
r
k
(
t
k
)
in
S
(obtained in the previous
s
tep), on
the left-hand side of this implication replace each equation
(f
r
(
y
i
)
.
=
1
)
, where
y
i
⊆
x
i
and
f
r
is the characteristic function of a hidden relational symbol
r/
∈
A
(introduced by the algorithm
Compose
), by the atom
r(
y
i
)
.
3. (
Transformation into operad's operations
)
Consider
S
with
χ
i
being a view-based query mapping (impli-
cation from conjunctive query over
={
χ
1
,...,χ
m
}
r
(
t
i
)
,
A
into a relation of
B
),
q
Ai
(
x
i
)
⇒
where
S
q
=
(r
i
1
,
1
,...,r
i
k
,k
)
is the ordered list of relational symbols as they ap-
pear (from left to right) in the conjunctive query
q
Ai
(
x
i
)
. Then replace each such
implication
χ
i
in
S
with the operad's operations
q
i
∈
O(r
i
1
,
1
,...,r
i
k
,k
,r
)
where
(r
i
1
,
1
,...,r
i
k
,k
)
=
S
q
and
q
i
is the expression obtained from
q
Ai
(
x
i
)
by replacing
