Databases Reference
In-Depth Information
2.
We now go round the inner loop four times, once for each of the given FDs. On the first iteration (for the FD
A
→
BC
), we find that the determinant
A
is indeed a subset of
AB
+
as computed thus far, so we add attributes
(
B
and)
C
to the result.
AB
+
is now the set
ABC
.
3.
On the second iteration (for the FD
E
→
CG
), we find that the determinant
E
is
not
a subset of the result as
computed so far, which thus remains unchanged.
On the third iteration (for the FD
B
→
E
), we add
E
to
AB
+
, which thus now has the value
ABCE
.
4.
On the fourth iteration (for the FD
CD
→
EG
),
AB
+
remains unchanged.
5.
6.
Now we go round the inner loop four times again. On the first iteration, the result remains unchanged; on the
second, it expands to
ABCEG
; on the third and fourth, it remains unchanged.
7.
Now we go round the inner loop four times again. The result remains unchanged, and so the whole process
terminates, with
AB
+
=
ABCEG
.
Well, I hope you can see from this example that computing
Z
+
given
H
,
F
, and
Z
is essentially
straightforward. And the important thing is this: Given some set
F
of FDs (with respect to some heading
H
), we
can easily tell whether some specific FD
X
→
Y
(with respect to that same heading
H
) is implied by
F
, because it
will be so if and only if
Y
is a subset of the closure
X
+
of
X
under
F
. In other words, we now have a simple way of
determining whether a given FD
X
→
Y
is in the closure
F
+
of
F
without actually having to compute
F
+
.
It also follows from the definition (of closure of a set of attributes) that the superkeys for a relvar
R
are
precisely those subsets
SK
of the heading of
R
such that the closure
SK
+
of
SK
—under the pertinent set of FDs—is
the entire heading of
R
.
EXERCISES
7.1
What does it mean to say that Armstrong's rules are sound? Complete?
7.2
What's the closure of a set of FDs? Show the closure of the set of FDs that hold in the shipments relvar SP.
7.3 Given the definition of what it means for an FD to be satisfied, show that the reflexivity, augmentation, and
transitivity rules are reasonable.
7.4 (
Try this exercise without referring back to the body of the chapter.
) Prove that the three rules of the
previous exercise imply the self determination, union, composition, and decomposition rules.
The following theorem is due to Hugh Darwen:
5
7.5
If
X
→
Y
and
Z
→
W
, then
XV
→
YW
, where
V
=
Z
-
Y
.
5
Hugh Darwen: “The Role of Functional Dependence in Query Decomposition,” in C. J. Date and Hugh Darwen,
Relational Database Writings
1989-1991
(Addison-Wesley, 1992).
