4 ms·

So I struggled with this. I guess the intention is to be better than SQL but then I was left with "under which circumstances?". With that question in mind I d

So I struggled with this. I guess the intention is to be better than SQL but then I was left with "under which circumstances?". With that question in mind I didn't feel the article addressed the issue. The author might do better to think in terms of "what burning problem are we trying to fix and how did we fix it".

YeGoblynQueenne 4y ago
>> The author might do better to think in terms of "what burning problem are we trying to fix and how did we fix it". I have no idea who first came up with the name "datalog", and what exactly was their motivation (I've looked, but couldn't find the original reference to datalog), but the burning problem that datalog does fix is Prolog's semi-decidability, or in other words, its tendency to enter infinite recursions. One half of the reason for that is Prolog's "compound terms" (known as functions, in First-Order Logic terminology) and the other half is Prolog's use of depth-first search for evaluation. Functions, along with logic variables, mean that a predicate's Herbrand base (its set of logical atoms) can be expanded forever: if f(x) is a term, f(f(x)) is a term, f(f(f(x))) is a term... and so on, ad infinitum. The depth-first search evaluation just gets stuck in left-recursions when the first body literal of a clause is a recursive literal: p(x):- p(x), q(x) loops forever, in Prolog with depth-first search. Datalog is Prolog without functions other than constants, and it can be evaluated "bottom up", both of which overcome Prolog's semi-decidability (but eliminate its completeness). But of course this is not a very clear motivation for its use as a database language, only its use as an alternative to Prolog. More to the point, there are many datalog variants. Some that accept negation, some that do not, some that allow recursion, some that do not, and so on. There's a lot of information on different datalogs, seen from the point of view of database research in this free ebook on databases: http://webdam.inria.fr/Alice/ http://webdam.inria.fr/Alice/ See chapters 12 - 15. And see these lecture notes for a more logic-programm-y discussion of fixpoint semantics of definite logic programs: https://www.doc.ic.ac.uk/~mjs/teaching/KnowledgeRep491/Fixpoint_Definite_491-2x1.pdf https://www.doc.ic.ac.uk/~mjs/teaching/KnowledgeRep491/Fixpo...
- falsissime 4y ago
  > but the burning problem that datalog does fix is Prolog's semi-decidability, or in other words, its tendency to enter infinite recursions. Prolog's built-in search is not semidecidable. https://en.wikipedia.org/wiki/Decidability_(logic)#Semidecidability https://en.wikipedia.org/wiki/Decidability_(logic)#Semidecid... As you observe, Prolog gets stuck in left-recursions. But iterative deepening for Prolog is semidecidable (among other fair methods). This indeed is restricted to the pure, monotonic subset of (full) Prolog together with all pure, monotonic extensions.
  - YeGoblynQueenne 4y ago
    >> As you observe, Prolog gets stuck in left-recursions. But iterative deepening for Prolog is semidecidable (among other fair methods). This indeed is restricted to the pure, monotonic subset of (full) Prolog together with all pure, monotonic extensions. Thanks, yes, I might be fudging terminology a bit. Generally, when I talk about Prolog I mean definite programs (sets of definite clauses and Horn goals, the latter usually called "definite goals") under SLD-resolution. That's more or less what is usually meant by "pure" Prolog: definite programs, without not/1 implementing Negation-As-Failure, without the cut, and without side effects; and executed by giving an initial Horn goal as a "query". Entailment between definite clauses and satisfiability of definite programs is undecidable. By "semi-decidable" I mean that an SLD-refutation proof will terminate if there is a branch of the proof that ends in □ and is of finite length. If such a branch does not exist, a proof will "loop" forever. That's regardless of whether the branch succeeds or fails, which is a bit of a fudge, but, in practice, there is no other way to decide the success or failure of a proof than to search all its branches. Left-recursion is one way in which Prolog, with depth-first search, generates branches of infinite length, but you can get those with right-recursion also. There are restrictions of Prolog, like SLG-resolution (similar to DFS with iterative deepening) that don't loop on left-recursions but the general case remains undecidable. Fortunately, there seem to be at least as many finite proofs as there are infinite ones, or in any case I have never encountered a Prolog program that looped inintially and that couldn't be rewritten to terminate, at least when called in the way it was meant to be called. And that's also a bit of a fudge.
