Database query

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.