CS145 - Fall 2013
Introduction to Databases
Assignment #4
Due Monday October 28 -- NO LATE WORK ACCEPTED

This assignment consists of writing XPath, XQuery, and XSLT queries over two different databases, along with a few challenge problems in relational design.

Automated XML Query Exercises

Log into the CS145 Class2Go Site. Click on the Interactive Exercises link. Under Querying XML, complete four exercise sets:
You will also see four companion exercise sets to the ones assigned -- with the same title except "(extras)" instead of "(assigned)". These four exercise sets are not assigned and have no due date during the course. They are simply there to provide you with extra practice if you wish.

As with all of the automated exercises, the website is designed so you can interactively develop your solutions in place: each problem allows you to run your proposed solution and see a comparison between your result and the expected one. Once you're happy with your solutions, you must press Submit Answers for your score to be recorded.

If you prefer to develop your solutions offline, you can install Kernow (an interface with Saxon embedded) on your computer, download the data files, and work offline:
Whichever way you work, don't forget to enter your solutions and press "Submit Answers" to obtain your score. You may do the exercises as many times as you like, with no time lapse required between tries. Although all scores are recorded, we will only use the highest score you achieve as of the due date. As usual, automated exercises receive no credit if submitted late.

Challenge Problems

Problem 1

Your task is to write SQL queries to check satisfaction of certain functional and multivalued dependencies on table instances. Suppose you have a table T(A,B,C,D). You may assume there are no NULL values in T, but otherwise make no assumptions about the data. For each of the following three dependencies -- two functional dependencies and one multivalued dependency -- write a query that returns an empty result if and only if the current contents of table T satisfy the dependency. That is, if the dependency is satisfied then the result of the query is empty, while if the dependency is not satisfied then the query result is nonempty (the specific contents of the result don't matter).

(a) Functional dependency  AB C
(b) Functional dependency  A BC
Multivalued dependency 
A > BC


Problem 2

Consider a relation R(A1,A2,...,An) with n > 0 attributes. Your goal is to construct an instance (set of tuples) for this relation that satisfies the functional dependencies Ai A(i+1) for all i=1..(n-1). That is, in your instance:

  A1  A2
  A2  A3
  A3  A4
  A(n-1)  An
Furthermore, the only functional dependencies your relation instance should satisfy are the ones above, and those that follow from them. All other functional dependencies (e.g., A2 A1, or A4,A3 A2, etc.) should be violated by the set of tuples in your relation instance. Try to find an instance that has as few tuples as possible.

Your solution writeup should consist of a clear description or depiction of how to generate your relation instance for any n > 0. As examples, show the actual instances for n=2, n=4, and n=6 (i.e., relations with 2, 4, and 6 attributes).

Problem 3

Prove the intersection rule for multivalued dependencies. Specifically, consider a relation R, and let A, B, and C be three sets of attributes in R. Prove that if  A > B and  A> C hold for R, then  A > (B C) also holds, where ∩ is the standard intersection of attribute sets. For simplicity you may assume that A does not intersect B or C, and there are no attributes in R besides those in sets A, B, and C.

Your proof should be based on the formal definition of MVDs, not on other rules. In other words, it should have roughly the following form: "Suppose  A > B and  A> C hold. Let  D = (B C). To prove  A > D, we need to prove that for all tuples t and u in R there exists a tuple v1 in R such that ... [fill in] ... From  A > B  we know that for all tuples t and u in R there exists a tuple v2 in R such that ... [fill in] ... Also, from   A > C  we know that for all tuples t and u in R there exists a tuple v3 in R such that ... [fill in] ... [Fill in more] We have shown that the required tuple v1 exists, therefore  A > D  holds."

Submission Instructions: Challenge Problems

Solutions should be submitted in pdf format. For students who prefer hand-writing their solutions or using some other format, solutions may be scanned and submitted as jpg. Solutions must be submitted through Coursework, and must be in a single file named challenge4.pdf (or challenge4.jpg). Login to Coursework. Under Assignments you will see Challenge Problems #4 (for Assignment #4 challenge problems -- don't worry, there was no Challenge Problems #3). Upload your solution file and submit for grading. You may resubmit as many times as you like, however only the latest file and the latest timestamp are saved, and those are what we will use for grading your work and determining late penalties. Submissions via email will not be accepted.

Reminders: Late Policy and Honor Code