Understanding Database Decomposition and Normalization

This problem involves analyzing a database relation that has been decomposed into two sub-relations and determining their normalization forms (2NF and 3NF) and checking for the dependency preservation property.

We are given a universal relation R(A, B, C, D, E) with the functional dependency set F: ${A \rightarrow BC, D \rightarrow E, BC \rightarrow D, A \rightarrow D}$. The relation R is decomposed into two tables: R₁(A, B, C) with functional dependency set F₁ = ${A \rightarrow B, A \rightarrow C}$, and R₂(A, D, E) with functional dependency set F₂ = ${A \rightarrow D, D \rightarrow E}$. We need to evaluate the given options regarding this decomposition.

Analyzing Relation R₁(A, B, C) and its Normal Form

The functional dependencies for R₁ are F₁ = ${A \rightarrow B, A \rightarrow C}$.

• Finding the Candidate Key: To find the candidate key, we look for an attribute or set of attributes whose closure contains all attributes in R₁ (A, B, C).
  • ${A}^{+} = A$. Using $A \rightarrow B$, ${A}^{+} = AB$. Using $A \rightarrow C$, ${A}^{+} = ABC$.

Since ${A}^{+}$ contains all attributes (A, B, C), A is a candidate key for R₁. As A is the only attribute on the left side of any dependency in F₁ that can determine all others, A is the only candidate key.

• Prime and Non-Prime Attributes:
  • Prime attributes are attributes that are part of any candidate key. In R₁, A is the only prime attribute.
  • Non-prime attributes are attributes that are not part of any candidate key. In R₁, B and C are non-prime attributes.

Now, let's check the normalization forms for R₁:

• Second Normal Form (2NF): A relation is in 2NF if it is in 1NF (which is given as all attributes are simple and atomic) and every non-prime attribute is fully functionally dependent on every candidate key.
  • Candidate key is A.
  • Non-prime attributes are B and C.
  • Is B fully dependent on A? Yes, $A \rightarrow B$ is given in F₁. Since A is a simple key, any dependency on A is a full dependency.
  • Is C fully dependent on A? Yes, $A \rightarrow C$ is given in F₁. Since A is a simple key, any dependency on A is a full dependency.

R₁ is in 2NF.

• Third Normal Form (3NF): A relation is in 3NF if it is in 2NF and there are no transitive dependencies of non-prime attributes on the candidate key. A transitive dependency exists if Key → X and X → Y, where Y is a non-prime attribute and X is not part of the key.
  • Candidate key is A.
  • Non-prime attributes are B and C.
  • Are there any dependencies like A → X and X → Y where Y is non-prime and X is not A? The dependencies are $A \rightarrow B$ and $A \rightarrow C$. Neither B nor C functionally determines any other attribute in R₁ according to F₁. There is no path A → (non-key) → (non-prime).

Therefore, R₁ is in 3NF.

Analyzing Relation R₂(A, D, E) and its Normal Form

The functional dependencies for R₂ are F₂ = ${A \rightarrow D, D \rightarrow E}$.

• Finding the Candidate Key:
  • ${A}^{+} = A$. Using $A \rightarrow D$, ${A}^{+} = AD$. Using $D \rightarrow E$, ${A}^{+} = ADE$.

Since ${A}^{+}$ contains all attributes (A, D, E), A is a candidate key for R₂. A is the only candidate key.

• Prime and Non-Prime Attributes:
  • Prime attributes: A.
  • Non-prime attributes: D, E.

Now, let's check the normalization forms for R₂:

• Second Normal Form (2NF): R₂ is in 1NF. Is every non-prime attribute fully dependent on every candidate key?
  • Candidate key is A.
  • Non-prime attributes are D and E.
  • Is D fully dependent on A? Yes, $A \rightarrow D$ is given in F₂. A is a simple key, so it's a full dependency.
  • Is E fully dependent on A? Yes, from $A \rightarrow D$ and $D \rightarrow E$, we can derive $A \rightarrow E$ by transitivity. Since A is a simple key, this is a full dependency.

R₂ is in 2NF.

• Third Normal Form (3NF): R₂ is in 2NF. Are there any transitive dependencies of non-prime attributes on the candidate key?
  • Candidate key is A.
  • Non-prime attributes are D and E.
  • Consider the dependency $A \rightarrow D$ and $D \rightarrow E$. Here, A is the key, E is a non-prime attribute, and D is a non-key attribute that is not part of the key. This forms a transitive dependency: $A \rightarrow D \rightarrow E$.

Because of the transitive dependency $A \rightarrow E$ via D, R₂ is not in 3NF.

Analyzing Dependency Preservation Property

