SQL Relationally Complete
Is SQL relationally complete?
Note: To prove that SQL is relationally complete, you need to show that for every expression of the relational algebra, there exists a semantically equivalent expression in SQL.
Proof by Contradiction:
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
- 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
- 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:
| Algebra |
SQL |
| R WHERE bx |
SELECT * FROM R WHERE bx |
| R { A , B , ... , C } |
SELECT DISTINCT A , B , ... , C FROM R |
| R1 TIMES R2 |
SELECT * FROM R1, R2 |
| R1 UNION R2 |
SELECT * FROM R1 |
|
UNION CORRESPONDING |
| |
SELECT * FROM R2 |
| R1 MINUS R2 |
SELECT * FROM R1 |
| |
EXCEPT CORRESPONDING |
|
SELECT * FROM R2 |
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.