GATE CS 2015 Set 1 Q41 — ER-model

To find the minimum number of relations in 3NF, we analyze the entities and their relationships step-by-step:

1. Entity Sets

• $E_1$ has attributes: $\{a_{11}, a_{12}\}$ with primary key $a_{11}$.
• $E_2$ has attributes: $\{a_{21}, a_{22}\}$ with primary key $a_{21}$.
• $E_3$ has attributes: $\{a_{31}, a_{32}\}$ with primary key $a_{31}$.

2. Many-to-Many ($m:n$) Relationship $R_{12}$

For an $m:n$ relationship between $E_1$ and $E_2$, we cannot merge the relationship into either entity relation without causing redundancy and violating 2NF/3NF. Thus, we must create a separate relation for $R_{12}$:

Where $a_{11}$ and $a_{21}$ are foreign keys referencing $E_1$ and $E_2$ respectively.

3. One-to-Many ($1:n$) Relationship $R_{13}$

For a $1:n$ relationship where $E_1$ is on the $1$-side and $E_3$ is on the $n$-side, we can merge the relationship into the relation of the $n$-side entity ($E_3$) by adding the primary key of $E_1$ as a foreign key. This avoids creating an extra relation and keeps the schema in 3NF:

Here, the functional dependencies are $a_{31} \rightarrow a_{32}$ and $a_{31} \rightarrow a_{11}$. Since the determinant $a_{31}$ is a candidate key, this relation is in 3NF.

4. Final Set of Relations

The minimum set of relations required is:

1. $E_1(\underline{a_{11}}, a_{12})$
2. $E_2(\underline{a_{21}}, a_{22})$
3. $E_3(\underline{a_{31}}, a_{32}, a_{11})$
4. $R_{12}(\underline{a_{11}, a_{21}})$

Thus, the minimum number of relations is 4.