Skip to content
Jamie Little
Part IA Michaelmas Term

Tripos Worked Solutions: 2022 Paper 3 Questions 1 and 2

Question: Databases (Dr Timothy Griffin) --- 2 questions, 10 marks each

Uses the relational movie database: movies(movie_id, title, year), people(person_id, name), has_position(person_id, movie_id, position), plays_role(person_id, movie_id, role), genres(genre_id, genre), has_genre(movie_id, genre_id).

Question 1: SQL queries on the movie database [10 marks]

(a) Number of romantic comedies [4 marks]

Write an SQL query to return the number of movies that are romantic comedies (i.e., movies that have both the ‘Romance’ and ‘Comedy’ genres).

Answer:

A movie is a romantic comedy if it has (at least) one has_genre entry linking it to the ‘Romance’ genre and (at least) one has_genre entry linking it to the ‘Comedy’ genre. We join has_genre to itself on movie_id and join each to genres to filter by genre name:

SELECT COUNT(DISTINCT hg1.movie_id)
FROM has_genre AS hg1
JOIN genres AS g1 ON g1.genre_id = hg1.genre_id
JOIN has_genre AS hg2 ON hg2.movie_id = hg1.movie_id
JOIN genres AS g2 ON g2.genre_id = hg2.genre_id
WHERE g1.genre = 'Romance' AND g2.genre = 'Comedy';

The DISTINCT is a safeguard: if a movie has multiple ‘Romance’ or ‘Comedy’ genre entries (e.g., sub-genres), the self-join could produce multiple matching rows for the same movie, inflating the count.

An alternative using subqueries:

SELECT COUNT(*)
FROM movies
WHERE movie_id IN (
    SELECT movie_id FROM has_genre JOIN genres ON genres.genre_id = has_genre.genre_id
    WHERE genre = 'Romance'
)
AND movie_id IN (
    SELECT movie_id FROM has_genre JOIN genres ON genres.genre_id = has_genre.genre_id
    WHERE genre = 'Comedy'
);

Both approaches are correct. The subquery approach is arguably clearer but the self-join approach (or using INTERSECT) may perform differently depending on the query planner.

(b) Complete SQL for co-actors in romantic comedies [3 marks]

Complete the SQL query to find pairs of co-actors (people who have acted in the same romantic comedy):

SELECT R1.person_id AS pid1, R2.person_id AS pid2, M.movie_id AS movie_id
FROM plays_role AS R1
JOIN plays_role AS R2 ON R1.movie_id = R2.movie_id
JOIN movies AS M ON M.movie_id = R1.movie_id
WHERE R1.person_id <> R2.person_id
AND R1.movie_id IN (
    -- subquery from part (a) to select romantic comedy movie_ids
    SELECT hg1.movie_id
    FROM has_genre hg1
    JOIN genres g1 ON g1.genre_id = hg1.genre_id
    JOIN has_genre hg2 ON hg2.movie_id = hg1.movie_id
    JOIN genres g2 ON g2.genre_id = hg2.genre_id
    WHERE g1.genre = 'Romance' AND g2.genre = 'Comedy'
);

Key points:

  • The JOIN ... ON R1.movie_id = R2.movie_id pairs every actor in a given movie with every other actor in the same movie.
  • R1.person_id <> R2.person_id prevents a person from being their own co-actor and eliminates duplicate self-pairings.
  • The subquery restricts results to romantic comedies only.
  • The result contains both (pid1=A, pid2=B) and (pid1=B, pid2=A) for each co-actor pair. If symmetric pairs are not desired, use R1.person_id < R2.person_id instead of <>.

(c) Co-actor chains [3 marks]

Write an SQL query to find actors who have a co-actor chain of length 2 to a given actor (i.e., A co-acted with B who co-acted with C). Use the co-actor view from part (b).

Answer:

We first define a view (or CTE) for the co-actor relation from part (b), then self-join it to find length-2 chains:

WITH co_actors AS (
    SELECT R1.person_id AS pid1, R2.person_id AS pid2
    FROM plays_role AS R1
    JOIN plays_role AS R2 ON R1.movie_id = R2.movie_id
    WHERE R1.person_id <> R2.person_id
)
SELECT DISTINCT ca1.pid1 AS actor, ca2.pid2 AS chain_end
FROM co_actors ca1
JOIN co_actors ca2 ON ca1.pid2 = ca2.pid1
WHERE ca1.pid1 = ?  -- given actor's person_id
  AND ca2.pid2 <> ca1.pid1;  -- exclude the original actor themselves

For chains of arbitrary length (transitive closure), a recursive CTE is required:

WITH RECURSIVE co_actor_chain(n, person_id) AS (
    -- Base case: the given actor at distance 0
    SELECT 0, person_id FROM people WHERE name = 'Given Name'

    UNION

    -- Recursive case: extend chain by one co-actor step
    SELECT c.n + 1, ca.pid2
    FROM co_actor_chain c
    JOIN co_actors ca ON ca.pid1 = c.person_id
    WHERE c.n < 6  -- depth limit to avoid infinite loops
)
SELECT DISTINCT person_id, n
FROM co_actor_chain
ORDER BY n;

