1

I am trying to find the 3NF lossless decomposition of the following relation with respect to the functional dependencies:

enter image description here

I started by deriving the keys from the functional dependencies given above. The keys are {L,T}, {E,T} and {T,M} because all of the attributes in the relation can be obtained using any of these keys.

The definition of 3NF:

A relation schema R is in 3NF if, whenever a function dependency X -> A holds in R, either
a. X is a superkey of R, or
b. A is a prime attribute of R.

Applying this to the FDs:

  • LT -> E satisfies (a) because LT is a key (hence a superkey).
  • ET -> L satisfies (a) because ET is a key (hence a superkey).
  • TM -> E satisfies (a) because TM is a key (hence a superkey).
  • E-> M satisfies (b) because M is a prime attribute.

How can one obtain a 3NF lossless decomposition of the relation with respect to the functional dependencies?

I might be wrong that the relation is in 3NF because there are transitive dependencies.

Where I could be going wrong?

philipxy
  • 14,867
  • 6
  • 39
  • 83
bawse
  • 130
  • 4
  • 21

2 Answers2

1

Your answer is correct:

  1. All the keys are actually LT, ET, TM, since they determines all the other attributes, and there are no other keys, since no subset of them satisfies this property.

  2. The dependencies are already a canonical cover of the relation.

  3. The relation is already in 3NF exactly for the reasons that you stated.

Note that, if you follow the definition of Third Normal Form as you have correctly done, you don't need to check if there are or not transitive functional dependencies.

We can also note that the original relation instead is not in Boyce-Codd Normal Form, for the dependency E → M, and by applying the analysis algorithm to bring it in BCNF produces the decomposition:

R1 <(E M), {E → M}>

R2 <(E L T), {L T → E, E T → L}>

that has the property that the dependency T M → E is lost.

Renzo
  • 26,848
  • 5
  • 49
  • 61
  • So I assume there is no lossless decomposition of the relation into BCNF where dependencies are preserved? – bawse Jun 10 '16 at 07:18
  • 2
    Actually, the dependency is lost if we use the most common algorithm (the “analysis” algorithm) defined in all the books. There are other algorithms, however, that are not used in practice, that can produce different decompositions in BCNF. One of this is that of [Tsou and Fisher](http://portal.acm.org/citation.cfm?doid=990511.990513), and in this case it produces the decomposition: R1(M L T), R2(E L T), which has more redundancy, but which preserves the dependencies. This algorithm, as I said, is not used since it produces “innatural” decompositions, and very often with too many tables. – Renzo Jun 10 '16 at 07:35
  • Final note: there exist schemas in which *we can prove* that there is no decomposition in BCNF preserving the dependencies (these are shown in many books), but in general the problem of deciding if there exists a functional dependency preserving decomposition for a generic relation is a NP-hard problem (see [wikipedia](https://en.wikipedia.org/wiki/NP-hardness)), so we do not know any polynomial algorithm to solve this problem. – Renzo Jun 10 '16 at 07:42
-1

I think that relation can't be 3NF.

Because 3NF's definition is

  1. The relation R (table) is in second normal form (2NF).
  2. No non-prime attribute of R is transitively dependent on the primary key.

In your figure doesn't have primary key, so one of candidate key can be assumed primary key. But the {E->M} E is subset of candidate key (ET).

Edit: Above definition of 3NF took from wikipedia(https://en.wikipedia.org/wiki/Third_normal_form), it was wrong definition. But point of mine is that relation can't be 2NF. Because of subset of ET is in partial functional dependency {E->M}.

임재동
  • 1
  • 1
  • That is not a definition of 3NF. One of the things wrong is that PKs don't matter, CKs do. Also it's not just the FDs in some canonical set that matter, its all the FDs that hold when those do. Also your reasoning isn't clear & it isn't connected to your definition. – philipxy Jun 03 '23 at 10:55
  • Your argument is still not clear & since it doesn't appeal to any correct definition it cannot be sound. Also "subset of ET is in partial functional dependency" is wrong; the partial FD is the one with the superset as determinant, not the one with the subset. Please don't insert "EDIT"s/"UPDATE"s, just make your post the best presentation as of edit time. [ask] [Help] Please don't write "my point is"; just say it. Please don't say "I think"; either just say it or say "I don't know" (ie you *don't* think it--so don't say you do). Please don't say wrong things & repudiate, say true things. – philipxy Jun 04 '23 at 08:38
  • @philipxy I think we are discussing different things. 2NF's definition is 1.relation must be 1NF. 2. eliminatie partial FD. partial FD means a subset of CKs determines determinant. So the relation's ET is candidate key and the subset of ET( {E->M} ) is in FDs. Reason that ET is CK is ET's clousure is EMLT. – 임재동 Jun 04 '23 at 08:42
  • Please clarify via edits, not comments. Please delete & flag obsolete comments. That is not a definition of 2NF. (Details matter.) Go to an authoritative reference--eg a good textbook. [Partial Dependency (Databases)](https://stackoverflow.com/a/25827210/3404097) – philipxy Jun 04 '23 at 08:43
  • "Go to an authoritative reference--eg a good textbook." – philipxy Jun 04 '23 at 08:47
  • [Normal forms - 2nd vs 3rd - is the difference just composite keys? non trivial dependency?](https://stackoverflow.com/a/27504915/3404097) – philipxy Jun 04 '23 at 08:52
  • @philipxy In 2nd vs 3rd, 2NF is violated if A is not a superkey but is a proper subset of a candidate key. ET is CK, and {E->M} E is subset of ET. So, that relation is not 2NF. – 임재동 Jun 04 '23 at 08:58
  • "Please clarify via edits, not comments." – philipxy Jun 04 '23 at 09:00
  • Dozens of published academic information modeling & DB design textbooks are online free. Q&A is poor for learning topics; it is good for getting unstuck. You can post a researched non-duplicate question. "[ask] [Help]" [How much research effort is expected of Stack Overflow users?](https://meta.stackoverflow.com/q/261592/3404097) [meta] [meta.se] PS "Details matter." 2nd vs 3rd says "Suppose that some relation satisfies a non-trivial functional dependency of the form A->B, **where B is a nonprime attribute**. 2NF is violated if A is not a superkey but is a proper subset of a candidate key". – philipxy Jun 04 '23 at 09:32