Database Reference
In-Depth Information
where
q
A
(
x
)
is a conjunction of atomic formulae over a given database schema,
and
y
are among the variables in
x
, and
y
.
=
y
1
,...,y
k
,
z
=
z
1
,...,z
k
=
z
is
.
=
.
=
∧···∧
a shorthand for the formula
(y
1
z
1
)
(y
k
z
k
)
with the built-in binary
identity predicate
.
=
of the FOL.
Note that a tgd
∀
x
(
∃
y
φ
A
(
x
,
y
)
⇒∃
z
ψ
A
(
x
,
z
))
is logically equivalent to the for-
mula
∀
x
∀
y
(φ
A
(
x
,
y
)
⇒∃
z
ψ
A
(
x
,
z
))
, i.e., to
∀
x
1
(φ
A
(
x
1
)
⇒∃
z
ψ
A
(
x
,
z
))
with the set
of distinguished variables
x
x
1
.
We will use for the integrity constraints
Σ
A
of a database schema
⊆
A
both tgds
and egds, while for the inter-schema mappings, between a schema
A
=
(S
A
,Σ
A
)
and a schema
B
=
(S
B
,Σ
B
)
, only the tgds
∀
x
(q
A
(
x
)
⇒
q
B
(
x
))
, as follows:
Definition 3
An elementary schema mapping is a triple
(
A
,
B
,
M
)
where
A
and
B
are schemas with no relational symbol in common and
M
is a set of
tgds
q
B
(
x
))
, such that
q
A
(
x
)
is a conjunctive query with conjuncts
equal to relational symbols in
S
A
or to a formula with built-in relational symbols,
∀
x
(q
A
(
x
)
⇒
.
=
,<,>,...
), while
q
B
(
x
)
is a conjunctive query with relational symbols in
S
B
.
An instance of
M
is an instance pair
(A,B)
(where
A
is an instance of
A
and
B
is an instance of
B
) that satisfies every tgds in
M
, denoted by
(A,B)
|=
M
AB
.We
write
Inst(
M
)
to denote all instances
(A,B)
of
M
.
Notice that the formula with built-in predicates, in the left side of implication of
a tgd, can be expressed by only two logical connectives, conjunction and negation,
from the fact that implication and disjunction can be reduced to equivalent formulae
with these two logical connectives.
Recall that in data exchange terminology,
B
is a solution for
A
under
M
if
(A,B)
∈
Inst(
M
)
, and that an instance of
M
satisfies all FOL formulae in
Σ
A
∪
Σ
B
∪
M
.
For a given set of FOL formulas
S
, we denote by
S
the conjunction of all
formulae in the set
S
.
Lemma 1
For any given Tarski's interpretation I
T
that is a model of the schemas
A
=
B
=
M
(S
A
,Σ
A
) and
(S
B
,Σ
B
) and of the set of tgds in the mapping
,
that is
,
when I
T
(
Σ
A
)
I
T
(
Σ
B
)
I
T
(
M
=
=
)
=
1,
one has (
{
I
T
(r)
|
r
∈
S
A
}
,
{
I
T
(r)
|
r
)
.
Proof
Due to the fact that
I
T
(
Σ
A
)
=
∈
S
B
}
)
∈
Inst(
M
1 means that all integrity constraints of
A
are satisfied, one has that
A
={
I
T
(r)
|
r
∈
S
A
}
is an instance (model) of
A
.The
same holds for the schema
B
, so that
B
={
I
T
(r)
|
r
∈
S
B
}
is an instance of
B
.
From the fact that
I
T
(
M
)
=
1, each tgd
φ
∈
M
AB
is satisfied, i.e.,
I
T
(φ)
=
1,
and hence
(A,B)
|=
M
, i.e.,
(A,B)
∈
Inst(
M
)
.
The formulae (tgds) in the set
M
express the constraints that an instance
(A,B)
over the schemas
must satisfy. We assume that the satisfaction relation
between formulae and instances is preserved under isomorphism, which means that
A
and
B
