NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/comp/database/6317

Internet Message Format | 1992-08-25 | 5.8 KB

Path: sparky!uunet!dtix!darwin.sura.net!jvnc.net!yale.edu!ira.uka.de!chx400!bernina!neptune!nugget.inf.ethz.ch!marti
From: [e-mail] (Robert Marti)
Newsgroups: comp.databases
Subject: Re: nested SQL select
Message-ID: <[e-mail]>
Date: 25 Aug 92 16:18:11 GMT
References: <[e-mail]> <[e-mail]>
Sender: [e-mail] (Mr News)
Organization: Dept. Informatik, Swiss Federal Institute of Technology (ETH), Zurich, CH
Lines: 110
Nntp-Posting-Host: nugget.inf.ethz.ch

Editorial comment:  This posting is more of an academic exercise
than of practical interest.  All I am trying to show is that any
_pure_ relational algebra expression can be translated into a
single SQL SELECT-statement -- for what it's worth ...

In article <[e-mail]>, [e-mail]
(Jon Roland) writes:
jr> Relational algebra allows expressions which have no SQL
jr> equivalents, because SQL is not an implementation of relational
jr> theory, and doesn't threaten to become one in the future.

rm> An interesting statement.  Could you give me a few examples of
rm> relational algebra expressions which have no SQL equivalent?
rm> (Please only use operators from the set {selection, projection,
rm> union, difference, cartesian product}.  This set of operators
rm> has been shown to be complete.)

jr> You discussed one in your own posting.

Sigh.  No, I didn't.  But I assume that you refer to the following
example in an earlier posting by Paul Singleton:

ps> I have a table T(A,B,C) and I want effectively to
ps>   select A, count(B) from ( project A, B from T ) group by A

As I pointed out in my previous posting, this is _not_ a relational
algebra (RA) expression -- strictly speaking:  "count" and "group by"
are certainly useful operators, but they are _not_ part of RA.
Indeed, in terms of RA, Paul Singleton's expression should
probably look somewhat like

  project[A,count(B)]( group_by[A]( project[A,B](T) ) )
  ^^^^^^^

(The select- (sometimes called restrict-) operator requires a selection
predicate and an RA expression as parameters and filters out the tuples
which do not fulfill the selection predicate.)

jr> A single relational algebra
jr> expression can be composed that does not translate into a single SQL
jr> statement, but requires several of them. Granted, it does translate,
jr> but so clumsily that one has to complain.

Like I said before, it has been shown that the five operators

  select[ <selection-predicate> ]( <RA-expr> )
  project[ <attribute-list> ]( <RA-expr> )
  <RA-expr> * <RA-expr>                      <--- cartesian product
  <RA-expr> + <RA-expr>                      <--- union
  <RA-expr> - <RA-expr>                      <--- difference

are complete, i.e., that any relational algebra expression can be
expressed using just these five operators.  Now, I will give an outline
of an algorithm which shows why I believe that any RA expression _as_
_defined_above_ can _always_ be translated into a single SQL statement:

First, we transform the RA-expression into an equivalent RA-expression
in which the cartesion products will be performed before selections and
projections, and they in turn will be performed before unions and
differences.  This can be done using equivalence laws such as
- moving union and difference "outward":
  select[...](R + S)   ---->  select[...](R) + select[...](S)
  select[...](R - S)   ---->  select[...](R) - select[...](S)
  project[...](R + S)  ---->  project[...](R) + project[...](S)
  project[...](R - S)  ---->  project[...](R) - project[...](S)
  (R + S) * T          ---->  R*T + S*T
  (R - S) * T          ---->  R*T - S*T
- and moving selection and projection "outward":
  select[...](R) * S   ---->  select[...](R * S)
  project[...](R) * S  ---->  project[...](R * S)

Then, translate the parts between union and/or difference operators
separately (see below) and concatenate the results using the SQL-
UNION and WHERE NOT EXISTS constructs.  For each part between union
and/or difference, the attributes in the projection lists end up in
the SQL SELECT-clause (actually, a SELECT DISTINCT-clause, see below),
the selection predicates of the select operators end up as conjunction
in the SQL WHERE-clause and the names listed as arguments of the product-
operator end up in the SQL FROM-clause.   (Don't forget to introduce
aliases for table names if required ... )  I hope this also answers
Paul Singleton's question:
ps> Is there a general algorithm for translating relational algebra
ps> expressions into SQL?

Jon Roland goes on to say:
jr> More serious, however, is the fact that in relational algebra operators
jr> applied to relations yield relations, whereas in SQL they do not always
jr> do so. To be a relation, a table's rows must be unique, and SQL can
jr> yield tables with redundant rows.

Sigh.  The question was whether you could come up with a legal RA expression
which could _not_ be translated into SQL.  You instead tell me that there
are SQL expressions which have no equivalent in RA.  Yes, there are, but
that wasn't my point.

jr> There is no really good substitute for Turing-computable languages, even
jr> only for use in data access.

Well, one of the nice things of languages which are not Turing-complete
(e.g., SQL or even slightly more powerful languages such as Datalog with
stratified negation) is that all statements that you can write in these
languages will return an answer in a finite amount of time.  Many people
view this as a desireable property in the typical database environment
with potentially many users competing for resources.

--
Robert Marti                    |  Phone:    [phone]
Informationssysteme             |  FAX:      [phone]
ETH-Zentrum                     |  E-Mail:   [e-mail]
CH-8092 Zurich, Switzerland     |