bambataa 4y ago
I had the exact same reaction. I did a bit of reading about Datalog and I get that it’s useful in things like static analysis where you get the fixed point analysis for free, but apart from that I am not really sure why I’d use it.
- maweki 4y ago
  The main reasons I'd say are the very intuitive JOINs and queries. Like you give some partial relation and you get every "fit". So as long as you mostly do equalities in JOIN and WHERE, the queries will be very intuitive and obvious to the layperson. If you work with VIEWs or CTEs a lot, then Datalog is your friend, as every derived relationship is just a VIEW. If you like to encapsulate and reuse queries, then Datalog is ideal. We had plenty discussions on HN about SQL code reuse. Not an issue in Datalog. And lastly, there are many ways to compile Datalog programs to "executables" that take maybe a few CSV-files as input and give you the results. I'm not saying that this would be always faster than loading the CSVs into SQLite and running SQL against the data, but a lot of work has been done on Datalog query optimization and compilers can emit very efficient code.
  - samuell 4y ago
    > If you like to encapsulate and reuse queries This is what I always thought was the main benefit. You are able to much easier raise your level of abstraction, by building up a vocabulary of definitions, and model your further queries (or definitions) using them.
sirwhinesalot 4y ago
That's a good point, to be honest I'm not sure there's a particularly good answer to that beyond "it's a much better underlying model". SQL is an ugly bastardization of the relational model, whereas Datalog is a clean application of the logical model to the relational setting. One thing that's really nice about Datalog is that it puts the focus on modelling relations between data instead of "tables" which often end up with a jumble of data and then need to be normalized to work properly. It pushes you into good structures by default, which is a really good property to have. It's also much much simpler than SQL, no need to think in terms of inner joins and outer joins and whatever else, it is all relations. It also easily produces derived data from existing data, without needing any kind of procedural process, and is highly composable. It's not so much that it's solving a burning problem than SQL, it's just better than SQL... (note: the clojure syntax used in that page is much more confusing than the native Datalog syntax IMO)
- zh217 4y ago
  Another problem with Clojure-based Datalog is performance. Yet another is you are pretty much tied to the Clojure ecosystem. And I don't really like the Clojure-fused Datalog syntax either. These pains spurred me to write my own: https://docs.cozodb.org/en/latest/ https://docs.cozodb.org/en/latest/ (FOSS), and so far I'm satisified with my own work.
  - arohner 4y ago
    What is the performance problem?
