The last topic I want to address in this chapter is ORDER BY (just ORDER, in Tutorial D). Now, despite the title of this chapter, ORDER BY isn’t actually part of the relational algebra; in fact, as I pointed out in Chapter 1, 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). Please don’t misunderstand me here; I’m not saying ORDER BY isn’t useful; however, I am saying it can’t sensibly appear in a relational expression^[110] (unless it’s treated simply as a “no op,” I suppose). By definition, therefore, the following expressions, though legal, aren’t relational expressions as such:

That said, I’d like to point out that for a couple of reasons ORDER BY 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, as we know from Chapter 3.^[111] Second, it’s not a function. All of the operators of the relational algebra described in this book—in fact, all read-only operators, as that term is usually understood—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):

Note: It would be remiss of me not to mention in passing that although the operators of the relational algebra described in this book are indeed functions, most of them have counterparts in SQL that aren’t. This state of affairs is due to the fact that, as explained in Chapter 2, SQL sometimes defines the result of the comparison v1 = v2 to be TRUE even when 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 explained in Chapter 2, therefore, certain SQL expressions are “possibly nondeterministic.” Here’s a simple example:

SELECT DISTINCT CITY FROM S

If one supplier has CITY ‘Paris’ and another ‘Paris ’, then the result will include either ‘Paris’ or ‘Paris ’ (or possibly both), but which result we get might not be defined. 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 the implications of this state of affairs.