Practice Problems - Exam 3
SOLUTIONS
---------

(1) Consider R = BOSQID and F = { S --> D, I --> B, IS --> Q, B --> O }.
    (a) List all candidate keys for R,F.

         Only one candidate key: IS

    (b) Obtain a 3NF decomposition of R satisfying the LJD and FDP properties.

         SD, IB, ISQ, BO

(2) Consider R = ABCDE and 
             F = { A --> C, BD --> E, B --> D, B --> E, C --> AD }.

    (a) Obtain a minimal cover for F.

           { A --> C, B --> D, B --> E, C --> A, C --> D }.

    (b) List all the candidate keys for F.

         AB and BC

    (c) Obtain a 3NF decomposition of R satisfying the LJD and FDP properties.

        BDE, ACD, AB

(3) Using only the Armstrong's axioms, prove that 

    if X --> Y and U --> V hold then XU --> YV holds.

    Proof:
      1. X --> Y,  Given
      2. XU --> YU, Augment (1) by U
      3. U --> V, Given
      4. YU --> YV, Augment (3) by Y
      5. XU --> YV  Transitivity on (2) and (4)

(4) Are the following two sets of FDs equivalent? Show your work and
    give reasons why or why not.

    F = { AB --> C, B --> C, A --> D }
    G = { A --> B, B --> C, C --> D }

    NO. Because
          A --> B in G is not implied by F; A+ wrt F equals AD and does
                            not include B
          C --> D in G is not implied by F; C+ wrt F equals C and does
                            not include D

(5) Given F = { AB --> E, BE --> I, E --> C, CI -->  D }

    Prove that AB --> CD is derivable from F. 


    Simple Proof:

      (AB)+ = ABEICD  which includes CD.

    Proof using Armstrong's Axioms:

    1. AB --> E, Given
    2. E --> C, Given
    3. AB --> C, Transitivity on (1) and (2)
    4. AB --> BE, Augment (1) by B
    5. BE --> I, Given
    6. AB --> I, Transitivity on (4) and (5)
    7. ABC --> CI, Augment (6) by C
    8. AB --> ABC, Augment (3) by AB
    9. AB --> CI, Transitivity on (7) and (8)
    10. CI --> D, Given
    11. AB --> D, Transitivity on (9) and (10)
    12. ABC --> CD, Augment (11) by C
    13. AB --> CD, Transitivity on (8) and (12)


TRC/DRC/Datalog Questions:

Write expressions in DRC, TRC, and Datalog for the queries in exam 2, problem 1.

(1) Get names of members who have purchased ORCL shares.

  TRC: {m.fname, m.lname | 
          member(m) and (exists t)(transaction(t) and m.mid = t.mid and 
                                      t.transtype='buy' and t.symbol='ORCL') }

  DRC: {f, l | (exists m,p,a,e)(member(m,p,f,l,a,e) and
                        (exists d,q)(transaction(m,'ORCL',d,'buy',q))) } 

  Datalog: answer(f,l) :- member(m,_,f,l,_,_), transaction(m,'ORCL',_,'buy',_).

(2) Get names of members who have purchased only ORCL shares.

  TRC: {m.fname, m.lname | member(m) and 
           (forall t)(transaction(t) and t.mid=m.mid and t.transtype='buy' --> 
                                             t.symbol='ORCL') }

  DRC: {f, l | (exists m,p,a,e)(member(m,p,f,l,a,e) and 
           (forall s,d,q)(transaction(m,s,d,'buy',q) --> s='ORCL')) }

  Datalog: 
    nonORCLBuyers(m) :- transaction(m,s,_,'buy',q), s <> 'ORCL'.
    answer(f,l) :- member(m,_,f,l,_,_), not nonORCLBuyers(m).

    To avoid members who have not purchased any shares at all, 
    the second rule may be written as:

    answer(f,l) :- member(m,_,f,l,_,_), transaction(m,'ORCL',_,'buy',_),
                   not nonORCLBuyers(m).

(3) Get company names of securities whose shares are purchased by all
    members.

    TRC: { s.cname | security(s) and 
               (forall m)(member(m) --> (exists t)(transaction(t) and
                                                   t.transtype='buy' and
                                                   t.mid = m.mid and 
                                                   t.symbol=s.symbol)) }

    DRC: { c | (exists s)(security(s,c) and 
                   (forall m,p,f,l,a,e)(member(m,p,f,l,a,e) --> 
                       (exists t)(transaction(m,s,d,'buy',q)))) }

    Datalog:
        allpairs(s,m) :- member(m,_,_,_,_,_), security(s,_).
        boughtby(s,m) :- transaction(m,s,_,'buy',_).
        missing(s) :- allpairs(s,m), not boughtby(s,m). 
        answer(c) :- security(s,c), not missing(s).

(4) Get the names of members who have purchased shares from all of the
    companies that member with MID=1000 has purchased shares from.
        
 TRC: {m.fname, m.lname | member(m) and
        (forall t1)(transaction(t1) and t1.mid=1000 and t1.transtype='buy' -->
                       (exists t2)(transaction(t2) and t2.mid=m.mid and 
                                  t2.symbol=t1.symbol and t2.transtype='buy'))}

 DRC: {f, l | (exists m,p,a,e)(member(m,p,f,l,a,e) and
            (forall s,d1,q1)(transaction(1000,s,d1,'buy',q1) -->
                          (exists d2,q2)(transaction(m,s,d2,'buy',q2))))}  

 Datalog:

    allPairs(m,s) :- member(m,_,_,_,_,_), transaction(1000,s,_,'buy',_).
    buys(m,s) :- transaction(m,s,_,'buy',_).
    missing(m) :- allPairs(m,s), not buys(m,s).
    answer(f,l) :- member(m,_,f,l,_,_), not missing(m).