Tripos Worked Solutions: 2023 Paper 3 Questions 1 and 2

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

Question 1 [10 marks]

(a) Vehicle manufacturer ER diagram and schema [4 marks]

(i) Draw an E/R diagram for a vehicle manufacturer.

The scenario: a manufacturer produces vehicles; each vehicle has a VIN, model, number of seats, and colour. Each vehicle contains one engine; each engine has an engine ID, fuel type, and horsepower. Engines are supplied by suppliers; each supplier has a supplier ID, name, and contact details. A supplier may supply many engines, but each engine comes from exactly one supplier.

Answer:

The ER diagram has three entities and two relationships:

• has_engine: Vehicle to Engine, 1:1 (each vehicle has one engine; each engine is in one vehicle).
• supplies: Supplier to Engine, 1:N (a supplier can supply many engines; each engine has exactly one supplier). The arrow from Engine to Supplier indicates the “many” side pointing to the “one” side.

(ii) Draw the relational schema with keys underlined.

Answer:

Vehicles(vin, model, seats, colour)
         ___

Engines(engine_id, fuel, horsepower)
        _________

Supplies(supplier_id, engine_id)
         ___________  _________

Suppliers(supplier_id, name, contact)
          ___________

Since has_engine is 1:1, we can absorb the relationship by putting a foreign key in either table. Here we assume engine_id is included in Vehicles (not shown explicitly but the Supplies table joins Suppliers to Engines).

A more complete representation showing the foreign keys:

Vehicles(vin, model, seats, colour, engine_id)
         ___                          _________
         PK                           FK → Engines

Engines(engine_id, fuel, horsepower, supplier_id)
        _________                    ___________
        PK                           FK → Suppliers

Suppliers(supplier_id, name, contact)
          ___________
          PK

The has_engine relationship is implemented by Vehicles.engine_id referencing Engines.engine_id (with either side being the FK since it is 1:1). The supplies relationship is implemented by Engines.supplier_id referencing Suppliers.supplier_id (FK on the many side).

(iii) Foreign keys and referential integrity.

In this schema:

• Vehicles.engine_id is a foreign key referencing Engines.engine_id.
• Engines.supplier_id is a foreign key referencing Suppliers.supplier_id.

The schema satisfies referential integrity for a given instance if:

• Every engine_id value in Vehicles exists in Engines.
• Every supplier_id value in Engines exists in Suppliers.

Whether a particular example instance satisfies this depends on the data. If the instance has no orphaned foreign key values, it satisfies referential integrity.

(b) GROUP BY and reduction operators [2 marks]

(i) Why does GROUP BY require a reduction operator?

Answer:

GROUP BY partitions the rows of a table into groups where all rows in a group share the same value for the grouping column(s). After grouping, there are multiple rows in each group, but the output must contain exactly one row per group. A reduction (aggregate) operator collapses all the values in the group into a single scalar value. Without an aggregate function, it would be ambiguous which row’s value to emit for non-grouped columns.

For example, in SELECT department, AVG(salary) FROM employees GROUP BY department, the AVG reduces the many salaries per department into one average per department.

(ii) What properties should reduction operators satisfy and why?

Answer:

Reduction operators should be commutative and associative. These properties ensure the result is independent of the order in which rows are processed. Since SQL does not guarantee any particular order of rows within a group (unless ORDER BY is specified in an aggregate context, which is not standard), the aggregate must produce the same result regardless of row ordering.

• Commutative: f(a, b) = f(b, a). The result does not depend on which row is processed first.
• Associative: f(f(a, b), c) = f(a, f(b, c)). The result does not depend on how rows are paired during parallel aggregation.

MIN, MAX, SUM, and COUNT satisfy both properties. AVG is not directly associative, but it can be decomposed into SUM and COUNT which are, and then SUM / COUNT gives the average. This decomposition matters for distributed query processing where partial aggregates from different nodes must be combined.

(c) Eventual consistency [2 marks]

Define eventual consistency. State one advantage and one disadvantage.

Answer:

Definition: Eventual consistency is a consistency model in which, if no new updates are made to a data item, eventually all accesses to that item will return the last updated value. During the period between an update and the convergence of all replicas, different replicas may return different (stale) values.

Advantage: Higher availability. A system using eventual consistency can always accept reads and writes, even during network partitions or replica failures. Any replica can serve a read request without coordinating with others, reducing latency for geographically distributed users.

Disadvantage: During the convergence window, clients may observe inconsistent states. An application reading from two different replicas could see contradictory data, leading to incorrect decisions. For example, after a bank transfer, one replica might still show the money in the source account while another shows it deducted --- an application summing both replicas could double-count the amount.

(d) Graph database architecture [2 marks]

Why does a graph database hold just one graph?

Answer:

A graph database holds a single graph because the model is based on typed nodes and typed directed arcs, where all entities and all relationships coexist in one large connected structure. The value of a graph database lies in path-oriented queries that traverse arbitrary chains of relationships across different entity types (e.g., “find all suppliers within 3 hops of a given part through any combination of relationships”). Splitting the data into multiple disconnected graphs would break these multi-hop queries that cross entity type boundaries. The entire database is the graph; individual “tables” or collections are implemented as node labels and relationship types within the single graph.

---

Question 2 [10 marks]

(a) Join associativity and execution plans [2 marks]

