Examinable Syllabus Checklist

What the exam tests

The Part IA Databases paper (Paper 3) covers 8 lectures taught in Michaelmas term. The exam typically has 2 questions, each worth 20 marks, testing a mixture of bookwork (definitions, terminology, concepts) and application (SQL queries, relational algebra, ER diagram construction, normalisation). Students must learn everything in the slide deck unless specifically marked unexaminable, must learn a core subset of SQL, and must know all words in the two course glossaries.

Syllabus checklist

1. Introduction (Lecture 1)

• DBMS definition: software abstraction over secondary storage, narrow waist model
• Fields, records, schema, key, index, query, transaction (glossary items)
• Primary vs secondary storage; in-core vs persistent; big data
• Consistency mechanisms: value range check, referential integrity, value atomicity, entity integrity
• CRUD operations: Create, Read, Update, Delete
• The three data models: relational, document, graph
• Distributed databases: CAP theorem, BASE properties

2. Entity-Relationship Models (Lecture 2)

• Entities and attributes as the nouns of data modelling
• Keys: natural keys, synthetic keys, primary keys; notation (underlining)
• Relationships as verbs; cardinality notation (arrows for many-to-one, lines for many-to-many)
• One-to-one, one-to-many, many-to-many cardinalities
• Ternary relationships (diamonds connected to three entities)
• Weak entities: definition, identifying relationship, discriminator, double-border notation
• Entity hierarchies: IsA inheritance; specialisation and generalisation
• Converting ER diagrams to schemas (later formalised in Lecture 4)

3. The Relational Model (Lecture 3)

• Mathematical relations: Cartesian product, subset definition, tuples
• n-ary database relations; attribute domains
• Relational algebra operators:
  • Selection (σ): horizontal subset; condition on attributes
  • Projection (π): vertical subset; eliminates duplicate rows (set semantics)
  • Union (∪): requires union-compatible schemas
  • Intersection (∩): rows common to both relations
  • Set difference (−): rows in first but not second
  • Cartesian product (×): all combinations
  • Renaming (ρ): rename attributes or the relation itself
  • Natural join (⋈): equijoin on all common attribute names, projected once
• Relational algebra expressions: composition of operators into tree form

4. ER to Relational Mapping (Lecture 4)

• Update anomalies: insertion anomaly, deletion anomaly, update/modification anomaly
• Motivation for splitting one big table into multiple smaller tables
• Superkeys and keys: formal definitions; candidate keys; primary key selection
• Foreign keys: definition, referencing constraint, referential integrity
• SQL DDL: CREATE TABLE, PRIMARY KEY, REFERENCES, NOT NULL, data types
• Implementing relationships of various cardinalities:
  • Many-to-many: junction/join table with two foreign keys
  • Many-to-one: foreign key on the many side
  • One-to-one: foreign key on either side with UNIQUE constraint
• Implementing weak entities: composite key (owner’s key + discriminator); foreign key references the identifying owner
• Implementing IsA hierarchies: three strategies (ER style, object-oriented, single table with nulls)

5. Transactions and Normalisation (Lecture 5)

• Transaction definition: a sequence of operations treated as a single logical unit
• ACID properties:
  • Atomicity: all or nothing
  • Consistency: transactions preserve database invariants
  • Isolation: concurrent transactions do not interfere
  • Durability: committed changes survive failures
• BASE properties: Basically Available, Soft state, Eventual consistency
• ACID vs BASE: trade-off between consistency and availability/performance
• Locks and throughput: read locks vs write locks; lock granularity; deadlock
• Redundant data: causes and consequences (update anomalies, wasted storage, inconsistency)
• Normalisation and normal forms:
  • First Normal Form (1NF): atomic values, no repeating groups
  • Second Normal Form (2NF): 1NF + no partial dependencies on a composite key
  • Third Normal Form (3NF): 2NF + no transitive dependencies
  • Boyce-Codd Normal Form (BCNF): stronger than 3NF; every determinant is a candidate key
• OLAP vs OLTP: Online Analytical Processing vs Online Transaction Processing
• ETL: Extract, Transform, Load (for data warehousing)
• Read-oriented vs write-oriented databases; denormalisation trade-offs

6. Document-Oriented Databases (Lecture 6)

