Tripos Worked Solutions: 2025 Paper 3 Questions 1 and 2

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

Question 1 [10 marks]

(a) SQL for relational algebra expression [2 marks]

The expression $X \cap (Y \cup Z)$ is proposed to be translated to SQL as:

SELECT X.A
FROM X
JOIN Y
JOIN Z
WHERE X.A = Y.A OR X.A = Z.A;

Criticise this translation. Provide a correct SQL formulation.

Answer:

Criticism of the proposed translation:

The proposed SQL has multiple flaws:

1. Missing join conditions. The JOIN clauses lack ON conditions, producing Cartesian products among X, Y, and Z. For tables with $|X|$, $|Y|$, $|Z|$ rows, the intermediate result has $|X| \times |Y| \times |Z|$ rows before the WHERE filter is applied. This is both semantically wrong and catastrophically inefficient.

2. OR condition does not compute intersection of union. The WHERE X.A = Y.A OR X.A = Z.A selects rows where X.A matches something in Y or in Z. This computes $X \cap (Y \cup Z)$ incorrectly for two reasons: (a) a row in X could match Y but not Z and still be included (which is correct for $X \cap (Y \cup Z)$ --- but the cross join amplifies counts), and (b) if a row in X matches both Y and Z, it will appear twice in the result (once from the Y match, once from the Z match), which violates set semantics.

3. No DISTINCT. Even with correct joins, the result would contain duplicates if a value of X.A appears in both Y and Z, or appears multiple times in Y or Z.

Correct SQL formulations:

Approach 1: Using INTERSECT and UNION.

SELECT X.A FROM X
JOIN Y ON X.A = Y.A
INTERSECT
SELECT X.A FROM X
JOIN Z ON X.A = Z.A;

This directly implements $X \cap (Y \cup Z)$: first select X.A values that appear in Y, then intersect with X.A values that appear in Z. But wait --- does this equal $X \cap (Y \cup Z)$? Let us verify: $X \cap (Y \cup Z) = (X \cap Y) \cup (X \cap Z)$. The INTERSECT of “(X join Y) intersect (X join Z)” gives $(X \cap Y) \cap (X \cap Z) = X \cap Y \cap Z$, which is wrong --- it is missing elements that are only in one of Y or Z.

So the correct approach is:

(SELECT DISTINCT X.A FROM X JOIN Y ON X.A = Y.A)
UNION
(SELECT DISTINCT X.A FROM X JOIN Z ON X.A = Z.A);

This correctly computes $(X \cap Y) \cup (X \cap Z) = X \cap (Y \cup Z)$. The DISTINCT in each branch is optional if UNION (rather than UNION ALL) is used, since UNION eliminates duplicates by default. However, including DISTINCT in the sub-selects can reduce the size of intermediate results.

Approach 2: Using subqueries with IN.

SELECT DISTINCT X.A
FROM X
WHERE X.A IN (SELECT Y.A FROM Y)
   OR X.A IN (SELECT Z.A FROM Z);

This is closer to the intent of the original but correctly avoids the Cartesian product. Note the use of OR, which matches the $\cup$ in the expression.

Approach 3: Using EXISTS (most explicit).

SELECT DISTINCT X.A
FROM X
WHERE EXISTS (SELECT 1 FROM Y WHERE Y.A = X.A)
   OR EXISTS (SELECT 1 FROM Z WHERE Z.A = X.A);

(b) Representing lists and sets [3 marks]

(i) Describe two differences between sets and lists.

Answer:

1. Order: Lists are ordered collections; the position of each element matters. Sets are unordered; an element either belongs to a set or does not, with no notion of position.
2. Duplicates: Lists may contain duplicate elements (a value can appear at multiple positions). Sets contain each value at most once; adding a value already in the set has no effect.

(ii) Design relational schemas for representing a list and a set.

Answer:

List schema:

Lists(list_name, position, value)
      _________  ________

Primary key: (list_name, position). Each list is identified by list_name; within each list, position (a natural number, typically 1-based) gives the index of the element. The value at that position is stored in value. The primary key ensures at most one value per position per list. To preserve list semantics, positions should be consecutive (no gaps) and start from 1, but this constraint is procedural rather than declarative.