yaantc 4y ago
In 2021 Google introduced Logica, a Datalog variant. In their introduction blog they contrast it with SQL, so this may answer your question: https://opensource.googleblog.com/2021/04/logica-organizing-your-data-queries.html https://opensource.googleblog.com/2021/04/logica-organizing-... In short, it's easier to compose (and decompose), which helps with complex queries that can be assembled from simpler, independently tested parts. No personal experience in this, I just remembered that blog contrasting Datalog and SQL.
ekidd 4y ago
> I guess the intention is to be better than SQL but then I was left with "under which circumstances?" Excellent question. Two of the most common use cases for databases are "transactional processing" (manipulating small numbers of rows in real time) and "analytical processing" (querying enormous numbers of rows, typically in a read-only fashion). SQL is generally fine for transactional workloads. But analytical queries sometimes involve multi-page queries, with lots of JOINs and CTEs. And these queries are often automatically generated. And once you start writing actual multi-page "programs" in SQL, you may decide that it's a fairly clunky and miserable programming language. What Datalog typically buys you is a way to cleanly decompose large queries into "subroutines." And it offers a simpler syntax for many kinds of complex JOINs. Unfortunately, there isn't really a standard dialect of Datalog, or even a particular dialect with mainstream traction. So choosing Datalog is a bit of a tradeoff: does it buy you enough, for your use case, that it's worth being a bit outside the mainstream? Maybe! But I'd love to see something like Logica gain more traction: https://logica.dev/ https://logica.dev/
anon291 4y ago
Sql doesn't compose at all. You can't take two sql programs and combine them with a single operator and get a new program. In datalog you can. Either by using the comma or semicolon operator.
- crabbone 4y ago
  You are thinking about the declarative part. SQL/STP, the standard that's the basis for definition of the imperative part of SQL (stored procedures) can compose in a similar way (eg. you can call a stored procedure from a stored procedure), but the standard doesn't go far enough, and so every practical database has its own extensions which deters people from using stored procedures because they'd end up with non-portable code.
  - anon291 4y ago
    stored procedures, being procedural, are the antithesis of a declarative database library. I'm talking about this: Query 1: SELECT a, b, c FROM table1 JOIN table2 ... Query 2: SELECT d, e, f FROM (SUBSELECT ... ) AS table3 JOIN table4 ... Now, join those queries together. How? Well you have to analyze the join clauses in from and then combine those together, then rewrite the SELECTION. Okay, great... not so hard. Now use Query 2 in a recursive CTE for Query 1. Oh goodness... much harder. Or what about: Query 1: SELECT a, b, c FROM table1 JOIN table2 ... Query 2: SELECT d, e, f FROM (SUBSELECT ... ) AS table3 JOIN table4 ... ORDER BY table4.column LIMIT 10 Now join 1 and 2 together... the syntax is much much much different. Some SQL libraries in Haskell, like Beam, Opaleye, Squeal, etc, demonstrate the kind of composability I mean. In particular, all three of these offer a monadic interface where arbitrary queries can be joined using well-known relational operators (relational cross joins form a monad). I'm not sure of Opaleye and Squeal, but Beam does it's best to produce a human-comprehensible query. Moreover, the first queries given above are 'easy' in the sense that the portion after the `FROM` in a regular SQL SELECT does actually compose well, since the JOIN operators are basically a direct translation of the underlying relational algebra. However, they start to fail when you want to join up aggregations and the like. While true that aggregations and ordering are not strictly relational, it is of great use to be able to compute with such things. Again, the libraries above demonstrate the composability. For example, the beam library offers this: https://haskell-beam.github.io/beam/user-guide/queries/aggregates/ https://haskell-beam.github.io/beam/user-guide/queries/aggre... Notice how we are able (in the second to last query), simply combine the query `all_ (track chinookDb)` with the complex aggregate expression. In this DSL, the entire aggregate could be floated out. In particular, notice how the queries for either the first `all_` or the second complex aggregate would look much different on their own. That's what I mean by SQL doesn't compose. Of course all these DSLs have the problem that they're trying to work with an existing language SQL that is not nice and orthogonal, and so they all have their varying deficiencies. Datalog mostly fixes these issues and provides a nice model.
felixyz 4y ago
> then I was left with "under which circumstances?" Foremost, Datalog has great compositionality, which is one of SQL:s big weaknesses (it was designed with completely different goals). Also, things like recursive queries are completely natural in Datalog, whereas in SQL they are bolted on with recursive common table expressions.
- refset 4y ago
  > Datalog has great compositionality, which is one of SQL's big weaknesses There's a good write-up on this aspect (amongst others) here: https://www.scattered-thoughts.net/writing/against-sql/ https://www.scattered-thoughts.net/writing/against-sql/ > recursive queries are completely natural in Datalog, whereas in SQL they are bolted on with recursive common table expressions And similarly: https://github.com/frankmcsherry/blog/blob/master/posts/2022-12-25.md https://github.com/frankmcsherry/blog/blob/master/posts/2022...
  - felixyz 4y ago
    Of all the anti-SQL screeds out there, this is my favorite as well. And Frank McSherry... well, everything he writes is gold.
