Tripos Worked Solutions: 2024 Paper 3 Questions 1 and 2

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

Question 1 [10 marks]

(a) Relational union and intersection [2 marks]

(i) What is required for two relations to be union-compatible?

Answer:

Two relations are union-compatible if they have the same arity (number of attributes) and the corresponding attributes share the same domain (data type). For example, R(A: INTEGER, B: VARCHAR) and S(C: INTEGER, D: VARCHAR) are union-compatible: both have two attributes where the first is integer and the second is varchar. The attribute names do not need to match; the result takes the attribute names from the first operand.

(ii) Does intersection require the same condition?

Answer:

Yes, intersection requires union-compatibility for the same reason: intersection is defined as the set of tuples that appear in both relations, and comparing tuples only makes sense if they have the same structure. The formal definition is $R \cap S = \{t \mid t \in R \land t \in S\}$, which requires that the tuples in R and S be comparable.

(b) Cardinality bounds [2 marks]

Relation R(P, B) has P rows, relation S(B, Q) has Q rows. Consider R ∪ S (union) and R ⋈ S (natural join). Give the minimum and maximum number of rows possible.

Answer:

Union R ∪ S: R and S must be union-compatible for R ∪ S to be defined. Assuming they share schema (A, B):

• Minimum: $\max(P, Q)$. Occurs when one relation is a subset of the other; the union is just the larger relation.
• Maximum: $P + Q$. Occurs when R and S are disjoint (no tuple appears in both).

Natural join R ⋈ S: Joins on the common attribute B. R has schema (P, B), S has schema (B, Q). The join is R ⋈ S with result schema (P, B, Q).

• Minimum: 0. Occurs when no value of B appears in both R and S (the sets of B values are disjoint).
• Maximum: $P \times Q$. Occurs when all rows in R and S share the same value of B. Every row in R matches every row in S, producing the Cartesian product. If the common B value appears $P$ times in R and $Q$ times in S, all $P \times Q$ pairs are produced.

(c) Textbook chapters ER diagram [3 marks]

A textbook database stores books and their chapters. Each book has an ISBN, title, and author. Each chapter has a number, title, and page count. Chapters belong to exactly one book. A book can have many chapters.

(i) Draw the ER diagram.

Answer:

• Book is a strong entity with primary key ISBN.
• Chapter is a weak entity: a chapter is identified by its number within a specific book (the same chapter number can appear in different books). The relationship Contains is the identifying relationship.
• Cardinality: 1:N (one book contains many chapters; each chapter belongs to exactly one book).

(ii) Write the relational schema.

Answer:

Books(ISBN, title, author)
      ____

Chapters(ISBN, chapter_number, title, page_count)
         ____  ______________

• Books: primary key is ISBN (simple key, single attribute).
• Chapters: primary key is (ISBN, chapter_number) (composite key). ISBN is also a foreign key referencing Books.ISBN.
• The composite key ensures chapter numbers are unique within a book but can be reused across different books.

(d) Extending the textbook database [3 marks]

The database might be extended to support full-text search and cross-referencing. Discuss what structural changes are needed and the benefits of enforcing consistency rules.

Answer:

Structural changes for full-text search:

• Add a content column (type TEXT or CLOB) to the Chapters table to store the full text of each chapter.
• Create a full-text index on the content column. Many RDBMSs provide specialised full-text index types (e.g., PostgreSQL’s GIN index with tsvector, MySQL’s FULLTEXT index) that support stemming, ranking, and phrase search.
• Alternatively, store chapter text in a separate ChapterText(chapter_id, paragraph_number, text) table for finer granularity, which allows retrieving specific paragraphs rather than the entire chapter.

Structural changes for cross-referencing:

• Add a References table: References(from_book_ISBN, from_chapter_num, to_book_ISBN, to_chapter_num) to model cross-references between chapters. Both foreign key pairs reference Chapters.
• This enables queries like “find all chapters that reference chapter X” or “build a citation graph”.

Benefits of enforcing consistency rules:

1. Referential integrity ensures that cross-references point to chapters and books that actually exist in the database. Without this, broken references accumulate.
2. Chapter number uniqueness (enforced by the composite primary key) prevents duplicate chapter numbers for the same book, which would confuse cross-references.
3. Positive page counts can be enforced with a CHECK(page_count > 0) constraint, preventing nonsensical data entry.
4. Cascading deletes can be configured: deleting a book automatically removes its chapters and any cross-references involving those chapters, maintaining database consistency without manual cleanup.

---

Question 2 [10 marks]

(a) CAP theorem [3 marks]

(i) State and explain the CAP theorem.

Answer:

The CAP theorem (Brewer, 2000) states that a distributed data system can provide at most two of the following three guarantees simultaneously:

• Consistency (C): All nodes see the same data at the same time. After a write completes, all subsequent reads (from any node) return the written value. Equivalent to linearisability.
• Availability (A): Every request received by a non-failing node must result in a response (without error). The system remains operational and responsive.
• Partition tolerance (P): The system continues to operate despite arbitrary message loss or failure of part of the system (a network partition).

It is impossible to achieve all three because: if a network partition occurs, a write to one side of the partition cannot be propagated to the other side. The system must either (a) refuse the write or read on one side (sacrificing Availability), or (b) allow reads to return stale data on the non-updated side (sacrificing Consistency). There is no way to maintain both consistency and availability across a partition.

Many systems label themselves CP (consistent and partition-tolerant, e.g., HBase, BigTable) or AP (available and partition-tolerant, e.g., Dynamo, Cassandra). The “CA” choice is essentially a non-partitioned system and cannot exist in a distributed network.

