Database Reference
In-Depth Information
We have demonstrated that a set of tgds of a given inter-schema mapping can
be equivalently represented by a single SOtgd (by the algorithm
TgdsToSOtgd
).
A relational database schema
is generally specified by a pair
(S
A
,Σ
A
)
where
S
A
is a set of
n
-ary relational symbols,
Σ
A
=
Σ
tgd
A
A
∪
Σ
egd
with the set of the
A
database integrity constraints
Σ
egd
A
expressed by
equality-generating dependencies
(egds) and the set of the
tuple-generating dependencies (tgds) Σ
tgd
A
in Definition
2
.
(
y
.
∀
⇒
=
Any integrity constraint (egd)
x
(φ
A
(
x
)
z
))
of a given schema database
A
=
y
1
,...,y
k
⊆
=
z
1
,...,z
k
⊆
, with
y
x
and
z
x
, w
ill be represented
∀
∧
=
⇒
(Lemma
3
) by the new mapping
x
((φ
A
(
x
)
(
y
z
))
r
(
0
,
1
))
(from Lemma
3
),
where
r
is the built-in binary relational symbol for equality of FOL. The interpre-
tation of this mapping is the same as for the standard inter-schema mappings:
When
φ
A
(
x
)
∧
=
z
)
is true for a tuple of values
d
, from the fact that the gr
ound
atom
r
(
0
,
1
)
is a false, it holds that the mapping
(φ
A
(
x
)
(
y
∧
=
⇒
r
(
0
,
1
)
is not satisfied. It is easy to see that if the instance-database
A
is a
model
of the
schema
(
y
z
))
(i.e., when the integrity constraints expressed by the corresponding egds
are satisfied) then
q
A
(
x
)
A
z
)
cannot be satisfied. The “transferred” information
flux by this mapping (from
A
into the built-in relational symbol
r
∧
(
y
=
) is always empty
0
(i.e., equal to the empty database
).
Analogously, any normalized tgd of an integrity constraint
⊥
={⊥}
x
(φ
A
(
x
)
⇒
r(
t
))
where
t
is a tuple of terms with variables in
x
and
r
is a relational symbol of
schema
∀
x
((φ
A
(
x
)
∧
¬
r(
t
))
⇒
r
(
0
,
1
))
. It is easy to see that if the instance-database
A
is a
model
of
the schema
A
, ca
n
b
e
equivalently represented (Lemma
2
) by the formula
∀
(i.e., when the integrity constraints expressed by the corresponding
tgds are satisfied) then
q
A
(
x
)
∧
r(
t
)
cannot be satisfied. The “transferred” informa-
tion flux by this mapping (from
A
into the built-in relational symbol
r
A
) is always
0
empty (i.e., equal to the empty database
).
It is consistent with the representation of the integrity constraints (both egds and
tgds) by the inter-schema mappings because the sentences as integrity-constraints
do not transfer any data from source to target database and hence their informa-
tion flux has to be empty. Note that in the case of ordinary query mappings, the
minimal information flux is
⊥
={⊥}
0
{⊥}=⊥
as well. We have demonstrated that a set of
tgds in
Σ
tgd
A
can be equivalently represented by a single SOtgd (by the algorithm
TgdsToConSOtgd
in Sect.
2.2.1
) and that a set of egds in
Σ
egd
A
can be equivalently
represented by a single SOtgd (by the algorithm
EgdsToSOtgd
in Sect.
2.2.2
).
Moreover, in order to translate this particular second-order logic (based on SOt-
gds sentences) into the categorial setting, we explained how we can translate the
SOtgds into the set of abstract operad's operations that specify a mapping be-
tween database schemas and hence to use the functorial semantics for the database
mappings based on R-algebras for operads (provided in the previous Sect.
2.4
).
Based on this translation into operads, we have seen that each operad's operation
q
i
∈
O(r
1
,...,r
m
,r)
obtained from an
atomic
mapping (Definition
7
) is an alge-
braic specification for an implication conjunct in a normalized SOtgd.
Based on these considerations and Example
12
for the integrity constraints, we
will formally define a graph used to specify a database schema-mapping system: