Lesson 3 | Relational completeness |

Objective | Describe Relational Completeness |

Relational completeness is a basic measure of the expressive capability of a language. If a language is relationally complete, it means that queries of arbitrary complexity can be formulated without having to resort to iterative loops or branching. In other words, it is relational completeness that allows end users (at least in principle), though possibly not in practice to access the database directly, without having to implement repetitive constructs such as 1)for, 2) while or 3) do-while loops.

A relationally complete (q.v.), "reduced instruction set" version of relational algebra with just two primitive operators

As this expanded name suggests, the algebra

But it then goes on to show that (a) either OR or AND could be removed without loss, and (b) NOT and whichever of OR and AND is retained could be collapsed into a single operator; NOT and OR into NOR, or NOT and AND into NAND and thus no serious harm is done by thinking of either NOR or NAND (like REMOVE) as a primitive operator of A.

- REMOVE (essentially projection on all attributes but one), and
- an algebraic analog of either NOR or NAND.

As this expanded name suggests, the algebra

`A`

is designed in such a way as to
- emphasize its close relationship to, and
- solid foundation in,

`A`

operator; rather,
it defines A as supporting explicit NOT, OR, and AND operators. But it then goes on to show that (a) either OR or AND could be removed without loss, and (b) NOT and whichever of OR and AND is retained could be collapsed into a single operator; NOT and OR into NOR, or NOT and AND into NAND and thus no serious harm is done by thinking of either NOR or NAND (like REMOVE) as a primitive operator of A.

The "generic relational operators" are the operators that make up the relational algebra (or something logically equivalent to the algebra), and they are therefore built in, though there is no inherent reason why users should not be able to define additional operators of their own, if desired.
Precisely which operators are included is not specified, but they are required to provide at least the expressive power of the relational calculus.
In other words, they are required to be *relationally complete*.

There seems to be a widespread misconception concerning the purpose of the algebra. To be specific, many people seem to think it's meant just for writing queries, but it is not. Rather, it is for writing relational expressions. Those expressions in turn serve many purposes, including queries but certainly not limited to queries alone. Here are some other important purposes.

There seems to be a widespread misconception concerning the purpose of the algebra. To be specific, many people seem to think it's meant just for writing queries, but it is not. Rather, it is for writing relational expressions. Those expressions in turn serve many purposes, including queries but certainly not limited to queries alone. Here are some other important purposes.

- Defining views and snapshots
- Defining the set of tuples to be inserted into, deleted from, or updated in, some relational variable. (or, more generally, defining the set of tuples to be assigned to some relvar)
- Defining constraints (though here the relational expression in question will be just a subexpression of some boolean expression, typically but not invariably an IS_EMPTY invocation)
- Serving as a basis for investigations into other areas, such as optimization and database design

The relational algebra also serves as a measurement against which the expressive power of database languages can be measured. A language is said to be relationally complete if and only if it is at least as powerful as the algebra, meaning its expressions permit the definition of every relation that can be defined by means of expressions of the algebra (or the calculus).
Relational completeness is a basic measure of the expressive capability of a language; if a language is relationally complete, it means that queries of arbitrary complexity can be formulated without having to resort to branching or iterative loops.