Boyce-Codd normal form 2026-10-31
A relational schema is in Boyce-Codd normal form if the determinant of every non-trivial functional dependency is a superkey.
Database Created 2026-10-31 Updated 2026-11-05
A database is an organized collection of data maintained for queries and updates. A database management system manages that collection, enforcing access rules and database integrity constraints. A relational database represents it through database relations, rather than exposing only an arbitrary collection of bytes in files.
For example, a laboratory can store biological sample identifiers, measurement values and scientific instrument identifiers as database tuples. A database query can select measurements above a threshold and join them to scientific instrument records. A foreign key can require every recorded scientific instrument identifier to name an existing scientific instrument. This makes the connection a maintained rule rather than a convention that every application must remember.
The logical relational schema and actual storage are distinct. A database query plan may use an index or scan database pages while returning the same specified result. Database transactions coordinate related updates, and database integrity constraints restrict the permitted states. PostgreSQL's documentation gives a concrete implementation in which named tables contain rows with named, typed columns and databases group tables.[ref]
Database integrity constraint 2026-10-31
Database normalization Created 2026-10-31 Updated 2026-11-05
Database normalization organizes relational schemas using their dependencies to reduce redundant facts and update anomalies. If a table stores
(student,course,instructor,office) and each instructor has one office, repeating the office in every enrolment creates multiple places to update. Splitting instructor-office facts into a separate relation can remove that redundancy. A decomposition must be checked for lossless join and, when needed, dependency preservation; merely creating more tables is not a correctness argument. Different normal forms impose different conditions on functional dependencies and other dependency types. Data independence 2026-11-05
Data independence separates the logical meaning of stored data from details that an application need not know. Physical independence permits changing indexes, page layout or access paths without changing a query's meaning. Logical independence permits some changes in the database's logical organization while preserving the interface exposed to existing applications, often through views.
For example, a query asking for an employee's department should return the same answer after the database replaces a table scan with a B-tree index. An application that follows stored record addresses directly would instead depend on that representation. E. F. Codd's1970 relational model explicitly argued against dependencies on ordering, indexes and access paths.[ref] Independence does not mean every schema change is invisible: removing a field an application needs changes its contract unless another representation supplies equivalent information.
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.
Fourth normal form 2026-10-31
A relational schema is in fourth normal form if the determinant of every non-trivial multivalued dependency is a superkey. This implies Boyce-Codd normal form because every functional dependency implies a multivalued dependency.
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.
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.
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 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 c Solution 2026-10-31
Take the relational schema and functional dependencyThe attribute closure of is , so is a candidate key. The attribute closure of is just , so it is not a superkey. The set is a superkey but is not a candidate key, because removing leaves the superkey . Thus the only candidate key is , and occurs in none.
For example, records illustrate that the same value may occur at different values. The conclusion about candidate keys follows from the declared functional dependencies, rather than from accidental uniqueness in any one sample.
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 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]