Database Reference
In-Depth Information
If for a tuple
d
=
d
1
,...,d
m
of values (in a given universe
U
, which defines
an assignment
g
:{
x
1
,...,x
m
}→
U
such that
g(x
j
)
=
d
j
,
1
≤
j
≤
m
), the sentence
φ
Ai
(
x
)/g
is true then
g
∗
(
t
)
is a tuple in the relation
α(r
B
)
∈
B
as it follows from
Proposition
2
.
Consequently, for the operad's operation
q
i
∈
O(r
1
,...,r
k
,r
B
)
obtained from
the implication
χ
, where
q
i
=
v
i
·
q
A,i
with
q
A,i
∈
O(r
1
,...,r
k
,r
q
)
and
v
i
∈
O(r
q
,r
B
)
, the function
f
=
α(q
A,i
)
:
R
1
×···×
R
k
→
α(r
q
)
is well defined for
each
d
i
∈
R
i
with
d
=
Cmp(S,
d
1
,...,
d
k
)
and, from Definition
11
,
f
d
1
,...,
d
k
=
g
∗
(
t
)
∈
α(r
q
),
with
α(v
i
)(g
∗
(
t
))
g
∗
(
t
)
=
∈
α(r
B
)
. Otherwise, if
φ
Ai
(
x
)/g
is false then
f(
d
1
,...,
d
k
)
=
, the empty tuple in the relation
α(r
q
)
, with
α(v
i
)(
)
=∈
α(r
B
)
.
Consequently, the function
α(v
i
)
:
α(r
q
)
→
α(r
B
)
is an injection.
Let us consider the case when an operad's operation is obtained from the integrity
constraints of a schema:
Example 12
r
(
0
,
1
)
be an implication
χ
in the SOtgd
obtained from the algorithm
EgdsToSOtgd
of a given egd
(φ
Ai
(
x
)
Let
(φ
Ai
(
x
)
∧
(
y
=
z
))
⇒
(
y
.
⇒
=
z
))
∈
Σ
A
of a schema
A
=
(S
A
,Σ
A
)
, with
{
r
1
,...,r
k
}⊆
S
A
the set of all relational symbols
of
A
that appear in the conjunctive formula
φ
Ai
(
x
)
and
y
=
x
j
1
,...,x
j
m
⊆
x
,
z
=
x
l
1
,...,x
l
m
⊆
x
, with
j
i
=
l
i
for 1
≤
i
≤
m
.
We recall that the formula
(
y
=
z
)
is an abbreviation for the disjunctive formula
(x
j
1
=
x
l
m
)
.
Then, by the algorithm
MakeOperads
, from this implication
χ
we obtain the
operad's operation
q
A,i
∈
x
l
1
)
∨···∨
(x
j
m
=
O(r
1
,...,r
k
,r
q
i
)
,
v
i
∈
O(r
q
i
,r
)
such
t
h
a
t
q
A,i
is the
expression obtained from the im
pl
i
c
ation
(φ
Ai
(
x
)
∧
(
y
=
z
))
⇒
r
q
i
(
0
,
1
)
, that is, the
expression
(e
(
_
)(
0
,
1
)
where
e
is the expression on the left-hand side
of the implication, obtained from the formula
φ
Ai
(
x
)
, where each relational symbol
r
m
is replaced by a place symbol
(
_
)
m
,for1
∧
(
y
=
z
))
⇒
≤
m
≤
k
. Thus:
1. If the integrity condition, given by the egd
.
=
∀
x
(φ
Ai
(
x
)
⇒
(
y
z
))
, is satisfied
then
φ
Ai
(
x
)
z
)
is false for each assignment
g
to variables in
x
. Thus, from
Definition
11
for the mapping-interpretation
α
, for each
∧
(
y
=
d
1
,...,
d
k
∈
×
α(r
1
)
···×
α(r
k
)
,
α(q
A,i
)(
d
1
,...,
d
k
)
=
so that
α(q
A,i
)
is a constant function
and
α(r
q
i
)
={}
and hence
α(v
i
)(
)
=∈
α(r
)
=
R
. Consequently, the
=
function
α(v
i
)
is an injection.
2. If this integrity constraint
is not
satisfied then there exists a tuple
d
which de-
fines an assignment
g
for the variables in
x
with
d
y
=
g
∗
(
y
)
=
d
j
1
,...,d
j
m
and
d
z
=
g
∗
(
z
)
=
d
l
1
,...,d
l
m
such that
φ
Ai
(
x
)/g
∧
(
d
y
=
d
z
)
is true. That
is, there exist at least one index 1
≤
i
≤
m
such that
d
j
i
=
d
l
i
and for the op-
erad's operation
q
i
=
v
i
·
q
A,i
(the expression
e
⇒
(
_
)(
0
,
1
)
), from Definition
11
,
d
1
,...,
d
k
∈
×···×
=
d
1
,...,
d
k
for
α(r
1
)
α(r
k
)
such that
d
Cmp(S,
)
and
{
π
j
h
(
d
j
)
=
π
n
h
(
d
n
)
|{
(j
h
,j),(n
h
,n)
}∈
S
}
is true,
α(q
A,i
)(
d
1
,...,
d
k
)
=
g
∗
(
0
,
1
)
=
g(
0
),g(
1
)
=
0
,
1
∈
α(r
q
i
)
and hence
α(v
i
)(
0
,
1
)
=
(be-
cause
0
,
1
∈
/
α(r
)
=
R
). Consequently, the function
α(v
i
) is not
an injection.
=