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 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]
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 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 view 2026-11-05
A database view is a named database query that can be used much like a database relation. An ordinary view stores the query definition rather than a separate persistent copy of its result. Referring to the view evaluates that definition as part of the surrounding database query; changes in the underlying data can therefore change the view's result.[ref]
For example, an orders table might contain identifiers, totals and payment flags. The definition CREATE VIEW unpaid_orders AS SELECT id, total FROM orders WHERE paid = false; exposes the unpaid orders without requiring every application query to repeat the condition. If order 17 is marked paid, the next query of the ordinary view no longer includes that order, subject to the query's database transaction snapshot. Creating the view did not create another independent copy of order 17.
A view can hide storage and schema details behind a stable interface, supporting data independence. A materialized view instead stores results that require a refresh policy. Some ordinary views permit updates, but a view containing aggregation or certain joins may not identify a unique underlying row to change. Update behavior and access control are separate specifications; the word view alone does not guarantee that an arbitrary definition is writable or supplies a security boundary.[ref]
Dependency-preserving decomposition Created 2026-10-31 Updated 2026-11-05
A decomposition in which the database integrity constraints can be enforced using constraints on individual component database relations, without computing their relational join.
A database query has the same result when its ambient domain is extended while all input database relations are unchanged.
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]
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.
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]
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.
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.
A decomposition of a relational schema whose component relational projections always reconstruct the original database relation by natural join, without extra database tuples.
Multi-tenancy 2026-11-05
Multi-tenancy lets distinct consumers share a software service or computing infrastructure while retaining separate data and permitted operations. A tenant is the consumer or administrative grouping treated as one isolated customer. Resource pooling commonly assigns shared physical resources dynamically among tenants.[ref]
For example, two laboratories can use one hosted database application. Each laboratory's users must access only their permitted records, even when both laboratories' records occupy the same database relation. Checks on each database query and limits on resource use serve different purposes: data isolation does not prevent one tenant's expensive work from delaying another. Separate virtual machines are one possible implementation boundary, rather than a requirement of multi-tenancy.
Natural join Created 2026-10-31 Updated 2026-11-05
A natural join combines two database relations by equating every identically named attribute and retaining one copy of each common attribute. If people(id,name) contains (7,Ada) and scores(id,mark) contains (7,90), their natural join contains (7,Ada,90). With no common names it becomes a Cartesian product. Matching several common columns requires all their equalities, so adding a same-named column can silently change the result. An explicit join condition is often clearer when schemas evolve. In SQL, duplicates and null values follow the implementation's join semantics.[ref]
Solutions to all three questions of the examination dated 3 June 2015. The cover permits answers to two questions.[ref]
Use classical relational algebra with set semantics. Write for the paper's Car, Sales, Customer and Salesperson database relations. A natural join between and matches serialnumber; joins involving a salesperson explicitly match salespersonid to empid. Identifiers, rather than names, distinguish customers and salespeople. The calculations use the ordinary non-null relational model; the SQL aggregate below also explains its empty-input behavior.
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.
Take a unary database relation and the positive domain relational calculus query
For the finite input , every pair and belongs to , for every value in the ambient domain. On an infinite ambient domain the answer is infinite. Even if one compares only finite ambient domains, adding a fresh value changes the answer while leaving fixed, violating domain independence of a database query.
The logical disjunction leaves unrestricted in its first branch and unrestricted in its second branch. Thus both variables occur in relational atoms somewhere in the formula, yet database query safety still fails. No negation or implication symbol occurs.
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 dependency
I 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 is
There 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 is
Exactly 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, is
For 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 decomposition
Their 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.