CS145 - Spring 2003
Introduction to Databases
Challenge Problems #2   --   Due 11:59pm, Tuesday April 22
Email to cs145-submit@cs.stanford.edu

Challenge Problems

  1. Consider the following 29 query forms. You may assume that Rlist1 and Rlist2 are disjoint lists of relations, and that all attribute names are unique across the entire database. Note that cond2 may include references to attributes from relations in Rlist1, i.e., references to relations outside of the subquery.

    1. plain:
      SELECT DISTINCT Alist FROM Rlist WHERE cond
      (cond contains no subqueries)
      

    2. in:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and A1 in
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    3. not in:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and A1 not in
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    4. exists:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and exists
      (SELECT DISTINCT * FROM Rlist2 WHERE cond2)
      

    5. not exists:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and not exists
      (SELECT DISTINCT * FROM Rlist2 WHERE cond2)
      

    6. = all:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and A1 = ALL
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    7. not = all:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and NOT A1 = ALL
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    8. <> all:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and A1 <> ALL
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    9. not <> all:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and not A1 <> ALL
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    10. < all:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and A1 < ALL
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    11. not < all:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and not A1 < ALL
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    12. <= all:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and A1 <= ALL
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    13. not <= all:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and not A1 <= ALL
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    14. > all:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and A1 > ALL
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    15. not > all:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and not A1 > ALL
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    16. >= all:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and A1 >= ALL
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    17. not >= all:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and not A1 >= ALL
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    18. = any:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and A1 = ANY
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    19. not = any:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and not A1 = ANY
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    20. <> any:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and A1 <> ANY
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    21. not <> any:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and not A1 <> ANY
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    22. < any:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and A1 < ANY
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    23. not < any:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and not A1 < ANY
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    24. <= any:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and A1 <= ANY
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    25. not <= any:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and not A1 <= ANY
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    26. > any:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and A1 > ANY
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    27. not > any:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and not A1 > ANY
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    28. >= any:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and A1 >= ANY
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    29. not >= any:
      SELECT DISTINCT Alist FROM Rlist1
      WHERE cond1 and not A1 >= ANY
      (SELECT DISTINCT A2 FROM Rlist2 WHERE cond2)
      

    Now here's the problem:

    (a) For each query type except (1), if you can write an equivalent query using one of the other query types, show the equivalent query. You may assume there are no null values in any of the relations.

    (b) Give a minimal set of query types that is sufficient to express queries equivalent to all 29 query forms. A set of query types is minimal if taking any type out of the set would produce a strict loss in expressive power, i.e., not all 29 query forms would be expressible. Include query type (1) in your minimal set.

  2. Provide a general algorithm for eliminating HAVING clauses in SQL queries. That is, provide an algorithm that takes as input a SQL query Q with a HAVING clause. The algorithm should produce as output a SQL query Q' without a HAVING clause such that Q and Q' are equivalent, i.e., Q and Q' produce exactly the same answer on all databases. For simplicity you may assume: Do not make any other assumptions about the input query Q. Your algorithm should be based only on the query itself, not on the schema, the state of the database, or any other external information. (Hint: The solution to this problem is not all that complex. If you are developing a very complicated algorithm then you're probably headed in the wrong direction.)