Homework 3 (due 2/4)
CSC 355

We have continued (and will continue) talking about SQL. This week's material corresponds to what the book covers in Sections 6.1, 6.2, and parts of 6.3 (6.3.6-6.3.8). Next week we'll cover Sections 6.3 and 6.4. After that we'll go back to Chapter 3 in the book for relational design.

Handing it in: Submit to the d2l dropbox. Use some standard format for your homework (Word or pdf, for example), and make sure to include your name and assignment number. Include screenshots for code and testruns.

1. (Reading Assignment) Read Sections 6.1-6.3 of the textbook (Ullman, Widom, A First Course in Database Systems).

2. (Nulls and 3-valued logic, 10pt) Remember Date's example from class (last slide of the Basic SQL presentation). Date argues that queries can "produce results that are correct according to the three-valued logic but not correct in the real world". Some people would argue that the problem is with the query that Date writes:

Help Date write a correct query, i.e. a query that lists all pairs (SNO,PNO) "where either the supplied and part cities are different or the part city isn't Paris (or both)", even if there are null values in the city fields. Test-run it on a couple of examples to make sure it really works correctly. E.g. in Date's sample database

(S1,P1) should get listed (since City is either London, in which case it's different from Paris, or different from London, so supplier and part city are different and it should get listed). But the query should also still work if S.City contains null values (or, of course, other cities than London). Hint: there are four possible cases to consider depending on whether S.City and/or P.City are null. Analyze the four cases and figur out which of the cases cause the query above to fail (e.g. if both S.city and P.city are known, the query works just fine). Then add conditions to deal with that case/those cases. Briefly explain your reasoning for each case.

3. (3-valued logic, 10pt)  Not all 2-valued truths are 3-valued truths. E.g. in 2-valued logic "A or not(A)" can always be replaced with "TRUE", but that's not the case in 3-valued logic. In 2-valued logic there is a law which states that "not(A or B)" is equivalent to "not(A) and not(B)" for all truth-values of A and B. Intuitively, both are ways of expressing that neither A nor B are true. We can prove the equivalence using a truth table in which we "plot" the truth values of "not(A or B)" compared to "not(A) and not(B)" for all combinations of A and B to verify that they are equal:

This is a useful law to have, and it could help us simplify some database queries ("not(A or B)" has one less negation than "not(A) and not(B)"), but is this law still true for 3-valued logic? Build a truth-table like the one above for all 9 possible combinations of truth-values of A and B, and calculate expressions "not(A)", "not(B)", "A or B", "not(A or B)" and "not(A) and not(B)" to check whether this law still holds for 3-valued logic. State clearly whether it does or not.

4. (University SQL, 20pt) Write SQL for the following problems on the university database. Run each query. Submit screenshots of both query and output. Note: Do not use SQL features (e.g. GROUP BY) that we haven't seen in class.

  1. List students (LastName, SID) and which groups (GroupName, Founded) they are members of. Students should be listed even if they are not members of a group. However, we don't want to list groups that have no members.

  2. List undergraduate computer science students (LastName, SID) who haven't taken any computer science courses.

  3. List students who enrolled in classes in both 2011 and 2013. (You'll need to add some data to the enrolled table to make this interesting.) Hint: you won't need the course table for this or the following query.

  4. List students who enrolled in classes in 2011 and 2013, but not in 2012. Hint: as above.

5. (Extra Credit, requires logic, 10pt) 3-valued logic is functionally incomplete. That is, there are truth-functions that cannot be realized based on the 3-valued operations AND, OR, and NOT, even if you allow constants TRUE and FALSE. Show that this is the case by giving a truth-function that cannot be defined using AND, OR, NOT, TRUE and FALSE.

Marcus Schaefer
Last updated: January 29h, 2014.