Attribute closure 2026-10-31
The set of database attributes determined by under given functional dependencies. Start from and repeatedly add the right-hand side of each functional dependency whose left-hand side is already included.
Candidate key 2026-10-31
An inclusion-minimal superkey: removing any of its database attributes destroys the superkey property. Minimal means inclusion-minimal, not necessarily smallest in size.
Clustered database index 2026-10-31
An index whose search order determines, or closely follows, the physical placement of the data records. Clustering by one database attribute does not give indexed access by an unrelated database attribute.
Database query Created 2026-10-31 Updated 2026-11-05
A database query requests information computed from stored data. It can filter database tuples, project selected database attributes, combine database relations or aggregate groups. For example, a query can return the count of orders per customer rather than retrieving every order separately. The query specifies a result; a database query plan chooses operations for computing it. Equivalent result specifications can have very different costs under different indexes and data sizes. In SQL, duplicate rows and null values require conventions beyond the simplest mathematical relational algebra.
Database relation 2026-10-31
A set of database tuples with the same named database attributes; unlike an SQL result without duplicate elimination, a mathematical database relation has no repeated database tuples.
Database tuple 2026-10-31
E. F. Codd 2026-11-05
E. F. Codd introduced the relational model in his 1970 paper on large shared data banks. Data is represented by relations rather than application-visible pointers and access paths, supporting data independence: changing physical organization need not change the meaning of a query.[ref]
The distinction is operationally important. A query can request tuples satisfying a predicate while the system chooses an index or scan. Applications specify the information they need instead of navigating one fixed storage layout. Mathematical relations also expose dependencies among attributes, providing a foundation for database normalization.
Entity-relationship model Created 2026-10-31 Updated 2026-11-05
An entity-relationship model describes identifiable entities, their database attributes and the relationships between them before committing to a physical database layout. Entity types classify the objects being recorded; relationship types describe associations, possibly with their own database attributes. Peter Pin-Shan Chen developed the model as a way to retain the meaning of data while relating several existing database models.[ref]
The Entity-Relationship Model-Toward a Unified View of Data by Peter Pin-Shan Chen. sections 1–2.3, entities, relationships, attributes and multilevel views
For example, a laboratory records scientific instrument entities and measurement entities, with a relationship saying which scientific instrument produced each measurement. An scientific instrument's serial number is an identifying database attribute. A calibration date can describe an scientific instrument, while a usage duration can describe a particular relationship occurrence. Distinguishing these placements prevents unrelated facts from being conflated.
Cardinality and participation constraints add rules: every measurement might require exactly one scientific instrument, while an scientific instrument can produce zero or many measurements. An entity-relationship diagram records these choices. Translating the design to a relational schema introduces database relations, identifiers and appropriate foreign keys; the diagram itself does not require a particular index or file structure.
Entity subtype 2026-10-31
An entity type whose instances inherit the identifier, database attributes and relationships of a more general entity type. A total disjoint specialization requires every parent instance to belong to exactly one listed subtype.
Foreign key Created 2026-10-31 Updated 2026-11-05
A foreign key is a database integrity constraint requiring designated database attributes to match a referenced identifier in a database relation. The referenced database relation may be the same one: a self-reference can represent each employee's manager. The identifier being referenced must have the required uniqueness, but the referencing database attributes need not be unique; several employees can have the same manager.[ref]
Constraints in the PostgreSQL documentation. version 18, section 5.5.5, foreign keys and self-referential tree example
For a simple example, let
Instrument(id) contain identifiers . A measurement carrying instrument_id=4 has a matching scientific instrument; one carrying instrument_id=7 violates the foreign key. Deleting scientific instrument four while measurements still refer to it requires a stated policy: reject the deletion, cascade a suitable deletion, or apply another permitted referential action.[ref]SQL NULL and compound foreign keys require an explicit matching policy. A nullable simple reference can represent no parent, whereas
NOT NULL can require a reference. A foreign key enforces reference existence; it does not by itself prove that a self-referencing structure has no directed cycles. Functional dependency 2026-10-31
A database integrity constraint saying that any two database tuples agreeing on database attributes also agree on database attributes .
Lossless join 2026-11-05
A decomposition has a lossless join when projecting any permitted Database relation onto the component schemas and taking their natural join reconstructs exactly the original relation. Every original tuple reappears; the substantive requirement is that no spurious tuples are introduced. The dependencies defining permitted instances are essential to the claim.
For example, decompose into and . If is a functional dependency, this is lossless. Any joined tuple combines and from original rows; the dependency forces every row with that to have the same , so the combined tuple was already present. Without that dependency, original rows and yield two additional crossed combinations on rejoining. Removing redundancy is therefore insufficient: the decomposition must preserve which facts belonged together. A binary decomposition is lossless under functional dependencies when the common attributes determine one of its component schemas.
Multivalued dependency 2026-10-31
For database tuples agreeing on , requires the combinations obtained by swapping their values on and on the remaining database attributes to occur too. A functional dependency implies the corresponding multivalued dependency; complementation exchanges with the remaining database attributes. A multivalued dependency is trivial if or is the full relational schema.
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 c i Solution 2026-10-31
Assume the two database queries have compatible output database attributes. ThenFor a finite input database, the result of the relational difference is a subset of the finite result of , so it is finite and introduces no new values. For the usual domain independence of a database query, let be the input database and let be two ambient value domains containing its data and the query constants. Database query safety givesand thereforeAlthough a domain relational calculus expression for the relational difference uses negation, its positive membership requirement in supplies the necessary range restriction. Negation is not by itself a reason for failure of database query safety.
Past exam of the computer science course of the University of Oxford 2015 Databases 3 b Solution 2026-10-31
Abbreviate the database attributes by for
EventId, ConfId, BuildingId, StartTime, EndTime and ConfOrganizer. Write for the full relational schema.The explicit event assumptions give the functional dependencyI additionally interpret the conference's organizer as a single organizer for the whole conference, giving . This is the natural reading of
ConfOrganizer, but it is stronger than saying only that each event has one organizer. Under this interpretation a compact generating basis of functional dependencies isThere is no premise that an EventId is globally unique, that a conference has one building, or that a start time determines an end time. In particular, the single-room requirement for one subtype in part (a) must not be imposed on this entire database relation.To specify all non-trivial functional dependencies without listing every augmented version, the attribute closure isExactly the functional dependencies with and are non-trivial consequences of the assumptions. In particular, is the only candidate key: both and must be present because neither is generated from other database attributes.
Every functional dependency implies the corresponding multivalued dependency. Thus and, by complementation, hold. Also holds for every , with the usual trivial cases omitted. A complete compact description, including all augmented and complemented cases, isFor a non-trivial multivalued dependency, additionally require and . To see the criterion, if either side of the split is determined by , swapping that side requires no new database tuple. Conversely, if both sides contain a database attribute outside , choose two database tuples agreeing exactly on . They satisfy every functional dependency in , but a mixed database tuple required by the proposed multivalued dependency is neither of them. The two-row database relation is therefore a counterexample.
There is no independent many-valued fact such as buildings freely combining with event times. For example, two events of one conference might have and . A multivalued dependency would require the building to be swappable independently of the event and its times, which these assumptions do not require and the event functional dependency may forbid.
Since is not a superkey, violates Boyce-Codd normal form. The corresponding non-trivial multivalued dependency violates fourth normal form. Use the decompositionTheir common database attribute is , which determines the whole first component. Consequently the decomposition is a lossless-join decomposition: each event joins to exactly its own conference's organizer, producing no spurious database tuples.
In the first component, the only basic non-trivial functional dependency is , whose determinant is a candidate key. In the second it is , again with a candidate key determinant. No independent non-trivial multivalued dependencies with determinants that are not superkeys are implied in either component, so both are in fourth normal form, and therefore in Boyce-Codd normal form. This reaches the strongest normal form tested here. The decomposition is a dependency-preserving decomposition: is enforced in the first component, in the second, and together they imply .
If only the explicitly stated event-level organizer uniqueness is assumed, omit . The basis is then just ; when and otherwise. Under those weaker assumptions the original database relation is already in fourth normal form and Boyce-Codd normal form, so no decomposition is necessary. In particular, separating under that reading could create extra database tuples when different events of one conference have different organizers.
Past exam of the computer science course of the University of Oxford 2015 Databases 3 d Solution 2026-10-31
Let contain the database attributes of , and let contain the given functional dependencies for . To compute the attribute closure , start with and repeatedly add for every functional dependency with , stopping when a full scan adds nothing.
Enumerate every . For each, test whether is not a superkey but becomes one on adding :If no enumerated passes both tests, return no. A direct implementation isIf a candidate key contains , choose . Minimality makes fail the superkey test while passes it, so the algorithm finds a witness.
for each subset X of attributes(R) minus {a}:
if closure(X, F) != attributes(R):
if closure(X union {a}, F) == attributes(R):
return yes
return noConversely, suppose an enumerated passes. Starting from , repeatedly discard any database attribute other than whose removal preserves the superkey property. The process terminates at a superkey minimal with respect to these deletions. Removing cannot leave a superkey: , and a subset of , which is not a superkey, cannot determine more database attributes than . Hence is a candidate key containing . The algorithm need not carry out this minimization to return the correct yes/no answer; it establishes why the witness test suffices.
For an explicit analysis of algorithms, let be the total encoded length of the functional dependencies, counting their left and right database attribute occurrences and delimiters. With Boolean membership arrays, one complete dependency scan costs . There are at most productive scans, followed by one unproductive scan, so a naive attribute closure costs . There are subsets and at most two attribute closure computations per subset. ThusThis is an exponential-time algorithm in the number of database attributes, not a polynomial-time claim. Subsets can be generated successively rather than stored all at once. The argument applies to functional dependencies within the database relation ; dependencies belonging to unrelated database relations do not constrain its candidate keys.
Peter Pin-Shan Chen 2026-11-05
Peter Pin-Shan Chen proposed the entity-relationship model in his 1976 paper. It represents the application world through entities, relationships and attributes, together with a diagrammatic method for database design. The model aims to preserve semantic distinctions before translating them into a particular database representation.[ref]
For example, a relationship between an employee and a project can carry an hours-worked attribute. That quantity belongs to the participation relationship, not to the employee or project alone. Making its placement explicit helps avoid duplicating or misinterpreting facts when designing a relational schema.
Relational difference 2026-10-31
For two database relations with compatible database attributes, retains the database tuples in the first and absent from the second.
Relational join 2026-10-31
Combines database tuples satisfying a matching condition. A natural join uses equality of all shared database attribute names.