Lossless-join decomposition 2026-10-31
A decomposition of a relational schema whose component relational projections always reconstruct the original database relation by natural join, without extra database tuples.
Past exam of the computer science course of the University of Oxford 2015 Databases 1 a ii Solution 2026-10-31
Construct the required models and the actual customer–model purchases using relational projection and a natural join:The Cartesian product lists every obligation: every customer paired with every model present in
Car. The relational difference consists of unfulfilled obligations. Remove the customer identifiers occurring in this database relation and only then recover names:This is an explicit relational division construction with all customers as the candidate universe. If there are no models, there are no missing obligations, so every customer qualifies. A version starting solely from customers occurring in would incorrectly omit customers with no purchases in that empty-model case.The quantified object here is the
model database attribute, so two makes sharing a model value contribute one required value. If a different application identified a model by the pair (make, model), both the required and purchased relational projections would use that pair. Also, Car contains unsold cars: a model available only in unsold inventory is still a required model, and then nobody qualifies. Testing identifiers before names prevents different customers with the same name from pooling their purchases. 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 1 b Solution 2026-10-31
The right-hand relational projection lists the models of cars for which at least one recorded sale was made by a salesperson earning strictly more than . The outer relational difference removes precisely those models from all models present in
Car. Thus the answer isThis includes models with no sales at all, as well as models sold exclusively by salespeople whose salaries are at most . A model sold by both a low-paid salesperson and a high-paid salesperson is excluded. A salary exactly equal to does not trigger exclusion. These are model-level statements: one unsold car of a model does not rescue that model if a different car of the same model had a qualifying sale. 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.
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 division Created 2026-10-31 Updated 2026-11-05
Relational division expresses an all-required-matches query. Let be a database relation, the required values and an explicit candidate database relation. The desired result isIt can be constructed using Cartesian product, relational projection and relational difference:The inner relational difference contains missing required pairs. Its relational projection identifies failing candidates; removing them from proves the formula.
For example, can record scientific instrument/test pairs and the required tests. An scientific instrument with both pairs passes; one with only the heat pair does not. This is a universal quantifier requirement, unlike an ordinary relational join asking for some match.
When is empty, vacuous truth gives . Choosing is conventional but cannot recover candidates absent from ; use an independently stored scientific instrument database relation if those candidates must be included. Stating the candidate universe makes this edge case unambiguous.
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]