(b) ‘Relation’ in discrete maths vs databases [3 marks]

Compare the meaning of ‘relation’ and ‘one-to-one’ in discrete mathematics and in databases.

Answer:

Relation in discrete maths: A relation $R$ on set $S$ is a subset of the Cartesian product $S \times S$. A relation can have any subset of pairs. A relation is reflexive if $(x, x) \in R$ for every $x \in S$.

Example: “is the same age as” on a set of people. Every person is the same age as themselves, so this relation is reflexive. “Is the parent of” is not reflexive because no one is their own parent.

Relation in databases: A relation is a subset of the Cartesian product of domains: a table with columns and rows. In the relational model, the term “relation” corresponds to the mathematical concept --- each row is an n-tuple, and the relation is the set of all such tuples.

A database may also have self-referencing (recursive) relationships: a foreign key from a table to itself. Example: Employee(emp_id, name, manager_id) where manager_id is a foreign key referencing emp_id. This models a “reports to” relationship within the same entity type. Unlike the mathematical reflexive relation, not all employees have this self-relationship: the CEO has NULL for manager_id, and only some employees are managers of others.

One-to-one in discrete maths: A bijection (one-to-one correspondence) between two sets --- every element of the first set maps to exactly one element of the second, and vice versa.

One-to-one in databases: A one-to-one relationship between two entity types, e.g., Employee has one Desk, and each Desk is assigned to one Employee. This is implemented with a foreign key in either table plus a UNIQUE constraint on the foreign key column. It is used when two entities have a tight coupling but are logically distinct (different lifetimes, different attributes). In a 1:1 relationship, not every employee must have a desk (the FK can be NULL), and not every entity participates --- unlike a bijection.

(c) Normalisation and redundancy trade-off [2 marks]

Given relations R1(A, B, C, D), R2(A, B, C), R3(A, B, D, E, F), R4(A, D), where F is predictable from E. Criticise the design. If updates are much rarer than reads, might you keep the redundancy?

Answer:

Criticism: Since F is predictable from E, the pair (E, F) contains a functional dependency $E \rightarrow F$. In R3, E and F are both non-key attributes, and E determines F. This is a transitive dependency (or partial dependency if E is part of the key), violating 3NF (or BCNF, depending on the keys). The redundancy means that whenever E is stored with a given value, F must be stored with the same value, creating the risk of update anomalies: changing F for one row without updating all rows with the same E leads to inconsistency.

Normalised design: Split R3 into:

• R3a(A, B, D, E) --- the original relation without F.
• R3b(E, F) --- a lookup table for the E → F mapping, with E as primary key.

Now F appears exactly once per value of E. An update to the mapping only touches one row.

Keeping the redundancy: If updates are much rarer than reads, there is an argument for denormalisation. Storing F alongside E in R3 avoids a join with R3b on every read. The trade-off is:

• For reads: faster (no join needed; single table scan or index lookup).
• For writes: need to update F in multiple rows in R3 (or accept eventual consistency if updates are batched). The application must guarantee that all rows with the same E get the same F.

This is the classic OLAP vs OLTP trade-off: OLTP workloads (many small writes) favour normalisation; OLAP workloads (large read-only queries) can tolerate controlled redundancy for query performance. But the designer must understand and document the redundancy so future maintainers know to update F consistently.

(d) Modelling IsA hierarchies [2 marks]

Describe three approaches to modelling a two-level IsA hierarchy in a relational database. Which scales best for multi-level hierarchies?

Answer:

Consider a hierarchy: Person (supertype) with subtypes Student and Staff, and Staff further subtyped into Academic and Administrator.

Approach 1: One table per type in the hierarchy (ER style).

• Person(person_id, name, dob) --- common attributes.
• Student(person_id, matric_year, college) --- student-specific attributes, FK to Person.
• Staff(person_id, office, salary) --- staff-specific, FK to Person.
• Academic(person_id, department, research_area) --- FK to Staff.
• Administrator(person_id, department, role) --- FK to Staff.

Each entity has exactly the attributes relevant to it. Queries about a specific subtype require joining to the supertype table. Adding a new level to the hierarchy means adding one new table for that level.

Approach 2: Single table with type discriminator and nullable columns.

• Person(person_id, name, dob, type, matric_year, college, office, salary, department, research_area, role)
• type column holds values like ‘Student’, ‘Academic’, ‘Administrator’.
• Columns irrelevant to a given type are set to NULL.

Queries are simple (no joins), but the table has many nullable columns, and constraints (“a Student must have a matric year”) are difficult to enforce declaratively.

Approach 3: One table per concrete subtype only (no supertype table).

• Student(student_id, name, dob, matric_year, college) --- duplicates Person attributes.
• Academic(staff_id, name, dob, office, salary, department, research_area) --- duplicates Person + Staff attributes.
• Administrator(staff_id, name, dob, office, salary, department, role) --- duplicates Person + Staff attributes.

Each table is self-contained, but common attributes are duplicated across multiple tables, and querying “all people” requires a UNION.

Scalability for multi-level hierarchies: Approach 1 scales best. Each level in the hierarchy adds exactly one table, and attributes are never duplicated. Adding a new subtype requires only a new table with a foreign key to its parent. Approach 2 becomes increasingly unwieldy as the number of nullable columns grows with each level, and the type discriminator must encode the full hierarchy path. Approach 3 explodes combinatorially: attributes from every ancestor level are duplicated in every leaf table, and the number of leaf tables grows with the hierarchy depth.