Natural join is associative. Yet different association orders (join plans) can give significantly different execution times. Explain, with an example.

Answer:

Natural join is indeed associative: $(R \bowtie S) \bowtie T = R \bowtie (S \bowtie T)$. However, associativity is an algebraic identity concerning the result, not the cost of computing it.

Consider: $R(A, B)$ with 10 rows, $S(B, C)$ with 1000 rows, $T(C, D)$ with 10 rows.

Plan 1: $(R \bowtie S) \bowtie T$

• First compute $R \bowtie S$. If all 10 values of B in R match all 1000 values in S, the intermediate result has up to 10,000 rows. Then join this with T (10 rows), producing the final result.
• The large intermediate result (10,000 rows) must be materialised and processed by the second join, consuming memory and I/O.

Plan 2: $R \bowtie (S \bowtie T)$

• First compute $S \bowtie T$. If all 10 values of C in T match all 1000 values in S, the intermediate result is again up to 10,000 rows. Then join with R.
• Same worst case, but with different actual data distributions, one plan may be much cheaper.

The optimal plan depends on:

• Selectivity of the joins (how many rows actually match).
• Index availability (if an index on the join column exists, the cost drops from O(NM) to O(N log M)).
• Data statistics collected by the DBMS (histograms, cardinalities).

The query planner uses these statistics to estimate the cost of each plan and choose the cheapest. Two algebraically equivalent expressions can have orders-of-magnitude differences in execution time.

(b) Keys and primary key selection [2 marks]

Give an example of a relation with multiple potential keys. Discuss reasons why one might not be suitable as the primary key.

Answer:

Consider a People relation:

People(national_insurance_no, email, name, date_of_birth)

Both national_insurance_no and email are candidate keys (assuming no two people share an email).

Reasons either might be unsuitable as the primary key:

National Insurance number:

• Not everyone has one (e.g., international students, visitors). A primary key value cannot be NULL, so people without a NI number cannot be stored.
• NI numbers can, in rare circumstances, be reassigned after a person’s death.
• Privacy concerns: using a government-issued identifier as a database key may be undesirable for data-protection reasons.

Email address:

• Email addresses can change over time. Updating a primary key value cascades to all foreign key references, which is expensive and error-prone.
• Email addresses can be shared (e.g., family email accounts), violating uniqueness.
• An email address may be NULL (not everyone has one), but primary key columns must be NOT NULL.

The preferred approach is often a synthetic key (e.g., an auto-incrementing integer person_id), which has no external meaning and therefore never needs to change. The natural keys (national_insurance_no, email) can still have UNIQUE constraints to enforce their logical uniqueness.

(c) XML and semi-structured data [3 marks]

(i) When is XML stored with varying structure useful?

Answer:

XML with varying (flexible) structure is useful in several scenarios:

1. Heterogeneous data sources. When integrating data from different systems, each system may produce differently structured XML for the same conceptual entity. A rigid schema would reject data from some sources; a flexible schema accommodates all of them.

2. Evolving schemas. When the data format changes over time (new fields added, old fields deprecated), existing documents should not become invalid. A flexible structure allows old and new documents to coexist without requiring a migration of all historical data.

3. Optional or sparse data. When different instances of an entity have very different sets of attributes, a fixed schema would require many nullable columns. A flexible XML structure stores only the attributes that are present.

(ii) How would you export relational data to a single XML document?

Answer:

For each table, create a repeated element at the root. For each row, create a child element. For each column, create either a named child element or an attribute.

Example for the movie database:

<database>
  <movies>
    <movie>
      <movie_id>tt0111161</movie_id>
      <title>The Shawshank Redemption</title>
      <year>1994</year>
    </movie>
    <movie>
      <movie_id>tt0068646</movie_id>
      <title>The Godfather</title>
      <year>1972</year>
    </movie>
  </movies>
  <people>
    <person>
      <person_id>1</person_id>
      <name>Tim Robbins</name>
    </person>
  </people>
  <has_genre>
    <entry>
      <movie_id>tt0111161</movie_id>
      <genre_id>1</genre_id>
    </entry>
  </has_genre>
</database>

The root element <database> contains one child per table. Each table element contains one child per row. Each row element contains one child per column (or attributes for columns). The same structure works for JSON: a top-level object with keys for each table, each containing an array of row objects.

(d) Projection in different data models [3 marks]

Projection in relational algebra selects a subset of columns. What is the equivalent in a document database and in a graph database?

Answer:

Document database: There is no direct equivalent of projection because documents do not have a fixed column set. Each document is a self-describing collection of key-value pairs (possibly nested). The closest operation is field selection: specifying which keys to include or exclude in the query result. For example, in MongoDB: db.collection.find({}, {title: 1, year: 1, _id: 0}) returns only the title and year fields. However, this differs from relational projection because:

• Different documents in the same collection may have different sets of fields, so the “projection” is per-document rather than schema-wide.
• Nested fields can be individually projected (e.g., {"address.city": 1}).

Graph database: Again, no direct equivalent. Nodes and edges have property maps (key-value dictionaries). Projection is achieved by specifying which properties to return in the RETURN clause of a Cypher query. For example:

MATCH (p:Person)
RETURN p.name, p.birth_year

This returns only the name and birth_year properties from each matched Person node. Properties not listed in RETURN are omitted from the result. Unlike relational projection, this operates on named properties within a flexible property map, not on a fixed column position.