RelationalDBDesign RelationalDBDesign



Database Design   «Prev 

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

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.