The ORDER BY Operator

The last topic I want to address in this chapter is ORDER BY. ORDER BY is yet another operator that's not part of the relational algebra; as I pointed out in Chapter 1, in fact, it isn't a relational operator at all, because it produces a result that isn't a relation (it does take a relation as input, but it produces something else namely, a sequence of tuples as output). Of course, I'm not saying ORDER BY isn't useful; however, I am saying it can't legally or sensibly appear in a relational expression.^[*] By definition, therefore, the following expressions, though legal, aren't relational expressions as such:

^[*] In particular, therefore, it can't appear in a view definition despite the fact that at least one well-known product allows it to!

   S MATCHING SP        | SELECT DISTINCT S.*     ORDER ( ASC SNO )  | FROM   S, SP                        | WHERE  S.SNO = SP.SNO                        | ORDER  BY S.SNO ASC 

That said, I'd like to point out that for a couple of reasons ORDER BY (just ORDER, in Tutorial D) is actually a rather strange operator. First, it effectively works by sorting tuples into some specified sequence and yet "<" and ">" aren't defined for tuples (see Exercise 3-11 in Chapter 3). Second, it's not a function. All of the operators of the relational algebra in fact, all read-only operators, in the usual sense of that term are functions, meaning there's always just one possible output for any given input. By contrast, ORDER BY can produce several different outputs from the same input. As an illustration of this point, consider the effect of the operation ORDER BY CITY on our usual suppliers relation. Clearly, this operation can return any of four distinct results, corresponding to the following sequences (I'll show just the supplier numbers, for simplicity):

   S5, S1, S4, S2, S3   S5, S4, S1, S2, S3   S5, S1, S4, S3, S2   S5, S4, S1, S3, S2 

A note on SQL: It would be remiss of me not to mention in passing that most of the algebraic operators have analogs in SQL that also aren't functions. This state of affairs is due to the fact that, as indicated in the exercises in Chapter 2, SQL allows the comparison v1 = v2 to evaluate to TRUE even if v1 and v2 are distinct. For example, consider the character strings 'Paris' and 'Paris ', respectively (note the trailing space in the latter); these values are clearly distinct, and yet SQL sometimes regards them as equal. As a consequence, certain queries give what the standard calls "possibly nondeterministic results." Here's a simple example:

   SELECT DISTINCT S.CITY FROM S 

If one supplier has CITY value 'Paris' and Paris 'another ', then the result will include either or both of 'Paris' and 'Paris ', but which result we get might be undefined. We could even legitimately get one result on one day and another on another, even if the database hasn't changed at all in the interim. You might like to meditate on some of the implications of this state of affairs.