dgb23 4y ago
One of the biggest advantages is re-use, extensibility and being robust to change, because you define things bottom up. Think of aggregates as "hashmaps with typed keys" rather than "structs with places in them". Aggregates are implicit groupings, not explicit slots. This wards you from risk of change and speeds up your feedback loop of making changes and experimenting with ideas. Plus you can compose new aggregate variants out of the same primitives (attributes) which is a fairly typical use-case. Another is query composition. I'm more familiar with SQL and I'm somewhat comfortable with writing nested queries. But we all know how both query builders and similar are often hard to re-use and compose. With these datalog dialects, composition, refactoring and extraction of logical units is much more straight forward, even as a beginner. Queries are "flat", and consist clauses that can be moved around and composed. Think of having more associative and commutative operations. On top of these, the mentioned technologies (in the article) are temporal and support time travel out of the box. That's something you can do on top of SQL of course but it's quite powerful to have it in-built as a primary feature. Whenever you have an application that does things like (non-exclusive), reporting, undo, revisions etc. You might want that.
crabbone 4y ago
I'm not the author, and I don't know how author would answer this question, but some things are really on the surface: 1. Modularity. In Datalog it's very easy to name a common (sub-)query and reuse it in multiple queries. You can have stored procedures / functions in SQL, but the syntax is very different implementation to implementation and users are typically afraid of using the feature (the SQL/PSM does not go far enough to define what users would normally want). Also, SQL/PSM is an imperative extension of otherwise declarative language. The two just don't work well together. 2. Structures other than primitives and tables (you get lists, vectors, hash-maps and sets, but you can also make your own). A lot of practical SQL extensions also offer some of these structures, but they aren't in the standard. 3. Operations on primitive types fall into the same category / work in the same way as operations on complex types. I.e. select / update / insert / delete in SQL only apply to tables, but strings or numbers don't work in the same way. It's more uniform in Datalog (not 100%, but still better).
conor-23 4y ago
A researchy perspective: Datalog was invented to extend relational algebra with recursion. Since it started out as an academic tool, people have been studying recursion-specific optimizations you can do for decades so it is extremely well suited to recursive use-cases e.g. iterative graph algorithms. Using Datalog for network algorithms won the thesis award in databases almost 20 years ago https://boonloo.cis.upenn.edu/papers/boon_interview.pdf https://boonloo.cis.upenn.edu/papers/boon_interview.pdf .
- tejtm 4y ago
  This is the answer I subscribe to. CTEs and recursive CTEs are SQL's answer to a limitation of plain relational algebra; no loops. CTEs are a great and most welcome addition to SQL but they are a bolt-on patch as compared with Datalog where it is a core feature.
- felixyz 4y ago
  > Datalog was invented to extend relational algebra with recursion. I'm not sure that is exactly right. Do you have a reference? (Not trying to put you on the spot, I'm just curious to learn the history!)
  - YeGoblynQueenne 4y ago
    Yeah, if the OP can give a reference I'd be very interested, too. I've searched for the "original" reference to datalog because I wanted to cite it, but I couldn't find anything like that. I have a sneaking suspicion that "function-free Prolog" is as old as ordinary Prolog, and "datalog", as an idea separate to Prolog and used as a database language, was born in the database community, but like the OP I have no reference to this.
  - refset 4y ago
    Agreed, my understanding is that Datalog has a distinct (though related) lineage that directly emerged from Prolog (i.e. logic programming, not relational algebra / database theory) - skimming the introduction of "Horn Clauses and the Fixpoint Query Hierarchy (1982)" seems to confirm this: https://dl.acm.org/doi/pdf/10.1145/588111.588137 https://dl.acm.org/doi/pdf/10.1145/588111.588137 Edit: this presentation describes things differently but it doesn't sound quite right to me "Chandra and Harel - 1982 Studied the expressive power of logic programs without function symbols on relational databases" https://www.dbai.tuwien.ac.at/datalog2.0/slides/Kolaitis.pdf https://www.dbai.tuwien.ac.at/datalog2.0/slides/Kolaitis.pdf
mmcdermott 4y ago
> I guess the intention is to be better than SQL but then I was left with "under which circumstances?". The way I see it, SQL's great strength as a query language is selection and projection whereas Datalog's great strength is inference. It takes a shift in mindset to take advantage of inference. I've started using Datalog when analyzing unfamiliar codebases. So I might set up something like: writes_to(microservice1, db1). writes_to(microservice2, microservice1). writes_to(microservice3, microservice2). depends_on(X, Y) :- writes_to(X, Z), depends_on(Z, Y). depends_on(X, Y) :- writes_to(X, Y). Allowing you to query something like: depends_on(microservice3, X) and get back db1, microservice1 and microservice2. Of course, you can ultimately do this in SQL as well, but it's far more compact in Datalog. Which brings me to the second half of the motivation - the principal advantage to the logical database model is the open world assumption. The relational model in practice tends to be fairly buttoned down - data is expected to suit a particular schema (which has its own advantages as a transactional system). This makes it easy to extend a logical database and ask more questions without changing the fact formats already specified. Of course, I can ultimately do all the things that feel natural in Datalog in SQL. I can work through queries like the one above by building out the data model and writing recursive CTEs. It's about strengths, not possibilities which I suppose brings me back to why SQL 'won'. A disproportionate amount of code is written for transactional line-of-business systems. It's really not hard to see why the validation layer and transactional focus would win in those areas.

