In addition to natural join, Codd originally defined an operator he called theta-join, where theta denoted any of the usual scalar comparison operators ("=", "", "<", and so on). The operator isnt primitive; in fact, it's equivalent to a restriction of a cartesian product. Here by way of example is a Tutorial D formulation of the "not equals"-join of suppliers and parts on cities (so theta here is ""):
( ( S RENAME ( CITY AS SCITY ) TIMES ( P RENAME ( CITY AS PCITY ) ) WHERE SCITY PCITY
Note that the result has two "city" attributes, SCITY and PCITY. An SQL analog:
SELECT S.SNO, S.SNAME, S.STATUS, S.CITY AS SCITY, P.PNO, P.PNAME, P.COLOR, P.WEIGHT, P.CITY AS PCITY FROM S, P WHERE S.CITY <> P.CITY
We can think of this SQL expression as being implemented in three steps, as follows:
At least to a first approximation, then, the FROM clause corresponds to a cartesian product, the WHERE clause to a restriction, and the SELECT clause to a projection, and the overall SELECT - FROM - WHERE expression represents a projection of a restriction of a cartesian product. It follows that I've just given a loose, but reasonably formal, definition of the semantics of SQL's SELECT - FROM - WHERE expressions; equivalently, I've given a conceptual algorithm for evaluating such expressions. Of course, there's no implication that the implementation has to use exactly that algorithm in order to implement such expressions; au contraire, it can use any algorithm it likes, just so long as whatever algorithm it does use is guaranteed to give the same result as the conceptual one. And there are often good reasons usually performance reasons for using a different algorithm, thereby (for example) executing the clauses in a different order or otherwise rewriting the original query. However, the implementation is free to do such things only if it can be proved that the algorithm it does use is logically equivalent to the conceptual one. Indeed, one way to characterize the job of the system optimizer is to find an algorithm that's guaranteed to be equivalent to the conceptual one but performs better.