Comment by yowlingcat | Hacker News Reader

Comment by yowlingcat | Hacker News Reader

Parent Full thread

You're talking about the "how" but I'm asking about the "what" -- and I'm not really sure I agree with much of what you mentioned. SQL "reading similar to english" doesn't really mean much. Homoiconicity is syntax sugar and in practice, you can do the same thing in any vanilla programming language you'd use with SQL anyways (query builder flavored ORMs). It's not really a killer app.

BNF and DCGs get a bit closer to what I'm asking, but even then I'm not sure it really adds anything novel -- what, if any advantages do you get from that over the relational algebra whose set theoretic underpinnings serve as the foundation for SQL? How is backtracking functionally different or more powerful than joining?

Let me give an example by way of another formalism, which is the Church-Turing correspondence that establishes a correspondence between the lambda calculus and Turing machines. Is there any theoretically stronger expressive power one gets from Prolog over SQL, or is it an ergonomics question, similar to using say, Ruby over Java?

> Is there any theoretically stronger expressive power one gets from Prolog over SQL,

I guess this is best illustrated by examples.

In prolog, you can define how people are related using "facts" or data:

    person_parent(alfred, benny).
    person_parent(benny, carl).

This then forms relationships. In SQL you could write:

    CREATE TABLE persons ( name TEXT NOT NULL, parent TEXT NOT NULL);

The difference lies in how you query said data.

Let's say I want to know if "carl" is the grandparent of "alfred", in Prolog I would first write a rule to define what a grandparent is:

    grandparent(X, Y):- person_parent(X, Z), person_parent(Z, Y).

Then query if "carl" is the grandparent of "alfred":

    grandparent(alfred, carl). --> true

Now, the interesting thing is that I can use the same rule to ask how many grandkids carl has:

    grandparent(X, carl). --> X = alfred (and any other kid)

Or, I could ask how many grandparents alfred has

    grandparent(alfred, Y). --> Y = carl (and any other grandparent)

Or I could ask for any combinations of kids and their grandparents

    grandparent(X, Y). --> X = alfred, Y = carl (and any other combination).

In SQL, on the other hand, you'd have to write each of these queries by hand.

A more powerful example, is defining the rules of suduko and then asking prolog to finish solving a board for you. I will not even begin to suggest how that would be done in SQL (partly because you simply would not use SQL for that).

I have to admit I never really got into SQL, and maybe learning Prolog in university ruined me for it, but can someone explain why SQL is considered "relational" when you still have to explicitly do queries for basic stuff like this?

If it's just that you can define relations in the database scheme, then pretty any programming language would be considered relational.

SQL is called relational because it's based on relational algebra [1]. Although in practice it only loosely follows that theory.

[1] https://en.m.wikipedia.org/wiki/Relational_algebra

It's relational because it ... sort of... uses relations, though it calls them "tables."

They're not "true" relations though because SQL allowed duplicate tuples ("rows") and missing values (null) which the pure relational model does not permit.

It's also considered relational because it uses at least some of the terminology and functionality of relational algebraic operators (join, project, restrict(select), union, cross product, etc.). Though this sometimes leads to confusion (e.g. "select" in the rel-algebra means something different from what a lot of people writing SQL queries think it means -- 'select' in the relational algebra is a restricting/filter operator, but the way it appears in a SQL query implies that it's the thing choosing which attributes (columns) to retrieve... which is another operation entirely (project) in the relational algebra...)

As for the explicitness, that's orthogonal to the question. Relational algebraic expressions are in fact quite explicit. Datalog queries (and Prolog maybe too, to some degree, but not always) can be essentially compiled down to relational algebraic operations (tho they don't have to be.) And so can SQL.

SQL is sort of ... inbetween... the relational algebra and something like a "relational calculus" which figures more out for you and does things more automagically.

Sometimes the explicitness of SQL is in fact a feature. I've found Datalog queries a bit awkward to read at times, with the joins sort of automagically happening, it's sometimes tricky to fully grasp what's happening behind the scenes.

Regardless one of the features of the relational algebra is that various operations can be re-ordered for efficiency without losing the semantic meaning. So behind the scenes SQL query planners restructure things as they need and desire.

> defining the rules of suduko [...] in SQL

Two rather distinct solutions:

https://www.sqlite.org/lang_with.html#outlandish_recursive_q...

http://conway.rutgers.edu/~ccshan/wiki/blog/posts/Sudoku_in_...

> In SQL, on the other hand, you'd have to write each of these queries by hand

Nope. Can be written as a non-predicated recursive CTE. Just add a 'where' at the end to specify what you want.

The practical difference is in the way the search takes place. In SQL you would get the right results but it might take a lot longer because it might (depending on what you're looking for) generate all possibilities and just pick the ones you want. In Prolog I think it's a bit more intelligent in searching.

That depends, of course because it's an implementation detail and predicate pushdown or whatever might regain that efficiency, but from experience I can say It Depends.

(I recently did something like this at work, so it is actually useful)

Edit: see https://www.andrewvillazon.com/recursive-cte-sql-server/ for something similar

Their theoretical expressive power are the same, they're both turing complete languages. However their practical expressive power is different that comes from language ergonomics, standard libraries and different default optimizations.

SQL with recursive CTEs is Turing-complete. So nothing stops you from writing compilers, rendering Mandelbrot fractals, parsing text, and training neural networks in SQL.

> nothing stops you

But ergonomics of the syntax certainly hinders you ...

Reply on news.ycombinator.com