YeGoblynQueenne 4y ago

>> The author might do better to think in terms of "what burning problem are we trying to fix and how did we fix it". I have no idea who first came up with the name "datalog", and what exactly was their motivation (I've looked, but couldn't find the original reference to datalog), but the burning problem that datalog does fix is Prolog's semi-decidability, or in other words, its tendency to enter infinite recursions. One half of the reason for that is Prolog's "compound terms" (known as functions, in First-Order Logic terminology) and the other half is Prolog's use of depth-first search for evaluation. Functions, along with logic variables, mean that a predicate's Herbrand base (its set of logical atoms) can be expanded forever: if f(x) is a term, f(f(x)) is a term, f(f(f(x))) is a term... and so on, ad infinitum. The depth-first search evaluation just gets stuck in left-recursions when the first body literal of a clause is a recursive literal: p(x):- p(x), q(x) loops forever, in Prolog with depth-first search. Datalog is Prolog without functions other than constants, and it can be evaluated "bottom up", both of which overcome Prolog's semi-decidability (but eliminate its completeness). But of course this is not a very clear motivation for its use as a database language, only its use as an alternative to Prolog. More to the point, there are many datalog variants. Some that accept negation, some that do not, some that allow recursion, some that do not, and so on. There's a lot of information on different datalogs, seen from the point of view of database research in this free ebook on databases: http://webdam.inria.fr/Alice/ http://webdam.inria.fr/Alice/ See chapters 12 - 15. And see these lecture notes for a more logic-programm-y discussion of fixpoint semantics of definite logic programs: https://www.doc.ic.ac.uk/~mjs/teaching/KnowledgeRep491/Fixpoint_Definite_491-2x1.pdf https://www.doc.ic.ac.uk/~mjs/teaching/KnowledgeRep491/Fixpo...

falsissime 4y ago
> but the burning problem that datalog does fix is Prolog's semi-decidability, or in other words, its tendency to enter infinite recursions. Prolog's built-in search is not semidecidable. https://en.wikipedia.org/wiki/Decidability_(logic)#Semidecidability https://en.wikipedia.org/wiki/Decidability_(logic)#Semidecid... As you observe, Prolog gets stuck in left-recursions. But iterative deepening for Prolog is semidecidable (among other fair methods). This indeed is restricted to the pure, monotonic subset of (full) Prolog together with all pure, monotonic extensions.
- YeGoblynQueenne 4y ago
  >> As you observe, Prolog gets stuck in left-recursions. But iterative deepening for Prolog is semidecidable (among other fair methods). This indeed is restricted to the pure, monotonic subset of (full) Prolog together with all pure, monotonic extensions. Thanks, yes, I might be fudging terminology a bit. Generally, when I talk about Prolog I mean definite programs (sets of definite clauses and Horn goals, the latter usually called "definite goals") under SLD-resolution. That's more or less what is usually meant by "pure" Prolog: definite programs, without not/1 implementing Negation-As-Failure, without the cut, and without side effects; and executed by giving an initial Horn goal as a "query". Entailment between definite clauses and satisfiability of definite programs is undecidable. By "semi-decidable" I mean that an SLD-refutation proof will terminate if there is a branch of the proof that ends in □ and is of finite length. If such a branch does not exist, a proof will "loop" forever. That's regardless of whether the branch succeeds or fails, which is a bit of a fudge, but, in practice, there is no other way to decide the success or failure of a proof than to search all its branches. Left-recursion is one way in which Prolog, with depth-first search, generates branches of infinite length, but you can get those with right-recursion also. There are restrictions of Prolog, like SLG-resolution (similar to DFS with iterative deepening) that don't loop on left-recursions but the general case remains undecidable. Fortunately, there seem to be at least as many finite proofs as there are infinite ones, or in any case I have never encountered a Prolog program that looped inintially and that couldn't be rewritten to terminate, at least when called in the way it was meant to be called. And that's also a bit of a fudge.

bambataa 4y ago

I had the exact same reaction. I did a bit of reading about Datalog and I get that it’s useful in things like static analysis where you get the fixed point analysis for free, but apart from that I am not really sure why I’d use it.

