RelationalDBDesignRelationalDBDesign





Database Design   «Prev  Next»
Lesson 3Relational completeness
ObjectiveDescribe Relational Completeness

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 REMOVE (essentially projection on all attributes but one), and an algebraic analog of either NOR or NAND.
The name A (note the boldface) is a doubly recursive acronym: It stands for ALGEBRA, which in turn stands for
A Logical Genesis Explains Basic Relational Algebra.
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, the discipline of predicate logic. Most books use solid arrowheads to delimit A operator names, as in NOR., in order to distinguish those operators from operators with the same name in predicate logic or Tutorial D or both, but those arrowheads are deliberately omitted here. More to the point, the Manifesto book does not actually define either NOR or NAND as a primitive 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.



Relational Operators

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, in their totality, 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.
  1. Defining views and snapshots
  2. 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)
  3. 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)
  4. Serving as a basis for investigations into other areas, such as optimization and database design

Relational Algebra

Relationally Complete
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.
SQL Relationally Complete