GATE CS 2005 Q76 — Integrity Constraints

The referential integrity constraint states that the foreign key $C$ references the primary key $A$ with an on-delete cascade policy. This means that if a tuple with primary key value $A = x$ is deleted, all tuples with foreign key value $C = x$ must also be automatically deleted.

Let's trace the cascade deletion step-by-step starting with the deletion of the tuple $(2, 4)$:

1. Delete $(2, 4)$:
   This removes the primary key value $A = 2$ from the relation.
2. Cascade to $C = 2$:
   We must delete all tuples where the foreign key $C = 2$. Looking at the table, these tuples are:
   • $(5, 2)$
   • $(7, 2)$
3. Cascade from the newly deleted tuples:
   • Deleting $(5, 2)$ removes the primary key value $A = 5$. Thus, we must delete all tuples where $C = 5$. The only such tuple is $(9, 5)$.
   • Deleting $(7, 2)$ removes the primary key value $A = 7$. Thus, we must delete all tuples where $C = 7$. There are no such tuples in the table.
4. Cascade from $(9, 5)$:
   Deleting $(9, 5)$ removes the primary key value $A = 9$. Thus, we must delete all tuples where $C = 9$. There are no such tuples in the table.

Therefore, the set of all tuples that must be additionally deleted to maintain referential integrity is $(5, 2)$, $(7, 2)$, and $(9, 5)$.