Past exam of the computer science course of the University of Oxford 2015 Databases 1 a i Solution 2026-10-31
First use relational selection to keep the Saab cars, then a natural join to find their sales, and finally a relational join to identify the corresponding salespeople. A relational projection givesThe foreign keys ensure that every sale has the referenced car and salesperson. Several qualifying sales by the same person produce just one occurrence of their name under set semantics. Two distinct people with the same name also yield that name only once: this is the requested relational projection onto names.
Past exam of the computer science course of the University of Oxford 2015 Databases 2 a Solution 2026-10-31
Find the salesperson identifiers satisfying each price condition using relational selection and relational projection:Intersect these identifier sets, relational join the result to the salesperson records, and apply relational projection to names:If intersection is not a primitive of the chosen relational algebra, use with relational difference. There is no need to access
Car: the foreign key already ensures that every sale refers to a car.Intersecting names instead of identifiers is wrong. Two different salespeople called Alex, one making only sales and the other only sales, would make Alex appear in both name sets although neither person satisfies the condition. Nor can one sale satisfy both price tests: the two distinct prices require distinct sale records.
Past exam of the computer science course of the University of Oxford 2015 Databases 2 b Solution 2026-10-31
A simple valid database query plan uses a block nested-loop join with the salesperson records on the outside, checking both sale conditions during the same inner scan. It avoids materializing the potentially much larger set of matching sale pairs.
- Read a block of salesperson records. Retain each
empid, its name, and two initially false flags, one for each target price. - Scan all of
Sales. Apply relational selection to disregard other prices. For each retained sale, matchsalespersonidagainst the identifiers in the current outer block, and set the corresponding price flag. Several matching sales only set the same flag again. - After the inner scan, output the names of outer records with both flags true. Repeat for the next outer block, then eliminate repeated names to implement set semantics.
Let be the actual number of salesperson data pages and the number of outer data pages that fit along with the flags and working buffers. With the usual convention of outer pages, one inner input page and one output page, take for . If flag storage requires an extra reserved page, reduce accordingly. The number of outer records is at most , and there are outer blocks. Every such block requires a complete scan of the sales data pages.
Count a database page read or write as one I/O. Conservatively charge to locate the first salesperson leaf and to locate the start of each inner scan; this permits a small double charge if a definition of height includes a data leaf. The estimated read cost isIn the common convention that scan startup and cached internal pages are ignored, the usual upper estimate isFor an empty outer input there are no inner scans. This database query plan requires neither a sorted sale input nor a price index. In particular, the clustered database index on
invoiceno cannot locate records by price. The quantities and describe the amount of qualifying data; they do not justify replacing a complete scan cost by . They can bound the retained work within each scan by roughly sale records, if those page counts describe packed qualifying records. Comparison cost against the outer block is CPU work rather than additional I/O.Finally let be the extra I/O for eliminating repeated output names, including any temporary writes and reads, and let be the final result size in database pages if materialization is required. The total estimate isIf enough additional memory is available to retain all distinct qualifying names while producing the stream, then . This extra memory is an additional assumption, separate from the join buffers. More generally, for pages of raw qualifying names, external merge sort gives for , including spooling. Names can be deduplicated during the merges. Counting this work matters because a database primary key on
empid does not make names unique. No claim of optimality is needed for this database query plan. Relational algebra 2026-10-31
An algebra of operations on database relations. Classical relational algebra has relational selection, relational projection, relational join, Cartesian product, union and relational difference; database aggregation requires an extension.
Relational model Created 2026-10-31 Updated 2026-11-05
The relational model represents data as database relations, which are sets of database tuples over specified value domains. A relational schema names the database attributes and states database integrity constraints; an instance supplies their current values. Relational algebra describes operations on this logical data, while storage order, indexes and access paths belong to its implementation.
For example, the database relation
Reading(sample, value) can contain . A relational selection for values above five followed by relational projection onto sample identifiers returns . Changing the underlying file layout or adding an index need not change that query's meaning. Mathematical database relations have set semantics; SQL often uses bag semantics and has additional SQL NULL behavior.In his 1970 paper, E. F. Codd argued for data independence: application logic should not rely on particular stored orderings, indexes or navigational paths. His relational formulation made that separation central to database design.[ref]
SQL NULL Created 2026-10-31 Updated 2026-11-05
SQL NULL marks a missing or unknown value. Ordinary comparisons involving SQL NULL, including
NULL = NULL, produce the truth value unknown. To test a scalar value for absence, use IS NULL; to compare while treating two missing values alike, use IS NOT DISTINCT FROM.[ref]Comparison Functions and Operators in the PostgreSQL documentation. version 18, section 9.2, null comparisons and predicates
This three-valued logic changes query reasoning.
5 NOT IN (2, NULL) is unknown: five differs from two, but the missing value might be five. A relational selection retains true conditions, so unknown does not pass the filter.[ref]Subquery Expressions in the PostgreSQL documentation. version 18, section 9.24.3, NOT IN with null inputs
Database aggregation has operation-specific rules. On values
2, NULL, 4, COUNT(*) counts three rows, COUNT(value) counts two non-null values and AVG(value) is three. With no input rows, COUNT returns zero while AVG and SUM return SQL NULL. Therefore a blanket rule that all database aggregation ignores SQL NULL is insufficient.[ref]Aggregate Functions in the PostgreSQL documentation. version 18, section 9.21, count variants and empty-input behavior