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

Relationally Complete
Relationally Complete

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 and Relational Theory
Question: How do relational databases draw some of their theoretical properties from Relational Algebra?
Relational databases are fundamentally built upon the principles of relational algebra, which is a branch of mathematics that deals with the theory of sets and relations. Developed by Edgar F. Codd in 1970, relational algebra provides a theoretical framework for relational databases, defining operations that can be performed on tables (or relations) within the database. Here's how relational databases draw some of their theoretical properties from relational algebra:
  1. Set-Based Operations: Relational algebra is centered around set theory, and operations in relational databases, such as UNION, INTERSECT, and EXCEPT, directly correspond to set operations. These operations allow for the combination, intersection, and difference of data sets, respectively, enabling complex data retrieval.
  2. Selection and Projection: The SELECT operation in relational algebra filters rows based on a specified criterion (similar to the WHERE clause in SQL), while the PROJECT operation selects specific columns from a relation. These operations underpin the fundamental ways in which data can be queried and manipulated in relational databases, allowing for the retrieval of specific data subsets.
  3. Join Operations: Join operations in relational algebra combine tuples from different relations based on a common attribute or condition. This is foundational to relational databases, enabling the relational model to establish links between tables through foreign keys and to perform complex queries across multiple tables.
  4. Closure Property: A key theoretical property drawn from relational algebra is the closure property, which states that the result of any operation in relational algebra is itself a relation. This property is crucial in relational databases, as it ensures that the result of any query can be treated as a table upon which further operations can be performed, enabling nested and complex queries.
  5. Data Integrity and Consistency: Relational algebra's strict definitions and operations help enforce data integrity and consistency in relational databases. The relational model's constraints, such as primary keys, foreign keys, and normalization principles, are designed to maintain consistent and non-redundant data, drawing from relational algebra's emphasis on set theory and structured data.
  6. Query Optimization: The theoretical foundations provided by relational algebra also contribute to query optimization in relational databases. Understanding the equivalences and properties of algebraic operations allows database systems to transform and optimize queries for efficient execution, choosing the most effective operation order and methods for data retrieval.

By grounding the operations and structure of relational databases in the solid mathematical framework of relational algebra, database systems benefit from a rigorous, well-defined set of operations that ensure data consistency, enable complex data manipulation, and support efficient data retrieval and storage.

SQL Relationally Complete
SEMrush Software