Set schema:

Sets(set_name, value)
     ________  _____

Primary key: (set_name, value). Each set is identified by set_name; each value appears at most once in each set. The primary key directly enforces uniqueness. No position column is needed.

(iii) Interpretation of two potential schemas.

Schema Foo(N, T, A): Primary key (N, T).

If N is a position (natural number) and T is a list identifier, then Foo represents a list (ordered by N). Alternatively, if T names a set and A is an item, then N being part of the key would make each (T, N) unique, meaning two items cannot share the same position within a set --- but since sets have no positions, using N (a position) in the key is semantically odd. Foo could also represent a set of lists: T names a list, N gives the position within that list, and A is the value. The key (N, T) ensures one value per position per list. Foo can also represent a list of sets if we interpret T as a set name and N as the list position --- but then (T, A) being unique (via the key) is not guaranteed, so Foo works better for lists.

Schema Bar(N, T, A): Primary key (T, A).

This schema cannot precisely represent a list of lists. With key (T, A), each (set, value) pair is unique, which is the definition of a set. If T is a set of sets identifier, Bar represents a set of sets. To represent a list of lists, we would need both the position and the list name in the key, as in Foo.

To represent a list of lists, we need two levels of ordering:

ListOfLists(outer_position, inner_list_name, inner_position, value)

Or equivalently, two tables: one for the outer list ordering and one for the inner lists.

(c) Outer join and three-valued logic [5 marks]

(i) Give an example demonstrating that outer join is not commutative (LEFT vs RIGHT).

Answer:

Consider:

Students(crsid, name, supervisor_id)
Supervisors(supervisor_id, name)

Students LEFT JOIN Supervisors ON Students.supervisor_id = Supervisors.supervisor_id

This returns all students, with supervisor details where available (NULL for students without a supervisor). Students without a supervisor are preserved.

Students RIGHT JOIN Supervisors ON Students.supervisor_id = Supervisors.supervisor_id

This returns all supervisors, with student details where available (NULL for supervisors without students). Supervisors without students are preserved.

The two results are different sets of tuples (one preserves unmatched students, the other preserves unmatched supervisors). Therefore outer join is not commutative.

(ii) Define equijoin using two-valued logic.

Given $R(A, B)$ and $S(B, C)$, the equijoin (natural join restricted to equality on a specific attribute, here B) is:

$R \bowtie S = \{ t = (a, b, c) \mid \exists u = (a, b) \in R,\; \exists v = (b', c) \in S,\; u.b = v.b' \}$

where the comparison $u.b = v.b'$ is evaluated in two-valued logic (TRUE or FALSE). Tuples where the comparison evaluates to TRUE are included; tuples where it evaluates to FALSE are excluded.

In tuple-relational calculus notation:

$\{ (u.A, u.B, v.C) \mid u \in R \land v \in S \land u.B = v.B \}$

(iii) Define left outer join using three-valued logic.

Given $R(A, B)$ and $S(B, C)$, the left outer join $R \ ⟕ \ S$ is:

$R \ ⟕ \ S = (R \bowtie S) \;\cup\; \{(u.A, u.B, \omega, \omega, \ldots) \mid u \in R \land \neg\exists v \in S,\; u.B = v.B \}$

where $\omega$ (or NULL) is used for padding unmatched tuples.

In the context of three-valued logic, the equality $u.B = v.B$ can evaluate to:

• TRUE if both operands are non-NULL and equal.
• FALSE if both operands are non-NULL and not equal.
• UNKNOWN (or NULL, denoted $\bot$) if either operand is NULL.

The natural join component only includes tuples where the equality evaluates to TRUE. Tuples where the equality evaluates to FALSE or UNKNOWN are excluded from the inner join. The outer join then adds back tuples from R that had no match (where for every $v \in S$, the equality was either FALSE or UNKNOWN), padded with NULL values for all attributes of S.

Formally, using three-valued logic:

$R \ ⟕ \ S = \{ t \mid \exists u \in R:\; ((\exists v \in S:\; [u.B = v.B] = \top \land t = (u.A, u.B, v.C)) \;\lor\; ((\forall v \in S:\; [u.B = v.B] = \bot \lor [u.B = v.B] = \bot) \land t = (u.A, u.B, \bot, \bot))) \}$

In simpler terms: for each tuple $u$ in R, check if there exists any $v$ in S where the equality is TRUE. If yes, output the joined tuple. If no, output $u$ padded with NULLs for the S attributes. The three-valued logic aspect is that NULLs in either B column cause comparisons to evaluate to UNKNOWN, which is not TRUE, so NULL-containing rows do not join with each other (even two NULLs do not match, since NULL = NULL evaluates to UNKNOWN, not TRUE).

---

Question 2 [10 marks]

(a) Vineyard database across multiple models [5 marks]

A vineyard produces wines from grapes. Each wine has a name, vintage, and alcohol percentage. Each grape variety has a name and colour. Each wine can be made from multiple grape varieties, each in a specific ratio (percentage). Wines are bottled; each bottle type has a shape and volume. Each wine can be bottled in multiple bottle types.

(i) Draw the ER diagram.

Answer:

• Wine and Grape have a many-to-many relationship Contains with attribute ratio (the percentage of that grape in the wine).
• Wine and Bottle have a many-to-one relationship Bottled_In (each wine is bottled in one type of bottle; each bottle type can hold many wines). If a wine can be bottled in multiple bottle types, the cardinality would be many-to-many with a junction entity, but the question says “each wine can be bottled in multiple bottle types”, so the ER should actually show N:M. Let us revise:

(ii) RDBMS implementation with a limit of three grape types per wine.

Answer:

With a hard limit of three grape varieties per wine, we can embed the grape references directly in the Wines table:

CREATE TABLE Wines (
    wine_id       INTEGER PRIMARY KEY,
    name          VARCHAR(100) NOT NULL,
    vintage       INTEGER NOT NULL,
    alcohol_pct   DECIMAL(4,1),
    grape1_id     INTEGER,
    grape2_id     INTEGER,
    grape3_id     INTEGER,
    ratio1        INTEGER CHECK (ratio1 >= 0 AND ratio1 <= 100),
    ratio2        INTEGER CHECK (ratio2 >= 0 AND ratio2 <= 100),
    ratio3        INTEGER CHECK (ratio3 >= 0 AND ratio3 <= 100),
    FOREIGN KEY (grape1_id) REFERENCES Grapes(grape_id),
    FOREIGN KEY (grape2_id) REFERENCES Grapes(grape_id),
    FOREIGN KEY (grape3_id) REFERENCES Grapes(grape_id)
);

Consistency rules:

• ratio1 + ratio2 + ratio3 = 100 for each wine (assuming all three columns are used; if fewer than three grapes, unused ratios should be 0, and the total of the non-zero ratios must still be 100).
• grape1_id, grape2_id, grape3_id must all be distinct (no duplicate grapes within the same wine). This is hard to enforce declaratively but can be checked with a trigger or application logic.
• Unused grape columns should be NULL, and the corresponding ratio should be 0 or NULL.

(iii) Unrestricted RDBMS implementation (any number of grapes per wine).

Answer:

CREATE TABLE Wines (
    wine_id       INTEGER PRIMARY KEY,
    name          VARCHAR(100) NOT NULL,
    vintage       INTEGER NOT NULL,
    alcohol_pct   DECIMAL(4,1)
);

CREATE TABLE Grapes (
    grape_id    INTEGER PRIMARY KEY,
    name        VARCHAR(50) NOT NULL,
    colour      VARCHAR(20)
);

CREATE TABLE WineGrapes (
    wine_id   INTEGER NOT NULL,
    grape_id  INTEGER NOT NULL,
    ratio     INTEGER NOT NULL CHECK (ratio > 0 AND ratio <= 100),
    PRIMARY KEY (wine_id, grape_id),
    FOREIGN KEY (wine_id) REFERENCES Wines(wine_id),
    FOREIGN KEY (grape_id) REFERENCES Grapes(grape_id)
);

CREATE TABLE Bottles (
    bottle_id   INTEGER PRIMARY KEY,
    shape       VARCHAR(30),
    volume      INTEGER  -- in ml
);

CREATE TABLE Bottling (
    wine_id    INTEGER NOT NULL,
    bottle_id  INTEGER NOT NULL,
    PRIMARY KEY (wine_id, bottle_id),
    FOREIGN KEY (wine_id) REFERENCES Wines(wine_id),
    FOREIGN KEY (bottle_id) REFERENCES Bottles(bottle_id)
);

The junction table WineGrapes handles any number of grape varieties per wine. The composite primary key (wine_id, grape_id) ensures each grape appears at most once per wine. The Bottling junction table handles the many-to-many relationship between wines and bottle types.

A constraint to ensure total ratios sum to 100 requires either a trigger or application-level validation, since SQL CHECK constraints cannot reference other rows.

(iv) Graph database representation using Cypher.

Answer:

CREATE
  (w:Wine {name: 'Château Margaux', vintage: 2015, alcohol_pct: 13.5}),
  (g1:Grape {name: 'Cabernet Sauvignon', colour: 'Red'}),
  (g2:Grape {name: 'Merlot', colour: 'Red'}),
  (b:Bottle {shape: 'Bordeaux', volume: 750}),
  (w)-[:CONTAINS {ratio: 80}]->(g1),
  (w)-[:CONTAINS {ratio: 15}]->(g2),
  (w)-[:BOTTLED_IN]->(b);

Each entity becomes a node with a label (:Wine, :Grape, :Bottle). Attributes become properties on the nodes. Relationships become typed edges with optional properties (ratio on CONTAINS). The many-to-many relationships are naturally represented as edges.

Cypher queries:

-- Find all wines containing Cabernet Sauvignon
MATCH (w:Wine)-[:CONTAINS]->(:Grape {name: 'Cabernet Sauvignon'})
RETURN w.name, w.vintage;

-- Find the composition of a specific wine
MATCH (w:Wine {name: 'Château Margaux'})-[c:CONTAINS]->(g:Grape)
RETURN g.name, c.ratio
ORDER BY c.ratio DESC;

(v) Relative merits of the approaches.

Hardcoded three-grape approach:

• Advantages: Simple schema, no joins needed to get grape composition, fast reads for queries that always need all grape data.
• Disadvantages: Inflexible --- adding a fourth grape requires a schema change (ALTER TABLE). Wastes storage (NULL columns for wines with fewer than three grapes). Complex query logic needed to handle variable numbers of grapes (“which wines use Merlot?” requires WHERE grape1_id = ? OR grape2_id = ? OR grape3_id = ?).

Junction table approach:

• Advantages: Fully flexible (any number of grapes per wine). Normalised --- each grape reference stored once. Simple queries using joins. Adding a grape variety is just a data change, not a schema change.
• Disadvantages: Requires joins for queries that need grape data alongside wine data. Aggregate queries (“total production using Merlot”) require GROUP BY on the junction table, which is more expensive than a column scan.

Graph database approach:

• Advantages: Intuitive model for many-to-many relationships --- grape composition is directly visible as edges. Path queries are natural (“find wines that share at least two grape varieties”). No join tables needed.
• Disadvantages: Less suited for aggregate queries (“total production volume by grape type across all wines”). Property graph databases historically had weaker support for aggregations and transactions compared to RDBMSs. Schema-less nature means less enforcement of data integrity.

(b) JSON in relational databases for recipes [5 marks]

(i) Compare storing recipes as (name, text) pairs vs adding a structured JSON ingredients field.

Answer:

Traditional approach: Recipes(recipe_id, name, instructions_text). The full recipe (including ingredient list and instructions) is stored as free text in instructions_text.

• Advantages: Simple to implement and query. Full-text search can find recipes mentioning “chicken” without parsing. No additional modelling effort.
• Disadvantages: Cannot run structured queries like “find all recipes using chicken and requiring less than 500g of flour”. Changing units (e.g., imperial to metric) requires parsing free text. Ingredient substitutions (e.g., “replace butter with margarine”) cannot be done programmatically without brittle text parsing.

With JSON ingredients field: Recipes(recipe_id, name, instructions_text, ingredients JSON). The ingredients column stores a structured representation, e.g.:

[
  {"name": "chicken breast", "quantity": 500, "unit": "g"},
  {"name": "olive oil", "quantity": 2, "unit": "tbsp"},
  {"name": "garlic", "quantity": 3, "unit": "clove"}
]

• Advantages: Enables structured queries on ingredients (by name, quantity, unit). Supports ingredient scaling (“double the recipe” --- multiply all quantities by 2). Can join with a nutritional database to compute calories per serving. The free-text instructions field remains for the procedural steps.
• Disadvantages: More complex to maintain. Risk of the JSON and text getting out of sync (the text mentions an ingredient not in the JSON, or vice versa). Schema validation for JSON is weaker than for relational columns. Updates to individual ingredients within the JSON array are awkward in SQL (usually requires extracting, modifying, and replacing the entire JSON value).

(ii) Problems with JSON-in-RDBMS and two useful JSON expansion mechanisms.

Answer:

Problems with JSON-in-RDBMS:

1. Opaque to the query planner. Traditional B-tree indexes cannot index values nested inside JSON columns. Without a specialised JSON index (e.g., PostgreSQL GIN index on jsonb), queries that filter on JSON fields require full table scans, reading and parsing every JSON document.
2. Weak schema guarantees. JSON columns do not enforce that documents conform to a particular structure. The database cannot guarantee that every document has an ingredients array, or that each element has name, quantity, and unit fields. This shifts validation burden to the application.
3. Complex updates. Updating a single field within a nested JSON structure usually requires extracting the entire document, modifying it in application code, and writing it back. This is non-atomic (unless wrapped in a transaction), slow, and risks concurrent-update conflicts.
4. Awkward joins. Joining JSON data with relational data requires extracting JSON fields into relational form first. The syntax for this is database-specific and often cumbersome.

Two useful JSON expansion mechanisms:

1. json_each() / json_table() (expanding arrays to rows).

These functions expand a JSON array into a set of rows, turning nested structure into flat relational form. Each element of the array becomes one row, with columns for the element value and, optionally, its index.

Example (PostgreSQL syntax with jsonb_array_elements):

SELECT recipe_id,
       ingredient->>'name' AS name,
       (ingredient->>'quantity')::INT AS quantity,
       ingredient->>'unit' AS unit
FROM recipes,
     jsonb_array_elements(ingredients) AS ingredient;

This produces one row per ingredient per recipe, which can then be filtered, grouped, and joined like any other relational data. For the recipe database, this would let us create a view that flattens the JSON ingredients into relational form, enabling queries like:

SELECT r.name
FROM recipes r,
     jsonb_array_elements(r.ingredients) AS ing
WHERE ing->>'name' = 'chicken breast'
  AND (ing->>'quantity')::INT <= 300;

2. json_extract() / -> operator (extracting individual fields).

These extract a specific field from a JSON value, returning it as a relational scalar. This is useful for pulling out top-level or nested fields into query results.

Example (PostgreSQL):

SELECT recipe_id,
       ingredients->0->>'name' AS first_ingredient,
       ingredients->0->>'quantity' AS first_quantity
FROM recipes;

This extracts the name and quantity of the first ingredient from each recipe’s JSON array. The -> operator navigates the JSON structure; ->> returns the result as text.

For recipes, json_extract could pull out metadata like total cooking time from a nested JSON field, or extract a specific ingredient’s quantity for scaling calculations:

SELECT name,
       (SELECT SUM((ing->>'quantity')::INT)
        FROM jsonb_array_elements(ingredients) AS ing) AS total_quantity
FROM recipes;

This computes the total quantity of all ingredients (summing across all units naively --- unit conversion would require additional logic).