CSc 8710 Fall 2005
Homework 1 (Due: September 7, 2005 - Wednesday)

1. For each of the following formulas, state if it is satisfiable or not. If satisfiable, give a model with natural numbers as a domain. If not, explain why it is not satisfiable.
   1. (Forall X)(Exists Y)p(X,Y) --> (Exists X)(Forall Y)p(X,Y)
   2. (Forall X)(Forall Y)p(X,Y) --> (Exists X)(Exists Y)p(X,Y)
   3. (Exists X)(Exists Y)p(X,Y) --> (Forall X)(Forall Y)p(X,Y)
2. Consider the following relational database schema:

     parts(PNO,pname,color)
     suppliers(SNO,sname,city)
     supply(SNO,PNO,qty)
   

   Write queries in Domain Relational Calculus (DRC) for the following:
   1. Find supplier number of suppliers who supply ALL "red" parts.
   2. Find supplier number of suppliers who supply ONLY "red" parts.
   Just for your reference, the query "Find supplier name of suppliers who supply "red" parts' in DRC is:

     { N | (Exists S,C)(suppliers(S,N,C) and (Exists P,Q)(supply(S,P,Q) and (Exists T)(parts(P,T,"red")))) }
   
     or in a more flat form:
   
     { N | (Exists S,C,P,Q,T)(suppliers(S,N,C) and supply(S,P,Q) and parts(P,T,"red")) }