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 attribute 2026-10-31
Database index 2026-11-05
A database index is an auxiliary data structure that helps a database management system locate records satisfying selected conditions. It stores information organized for an access pattern, such as searching a column value, without requiring every database tuple to be inspected. The database query still specifies the result; the index supplies a possible route to it.[ref]
Introduction to Indexes in the PostgreSQL documentation. §11.1, indexed lookup example and maintenance costs
For example, a database relation with a million samples can have an index on
sample_id. Looking for one identifier can follow a search structure instead of scanning all rows. A condition matching most rows may still favor a scan, since many separate lookups and row fetches can cost more. The index occupies storage and must be maintained on relevant updates. These costs explain why indexing every column is not automatically the best design. Database primary key 2026-10-31
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 query processing 2026-11-05
Database query processing is the sequence that turns a database query into returned results. In a typical SQL system, it includes parsing the text, checking names and types, rewriting the query when appropriate, database query optimization, and executing the chosen database query plan. Planning chooses operations; execution actually performs storage accesses, relational joins, filtering and aggregation.[ref]
For a request for each customer's total order value, the engine might scan orders, group their database tuples by customer identifier, sum the values and return one result per customer. An alternative plan can first restrict the orders using a database index. The result specification alone does not prescribe which access method performs the work.
A query against a stored database view illustrates why processing has more than a text-to-loop step. PostgreSQL can rewrite the reference into a query on the underlying tables before planning. The executor then walks the resulting plan and obtains rows from its operations. The distinction is useful when diagnosing a slow query: excessive planning work, a poor plan, and unexpectedly expensive execution are different causes even if the same statement triggered them.[ref]
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.
Domain relational calculus Created 2026-10-31 Updated 2026-11-05
Domain relational calculus describes a database query using first-order logic variables ranging over individual attribute values. A formula specifies which output tuples qualify, instead of prescribing a sequence of physical scans or joins. This differs from tuple relational calculus, whose variables range over whole database tuples.
For example, if records an scientific instrument identifier and a measurement value, thenreturns identifiers with some recorded value above five. The existential quantifier binds , while is the output variable. Each returned identifier occurs in a stored database tuple, so extending the ambient domain by unused values cannot change the result.
The apparently simple query behaves differently: with unrestricted quantification, it can return every unused domain value as well as absent recorded values. Database query safety and domain independence of a database query formalize why a finite input must not silently turn such a query into an unbounded enumeration. A finite candidate relation gives the safer intended query .
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.
External merge sort 2026-10-31
A sorting algorithm that sorts memory-sized runs and merges them using storage-backed passes. It can also eliminate repeated database tuples.
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.
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.
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.
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]
Relational projection 2026-10-31
Relational selection 2026-10-31
Retains the database tuples satisfying a condition.