The WHERE c.n < 6 limits recursion depth. Without a limit, cycles in the co-actor graph could cause infinite recursion. This is the Bacon number problem: finding the distance between any two actors in the collaboration graph.

Question 2: ER modelling for supervision allocation [10 marks]

The scenario concerns allocating students to supervision groups for courses at Cambridge. Each course has multiple supervision groups, each run by a supervisor. Students are allocated to groups.

(a) Argue that model M2 is better than M1 [4 marks]

Two ER models M1 and M2 are shown (not reproduced here). M1 links Students directly to Supervisors. M2 introduces a Group entity and an Allocation relationship. Argue why M2 is the better model.

Answer:

M2 is better than M1 for several reasons:

1. M1 conflates distinct concepts. M1 models the relationship “Student is supervised by Supervisor” directly, but this misses the fact that supervision happens in groups for specific courses. A student may be in multiple supervision groups (one for each course), and a supervisor may run different groups for different courses. M1’s direct Student-Supervisor link cannot distinguish which course a supervision belongs to, nor can it represent multiple students in the same group.

2. M2 properly captures the ternary nature. The real-world relationship is ternary: Student-Course-Group-Supervisor. M2 breaks this down cleanly: Group is an entity associated with a Course and a Supervisor; Allocation links Student to Group. This separation of concerns means:

  • A supervisor can run multiple groups for different courses.
  • A student can be in different groups for different courses.
  • The group identity persists independently of its members.

3. M2 avoids redundancy. In M1, if a supervisor changes, every student linked to that supervisor must be updated. In M2, only the Group-Supervisor relationship changes once. Similarly, adding a student to a group does not require storing the supervisor and course information repeatedly.

4. M2 supports queries about groups as first-class entities. With M2, one can ask “how many students are in group X?” or “which groups does course Y have?” without denormalising data. In M1, answering “which students are in the same supervision group?” requires an implicit grouping that the schema does not represent.

(b) Implement M2 in a relational schema [3 marks]

Write the CREATE TABLE statements for M2, including primary keys and foreign keys.

Answer:

CREATE TABLE Courses (
    course_id    INTEGER PRIMARY KEY,
    course_name  VARCHAR(100) NOT NULL
);

CREATE TABLE Supervisors (
    supervisor_id  INTEGER PRIMARY KEY,
    name           VARCHAR(100) NOT NULL,
    email          VARCHAR(100)
);

CREATE TABLE Students (
    crsid       VARCHAR(10) PRIMARY KEY,
    name        VARCHAR(100) NOT NULL,
    college     VARCHAR(50)
);

CREATE TABLE Groups (
    group_id       INTEGER PRIMARY KEY,
    course_id      INTEGER NOT NULL,
    supervisor_id  INTEGER NOT NULL,
    group_name     VARCHAR(50),
    FOREIGN KEY (course_id) REFERENCES Courses(course_id),
    FOREIGN KEY (supervisor_id) REFERENCES Supervisors(supervisor_id)
);

CREATE TABLE GroupMembers (
    group_id  INTEGER NOT NULL,
    crsid     VARCHAR(10) NOT NULL,
    PRIMARY KEY (group_id, crsid),
    FOREIGN KEY (group_id) REFERENCES Groups(group_id),
    FOREIGN KEY (crsid) REFERENCES Students(crsid)
);

Cardinality analysis:

  • Supervisor to Group: 1:N (one supervisor may run many groups; each group has exactly one supervisor, via Groups.supervisor_id).
  • Student to GroupMember: 1:N (one student can be in many groups for different courses; each GroupMembers row references one student).
  • Course to Group: 1:N (one course may have many groups; each group belongs to one course).
  • Group to GroupMember: 1:N (one group has many student members).

The composite primary key (group_id, crsid) on GroupMembers ensures a student cannot be in the same group twice.

(c) SQL for students and their groups [3 marks]

Write an SQL query listing all students with their course and group, including students who are not in any group.

Answer:

The requirement to include students with no group mandates a LEFT JOIN:

SELECT s.crsid, s.name, g.course_id, g.group_id
FROM Students s
LEFT JOIN GroupMembers gm ON s.crsid = gm.crsid
LEFT JOIN Groups g ON gm.group_id = g.group_id;

With LEFT JOIN, every row from Students is preserved. If a student has no matching GroupMembers row (and hence no matching Groups row), course_id and group_id appear as NULL. An INNER JOIN would silently omit these students.

An alternative using UNION:

SELECT s.crsid, s.name, g.course_id, g.group_id
FROM Students s
INNER JOIN GroupMembers gm ON s.crsid = gm.crsid
INNER JOIN Groups g ON gm.group_id = g.group_id
UNION
SELECT s.crsid, s.name, NULL, NULL
FROM Students s
WHERE s.crsid NOT IN (SELECT crsid FROM GroupMembers);

But the LEFT JOIN version is cleaner and typically more efficient, since it scans the data once rather than twice.

Back to Databases