title: Primary key of a relation with circular functional dependencies
body: <p>I'm studying for my database exam and I'm not sure about one question which goes as follow:</p>
  <blockquote>
  <p>Given the relation R={A, B, C, D, E, F, G, H, I} and the set of functional dependencies</p>
  <p>F = { AB -&gt; C,</p>
  <p>A -&gt; DE,</p>
  <p>C -&gt; AB,</p>
  <p>B -&gt; FGH,</p>
  <p>D -&gt; IJ,</p>
  <p>D -&gt; CBE
  }</p>
  <p>Under what (normal) form is this relation?</p>
  </blockquote>
  <p>First, I know I have to find all candidate keys. Looking at the right, I see that every attribute of R appears on the right hand-side, so it is not trivial that any single attribute of R is a candidate key. So looking at the left hand-size, only A, B, C, D appear, so one or some of these attributes must appear in the candidate keys.</p>
  <p>So using A, C and D works (details skipped), but using B alone doesn't. Considering using two-attribute ket is useless since any key that does not contain A, C or D won't &quot;bring us back&quot; to R. Exemple, BE allows us to find B, E, F, G, H, but then we can't proceed further, so not all attributes of R are found.</p>
  <p>Also, using any combination with A, C, or D in it is useless since it contains a subset (a single attribute) which is part of a candidate key (a single attribute). Example, AB can be reduced to A, and then all attributes of R can be found.</p>
  <p>What bugs me is AB -&gt; C and C -&gt; AB, which is a circular dependency. I thought of two possibilities:</p>
  <ol>
  <li>C is the primary key and we can use it to find A and B (C -&gt; AB);</li>
  <li>AB can be reduced to A (as said above) and with it we can find C.</li>
  </ol>
  <p>But it is very easy to see that AB must be unique and C must also be unique.</p>
  <p>Let's only use AB -&gt; C. We can have the following associations:</p>
  <blockquote>
  <p>11 -&gt; 1 (A = 1, B = 1, C = 1)</p>
  <p>12 -&gt; 1</p>
  </blockquote>
  <p>But then, if we reinsert the rule C -&gt; AB, we find:</p>
  <blockquote>
  <p>1 -&gt; 11</p>
  <p>1 -&gt; 12</p>
  </blockquote>
  <p>which can't hold.</p>
  <p>So C has to be unique.</p>
  <p>Same thing if we only consider C -&gt; AB, and then reinsert the rule AB -&gt; C.</p>
  <p>I'm starting to think that this is a trick and that the real primary key of this relation is ABC to ensure uniqueness of the combinations of AB and C. We would then have the following rules:</p>
  <blockquote>
  <p>F'={</p>
  <p>ABC -&gt; DEFGH</p>
  <p>D -&gt; IJ</p>
  <p>D -&gt; CBE</p>
  <p>}</p>
  </blockquote>
  <p>Is this right? What about the other circular dependency, i.e. C -&gt; D (first rule), D -&gt; C (third rule), and C -&gt; D (going back to first rule)? Do I simply not care about it?</p>
  <p>If I don't care about it (and assuming the primary key is ABC), then it seems obvious that this table is not in 3NF since ABC determines D (which is a non prime attribute here), and D determines IJ, two non prime attributes. But it seems to be in 2NF because no non prime attribute (D, E, F, G, H, I, J) can be obtain using a subset of attributes of the candidate keys (ABC here).</p>
  <p>Of course, I could consider the primary key to be A, C or D and split AB -&gt; C and C -&gt; AB in two separate relations, but I don't think joining those two tables will always respect the rules AB -&gt; C and C -&gt; AB. For example, if someone inserts a new row in one of the table, then the join could introduce an invalid row.</p>
  <p>I am thinking too much? Am I going in the wrong direction?</p>
  <p>Thanks for your help :)</p>