maweki 4y ago
The main reasons I'd say are the very intuitive JOINs and queries. Like you give some partial relation and you get every "fit". So as long as you mostly do equalities in JOIN and WHERE, the queries will be very intuitive and obvious to the layperson. If you work with VIEWs or CTEs a lot, then Datalog is your friend, as every derived relationship is just a VIEW. If you like to encapsulate and reuse queries, then Datalog is ideal. We had plenty discussions on HN about SQL code reuse. Not an issue in Datalog. And lastly, there are many ways to compile Datalog programs to "executables" that take maybe a few CSV-files as input and give you the results. I'm not saying that this would be always faster than loading the CSVs into SQLite and running SQL against the data, but a lot of work has been done on Datalog query optimization and compilers can emit very efficient code.
- samuell 4y ago
  > If you like to encapsulate and reuse queries This is what I always thought was the main benefit. You are able to much easier raise your level of abstraction, by building up a vocabulary of definitions, and model your further queries (or definitions) using them.

sirwhinesalot 4y ago

That's a good point, to be honest I'm not sure there's a particularly good answer to that beyond "it's a much better underlying model". SQL is an ugly bastardization of the relational model, whereas Datalog is a clean application of the logical model to the relational setting. One thing that's really nice about Datalog is that it puts the focus on modelling relations between data instead of "tables" which often end up with a jumble of data and then need to be normalized to work properly. It pushes you into good structures by default, which is a really good property to have. It's also much much simpler than SQL, no need to think in terms of inner joins and outer joins and whatever else, it is all relations. It also easily produces derived data from existing data, without needing any kind of procedural process, and is highly composable. It's not so much that it's solving a burning problem than SQL, it's just better than SQL... (note: the clojure syntax used in that page is much more confusing than the native Datalog syntax IMO)

zh217 4y ago
Another problem with Clojure-based Datalog is performance. Yet another is you are pretty much tied to the Clojure ecosystem. And I don't really like the Clojure-fused Datalog syntax either. These pains spurred me to write my own: https://docs.cozodb.org/en/latest/ https://docs.cozodb.org/en/latest/ (FOSS), and so far I'm satisified with my own work.
- arohner 4y ago
  What is the performance problem?

yaantc 4y ago

In 2021 Google introduced Logica, a Datalog variant. In their introduction blog they contrast it with SQL, so this may answer your question: https://opensource.googleblog.com/2021/04/logica-organizing-your-data-queries.html https://opensource.googleblog.com/2021/04/logica-organizing-... In short, it's easier to compose (and decompose), which helps with complex queries that can be assembled from simpler, independently tested parts. No personal experience in this, I just remembered that blog contrasting Datalog and SQL.

ekidd 4y ago

> I guess the intention is to be better than SQL but then I was left with "under which circumstances?" Excellent question. Two of the most common use cases for databases are "transactional processing" (manipulating small numbers of rows in real time) and "analytical processing" (querying enormous numbers of rows, typically in a read-only fashion). SQL is generally fine for transactional workloads. But analytical queries sometimes involve multi-page queries, with lots of JOINs and CTEs. And these queries are often automatically generated. And once you start writing actual multi-page "programs" in SQL, you may decide that it's a fairly clunky and miserable programming language. What Datalog typically buys you is a way to cleanly decompose large queries into "subroutines." And it offers a simpler syntax for many kinds of complex JOINs. Unfortunately, there isn't really a standard dialect of Datalog, or even a particular dialect with mainstream traction. So choosing Datalog is a bit of a tradeoff: does it buy you enough, for your use case, that it's worth being a bit outside the mainstream? Maybe! But I'd love to see something like Logica gain more traction: https://logica.dev/ https://logica.dev/

anon291 4y ago

Sql doesn't compose at all. You can't take two sql programs and combine them with a single operator and get a new program. In datalog you can. Either by using the comma or semicolon operator.

