10

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: http://blogs.msdn.com/b/doriancorompt/archive/2013/01/21/bringing-the-querying-power-of-sql-to-javascript.aspx

  • 1
    How would you model a JOIN or a GROUP BY clause? – Ixrec Jun 10 '15 at 18:08
  • 1
    @Ixrec: Like this – Mason Wheeler Jun 10 '15 at 18:11
  • 2
    gnat - If you read the other post, you'll see that they told me that the question was inappropriate for Stackoverflow so afterwards I posted here. You can't win with Stackoverflow sometimes. Either the post gets closed for being inappropriate, in the wrong forum, or too complex so not suitable for this site, or it's so easy you should have just used Google. – Sridhar Sarnobat Jun 10 '15 at 18:48
  • 1
    Oh, I'm supposed to delete the other post. Done. – Sridhar Sarnobat Jun 10 '15 at 18:54
  • 1
    @Sridhar-Sarnobat: Normally, when a bunch of users vote to migrate your question to Programmers.SE, it will automatically be migrated. You closed your question before it reached the requisite 5 votes. – Brian Jun 10 '15 at 19:41
6

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.

  • This only demonstrates that higher-order functions can be used to realize SQL operations, not that the two are related to each other in general. – Bart van Ingen Schenau Jun 10 '15 at 18:16
  • 1
    @Bart: Then question was "is there a sound semantic equivalence that can be proven?" Implementing one thing in terms of another is a time-honored technique for proving equivalence in computer science. For example, one way to prove that a language is Turing-complete by using it to implement another language that is already known to be Turing-complete. – Mason Wheeler Jun 10 '15 at 18:17
  • For a semantic equivalence, I would expect that you can show it in both directions. Both that SQL queries can be expressed in higher-order functions and that you can express a higher-order function in SQL syntax. – Bart van Ingen Schenau Jun 10 '15 at 18:23
  • 2
    Maybe I didn't phrase the question formally enough. I guess I don't need it to be bidirectionally equivalent in 100% of cases. Just that the typical queries through one approach can be rewritten as another. – Sridhar Sarnobat Jun 10 '15 at 18:54
  • 2
    To be fair, the OP did phrase the question as "are SQL queries equivalent to higher-order functions", not "is the SQL language equivalent to a functional programming language", so neither answer is wrong. – Ixrec Jun 10 '15 at 19:57
9

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.

  • Is relational algebra/calculus related to functional programming at all? I think relational languages are derived from set theory but am not sure if that makes them functional. – Sridhar Sarnobat Jun 10 '15 at 18:57
  • 1
    Which is why "higher-order" is in scare quotes. – Robert Harvey Jun 10 '15 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.