Database Design   «Prev 

SQL Relational Completeness and Semantic Equivalence

SQL relational completeness refers to the ability of a query language to express all operations defined by relational algebra, which forms the foundational theoretical basis for relational databases. Codd's theorem establishes that SQL, despite being a practical language rather than a pure theoretical one, is relationally complete because it can simulate the core relational algebra operators, such as selection, projection, join, union, intersection, and difference—through its SELECT, FROM, WHERE, and set operation clauses. Semantic equivalence in this context means that two SQL queries produce identical results for any given database state if they are logically equivalent expressions of the same relational algebra operation, allowing query optimizers to rewrite queries for efficiency without altering outcomes. Understanding both concepts is crucial for database professionals to ensure queries are not only correct but also capable of leveraging the full expressive power of the relational model.

Semantic equivalence in query languages

Two expressions are semantically equivalent when they return the same result set for the same input data, even if their syntax differs. This idea matters in databases because it lets us show that one query language can express the same operations as another.

Example (same meaning, different syntax):

Query 1

SELECT name, age
FROM users
WHERE age >= 18;

Query 2

SELECT name, age
FROM users
WHERE NOT (age < 18);

Both queries select the same rows (users age 18+). They are syntactically different, but semantically equivalent.

Goal: show SQL can express relational algebra

To support the claim that SQL is relationally complete, the standard strategy is:

  1. Identify a small set of core relational algebra operators that can express the rest (commonly: selection, projection, product, union, and difference—plus rename).
  2. Provide a semantically equivalent SQL pattern for each core operator.
  3. Confirm closure: SQL must allow these expressions to be nested (subqueries / derived tables), so outputs can become inputs.

If those requirements hold (under appropriate assumptions about duplicates and nulls), SQL can express every relational algebra expression, which is the practical meaning of “relational completeness” for query work.

Core operator mapping

The table below shows the typical correspondence between core algebra operators and SQL. The SQL forms are written in a style that is compatible with mainstream systems (including Oracle), and they can be nested using subqueries.

Relational Algebra (idea) SQL (semantically equivalent pattern)
Selection (restrict rows)
σpredicate(R)		 
SELECT *
FROM R
WHERE predicate;
Projection (keep columns)
πA,B,...(R)		 
SELECT DISTINCT A, B, ...
FROM R;
Cartesian product
R × S		 
SELECT *
FROM R
CROSS JOIN S;
Union
R ∪ S		 
SELECT *
FROM R
UNION
SELECT *
FROM S;
Difference
R − S		 
-- Standard SQL:
SELECT *
FROM R
EXCEPT
SELECT *
FROM S;
-- Oracle equivalent:
SELECT *
FROM R
MINUS
SELECT *
FROM S;
Rename (attributes / relations)
ρ(R)		 
SELECT col AS new_name, ...
FROM R AS r;

Closure (nesting) in SQL: each SQL block above can be wrapped as a derived table and used by another query: 

SELECT *
FROM (
  SELECT DISTINCT A, B
  FROM R
  WHERE predicate
) t
WHERE t.A IS NOT NULL;

Important caveats for a “formal” proof

If you are trying to prove relational completeness in a strictly formal sense (as in relational theory textbooks), you must account for differences between the pure relational model and real SQL implementations:

  • Duplicates (bags) vs. sets: relational algebra is set-based; SQL often permits duplicates unless you use DISTINCT. A completeness argument typically assumes set semantics (or explicitly applies DISTINCT where needed).
  • NULLs and three-valued logic: the pure model does not include NULL; SQL does. Completeness arguments typically restrict to non-NULL data (or carefully define how NULL participates).
  • Zero-attribute relations (DEE/DUM): some relational-theory discussions treat the inability to represent “tables with no columns” as a reason SQL is not perfectly aligned with the formal algebra in every corner case.
  • Schema compatibility: union/difference require compatible headings (same number and comparable types of columns). This matches the algebra’s requirement that operands be union-compatible.

Bottom line: for practical database querying over ordinary relations (tables with attributes), SQL can express the core relational algebra operators and supports arbitrary nesting. That is why SQL is commonly treated as relationally complete in day-to-day database work, even though strict theoretical edge cases and SQL’s extra features (NULLs, duplicates) complicate a “pure” proof.


www.sentrypc.com