ASSIGNMENT #3
                                 -------------

                           Due Wednesday, May 3, 2000


1.   Consider a database of suppliers (S), parts (P), and  projects  (J),  which
     are  uniquely  identified  by  supplier  number (S#), part number (P#), and
     project number (J#), respectively. An additional shipment (SPJ) relation is
     used to indicate that the specified supplier supplies the specified part to
     the specified project in the specified quantity (and  the  combination  S#-
     P#-J#  uniquely  identifies  such a tuple). An example extensional database
     is:

     supplier(s1, smith, 20, london).
     supplier(s2, jones, 10, paris).
     supplier(s3, blake, 30, paris).
     supplier(s4, clark, 20, london).
     supplier(s5, adams, 30, athens).
     
     part(p1, nut, red, 12, london).
     part(p2, bolt, green, 17, paris).
     part(p3, screw, blue, 17, rome).
     part(p4, screw, red, 14, london).
     part(p5, cam, blue, 12, paris).
     part(p6, cog, red, 19, london).
     
     job(j1, sorter, paris).
     job(j2, display, rome).
     job(j3, ocr, athens).
     job(j4, console, athens).
     job(j5, raid, london).
     job(j6, eds, oslo).
     job(j7, tape, london).
     
     shipment(s1, p1, j1, 200).
     shipment(s1, p1, j4, 700).
     shipment(s2, p3, j1, 400).
     shipment(s2, p3, j2, 200).
     shipment(s2, p3, j3, 200).
     shipment(s2, p3, j4, 500).
     shipment(s2, p3, j5, 600).
     shipment(s2, p3, j6, 400).
     shipment(s2, p3, j7, 800).
     shipment(s2, p5, j2, 100).
     shipment(s3, p3, j1, 200).
     shipment(s3, p4, j2, 500).
     shipment(s4, p6, j3, 300).
     shipment(s4, p6, j7, 300).
     shipment(s5, p2, j2, 200).
     shipment(s5, p2, j4, 100).
     shipment(s5, p5, j5, 500).
     shipment(s5, p5, j7, 100).
     shipment(s5, p6, j2, 200).
     shipment(s5, p1, j4, 100).
     shipment(s5, p3, j4, 200).
     shipment(s5, p4, j4, 800).
     shipment(s5, p5, j4, 400).
     shipment(s5, p6, j4, 500).

     Define the following predicates using safe Datalog  rules.   Validate  that
     your Datalog rules are correct using Prolog.

     a) allLondonParts(P#) that is true for parts P# supplied by a  supplier  in
        London to a project in London.

     b) redPartCompetitors(S#) that is true if supplier  S#  supplies  at  least
        onepart  that is supplied by at least one supplier who supplies at least
        one red part.

     c) lowerThanS1(S#) that is true if the status of supplier S# is lower  than
        the status of supplier S1.

     d) commonSuppliers(S#1, S#2) that is true if suppliers S#1 and  S#2  supply
        exactly the same set of parts each.

2.   Write each of the queries of the previous exercise in relational algebra.

3.   Prove that the relational operation of natural join is monotonic. Note that
     a  function  f  is monotonic  if  and only if R1 <= R3 and R2 <= R4 implies
     f (R1, R2) <= f (R3, R4), where <= denotes subset.

4.   Consider the following logical rules to define where a traveler may go:

     travel (T, X) :- ~forbid (T, X).
     forbid (T, X) :- located (X, Y) & forbid (T, Y).
     forbid (T, X) :- exiled (T, X).

     Assume the extensional database relations:

     exiled (Romeo, Verona).
     exiled (Napoleon, Europe).
     located (Paris, France).
     located (Mantua, Italy).
     located (Verona, Italy).
     located (Venice, Italy).
     located (France, Europe).
     located (Italy, Europe).

     a) If the rules are not safe, modify them appropriately to achieve safety.

     b) Convert the safe logical rules into "recursive" relational algebra.

     c) Compute the perfect fixed-point.

     d) Show another minimal fixed-point.

     e) Give a fixed point that is not minimal.