Dependency preservation means that the union of the functional dependencies in the decomposed relations is equivalent to the original set of functional dependencies (or their closure). That is, $F_{1} \cup F_{2}$ should be equivalent to F.

Original FDs: F = ${A \rightarrow BC, D \rightarrow E, BC \rightarrow D, A \rightarrow D}$.

Decomposed FDs: F₁ = ${A \rightarrow B, A \rightarrow C}$, F₂ = ${A \rightarrow D, D \rightarrow E}$.

Let's check if we can derive all original FDs from F₁ $\cup$ F₂ = ${A \rightarrow B, A \rightarrow C, A \rightarrow D, D \rightarrow E}$.

• $A \rightarrow BC$: From $A \rightarrow B$ and $A \rightarrow C$ in F₁, we can derive $A \rightarrow BC$. This is preserved.
• $D \rightarrow E$: This is explicitly in F₂. This is preserved.
• $A \rightarrow D$: This is explicitly in F₂. This is preserved.
• $BC \rightarrow D$: Can we derive $BC \rightarrow D$ from ${A \rightarrow B, A \rightarrow C, A \rightarrow D, D \rightarrow E}$? Let's find the closure of BC: ${BC}^{+}$.
  • ${BC}^{+} = BC$. There are no dependencies starting with B or C alone or BC in F₁ $\cup$ F₂ that would add A, D, or E. Therefore, ${BC}^{+} = BC$.

Since ${BC}^{+}$ does not contain D, the dependency $BC \rightarrow D$ from the original set F is not preserved in the decomposition.

Evaluating the Options

Based on our analysis:

• R₁ is in 3NF.
• R₂ is in 2NF but not in 3NF.
• The decomposition is not dependency preserving.

Let's look at the given options:

Options 2, 3 (assuming R3 is R1), and 4 all seem to contain true statements based on our analysis. However, multiple-choice questions typically have only one best or intended answer. The provided correct answer text is "R ₁is in 3 NF and R ₂is in 2 NF", which exactly matches Option 4. While R₂ being in 2NF and R₁ being in 3NF is also true (Option 3 with assumption), Option 4 specifically combines R₁ being in 3NF and R₂ being in 2NF, which is a precise statement of their highest achieved normal forms among 2NF and 3NF.

Conclusion on Normal Forms

Based on the detailed analysis of R₁ and R₂ regarding 2NF and 3NF:

• R₁(A, B, C) is in 3NF because it is in 2NF and has no transitive dependencies of non-prime attributes on the candidate key A.
• R₂(A, D, E) is in 2NF because it is in 1NF and all non-prime attributes (D, E) are fully dependent on the candidate key A. However, it is NOT in 3NF due to the transitive dependency $A \rightarrow E$ via D.

Therefore, the statement "R₁ is in 3 NF and R₂ is in 2 NF" is true.

Revision Table: Database Normalization Concepts

Additional Information: Dependency Preservation and Lossless Join Decomposition

When decomposing a relation, two desirable properties are Dependency Preservation and Lossless Join.

• Dependency Preservation: A decomposition is dependency preserving if the union of the functional dependencies of the decomposed relations is equivalent to the original set of functional dependencies. This ensures that we can check the original dependencies by only checking the dependencies in the decomposed relations, without needing to join the tables. As shown in our analysis, this decomposition is not dependency preserving because $BC \rightarrow D$ is lost.
• Lossless Join Decomposition: A decomposition of relation R into R₁, R₂, ..., R_n is lossless if joining R₁, R₂, ..., R_n recovers the original relation R without generating spurious tuples. For a decomposition into two relations R₁ and R₂, it is lossless if (R₁ $\cap$ R₂) → R₁ or (R₁ $\cap$ R₂) → R₂ holds based on the functional dependencies.
  • In our case, R₁ = (A, B, C) and R₂ = (A, D, E). The intersection is R₁ $\cap$ R₂ = ${A}$.
  • We need to check if ${A}^{+} \rightarrow ABC$ (i.e., A → R₁) or ${A}^{+} \rightarrow ADE$ (i.e., A → R₂) is derivable from the original FDs F.
  • From F, ${A}^{+} = A$. Using $A \rightarrow BC$, ${A}^{+} = ABC$. Using $A \rightarrow D$, ${A}^{+} = ABCD$. Using $D \rightarrow E$, ${A}^{+} = ABCDE$.
  • Since ${A}^{+}$ contains both R₁ (ABC) and R₂ (ADE) attributes, ${A} \rightarrow R_{1}$ and ${A} \rightarrow R_{2}$ are derivable. Thus, the decomposition is lossless.

This decomposition (R₁, R₂) is lossless join but not dependency preserving.