Database

An organized collection of data together with rules for its representation and access.

Represents entity types, their identifiers and database attributes, and relationships with participation and cardinality constraints.

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.

A diagram of an entity-relationship model, including relationship cardinalities and, when needed, subtype and identification constraints.

A sequence of operations treated as one unit of database work.

An ordering of operations of several database transactions that preserves the operation order within each database transaction.

A database schedule that can be turned into a serial database schedule by swapping adjacent operations of different database transactions that do not conflict. Reads and writes of the same object conflict when at least one is a write.

A directed graph with a vertex for each database transaction and an edge from the earlier to the later participant in each conflicting pair of operations. A database schedule is a conflict-serializable database schedule exactly when this directed graph has no directed cycle.

A database schedule in which every database transaction runs as one contiguous group, without interleaving another database transaction.

A block transferred between storage and memory; database query plan costs are often estimated by the number of such transfers.

A physical recipe for evaluating a database query, specifying scans, index accesses and implementations of relational joins and duplicate elimination.

A relational join implementation that retains a block of outer records in memory while scanning the inner input. With $b$ outer pages per block, $p$ outer pages and $q$ inner pages, its data-read cost is $p+\lceil p/b\rceil q$, before temporary output costs.

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.

Computes a summary such as a count, sum or arithmetic mean over a collection of records.

Database query results may contain repeated records, with their multiplicities retained.

Database query results contain no repeated database tuples. SQL usually uses bag semantics unless duplicate elimination is requested.

A database query language using first-order logic variables for individual values rather than whole database tuples.

The requirement that a database query have a finite, appropriately range-restricted answer on finite input. In the usual domain-independent interpretation, extending the ambient value domain with unused values must not change the answer. The absence of a negation symbol alone does not ensure safety.

A database query has the same result when its ambient domain is extended while all input database relations are unchanged.

SQL's marker for an unknown or absent value. Database aggregation generally ignores these markers, and AVG returns this marker when there are no non-null inputs.^[ref]

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.

A relational algebra operation expressing a universal matching requirement. An explicit relational difference construction can specify the intended candidate universe, including the case of an empty divisor.

For two database relations with compatible database attributes, retains the database tuples in the first and absent from the second.

Combines database tuples satisfying a matching condition. A natural join uses equality of all shared database attribute names.

Retains specified database attributes, eliminating repeated database tuples under set semantics.

Retains the database tuples satisfying a condition.

A database organized using the relational model.

Data are represented as database relations whose database tuples have named database attributes.

Names of database relations, their database attributes and value domains, together with applicable database integrity constraints.

A decomposition in which the database integrity constraints can be enforced using constraints on individual component database relations, without computing their relational join.

A decomposition of a relational schema whose component relational projections always reconstruct the original database relation by natural join, without extra database tuples.

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.

A relational schema is in Boyce-Codd normal form if the determinant of every non-trivial functional dependency is a superkey.

For database tuples agreeing on $X$, requires the combinations obtained by swapping their values on $Y\setminus X$ and on the remaining database attributes to occur too. A functional dependency implies the corresponding multivalued dependency; complementation exchanges $Y$ with the remaining database attributes. A multivalued dependency is trivial if $Y\subseteq X$ or $X\cup Y$ is the full relational schema.

A database integrity constraint saying that any two database tuples agreeing on database attributes $X$ also agree on database attributes $Y$.

The set of database attributes determined by $X$ under given functional dependencies. Start from $X$ and repeatedly add the right-hand side of each functional dependency whose left-hand side is already included.

A database integrity constraint requiring values of specified database attributes to occur in a referenced identifier of another database relation.

A set of database attributes that determines every database attribute of a database relation under its database integrity constraints.

An inclusion-minimal superkey: removing any of its database attributes destroys the superkey property. Minimal means inclusion-minimal, not necessarily smallest in size.

The candidate key selected as the principal identifier for database tuples of a database relation.

A condition required of every legal instance of a relational schema.

A named component of a database tuple.

One record of a database relation, assigning a value to each database attribute.

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.