C H A P T E R8
Relational Databa Design
Exercis
8.1Suppo that we decompo the schema R=(A,B,C,D,E)into
(A,B,C)
(A,D,E).
Show that this decomposition is a lossless-join decomposition if the
following t F of functional dependencies holds:
A→BC
CD→E
B→D
烟草物流
E→A
Answer:A decomposition{R1,R2}is a lossless-join decomposition if
R1∩R2→R1or R1∩R2→R2.Let R1=(A,B,C),R2=
(A,D,E),and R1∩R2=A.Since A is a candidate key(e Practice
Exerci8.6),Therefore R1∩R2→R1.
8.2List all functional dependencies satisfied by the relation of Figure8.17.
Answer:The nontrivial functional dependencies are:A→B and
C→B,and a dependency they logically imply:AC→B.There are
辛巴历险记19trivial functional dependencies of the form␣→,where⊆␣.C
does not functionally determine A becau thefirst and third tuples have
the same C but different A values.The same tuples also show B does not
functionally determine A.Likewi,A does not functionally determine
C becau thefirst two tuples have the same A value and different C
values.The same tuples also show B does not functionally determine C.
8.3Explain how functional dependencies can be ud to indicate the fol-
lowing:
9
10Chapter8Relational Databa Design
•A one-to-one relationship t exists between entity ts student and
instructor.
•A many-to-one relationship t exists between entity ts student
and instructor.
生态危机
Answer:Let Pk(r)denote the primary key attribute of relation r.
•The functional dependencies Pk(student)→Pk(instructor)and
Pk(instructor)→Pk(student)indicate a one-to-one relationship
becau any two tuples with the same value for student must have
the same value for instructor,and any two tuples agreeing on
instructor must have the same value for student.
•The functional dependency Pk(student)→Pk(instructor)indicates a
many-to-one relationship since any student value which is repeated
will have the same instructor value,but many student values may
have the same instructor value.
8.4U Armstrong’s axioms to prove the soundness of the union rule.(Hint:
U the augmentation rule to show that,if␣→,then␣→␣.Apply the
augmentation rule again,using␣→␥,and then apply the transitivitydie的各种形式
rule.)
Answer:To prove that:
if␣→and␣→␥then␣→␥
Following the hint,we derive:
␣→given
␣␣→␣augmentation rule
␣→␣union of identical ts
␣→␥given
␣→␥augmentation rule
␣→␥transitivity rule and t union commutativity
8.5U Armstrong’s axioms to prove the soundness of the pudotransitiv-
ity rule.
斯大林怎么死的
Answer:Proof using Armstrong’s axioms of the Pudotransitivity Rule:
if␣→and␥→␦,then␣␥→␦.
␣→given
␣␥→␥augmentation rule and t union commutativity
␥→␦given
␣␥→␦transitivity rule
8.6Compute the closure of the following t F of functional dependencies
for relation schema R=(A,B,C,D,E).
Exercis 11
A →BC
CD →E
B →D
E →A
List the candidate keys for R .Answer:Note:It is not reasonable to expect students to enumerate all of F +.Some shorthand reprentation of the result should be acceptable as long as the nontrivial members of F +are found.
Starting with A →BC ,we can conclude:A →B and A →C .
Since A →B and B →D ,A →D (decomposition,
transitive)Since A →C D and C D →E ,A →E (union,decom-position,transi-tive)
Since A →A ,we have (reflexive)A →ABC DE from the above steps (union)
Since E →A ,E →ABC DE (transitive)
Since C D →E ,C D →ABC DE (transitive)Since B →D and BC →C D ,BC →ABC DE (augmentative,transitive)Also,C →C ,D →D ,B D →D ,etc.
Therefore,any functional dependency with A ,E ,BC ,or C D on the left hand side of the arrow is in F +,no matter which other attributes appear in the FD.Allow *to reprent any t of attributes in R ,then F +is B D →B ,B D →D ,C →C ,D →D ,B D →B D ,B →D ,B →B ,B →B D ,and all FDs of the form A ∗→␣,BC ∗→␣,C D ∗→␣,E ∗→␣where ␣is any subt of {A ,B ,C ,D ,E }.The candidate keys are A ,BC ,C D ,and E .
幼儿活动
8.7Using the functional dependencies of Practice Exerci 8.6,compute the
北京周口店canonical cover F c .Answer:The given t of FDs F is:-
A →BC
CD →E
B →D
E →A
The left side of each FD in F is unique.Also none of the attributes in the left side or right side of any of the FDs is extraneous.Therefore the canonical cover F c is equal to F .
12Chapter8Relational Databa Design
8.8Consider the algorithm in Figure8.18to compute␣+.Show that this
algorithm is more efficient than the one prented in Figure8.8(Sec-
tion8.4.2)and that it computes␣+correctly.
Answer:The algorithm is correct becau:
•If A is added to result then there is a proof that␣→A.To e this,
obrve that␣→␣trivially so␣is correctly part of result.If
A∈␣is added to result there must be some FD→␥such that
A∈␥andis already a subt of result.(Otherwi f dcount
would be nonzero and the if condition would be fal.)A full proof
can be given by induction on the depth of recursion for an execution
of addin,but such a proof can be expected only from students with
a good mathematical background.
•If A∈␣+,then A is eventually added to result.We prove this by
induction on the length of the proof of␣→A using Armstrong’s
axioms.First obrve that if procedure addin is called with some
argument,all the attributes inwill be added to result.Also if a
韵母ei怎么读particular FD’s fdcount becomes0,all the attributes in its tail will
definitely be added to result.The ba ca of the proof,
A∈␣⇒A∈␣+,is obviously true becau thefirst call to addin
has the argument␣.The inductive hypothes is that if␣→A can
be proved in n steps or less then A∈result.If there is a proof in
n+1steps that␣→A,then the last step was an application of
either reflexivity,augmentation or transitivity on a fact␣→
proved in n or fewer steps.If reflexivity or augmentation was ud
in the(n+1)st step,A must have been in result by the end of the n th
step itlf.Otherwi,by the inductive hypothesis⊆result.
Therefore the dependency ud in proving→␥,A∈␥will
have f dcount t to0by the end of the n th step.Hence A will be
added to result.
To e that this algorithm is more efficient than the one prented in
the chapter note that we scan each FD once in the main program.The
resulting array a ppears has size proportional to the size of the given
FDs.The recursive calls to addin result in processing linear in the size
of a ppears.Hence the algorithm has time complexity which is linear in
the size of the given FDs.On the other hand,the algorithm given in the
text has quadratic time complexity,as it may perform the loop as many
times as the number of FDs,in each loop scanning all of them once.
8.9Given the databa schema R(a,b,c),and a relation r on the schema R,
write an SQL query to test whether the functional dependency b→c
holds on relation r.Also write an SQL asrtion that enforces the func-
tional dependency.Assume that no null values are prent.(Although
part of the SQL standard,such asrtions are not supported by any
databa implementation currently.)
Answer:
Exercis13
a.The query is given below.Its result is non-empty if and only if
b→c does not hold on r.
lect b
from r
group by b
having count(distinct c)>1
b.
create asrtion b to c check
(not exists
(lect b
from r
group by b
having count(distinct c)>1
)
)
8.10Our discussion of lossless-join decomposition implicitly assumed that
attributes on the left-hand side of a functional dependency cannot take on null values.What could go wrong on decomposition,if this property is violated?
Answer:The natural join operator is defined in terms of the cartesian product and the lection operator.The lection operator,gives unknown for any query on a null value.Thus,the natural join excludes all tuples with null values on the common attributes from thefinal result.Thus, the decomposition would be lossy(in a manner different from the usual ca of lossy decomposition),if null values occur in the left-hand side of the functional dependency ud to decompo the relation.(Null values in attributes that occur only in the right-hand side of the functional dependency do not cau any problems.)
8.11In the BCNF decomposition algorithm,suppo you u a functional de-
pendency␣→to decompo a relation schema r(␣,,␥)into r1(␣,) and r2(␣,␥).
a.What primary and foreign-key constraint do you expect to hold
on the decompod relations?
b.Give an example of an inconsistency that can ari due to an
erroneous update,if the foreign-key constraint were not enforced
on the decompod relations above.
c.When a relation is decompod into3NF using the algorithm in
Section8.5.2,what primary and foreign key dependencies would
you expect will hold on the decompod schema?
