Database Design   «Prev  Next»

Lesson 3Relational completeness
ObjectiveDescribe Relational Completeness

Relationally Complete

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
  1. REMOVE (essentially projection on all attributes but one), and
  2. 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
  1. emphasize its close relationship to, and
  2. 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 and Expressions

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.
  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.


Question: How do relational databases draw some of their theoretical properties from Relational Algebra?
Relational databases are based on the relational model, which was introduced by Dr. Edgar F. Codd in 1970. Relational Algebra, a formal system of operators and set theory, forms the theoretical foundation of the relational model. It provides a set of fundamental operations that can be used to manipulate and query relational data.
Relational databases draw some of their theoretical properties from Relational Algebra in the following ways:
  1. Tabular data representation: Relational Algebra provides the basis for representing data in a tabular format, where data is organized into tables (relations) consisting of rows (tuples) and columns (attributes). This tabular representation simplifies data modeling and manipulation, making it more intuitive for users.
  2. Set-based operations: Relational Algebra defines operations that manipulate tables as sets, allowing for powerful and efficient set-based operations such as union, intersection, and difference. These operations can be used to combine or filter data from multiple tables, making it easier to express complex queries.
  3. Selection and projection: Relational Algebra introduces the concept of selection and projection, which correspond to filtering rows and selecting specific columns from a table, respectively. These operations form the basis for querying and extracting relevant data from relational databases.
  4. Joins and Cartesian product: Relational Algebra defines the Cartesian product operation, which combines data from two tables by matching every row from one table with every row from the other table. This operation is the foundation for joins, which are used to combine data from multiple tables based on specific conditions.
  5. Relational integrity Constraints: The relational model, based on Relational Algebra, allows for enforcing integrity constraints such as primary keys, foreign keys, and unique constraints. These constraints help maintain data consistency and integrity in relational databases.
  6. Closure property: One of the essential properties of Relational Algebra is the closure property, which means that the result of any operation on one or more tables is always another table. This property enables the composition of multiple operations, allowing for the construction of complex queries.
  7. Declarative query language: Relational Algebra provides the theoretical foundation for declarative query languages like SQL. SQL allows users to specify what data they want to retrieve or manipulate without defining the specific steps to achieve the desired result. This abstraction simplifies the process of querying and updating data in a relational database.

In summary, relational databases draw many of their theoretical properties from Relational Algebra, which provides a formal system of operators and set theory to represent, manipulate, and query data. The concepts and operations from Relational Algebra form the basis for the relational model, allowing for efficient data modeling, querying, and manipulation in relational databases.

SQL and Relational Theory