• Semi-structured data: data that is self-describing (schema embedded with data)
• XML: structure, elements, attributes, well-formed vs valid, DTD, XSD
• JSON: objects, arrays, primitive types; comparison with XML
• Key-value stores: simplest document model; get/put/delete interface
• Document-oriented and aggregate-oriented databases
• NoSQL movement: motivations (web scale, flexible schema, horizontal scaling)
• TinyDB: a document database example; query-by-example
• Schema-free ideal: benefits (flexibility, rapid iteration) and critiques (no enforced constraints, application must validate)
• Branded types: user-defined type identifiers embedded in documents; inverse of semi-structured data

7. Further SQL (Lecture 7)

• Join complexity: nested-loop join (O(NM)), hash join, merge join, index-assisted join
• Database indexes: B-trees, hash indexes; how they reduce join cost
• Multisets (bags) vs sets: SQL defaults to bags; DISTINCT keyword; how this differs from relational algebra’s set semantics
• GROUP BY and aggregate functions:
  • GROUP BY creates groups of rows sharing a common value
  • Aggregate functions: MIN, MAX, SUM, AVG, COUNT
  • HAVING clause: filters groups after aggregation (WHERE filters before)
  • Aggregates must be commutative and associative
• NULL and three-valued logic:
  • NULL means unknown, not zero and not empty string
  • Three-valued truth tables: TRUE, FALSE, UNKNOWN
  • NULL behaviour in comparisons, arithmetic, and aggregates
  • IS NULL / IS NOT NULL tests
  • Outer joins: LEFT, RIGHT, FULL; preserving unmatched rows with NULL padding
• Function and relation composition: applying one query’s result as input to another
• Transitive closure: why it cannot be expressed in standard relational algebra
• Recursive SQL: WITH RECURSIVE construct
  • Base case (non-recursive union member)
  • Recursive case (union member referencing the CTE name)
  • Termination condition (empty recursive result)
  • Applications: bill of materials, graph reachability, Bacon numbers

8. Graph Databases (Lecture 8)

• Graph database model: typed nodes and typed directed edges; properties on both
• Why relational stores are inefficient for graph traversal: many joins required
• Neo4j: native graph database; property graph model
• Cypher query language:
  • ASCII art pattern matching: (n:Node)-[:REL]->(m)
  • MATCH, WHERE, RETURN clauses
  • Variable-length paths: -[*1..5]->
  • CREATE, MERGE for data manipulation
• Pattern matching: declarative specification of graph patterns
• Graph algorithms: BFS, DFS, shortest path, PageRank
• Convergence: graph features appearing in relational DBs (recursive CTEs, JSON columns); relational features in graph DBs (aggregation, ACID transactions)

Exam technique

1. Bookwork definitions (4-6 marks): State the definition concisely. Give the context. 3-4 sentences is enough. If asked to compare two things, use a table or structured contrast.
2. SQL / RA application (6-10 marks): Write the query carefully. Think about duplicates, NULLs, edge cases. If the question gives a schema, reference the column names precisely. For RA, use standard notation (σ, π, ⋈, etc.).
3. ER diagram construction (6-8 marks): Read the scenario carefully. Identify entities (nouns), relationships (verbs), and attributes. Decide cardinality. Check for weak entities and IsA hierarchies. Underline keys.
4. Extension / discussion (6-8 marks): Open-ended questions about trade-offs, design decisions, or evaluating a proposed solution. Two well-developed points with specific examples are better than four vague ones.

Key concepts to memorise

Concept	One-line summary
Natural join	Equijoin on all common attribute names, projecting them once
Foreign key	Attribute(s) in one relation referencing the primary key of another
Weak entity	Entity identified by its relationship to an owner entity plus a discriminator
ACID	Atomicity, Consistency, Isolation, Durability
BASE	Basically Available, Soft state, Eventual consistency
CAP theorem	A distributed system can satisfy at most two of: Consistency, Availability, Partition tolerance
CAP: Consistency	All nodes see the same data at the same time
CAP: Availability	Every request receives a (non-error) response
CAP: Partition tolerance	System continues despite network partitions
3NF	No transitive dependencies on non-prime attributes
BCNF	Every determinant is a candidate key
GROUP BY	Partition rows into groups sharing a common value; aggregates reduce each group
Outer join	Preserves unmatched rows from one or both sides, padding with NULL
Recursive CTE	WITH RECURSIVE: base union + recursive step; terminates when no new rows
Transitive closure	Cannot be expressed in standard relational algebra