CSE 444

Homework 5 Solutions

15.8

  1. A resulting join is lossless if for every instance r of R
  2. P AB(r) JN P BC(r) = r, or R1 JN R2 = R

    (see page 413)

  3. The possible tuples for R are {(5,1,9), (5,1,8), (6,1,8), (6,1,9)}. We can't say which tuples are definitely in R because there are multiple combinations of tuples which would produce the decomposition instances. We do know there must be at least two to include AB values of (5,1) and (6,1) and BC values of (1,8) and (1,9).

B is definitely not a key. In R2, we see the B value 1 occurring with C values 8 and 9. This shows B cannot be a key.

15.9

  1. candidate keys: BD
  2. The decomposition is BCNF. However, we cannot relate AD and BC after the decomposition, so it is lossy.

  3. candidate keys: AB, BC
  4. The relations are BCNF. It is a lossless decomposition since the join attribute, e.g. C, determines ACD. The decomposition is not dependency preserving, e.g. AB->C.

  5. candidate keys: A, C
  6. The relation was already in BCNF, so the decomposition was not needed. The resulting relations are still BCNF and is was a lossless decomposition since the join attribute A determines ABC.

  7. candidate keys: A
  8. It is not BCNF since C->D and A is the key for ACD. It is not dependency preserving, e.g. B->C. It was a lossless decomposition since the join attribute A determines both relations.

  9. candidate keys: A

The relations are BCNF. The decomposition is lossy since the join attribute for AD and CD is D and D does not determine either relation. Further, the decomposition is not dependency preserving, e.g. B->C.

15.11

1.

 

Violate BC->D

Violate BC->->D

a.

No

No

b.

No, as long as a !=2

No

c.

No, as long as a != 2

No, unless a = 2

d.

Yes

No, unless a = 2

e.

No, as long as a != 2

No, unless a = 2

f.

Yes

Yes

g.

Yes

No

2. We cannot say if A->B holds for sure, but it is not violated.

17.2

T3 ¬ T1

­ ¯

T2

17.3

 

serial

conflict serial

strict

recoverable

1.

No, unless T1 or T2 is aborted.

No.

No, T2 writes X before T1 commits.

Yes. No changes are read.

2.

Yes. Running T1 to completion and then running T2 yields the same results.

Yes.

No, T2 reads X before T1 commits.

Only if T1 commits before T2.

3.

Yes, T1 T3 T2.

Yes.

No. T3 writes X before T1 commits.

Only if T3 commits before T2.

4.

No, because of the T2 reads of Y around T3's write of Y.

No.

No. T2 reads Y before T3 commits.

Only if T3 commits before T2.

5.

Yes. T1

Yes.

No. T1 writes X before T2 aborts.

Yes.