crabbone 4y ago
You are thinking about the declarative part. SQL/STP, the standard that's the basis for definition of the imperative part of SQL (stored procedures) can compose in a similar way (eg. you can call a stored procedure from a stored procedure), but the standard doesn't go far enough, and so every practical database has its own extensions which deters people from using stored procedures because they'd end up with non-portable code.
- anon291 4y ago
  stored procedures, being procedural, are the antithesis of a declarative database library. I'm talking about this: Query 1: SELECT a, b, c FROM table1 JOIN table2 ... Query 2: SELECT d, e, f FROM (SUBSELECT ... ) AS table3 JOIN table4 ... Now, join those queries together. How? Well you have to analyze the join clauses in from and then combine those together, then rewrite the SELECTION. Okay, great... not so hard. Now use Query 2 in a recursive CTE for Query 1. Oh goodness... much harder. Or what about: Query 1: SELECT a, b, c FROM table1 JOIN table2 ... Query 2: SELECT d, e, f FROM (SUBSELECT ... ) AS table3 JOIN table4 ... ORDER BY table4.column LIMIT 10 Now join 1 and 2 together... the syntax is much much much different. Some SQL libraries in Haskell, like Beam, Opaleye, Squeal, etc, demonstrate the kind of composability I mean. In particular, all three of these offer a monadic interface where arbitrary queries can be joined using well-known relational operators (relational cross joins form a monad). I'm not sure of Opaleye and Squeal, but Beam does it's best to produce a human-comprehensible query. Moreover, the first queries given above are 'easy' in the sense that the portion after the `FROM` in a regular SQL SELECT does actually compose well, since the JOIN operators are basically a direct translation of the underlying relational algebra. However, they start to fail when you want to join up aggregations and the like. While true that aggregations and ordering are not strictly relational, it is of great use to be able to compute with such things. Again, the libraries above demonstrate the composability. For example, the beam library offers this: https://haskell-beam.github.io/beam/user-guide/queries/aggregates/ https://haskell-beam.github.io/beam/user-guide/queries/aggre... Notice how we are able (in the second to last query), simply combine the query `all_ (track chinookDb)` with the complex aggregate expression. In this DSL, the entire aggregate could be floated out. In particular, notice how the queries for either the first `all_` or the second complex aggregate would look much different on their own. That's what I mean by SQL doesn't compose. Of course all these DSLs have the problem that they're trying to work with an existing language SQL that is not nice and orthogonal, and so they all have their varying deficiencies. Datalog mostly fixes these issues and provides a nice model.

felixyz 4y ago

> then I was left with "under which circumstances?" Foremost, Datalog has great compositionality, which is one of SQL:s big weaknesses (it was designed with completely different goals). Also, things like recursive queries are completely natural in Datalog, whereas in SQL they are bolted on with recursive common table expressions.

refset 4y ago
> Datalog has great compositionality, which is one of SQL's big weaknesses There's a good write-up on this aspect (amongst others) here: https://www.scattered-thoughts.net/writing/against-sql/ https://www.scattered-thoughts.net/writing/against-sql/ > recursive queries are completely natural in Datalog, whereas in SQL they are bolted on with recursive common table expressions And similarly: https://github.com/frankmcsherry/blog/blob/master/posts/2022-12-25.md https://github.com/frankmcsherry/blog/blob/master/posts/2022...
- felixyz 4y ago
  Of all the anti-SQL screeds out there, this is my favorite as well. And Frank McSherry... well, everything he writes is gold.

dgb23 4y ago

One of the biggest advantages is re-use, extensibility and being robust to change, because you define things bottom up. Think of aggregates as "hashmaps with typed keys" rather than "structs with places in them". Aggregates are implicit groupings, not explicit slots. This wards you from risk of change and speeds up your feedback loop of making changes and experimenting with ideas. Plus you can compose new aggregate variants out of the same primitives (attributes) which is a fairly typical use-case. Another is query composition. I'm more familiar with SQL and I'm somewhat comfortable with writing nested queries. But we all know how both query builders and similar are often hard to re-use and compose. With these datalog dialects, composition, refactoring and extraction of logical units is much more straight forward, even as a beginner. Queries are "flat", and consist clauses that can be moved around and composed. Think of having more associative and commutative operations. On top of these, the mentioned technologies (in the article) are temporal and support time travel out of the box. That's something you can do on top of SQL of course but it's quite powerful to have it in-built as a primary feature. Whenever you have an application that does things like (non-exclusive), reporting, undo, revisions etc. You might want that.

crabbone 4y ago

