4 ms·

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 engli

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?

MichaelBurge 3y ago
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.
- e12e 3y ago
  > nothing stops you But ergonomics of the syntax certainly hinders you ...
Skinney 3y ago
> 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).
- ginko 3y ago
  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.
  - tracnar 3y ago
    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 https://en.m.wikipedia.org/wiki/Relational_algebra
  - cmrdporcupine 3y ago
    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.
oldsecondhand 3y ago
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.

MichaelBurge 3y ago

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.

e12e 3y ago
> nothing stops you But ergonomics of the syntax certainly hinders you ...

Skinney 3y ago

> 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).

ginko 3y ago
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.
- tracnar 3y ago
  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 https://en.m.wikipedia.org/wiki/Relational_algebra
- cmrdporcupine 3y ago
  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.

oldsecondhand 3y ago

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.