8 ms·

Could you explain more or point out some interesting references? I'm currently trying to understand how Datalog compares to SQL and, potentially GraphDBs

by pfilo8 2y ago

greenavocado 2y ago
Prolog and Datalog example (they are identical in this case) % Facts parent(john, mary). parent(mary, ann). parent(mary, tom). % Rules ancestor(X, Y) :- parent(X, Y). ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z). % Query ?- ancestor(john, X). The Prolog code looks identical to Datalog but the execution model is different. Prolog uses depth-first search and backtracking, which can lead to infinite loops if the rules are not carefully ordered. Datalog starts by evaluating all possible combinations of facts and rules. It builds a bottom-up derivation of all possible facts: a. First, it derives all direct parent relationships. b. Then, it applies the ancestor rules iteratively until no new facts can be derived. For the query ancestor(john, X): It returns all X that satisfy the ancestor relationship with john. This includes mary, ann, and tom. The order of rules doesn't affect the result or termination. Datalog guarantees termination because it operates on a finite set of possible facts. Prolog uses a top-down, depth-first search strategy with backtracking. For the query ancestor(john, X): a. It first tries to satisfy parent(john, X). This succeeds with X = mary. b. It then backtracks and tries the second rule: It satisfies parent(john, Y) with Y = mary. Then recursively calls ancestor(mary, X). c. This process continues, exploring the tree depth-first. Prolog will find solutions in this order: mary, ann, tom. The order of clauses can affect both the order of results and termination: If the recursive rule were listed first, Prolog could enter an infinite loop. Prolog doesn't guarantee termination, especially with recursive rules. SQL is more verbose. The equivalent of the Datalog/Prolog example above is: -- Create and populate the table CREATE TABLE Parent ( parent VARCHAR(50), child VARCHAR(50) ); INSERT INTO Parent VALUES ('john', 'mary'); INSERT INTO Parent VALUES ('mary', 'ann'); INSERT INTO Parent VALUES ('mary', 'tom'); -- Recursive query to find ancestors WITH RECURSIVE Ancestor AS ( SELECT parent, child FROM Parent UNION ALL SELECT a.parent, p.child FROM Ancestor a JOIN Parent p ON a.child = p.parent ) SELECT DISTINCT parent AS ancestor FROM Ancestor WHERE child IN ('ann', 'tom'); This is a more interesting example of how one might use Datalog on a large dataset: % Define the base relation friend(Person1, Person2). % Define friend-of-friend relation friend_of_friend(X, Z) :- friend(X, Y), friend(Y, Z), X != Z. % Define potential friend recommendation % (friend of friend who is not already a friend) recommend_friend(X, Z) :- friend_of_friend(X, Z), not friend(X, Z). % Count mutual friends for recommendations mutual_friend_count(X, Z, Count) :- recommend_friend(X, Z), Count = count{Y : friend(X, Y), friend(Y, Z)}. % Query to get top friend recommendations for a person top_recommendations(Person, RecommendedFriend, MutualCount) :- mutual_friend_count(Person, RecommendedFriend, MutualCount), MutualCount >= 5, MutualCount = max{C : mutual_friend_count(Person, _, C)}. The equivalent Postgres example would be: WITH RECURSIVE -- Base friend relation friends AS ( SELECT DISTINCT person1, person2 FROM friendship UNION SELECT person2, person1 FROM friendship ), -- Friend of friend relation friend_of_friend AS ( SELECT f1.person1 AS person, f2.person2 AS friend_of_friend FROM friends f1 JOIN friends f2 ON f1.person2 = f2.person1 WHERE f1.person1 <> f2.person2 ), -- Potential friend recommendations potential_recommendations AS ( SELECT fof.person, fof.friend_of_friend, COUNT(*) AS mutual_friend_count FROM friend_of_friend fof LEFT JOIN friends f ON fof.person = f.person1 AND fof.friend_of_friend = f.person2 WHERE f.person1 IS NULL -- Ensure they're not already friends GROUP BY fof.person, fof.friend_of_friend HAVING COUNT(*) >= 5 -- Minimum mutual friends threshold ), -- Rank recommendations ranked_recommendations AS ( SELECT person, friend_of_friend, mutual_friend_count, RANK() OVER (PARTITION BY person ORDER BY mutual_friend_count DESC) as rank FROM potential_recommendations ) -- Get top recommendations SELECT person, friend_of_friend, mutual_friend_count FROM ranked_recommendations WHERE rank = 1; Full example you can run yourself: https://onecompiler.com/postgresql/42khbswat https://onecompiler.com/postgresql/42khbswat
- dkarl 2y ago
  > Prolog uses depth-first search and backtracking, which can lead to infinite loops if the rules are not carefully ordered Is this an issue in practice? Most languages can create programs with infinite loops, but it's easy to spot in code reviews. It's been over a decade since I encountered an infinite loop in production in the backend. Just wondering if the same is true for Prolog.
  - Normal_gaussian 2y ago
    Yes. It is trivially easy to create loops of rules when describing abstract properties. Concrete properties tend to have "levels" to them, but many human concepts are self-referential. In this way, its possible to spot that there may be an issue now or in the future, because the presence or lack of a loop depends on the specific choice of dependencies of a concept. However spotting the potential for a loop doesn't do a lot to help remove its potential existence, or show that it is there or not there.
  - derdi 2y ago
    There are classes of infinite loops that are harder to spot for beginners, it takes a while to really understand the execution model. Prolog variables can have two states at runtime: unbound or bound. A bound variable refers to some value, while an unbound variable is a "hole" to be filled in at a later time. It's common to pass an unbound variable into some call and expect the callee to bind it to a value. This can cause problems with infinite recursion where you intend to write a call that binds some variable, but the way you've structured your program, it will not actually bind it. So the callee ends up in the same state as the caller, makes a recursive call hoping its callee will bind the variable, and down the infinite recursion you go. With experience you can definitely spot this in code review. You'll also catch it in testing, if you test properly. But it's different enough from other languages that learners struggle with it at first. Another source of (seeming) nontermination is when you ask Prolog's backtracking search to find an answer to some query in a search space that is too large and may not contain an answer at all, or only an answer that is impracticably far away. This is also sort of Prolog-specific since in other languages you rarely write the same kind of optimistic recursive search. This is harder to spot in code review since it's really application-specific what the search space looks like. But again, you test. And when in doubt, you direct and limit the search appropriately.
sirwhinesalot 2y ago
Don't have any interesting references, sorry. My reasoning is mainly one of simplicity and power. In SQL you need to think in terms of tables, inner joins, outer joins, foreign keys etc. whereas datalog you do everything with relations as in prolog. Not only is it conceptually much simpler, it's also a "pit of success" situation as thinking in terms of relations instead of tables leads you towards normal forms by default. Add the ability to automatically derive new facts based on rules and it just wins by a country mile. I recommend giving Soufflé a try. I haven't worked with GraphDBs enough to comment on that.
felixyz 2y ago
TypeDb is a practical Datalog-based database system [1] (with a different syntax). TerminusDb is a project in a similar vein [2], but actually an RDF store at its core. If you want to experiment with the connections between Datalog, relational algebra, and SQL, check out the Datalog Educational System. And if you want to jump into the theory, Foundations of Databases (the "Alice book") is very thorough but relatively readable [4]! Oh, and there's a Google project, Logica, to do Datalog over Postgres databases [5]. [1]: https://typedb.com/ https://typedb.com/ [2]: https://terminusdb.com/ https://terminusdb.com/ [3]: http://www.fdi.ucm.es/profesor/fernan/des/ http://www.fdi.ucm.es/profesor/fernan/des/ [4]: http://webdam.inria.fr/Alice/ http://webdam.inria.fr/Alice/ [5]: https://github.com/evgskv/logica https://github.com/evgskv/logica
burakemir 2y ago
Mangle is a language that includes "textbook datalog" as a subset https://github.com/google/mangle https://github.com/google/mangle ; like any real-world datalog language, it extends datalog with various facilities to make it practical. It was discussed on HN https://news.ycombinator.com/item?id=33756800 https://news.ycombinator.com/item?id=33756800 and is implemented in go. There is the beginnings of a Rust implementation meanwhile. If you are looking for datalog in the textbooks, here are some references: https://github.com/google/mangle/blob/main/docs/bibliography.md https://github.com/google/mangle/blob/main/docs/bibliography... A graph DBs short intro to datalog: just like the edges of a graph could be represented as a simple table (src, target), you could consider a database tuple or a datalog or prolog fact foo(x1, ..., xN) as a "generalized edge." The nice thing about datalog is then that as one is able to express a connections in an elegant way as "foo(...X...), bar(...X...)" (a conjunction, X being a "node"), whereas in the SQL world one has to deal with a clumsy JOIN statement to express the same thing.

Could you explain more or point out some interesting references? I'm currently trying to understand how Datalog compares to SQL and, potentially GraphDBs

by pfilo8 2y ago

Could you explain more or point out some interesting references? I'm currently trying to understand how Datalog compares to SQL and, potentially GraphDBs

greenavocado 2y ago

Prolog and Datalog example (they are identical in this case) % Facts parent(john, mary). parent(mary, ann). parent(mary, tom). % Rules ancestor(X, Y) :- parent(X, Y). ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z). % Query ?- ancestor(john, X). The Prolog code looks identical to Datalog but the execution model is different. Prolog uses depth-first search and backtracking, which can lead to infinite loops if the rules are not carefully ordered. Datalog starts by evaluating all possible combinations of facts and rules. It builds a bottom-up derivation of all possible facts: a. First, it derives all direct parent relationships. b. Then, it applies the ancestor rules iteratively until no new facts can be derived. For the query ancestor(john, X): It returns all X that satisfy the ancestor relationship with john. This includes mary, ann, and tom. The order of rules doesn't affect the result or termination. Datalog guarantees termination because it operates on a finite set of possible facts. Prolog uses a top-down, depth-first search strategy with backtracking. For the query ancestor(john, X): a. It first tries to satisfy parent(john, X). This succeeds with X = mary. b. It then backtracks and tries the second rule: It satisfies parent(john, Y) with Y = mary. Then recursively calls ancestor(mary, X). c. This process continues, exploring the tree depth-first. Prolog will find solutions in this order: mary, ann, tom. The order of clauses can affect both the order of results and termination: If the recursive rule were listed first, Prolog could enter an infinite loop. Prolog doesn't guarantee termination, especially with recursive rules. SQL is more verbose. The equivalent of the Datalog/Prolog example above is: -- Create and populate the table CREATE TABLE Parent ( parent VARCHAR(50), child VARCHAR(50) ); INSERT INTO Parent VALUES ('john', 'mary'); INSERT INTO Parent VALUES ('mary', 'ann'); INSERT INTO Parent VALUES ('mary', 'tom'); -- Recursive query to find ancestors WITH RECURSIVE Ancestor AS ( SELECT parent, child FROM Parent UNION ALL SELECT a.parent, p.child FROM Ancestor a JOIN Parent p ON a.child = p.parent ) SELECT DISTINCT parent AS ancestor FROM Ancestor WHERE child IN ('ann', 'tom'); This is a more interesting example of how one might use Datalog on a large dataset: % Define the base relation friend(Person1, Person2). % Define friend-of-friend relation friend_of_friend(X, Z) :- friend(X, Y), friend(Y, Z), X != Z. % Define potential friend recommendation % (friend of friend who is not already a friend) recommend_friend(X, Z) :- friend_of_friend(X, Z), not friend(X, Z). % Count mutual friends for recommendations mutual_friend_count(X, Z, Count) :- recommend_friend(X, Z), Count = count{Y : friend(X, Y), friend(Y, Z)}. % Query to get top friend recommendations for a person top_recommendations(Person, RecommendedFriend, MutualCount) :- mutual_friend_count(Person, RecommendedFriend, MutualCount), MutualCount >= 5, MutualCount = max{C : mutual_friend_count(Person, _, C)}. The equivalent Postgres example would be: WITH RECURSIVE -- Base friend relation friends AS ( SELECT DISTINCT person1, person2 FROM friendship UNION SELECT person2, person1 FROM friendship ), -- Friend of friend relation friend_of_friend AS ( SELECT f1.person1 AS person, f2.person2 AS friend_of_friend FROM friends f1 JOIN friends f2 ON f1.person2 = f2.person1 WHERE f1.person1 <> f2.person2 ), -- Potential friend recommendations potential_recommendations AS ( SELECT fof.person, fof.friend_of_friend, COUNT(*) AS mutual_friend_count FROM friend_of_friend fof LEFT JOIN friends f ON fof.person = f.person1 AND fof.friend_of_friend = f.person2 WHERE f.person1 IS NULL -- Ensure they're not already friends GROUP BY fof.person, fof.friend_of_friend HAVING COUNT(*) >= 5 -- Minimum mutual friends threshold ), -- Rank recommendations ranked_recommendations AS ( SELECT person, friend_of_friend, mutual_friend_count, RANK() OVER (PARTITION BY person ORDER BY mutual_friend_count DESC) as rank FROM potential_recommendations ) -- Get top recommendations SELECT person, friend_of_friend, mutual_friend_count FROM ranked_recommendations WHERE rank = 1; Full example you can run yourself: https://onecompiler.com/postgresql/42khbswat https://onecompiler.com/postgresql/42khbswat

dkarl 2y ago
> Prolog uses depth-first search and backtracking, which can lead to infinite loops if the rules are not carefully ordered Is this an issue in practice? Most languages can create programs with infinite loops, but it's easy to spot in code reviews. It's been over a decade since I encountered an infinite loop in production in the backend. Just wondering if the same is true for Prolog.
- Normal_gaussian 2y ago
  Yes. It is trivially easy to create loops of rules when describing abstract properties. Concrete properties tend to have "levels" to them, but many human concepts are self-referential. In this way, its possible to spot that there may be an issue now or in the future, because the presence or lack of a loop depends on the specific choice of dependencies of a concept. However spotting the potential for a loop doesn't do a lot to help remove its potential existence, or show that it is there or not there.
- derdi 2y ago
  There are classes of infinite loops that are harder to spot for beginners, it takes a while to really understand the execution model. Prolog variables can have two states at runtime: unbound or bound. A bound variable refers to some value, while an unbound variable is a "hole" to be filled in at a later time. It's common to pass an unbound variable into some call and expect the callee to bind it to a value. This can cause problems with infinite recursion where you intend to write a call that binds some variable, but the way you've structured your program, it will not actually bind it. So the callee ends up in the same state as the caller, makes a recursive call hoping its callee will bind the variable, and down the infinite recursion you go. With experience you can definitely spot this in code review. You'll also catch it in testing, if you test properly. But it's different enough from other languages that learners struggle with it at first. Another source of (seeming) nontermination is when you ask Prolog's backtracking search to find an answer to some query in a search space that is too large and may not contain an answer at all, or only an answer that is impracticably far away. This is also sort of Prolog-specific since in other languages you rarely write the same kind of optimistic recursive search. This is harder to spot in code review since it's really application-specific what the search space looks like. But again, you test. And when in doubt, you direct and limit the search appropriately.

sirwhinesalot 2y ago

Don't have any interesting references, sorry. My reasoning is mainly one of simplicity and power. In SQL you need to think in terms of tables, inner joins, outer joins, foreign keys etc. whereas datalog you do everything with relations as in prolog. Not only is it conceptually much simpler, it's also a "pit of success" situation as thinking in terms of relations instead of tables leads you towards normal forms by default. Add the ability to automatically derive new facts based on rules and it just wins by a country mile. I recommend giving Soufflé a try. I haven't worked with GraphDBs enough to comment on that.

felixyz 2y ago

TypeDb is a practical Datalog-based database system [1] (with a different syntax). TerminusDb is a project in a similar vein [2], but actually an RDF store at its core. If you want to experiment with the connections between Datalog, relational algebra, and SQL, check out the Datalog Educational System. And if you want to jump into the theory, Foundations of Databases (the "Alice book") is very thorough but relatively readable [4]! Oh, and there's a Google project, Logica, to do Datalog over Postgres databases [5]. [1]: https://typedb.com/ https://typedb.com/ [2]: https://terminusdb.com/ https://terminusdb.com/ [3]: http://www.fdi.ucm.es/profesor/fernan/des/ http://www.fdi.ucm.es/profesor/fernan/des/ [4]: http://webdam.inria.fr/Alice/ http://webdam.inria.fr/Alice/ [5]: https://github.com/evgskv/logica https://github.com/evgskv/logica

burakemir 2y ago

Mangle is a language that includes "textbook datalog" as a subset https://github.com/google/mangle https://github.com/google/mangle ; like any real-world datalog language, it extends datalog with various facilities to make it practical. It was discussed on HN https://news.ycombinator.com/item?id=33756800 https://news.ycombinator.com/item?id=33756800 and is implemented in go. There is the beginnings of a Rust implementation meanwhile. If you are looking for datalog in the textbooks, here are some references: https://github.com/google/mangle/blob/main/docs/bibliography.md https://github.com/google/mangle/blob/main/docs/bibliography... A graph DBs short intro to datalog: just like the edges of a graph could be represented as a simple table (src, target), you could consider a database tuple or a datalog or prolog fact foo(x1, ..., xN) as a "generalized edge." The nice thing about datalog is then that as one is able to express a connections in an elegant way as "foo(...X...), bar(...X...)" (a conjunction, X being a "node"), whereas in the SQL world one has to deal with a clumsy JOIN statement to express the same thing.