SQL Relationally Complete and Semantically Equivalent Expressions

Question: What is a semantically equivalent expression?
A semantically equivalent expression refers to two or more expressions that, although they may have different syntactical structures or representations, ultimately convey the same meaning or produce the same result when evaluated. In the context of databases and programming languages, semantically equivalent expressions may be used to achieve the same outcome, but with different syntax, algorithms, or query structures.
For example, let's consider the following two SQL queries:
Query 1:

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

Query 2:

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

Both queries have different syntactical structures (one uses >=, and the other uses NOT and <), but they are semantically equivalent because they both retrieve the same set of records - users who are 18 years old or older. Semantically equivalent expressions can be found in various contexts:

1. Mathematical expressions: Two mathematical expressions that simplify to the same result are semantically equivalent. For example, 2 + 3 and 5 are semantically equivalent, as they both represent the same value.
2. Logical expressions: Two logical expressions that evaluate to the same truth values under the same conditions are semantically equivalent. For example, A AND B and NOT (NOT A OR NOT B) are semantically equivalent, as they both represent the same logical operation.
3. Programming constructs: Two pieces of code that produce the same output or side effects when executed are semantically equivalent. For example, a for loop and a while loop that achieve the same iteration can be considered semantically equivalent.

In database query optimization, identifying semantically equivalent expressions can be useful for generating alternative, more efficient query plans that produce the same result. Similarly, in programming languages, semantically equivalent expressions can be used to refactor code for improved readability, performance, or maintainability.

Alternatively, to prove it is not, you need to show there exists at least one expression of the relational algebra for which no such SQL equivalent exists.

In order to show that SQL is relationally complete, it is sufficient to show that

1. there exist SQL expressions for each of the algebraic operators restrict, project, product, union, and difference (all of the other algebraic operators discussed can be defined in terms of these five), and
2. the operands to those SQL expressions can be arbitrarily complex SQL expressions in turn.

Attempt: First of all, as we know, SQL effectively does support the relational algebra RENAME operator, thanks to the availability of the optional AS specification on items in the SELECT clause. We can therefore ensure that tables do all have proper column names, and hence that the operands to product, union, and difference in particular satisfy the requirements of the algebra with respect to column naming. Furthermore, provided those column naming requirements are indeed satisfied, the SQL column name inheritance rules in fact coincide with those of the algebra. Here then are SQL expressions corresponding approximately to the five primitive operators mentioned above:

Moreover, (a) R, R1, and R2 in the SQL expressions shown above are all table expressions (in the sense in which I have been using this latter term up to this point), and (b) if we take any of those expressions and enclose it in parentheses, what results is a table expression in turn. It follows that SQL is indeed relationally complete. Or is it? Unfortunately, the answer is no.
The reason is that there is a slight (?) glitch in the foregoing argument. SQL fails to support projection on no columns at all, because it does not support empty comma lists in the SELECT clause. As a consequence, it does not support TABLE_DEE or TABLE_DUM, and therefore it is not relationally complete after all.
However, SQL is "nearly" relationally complete.