CSc 8710 -- Spring 2007

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.
- (a) (forall X)(exists Y)(P(X,Y)) --> (exists X)(forall Y)(P(X,Y))
- (b) (forall X)(P(X) V Q(X))
- (c) (exists X)(exists Y)(P(X,Y)) --> (forall X)(forall Y)(P(X,Y))
Consider the following MAILORDER relational schema describing the data for a mail order company:
```
parts(pno,pname,qoh,price,olevel)
customers(cno,cname,street,zip,phone)
employees(eno,ename,zip,hdate)
zipcodes(zip,city)
orders(ono,cno,eno,received,shipped)
odetails(ono,pno,qty)
```
The attribute names are self-explanatory. "qoh" stands for quantity on hand. Specify and execute the following queries using the RA and the DRC interpreters on the MAILORDER database schema.
- (a) Retrieve the names of parts that cost less than $20.00.
- (b) Retrieve the names and cities of employees who have taken orders for parts costing more than $50.00
- (c) Retrieve the pairs of customer number values of customers who live in the same zip code.
- (d) Retrieve the names of customers who have ordered parts only from employees living in the city of Wichita.
- (e) Retrieve the names of customers who have ordered all parts costing less than $20.00.
- (f) Retrieve the names of customers who have not placed a single order.
- (g) Retrieve the names of customers who have placed exactly two orders.