3 ms·

A researchy perspective: Datalog was invented to extend relational algebra with recursion. Since it started out as an academic tool, people have been studying r

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
  - felixyz 4y ago
    Thanks!
  - conor-23 4y ago
    Yeah I'm not up on the Prolog history side of things. My info is based on the Wikipedia article for Fixed Point Logic: "Least fixed-point logic was first studied systematically by Yiannis N. Moschovakis in 1974,[1] and it was introduced to computer scientists in 1979, when Alfred Aho and Jeffrey Ullman suggested fixed-point logic as an expressive database query language.[2]" [2] = Universality of Data Retrieval Languages : https://dl.acm.org/doi/10.1145/567752.567763 https://dl.acm.org/doi/10.1145/567752.567763

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
- felixyz 4y ago
  Thanks!
- conor-23 4y ago
  Yeah I'm not up on the Prolog history side of things. My info is based on the Wikipedia article for Fixed Point Logic: "Least fixed-point logic was first studied systematically by Yiannis N. Moschovakis in 1974,[1] and it was introduced to computer scientists in 1979, when Alfred Aho and Jeffrey Ullman suggested fixed-point logic as an expressive database query language.[2]" [2] = Universality of Data Retrieval Languages : https://dl.acm.org/doi/10.1145/567752.567763 https://dl.acm.org/doi/10.1145/567752.567763