Database Reference
In-Depth Information
where
(
x
) is a conjunction of atomic formulae in R
t
,and
x
i
,
x
j
are variables among
those in
x
.
ϕ
One can observe that the mapping we used in
Chapter 1
follows this pattern. Equality-
generating dependencies generalize functional dependencies, and in particular keys. Tuple-
generating dependencies generalize inclusion constraints. For example, if we have a bi-
nary relation
R
1
, then the fact that the first attribute is a key is expressed by an egd
∀
y
=
y
). The fact that each element of a set
R
2
occurs as
the first attribute of
R
1
is expressed by a tgd
y
(
R
1
(
x
,
y
)
R
1
(
x
,
y
)
x
∀
y
∀
∧
→
∀
xR
2
(
x
)
→∃
yR
1
(
x
,
y
). Together these two
constraints form a foreign key.
For the sake of simplicity, we usually omit universal quantification in front of st-tgds,
tgds, and egds. Notice, in addition, that each (st-)tgd
ϕ
(
x
,
y
)
→∃
z
ψ
(
x
,
z
) is logically
equivalent to the formula (
(
x
,
z
)). Thus, when we use the notation
θ (
x
)
→∃
z
ψ(
x
,
z
) for a (st-)tgd, we assume that θ (
x
) is a formula of the form
∃
y
ϕ(
x
,
y
),
where
∃
y
ϕ
(
x
,
y
))
→
(
∃
z
ψ
(
x
,
y
) is a conjunction of atomic formulae.
Tgds without existential quantification on the right-hand side,
ϕ
i.e., of the form
∀
(
x
)), are called
full
.
From now on, and unless stated otherwise, we assume all relational mappings to be of
the restricted form specified above. Such mappings are not restrictive from the database
point of view. Indeed, tuple-generating dependencies together with equality-generating de-
pendencies precisely capture the class of
embedded
dependencies. And the latter class con-
tains all relevant dependencies that appear in relational databases; in particular, it contains
functional and inclusion dependencies, among others.
x
∀
y
(
ϕ
(
x
,
y
)
→
ψ
L
AV
and
G
AV
mappings
There are two classes of data exchange mappings, called
Local-As-View
(L
AV
)and
Global-
As-View
(G
AV
) mappings, that we will often use. Both classes have their origin in the
field of data integration, but have proved to be of interest for data exchange as well. Let
M
=(R
s
,
R
t
,
Σ
st
) be a relational mapping without target dependencies. Then:
1.
M
is a L
AV
mapping if
Σ
st
consists of L
AV
st-tgds of the form:
∀
x
(
U
(
x
)
→∃
z
ϕ
t
(
x
,
z
))
,
where
U
is a relation symbol in R
s
. That is, to generate tuples in the target, one needs a
single source fact. In
Example 4.1
, the first rule is of this shape.
2.
M
is a G
AV
mapping if
Σ
st
consists of G
AV
st-tgds of the form:
∀
x
(
ϕ
s
(
x
)
→
U
(
x
))
,
where
U
is a relation symbol in R
t
. That is, conjunctive query views over the source
define single facts in the target.
Both G
AV
and L
AV
mappings - as well as mappings defined by full (st-)tgds - will
be useful for us in two different ways. First, sometimes restricting our attention to one