I'm not the author, and I don't know how author would answer this question, but some things are really on the surface: 1. Modularity. In Datalog it's very easy to name a common (sub-)query and reuse it in multiple queries. You can have stored procedures / functions in SQL, but the syntax is very different implementation to implementation and users are typically afraid of using the feature (the SQL/PSM does not go far enough to define what users would normally want). Also, SQL/PSM is an imperative extension of otherwise declarative language. The two just don't work well together. 2. Structures other than primitives and tables (you get lists, vectors, hash-maps and sets, but you can also make your own). A lot of practical SQL extensions also offer some of these structures, but they aren't in the standard. 3. Operations on primitive types fall into the same category / work in the same way as operations on complex types. I.e. select / update / insert / delete in SQL only apply to tables, but strings or numbers don't work in the same way. It's more uniform in Datalog (not 100%, but still better).

conor-23 4y ago

A researchy perspective: Datalog was invented to extend relational algebra with recursion. Since it started out as an academic tool, people have been studying recursion-specific optimizations you can do for decades so it is extremely well suited to recursive use-cases e.g. iterative graph algorithms. Using Datalog for network algorithms won the thesis award in databases almost 20 years ago https://boonloo.cis.upenn.edu/papers/boon_interview.pdf https://boonloo.cis.upenn.edu/papers/boon_interview.pdf .

tejtm 4y ago
This is the answer I subscribe to. CTEs and recursive CTEs are SQL's answer to a limitation of plain relational algebra; no loops. CTEs are a great and most welcome addition to SQL but they are a bolt-on patch as compared with Datalog where it is a core feature.
felixyz 4y ago
> Datalog was invented to extend relational algebra with recursion. I'm not sure that is exactly right. Do you have a reference? (Not trying to put you on the spot, I'm just curious to learn the history!)
- YeGoblynQueenne 4y ago
  Yeah, if the OP can give a reference I'd be very interested, too. I've searched for the "original" reference to datalog because I wanted to cite it, but I couldn't find anything like that. I have a sneaking suspicion that "function-free Prolog" is as old as ordinary Prolog, and "datalog", as an idea separate to Prolog and used as a database language, was born in the database community, but like the OP I have no reference to this.
- refset 4y ago
  Agreed, my understanding is that Datalog has a distinct (though related) lineage that directly emerged from Prolog (i.e. logic programming, not relational algebra / database theory) - skimming the introduction of "Horn Clauses and the Fixpoint Query Hierarchy (1982)" seems to confirm this: https://dl.acm.org/doi/pdf/10.1145/588111.588137 https://dl.acm.org/doi/pdf/10.1145/588111.588137 Edit: this presentation describes things differently but it doesn't sound quite right to me "Chandra and Harel - 1982 Studied the expressive power of logic programs without function symbols on relational databases" https://www.dbai.tuwien.ac.at/datalog2.0/slides/Kolaitis.pdf https://www.dbai.tuwien.ac.at/datalog2.0/slides/Kolaitis.pdf

mmcdermott 4y ago

> I guess the intention is to be better than SQL but then I was left with "under which circumstances?". The way I see it, SQL's great strength as a query language is selection and projection whereas Datalog's great strength is inference. It takes a shift in mindset to take advantage of inference. I've started using Datalog when analyzing unfamiliar codebases. So I might set up something like: writes_to(microservice1, db1). writes_to(microservice2, microservice1). writes_to(microservice3, microservice2). depends_on(X, Y) :- writes_to(X, Z), depends_on(Z, Y). depends_on(X, Y) :- writes_to(X, Y). Allowing you to query something like: depends_on(microservice3, X) and get back db1, microservice1 and microservice2. Of course, you can ultimately do this in SQL as well, but it's far more compact in Datalog. Which brings me to the second half of the motivation - the principal advantage to the logical database model is the open world assumption. The relational model in practice tends to be fairly buttoned down - data is expected to suit a particular schema (which has its own advantages as a transactional system). This makes it easy to extend a logical database and ask more questions without changing the fact formats already specified. Of course, I can ultimately do all the things that feel natural in Datalog in SQL. I can work through queries like the one above by building out the data model and writing recursive CTEs. It's about strengths, not possibilities which I suppose brings me back to why SQL 'won'. A disproportionate amount of code is written for transactional line-of-business systems. It's really not hard to see why the validation layer and transactional focus would win in those areas.