GATE CS 2015 Set 1 Q.51 (CS Q.41): ER Model and Relational Schema Design

Consider an Entity-Relationship (ER) model in which entity sets $E_1$ and $E_2$ are connected by an $m:n$ relationship $R_{12}$ . $E_1$ and $E_3$ are connected by a $1:n$ ( $1$ on the side of $E_1$ and $n$ on the side of $E_3$ ) relationship $R_{13}$ .

$E_1$ has two single-valued attributes $a_{11}$ and $a_{12}$ of which $a_{11}$ is the key attribute. $E_2$ has two single-valued attributes $a_{21}$ and $a_{22}$ of which $a_{21}$ is the key attribute. $E_3$ has two single-valued attributes $a_{31}$ and $a_{32}$ of which $a_{31}$ is the key attribute. The relationships do not have any attributes.

If a relational model is derived from the above ER model, then the minimum number of relations that would be generated if all the relations are in 3NF is _____.

Your answer

Official answer and solution

Official answer: 4
From: Official GATE 2015 answer key

Solution

Determine the minimal relational schema in 3NF by representing entity sets and relationships according to their mapping cardinalities.

Entity Sets:
- $E_1(a_{11}, a_{12})$ requires a table with primary key $a_{11}$ .
- $E_2(a_{21}, a_{22})$ requires a table with primary key $a_{21}$ .
- $E_3(a_{31}, a_{32})$ requires a table with primary key $a_{31}$ .
Relationship $R_{12}$ ( $m:n$ between $E_1$ and $E_2$ ):
- A many-to-many relationship cannot be combined into either entity table without introducing non-atomic attributes or redundancy.
- Hence, $R_{12}$ requires its own table: $R_{12}(\underline{a_{11}, a_{21}})$ with composite primary key $(a_{11}, a_{21})$ .
Relationship $R_{13}$ ( $1:n$ between $E_1$ and $E_3$ ):
- The relationship is $1$ on $E_1$ and $n$ on $E_3$ . Each entity in $E_3$ is associated with at most one entity in $E_1$ .
- Thus, the primary key of $E_1$ ( $a_{11}$ ) can be placed as a foreign key inside the table for $E_3$ without violating 3NF: $E_3(\underline{a_{31}}, a_{32}, a_{11}).$
- This eliminates the need for a separate table for $R_{13}$ .
Total Relations:
The resulting tables are:
- $E_1(\underline{a_{11}}, a_{12})$
- $E_2(\underline{a_{21}}, a_{22})$
- $E_3(\underline{a_{31}}, a_{32}, a_{11})$
- $R_{12}(\underline{a_{11}, a_{21}})$

All four relations are in 3NF, so the minimum number of relations is $4$ .

Final answer

Common trap

Creating a separate fifth table for the 1:n relationship R13 instead of embedding the foreign key inside entity set E3.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 1
Question: 51 of 65, printed as CS Q.41
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source