Assignment #3

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 may be found here .

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

a) nonlocalProjects(J#) that is true if the project specified by J# is supplied by at least one supplier not in the same city.

b) partPairs(P#1, P#2) that is true if some supplier supplies both part P#1 and part P#2.

c) noRedLondoners(J#) that is true if project J# is not supplied with any red part by any London supplier.

d) londonParts(P#) that is true if part P# is supplied to all projects in London.

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

3. Prove that the relational operations of intersection is monotonic.

4. Consider the Datalog rules

P (x) <- Q (x) AND NOT R (x)

S (x) <- Q (x) AND NOT P (x)

T (x) <- Q (x) AND NOT S (x)

Suppose the EDB relations for Q and R are {1, 2, 3} and {1}, respectively. Find, for the IDB predicates P, S and T:

a) The perfect fixed point.

b) Another minimal fixed point (if none exists, prove it).

c) A fixed point that is not minimal (if none exists, prove it).