title: Decomposing relations to Fourth Normal Form
body: <p><em>Disclosure: I am taking <a href="https://lagunita.stanford.edu/courses/Home/Databases/Engineering/about" rel="nofollow noreferrer">Stanford's online database course</a>. The forum there is dead, and I'm hoping for some help on SO.</em></p>
  <p><strong>Here's the quiz question:</strong></p>
  <blockquote>
  <p>Consider relation <code>R(A,B,C,D,E)</code> with multivalued dependencies:</p>
  <p><code>A -» B, B -» D</code></p>
  <p>and no functional dependencies. Suppose we decompose <code>R</code> into 4th Normal Form. Depending on the order in which we deal with 4NF violations, we can get different final decompositions. Which one of the following relation schemas could be in the final 4NF decomposition?</p>
  </blockquote>
  <p><strong>And here is my thinking:</strong></p>
  <p>Since we are given that there are no functional dependencies, the only key is set of attributes <code>(A,B,C,D,E)</code>. In other words, both multivalued dependencies in the question are violating, and we must decompose them.</p>
  <p>I am following the decomposition algorithm given in lecture:</p>
  <blockquote>
  <p>Compute keys for R <em>[done]</em></p>
  <p>Repeat until all relations are in 4NF</p>
  <pre><code>Pick any R' with nontrivial A -» B that violates 4NF
  Decompose R' into R_1(A, B) and R_2(A, rest)
  Compute functional dependencies and multivalued dependencies for R_1 and R_2
  Compute keys for R_1 and R_2
  </code></pre>
  </blockquote>
  <p>I see two ways to decompose the relations: start with <code>A -» B</code> or <code>B -» D</code>.</p>
  <p><em>Starting with A -» B</em></p>
  <pre><code>R(A,B,C,D,E)
        |
        +-----------+
        |           |
   R_1(A,B)  R_2(A,C,D,E)
  </code></pre>
  <p>Since <code>B</code> and <code>D</code> are no longer in the same relation, we do not have a 4NF violation, and we're done. I'm not sure how to compute the FDs, MVDs, and keys at this point.</p>
  <p><em>Starting with B -» D</em></p>
  <pre><code>R(A,B,C,D,E)
        |
        +-----------+
        |           |
   R_1(B,D)  R_2(B,A,C,E)
                    |
                    +----------+
                    |          |
               R_3(A,B)  R_4(A,C,E)
  </code></pre>
  <p>At this point, (<code>A</code> and <code>B</code>) and (<code>B</code> and <code>D</code>) are decomposed into their own relations, so we have no violations, and we're done.</p>
  <p><em>The answer choices:</em></p>
  <p>At this point, I'm completely stumped. I do not see any of the relations in the answer choices, nor can I come up with an idea that will get me there:</p>
  <blockquote>
  <ol>
  <li>CE</li>
  <li>AD</li>
  <li>AE</li>
  <li>ABD</li>
  </ol>
  </blockquote>
  <p>I don't need the answer outright, but what am I missing?</p>