Are (basic) SQL queries semantically equivalent to Higher Order Functions?

Question

Is SQL basically a domain specific instance of map + fold + filter?

It seems to me that the following SQL:

SELECT name
FROM fruits
WHERE calories < 100 

is just syntactic sugar for the following map + filter + fold operation:

var fruits = [{id : 1, name: 'orange', calories : 100},
    {id : 2, name : 'banana',  calories : 150},
    {id : 3, name: 'apple', calories : '50'}];

fruits.map(function(fruit) { return { name : fruit.name, calories : fruit.calories })
    .filter(function(obj) { return obj.calories < 100 })
    .reduce(function (accumulator, obj) { accumulator + "\n" + val.name; });

Is this coincidence, or is there a sound semantic equivalence that can be proven? How, roughly?

I know in practice SQL has a lot of bells and whistles but at its core is it simply a map-fold-filter operation?

The following article is relevant: Link

Answer 1

Have a look at LINQ, which takes the basic concepts behind SQL and generalizes it to object-oriented programming. The Where operator is a bog-standard Filter, the Select operator is a projection/Map, and so on. All of the basic SQL query operations are represented in LINQ, implemented using higher-order functions, so yes, you're correct in your intuitive understanding of SQL.

The big difference between the example you've got and the way a relational database works is that SQL is designed with a very limited set of commands in mind. It's not Turing-complete and the database designers know what it can and can't do, which makes it a lot easier for them to design the system to optimize queries to a far greater degree than would be possible with a simple Map enumerating a data set element-by-element.

Answer 2

SQL is based on Relational Algebra and Tuple Relational Calculus, not higher-order functions or functional programming. While SELECT, FROM and WHERE have analogous functions in other languages, SQL itself doesn't support generalized higher order functions, but only those "higher-order" functions that the language itself defines.

Since SQL doesn't allow you to write your own custom higher-order functions, it can't be said with any authority that the language supports higher-order functions.

Answer 3

I felt I didn't properly understand the conceptual foundation of SQL until I discovered Ken Iverson's APL.

APL was published late 1962, predominantly conceived not as a computer programming language, but as a shorthand mathematical notation for describing algorithms on the blackboard, which Iverson had developed over preceding years whilst teaching.

Most people with an interest in this topic get at least as far as understanding that SQL can be traced back to Ted Codd's "relational model" of databases, in work first published in 1970.

Personally I've always found most educational accounts of Ted Codd's relational algebra to be an un-general and incomplete explanation of SQL. They don't even do Codd himself much justice, let alone do justice to SQL.

Modern accounts of Codd also continue to employ his fairly awkward notation, which looks even more awkward when crudely typeset on a PowerPoint slideshow (Codd, like Iverson, was working mostly freehand on the blackboard), rather than employing the more modern and keyboard-friendly SQL as the notation to illustrate Codd's concepts.

Indeed, APL was also criticised for many aspects of its infamous and PC-unfriendly notation, if not for its underlying concepts.

Both Iverson and Codd were at IBM in the US during the same era in the 60s and 70s, and although it's unclear to me whether they were ever co-located at the same facility or directly cooperated with one another, they both ultimately became IBM Fellows (Codd just a few years after Iverson) and they were each responsible for some of the most notable IBM technologies, so it seems unlikely that Codd was not influenced by Iverson's thinking.

Anyway, a fundamental point about APL is that it is an array-oriented language. There are arrays of values as a fundamental feature, and operators that manipulate these arrays. The same feature exists in Codd's relational algebra.

And SQL also works in terms of there being arrays of values, array operators which can be composed together, and expressions supplied to certain operators to control their behaviour (which are basically the analogy of "lambda functions" in more recent general-purpose languages).

A crucial thing to note is that the order of evaluation in SQL goes From > Where > Select > Order By, which is not consistent with how it is visually presented. And there may be other perceived deviations at the periphery of the language.

But yes, a select-clause is the analogy of a map function, the where-clause is the analogy of a filter function. Various join-clauses and the group-by clause are implementations of corresponding relational operators. The having-clause is just a where-clause (filter operator) evaluated after, instead of before, the group-by clause.

It's worth noting that operators like join and group-by, are traceable first to Codd and are well-known only within the context of relational algebra, since they depend on the use of three-valued logic and their usefulness as operators is tightly integrated with the relational model.

But the more general concept of array operators, is explained best by Iverson through his work on APL.

Answer 4

A significant difference is that map and filter operate sequentially on ordered sequences, whereas SQL operate on sets which are by definition unordered.

SQL is at a higher abstraction level, because a SQL query does not imply that the operations have to be performed in a particular order. A naive implementation of SQL could translate SELECT and WHERE directly into map and filter, but a sophisticated implementation has a query planner which rearranges the operations into the order (and degree of parallelism) which will give the best performance, taking into account amounts of data and available indexes.

SQL does not have anything similar to reduce. Instead it has built-in aggregate operators like SUM, AVG, MIN, MAX etc which does not imply any particular order of operations.

But ignoring the order of execution, the operations are similar on a logical level. SELECT and map are both homomorphisms, which are operations on a structure that perform a function on each item in the structure but retain the structure. So map on a list yields a new list of the same length and SELECT on a relation (table) in a database yield a new relation of the same size.