# Why databases make the distinction between basic logical operations and functions

It just occurred to me that things like "greater than or equal to" and other "logical operators" are also just simple functions, such as gte(a, b) == a >= b. This makes me wonder why these are treated as "special" in databases and why they are not just functions like SQL functions. Wondering if there is some advantage to treating them differently like they do.

• It might just be syntactic sugar. In what way are they treated as "special"? – Yuval Filmus Feb 10 '19 at 11:48
• I imagine they are used to optimize internals somewhere/somehow, as I'm thinking about >= is a low-level thing implemented by hardware, while SUM isn't necessarily. Stuff like that. – Lance Pollard Feb 10 '19 at 14:17
• In that case, the advantage is obvious. – Yuval Filmus Feb 10 '19 at 14:17

Database indices are typically binary search trees, meaning you can do range queries on them very efficiently. If you handed the database the >= relation as a black box, on the other hand, it would have to iterate over every single record in the table performing the check.

Is this q specific to databases DBMS's/query languages, or to SQL? (I think you don't mean "databases": they're artefacts that hold data.) In all programming languages, operators are just functions written infix, aren't they? In programming languages that allow user-defined operators (like Haskell) that's explicitly syntactic sugar: you can define some operator as equivalent to a function; then you can use the operator infix.

The SQL aggregate functions like SUM( ), COUNT( ) are not really functions in the same way as say SIN( ), because aggregate functions need all sorts of syntax around them such as GROUP BY.

Re "logical operators" in SQL like AND, OR, NOT, [NOT] EXISTS (that is a good question): their appearing in WHERE clauses is more syntactic, like aggregate functions, than merely being sugar for a function.

Let's start by washing away SQL thinking, and look at Codd's original Relational Algebra.

The RA relational operators are "closed over relations". That is, they take relations as arguments and return relations as results. That means those operators are orthogonal to the types of the values in attributes. (They do require we can test values for equality, as needed for Natural Join, for example.)

An operation like greater-than is 'domain specific'. That is, we can test numbers or strings or dates for greater-than; but we can't test images or sounds or other exotica we might want to hold in the database.

Similarly arithmetic is domain specific: you can't multiply two strings.

Coming back to "logical operators", we need to distinguish: if your attributes are holding Boolean values (or integer 1 vs 0, treated as Booleans), then operations on them that return Booleans are also domain specific: you can't AND strings.

OTOH the Relational Operators do correspond to logical operators (see Codd's 1972 paper on 'relational completeness' of the RA operators: 'complete' means can express all logical operations over relations considered as sets of axioms).

But RA operators do not operate on Booleans, returning Booleans. They operate on relations (sets of axioms) returning relations (sets of consequences).

There is a crossover (I'll do this in SQL, for fear you won't follow the RA):

SELECT DISTINCT * FROM S
WHERE City = 'London' AND Status = 10 ;


The AND in there can be equivalently expressed:

( SELECT DISTINCT * FROM S WHERE City = 'London')
INTERSECT
( SELECT DISTINCT * FROM S WHERE Status = 10) ;


Similarly OR in a WHERE can be expressed using UNION; AND NOT can be expressed using EXCEPT (if your SQL supports it).

The execution engine/query plan may well take advantage of those equivalences: if the database has indexes over City and Status, it's going to be more efficient to stream rows from the database using those indexes separately, then intersect the two streams, as opposed to a full table scan looking for rows matching both tests.

BTW INTERSECT is just a special case of Natural Join.

The equivalences go deeper. Imagine I have a way in SQL to write a table literal, then that above query could be

SELECT DISTINCT *
FROM S
NATURAL JOIN (TABLE (ROW( City 'London')))
NATURAL JOIN (TABLE (ROW( Status 10)))


NATURAL JOIN corresponds to logical AND over the sets of axioms (facts) represented by rows held in a table. Natural Join is more flexible than INTERSECT: the tables aren't required to have the same set of columns. It's an accident of history that SQL INTERSECT must appear as an operator between SELECT clauses; whereas NATURAL JOIN must appear within a FROM phrase as an operator between tables (which might be sub-SELECTs).