• Submission Instructions & Guidelines for Typing Assignments: All challenge problems should be submitted by email to cs145-submit@cs.stanford.edu. Please refer to Challenge Problem 1 for guidelines for typing assignments and accepted formats. Please see the Assigned Work page for our policy regarding late submissions. Please remember that challenge problems must be submitted electronically, and plan accordingly.

• Honor Code reminder: For more detailed discussion of the Stanford Honor Code as it pertains to CS145, please see the Assigned Work page under Honor Code. In summary: You must indicate on your written and programming assignments any assistance (human or otherwise) that you received. Any assistance received that is not given proper citation will be considered a violation of the Honor Code. In any event, you are responsible for understanding and being able to explain on your own all material that you submit.

• Partners are not permitted. Problems must be completed individually.

• IMPORTANT NOTE: Please go back and review format instructions noted in challenge problems 1. Submissions that do not follow instructions may lose points. Specifically:
  • Name, student ID number, leland username must be at the top of the assignment itself.
  • Please only submit one file containing all of your solutions.
  • Resubmissions are discouraged and should only be used if you discovered a serious error. Please try to make your submission be your final solution.
  • If submitting a text file, make sure that your file is easy to read.

Challenge Problems

1. Write a query in XQuery that requires the use of the some-in-satisfies construct. That is, an equivalent query should not be able to be written without using some-in-satisfies, despite XQuery's semantics based on implicit existential quantification.
   

2. This question is about the BCNF decomposition algorithm. We start with a relation R and a set of functional dependencies F for R. Show that after we perform the decomposition step, to determine if the decomposed relations are in BCNF it is necessary to check not only the FDs given in F, but also those that follow from F. More specifically, complete the details of the following counterexample showing that checking F alone is not sufficient. We decompose a relation R(A,B,C,D) into R1(A,B) and R2(A,C,D) according to a BCNF violation A->B. Give an example set of FDs F such that:
   • F contains at least A->B, and A->B is a BCNF violation for R.
   • R2 has a BCNF violation that follows from F.
   • No FD's in F itself are BCNF violations for R2.

   Try to find the smallest set F satisfying these three conditions.
   

3. Prove the transitivity rule for multivalued dependencies. Specifically, consider a relation R(A,B,C,D). Prove that if A ->> B and B ->> C hold then A ->> C holds. Your proof might have roughly the following form: Suppose A ->> B and B ->> C hold. Then for all tuples t and u there exists a tuple v such that ... [fill in] ... To prove that A ->> C holds, we need to prove that for all tuples t and u there exists a tuple v such that ... [fill in] ... Therefore A ->> C holds.
   

4. Write a relational algebra expression that returns empty if and only if the multivalued dependency A->>B holds on R(A,B,C).