Midterm 2 Solutions

Q1a)  SELECT E.I#
      FROM ENGINES E, ORDER_ITEM T, ORDER O
      WHERE E.I#=T.I# AND T.O#=O.O# AND ODATE=990101

Q1b)  SELECT Cust#, SUM($amount) "Total Amount"
      FROM ORDER
      GROUP BY Cust#

Q1c)  SELECT Cname
      FROM CUSTOMER C
      WHERE NOT EXISTS (SELECT *
                        FROM ORDER O
                        WHERE C.CUST#=O.CUST#)

Q1d)  T1=proj(Cust#)ORDER
      T2=proj(Cust#)CUSTOMER
      T3=T2-T1
      T4=T3(join Cust#)CUSTOMER
      RESULT=proj(Cname)T4

             proj(Cname)
                 |
                join
          _______|________
          |              |
       ___-___        CUSTOMER
       |     |            
      proj  proj
       |     |
    ORDER  CUSTOMER

Q2a)  Inclusion Dependency
      -ENGINES.I# < ITEM.I# (set-subset relationship)
        proj(I#)ENGINES <= proj(I#)ITEM

      -ORDER.Cust# < CUSTOMER.Cust#
        proj(Cust#)ORDER <= proj(Cust#)CUSTOMER

Q2b)  B->AD => BI->AID
               I->E    => BI->E => BI->ADE
                                   But, DE->J => BI->J

      => BI->ADE, BI->J, BI->C (given)
      => BI is a key of R

Q2c)  Not trivial.
      BOOK->>Author|Website, because independently, a book is related to
      multiple authors and multiple websites and all combination of the
      Author|Website are present.

Q2d)  a)  In 1NF, because of partial dependency (Job#->Job-deadline)
      b)  Yes, lossless.  INTERSECTION(MJ1, MJ2)=OP#,Mach#, MJ2-MJ1=OpType.
          Lossless, since OP#->OpType, OP#,Mach#->OpType.
      c)  MJ1 decomposition
          MJ11(_Mach#_, MachType)
          MJ12(_Job#_, JobDeadline)
          MJ13(_Mach#_, _Job#_, Operator#, NoHrs)
      d)  Yes.  {MJ2, MJ11, MJ12, MJ13} is a design in BCNF.

Q3a)  What are the numbers of the items which were sold to customers from
      the 30022 ZIP code since
      the beginning of 1999, and how many are left on hand?

Q3b)
                            proj(I#,Quant_on_hand)
                                       |
                         sel(Odate=990101, ZIP=30022,
                             T.O#=O.O#, O.Cust#=C.Cust#, I.I#=T.I#)
                                       |
                            ___________X__________
                            |                    |
                ____________X____________        |
                |                       |        |
        ________X______                 |        |
        |             |                 |        |
        |             |                 |        |
        |             |                 |        |
        T             O                 C        I                 


Q3c)  Push down the selects, replace Cartesian product with joins.

                            proj(I#,Quant_on_hand)
                                       |
                            _______I.I#=T.I#______
                            |                    |
                _____O.Cust#=C.Cust#_____        |
                |                       |        |
        ____T.O#=O.O#__                 |        |
        |             |                 |        |
        |     sel(Odate=990101)  sel(ZIP=30022)  |
        |             |                 |        |
        T             O                 C        I

      Push down the projects (only for first level of joins).

                            proj(I#,Quant_on_hand)
                                       |
                            _______I.I#=T.I#______
                            |                    |
                _____O.Cust#=C.Cust#_____        |
                |                       |        |
        ____T.O#=O.O#__                 |        |
        |             |                 |        |
    proj(O#,I#) proj(O#,Cust#)    proj(Cust#) proj(I#,Quant_on_hand)
        |             |                 |        |
        |     sel(Odate=990101)  sel(ZIP=30022)  |
        |             |                 |        |
        T             O                 C        I

Q3d)  The selectivity is .1% (0.001).  There is a customer for each order,
      and joining the tables results in a third table with 10,000 tuples.
      |ORDER x CUSTOMER| = 10,000,000.  Join selectivity is therefore:
      10,000/10,000,000 = .001.

Q3e)  Cost=b(R) + [b(R) * b(S)] + [(js * |R| * |S|)/bfr(RS)]
      Set CUSTOMER to be the outer relation, and ORDER to be the inner
      relation.  Then, since CUSTOMER is 20 blocks, there must be two
      iterations of the nested-loop method, where 10 blocks are read
      for each iteration.  Also for each iteration, 100
      blocks for the ORDER relation must be read, so a total of
      10 + (1 * 100) blocks are read per iteration, and 220 block read are
      done over both iterations.
      To save, if we assume there are 10,000 tuples in the result, and
      100 tuples are in each block, then 100 blocks must be saved,
      for a total of 320 blocks read or written.