7 ms·

That's a very justified question! In my opinion, Datalog or — more generally — Prolog is where many querying APIs will eventually arrive, because this syntax h

by triska 7y ago

That's a very justified question! In my opinion, Datalog or — more generally — Prolog is where many querying APIs will eventually arrive, because this syntax has many nice advantages: It is very convenient, expressive and readable, programs and queries can be easily parsed and analyzed with Prolog's built-in mechanisms, there is an ISO standard for it etc. When semantic web formalisms were discussed, Prolog was sometimes mentioned. However, it is so far not very widely used as a querying or modeling language even for semantic web applications. Recent advances in Prolog implementations may increase the uptake of this syntax. Also, public perception of Datalog and Prolog lags somewhat behind recent developments in these areas and what these technologies can actually do or what they even are. For example, here on HN, many posted articles that claim to be about Datalog often show snippets and examples that use completely different notations which are no longer a subset of ISO Prolog and therefore also not Datalog. Thus, they also do not immediately benefit from recent advances in Prolog systems in that they cannot directly be parsed and interpreted by them. It may take some time to advertise these improvements, and increase interest in these formalisms.

patrickmn 7y ago
What's the best example of modern Datalog?
- thom 7y ago
  Datomic. Also interesting: https://github.com/sixthnormal/clj-3df https://github.com/sixthnormal/clj-3df
  - refset 7y ago
    Datomic provides a fantastic range of query features, but the underlying Datalog engine does have drawbacks in how it evaluates results eagerly and requires intermediate result sets to fit in memory [0]. For comparison, I work on https://opencrux.com https://opencrux.com which uses lazy Datalog evaluation and can spill to disk when necessary. Naturally there are downsides to this approach also, including a dependence on seek-heavy use of local KV indexes. clj-3df is definitely interesting although not strictly comparable :) [0] https://docs.datomic.com/on-prem/query.html#memory-usage https://docs.datomic.com/on-prem/query.html#memory-usage
    - thom 7y ago
      Oh hello! I hadn't realised JUXT had their own products now, will definitely check this out.
- triska 7y ago
  A good way to try Datalog is to use a state-of-the-art Prolog system that supports SLG resolution (tabling). SLG resolution is an evaluation strategy of Prolog programs that provides favourable termination properties compared to SLDNF resolution which is Prolog's default execution strategy. A great example for this is XSB Prolog, since it has pioneered and refined many of these techniques and serves as an example and benchmark for many other Prolog systems in this area: https://xsb.com/xsb-prolog https://xsb.com/xsb-prolog The nice thing is that this approach allows you to use Datalog, and at the same time gives you a Turing-complete programming language that is comparatively easy to grasp once you understand Datalog, while sharing many of the same advantages and being syntactically only a slight extension of it.
  - mycall 7y ago
    A turning complete query language sounds like a recipe for DoS attacks.
    - maweki 7y ago
      It is only Turing complete if you allow new rules. Usually a client would only be allowed to formulate query goals. In that sense, GraphQL is Turing complete as well, as the underlying implementation could just simulate a Turing machine.
      - onion2k 7y ago
        What I read from your post here is that GraphQL is safe by default and would require effort to make it dangerous while Datalog is dangerous by default and would require configuration to make it safe. I know which one I'd rather put on a server.
        maweki 7y ago
        You have read that incorrectly. A Datalog/Prolog query does not define new rules. That's like calling arbitrary code on remote machines. You would never allow that. But IF you were allowed to define new rules, THEN you could simulate a turing machine or create infinite reductions.
- muydeemer 7y ago
  You might want to check out Grakn (https://github.com/graknlabs/grakn/ https://github.com/graknlabs/grakn/) - its query language is an implementation of recursive datalog with negation and comes with lazy execution. I am one of its developers.
- lordgrenville 7y ago
  Certainly not the best, but worth mentioning the Python implementation pydatalog. https://sites.google.com/site/pydatalog/home https://sites.google.com/site/pydatalog/home
zdragnar 7y ago
My last and only experience with Datalog (or a variation thereof) was (I believe) Logicblox, which (at least at the time) had zero support for pagination. In spite of all the supposed benefits of the system, that makes it fundamentally unsuitable imho.
Karrot_Kream 7y ago
This was (is?) what the semantic web dream was all about, and I find it funny that it took a corporation (FB) developing a clone before others discovered the concept. Semantic web data would be published as RDF data and clients would consume this data using a SPARQL query engine to get whichever shape of data that they desired.
- triska 7y ago
  To clarify: I mean that Prolog was under consideration to be used for what SPARQL was then developed, as a more readable and simpler query and also modeling language. Several researchers working in this area considered the development of SPARQL to be a missed opportunity for better formalisms, since Prolog could have been used instead. And, yes, to many who have worked with RDF, SPARQL and the various notations that have been developed for semantic web technologies, Prolog seems like a dream that shows what these technologies could have been, and can become in the future, i.e., easily processable, with a uniform and simple syntax that already has an ISO standard, and amenable to formal reasoning based on well-known logical rules.
  - j-pb 7y ago
    > easily processable > formal reasoning based on well known logical rules Oof, I do not know any serious researcher of logic who would support that claim. Prolog is, due to its age and heritage, inherently side/effectful and undecidable/turing-complete. SPARQL has big fat warts, for sure, design by committee, bulky syntax, way too long spec, way too many capabilities, and questionable decidability (looking at you MAYBE clause), BUT at its heart it's non recursive conjunctive queries over regular path expressions. CJ over PathRegex are a really elegant way to describe arbitrarily nested datastructures with flat queries, and are a lot more intuitive and concise than the corresponding datalog query. Edit: Not saying that prolog doesn't have its place btw, it's a neat language with awesome capabilities, but is NOT a query language.
    - YeGoblynQueenne 7y ago
      That's right- Prolog is not a query language. But the claim I believe is that _Datalog_ is a subset of Prolog that is a query language. That claim is true by design. Also, given bottom-up evaluation, Datalog programs are guaranteed to terminate and, restricted to definite clauses with no function symbols (of arity more than 0) they are also amenable to formal proofs of correctness, perhaps more so than Prolog itself. EDIT: Oh. I assume that by "formal reasoning" you and triska are discussing formal proofs of correctness- otherwise I don't understand the disagreement. Resolution is a well-known logical rule (an inference rule) and it's amenable to formal reasoning, for sure.
deleted 7y ago
[deleted]
j-pb 7y ago
> notations which are no longer a subset of ISO Prolog and therefore also not Datalog. This is false. Datalog is not (or no longer) about prolog like syntax, Datalog as used nowadays in research, describes the semantics for a logic which includes conjunctive queries and recursion, often denoted as an abstract syntax consisting of rules with a body and head, no ascii syntax attached. > Thus, they also do not immediately benefit from recent advances in Prolog systems in that they cannot directly be parsed and interpreted by them. This is like saying, that Javascript can benefit from updates to the Java virtual machine. Prolog and Datalog require radically different evaluation strategies and implementations.

by triska 7y ago

patrickmn 7y ago

What's the best example of modern Datalog?

thom 7y ago
Datomic. Also interesting: https://github.com/sixthnormal/clj-3df https://github.com/sixthnormal/clj-3df
- refset 7y ago
  Datomic provides a fantastic range of query features, but the underlying Datalog engine does have drawbacks in how it evaluates results eagerly and requires intermediate result sets to fit in memory [0]. For comparison, I work on https://opencrux.com https://opencrux.com which uses lazy Datalog evaluation and can spill to disk when necessary. Naturally there are downsides to this approach also, including a dependence on seek-heavy use of local KV indexes. clj-3df is definitely interesting although not strictly comparable :) [0] https://docs.datomic.com/on-prem/query.html#memory-usage https://docs.datomic.com/on-prem/query.html#memory-usage
  - thom 7y ago
    Oh hello! I hadn't realised JUXT had their own products now, will definitely check this out.
triska 7y ago
A good way to try Datalog is to use a state-of-the-art Prolog system that supports SLG resolution (tabling). SLG resolution is an evaluation strategy of Prolog programs that provides favourable termination properties compared to SLDNF resolution which is Prolog's default execution strategy. A great example for this is XSB Prolog, since it has pioneered and refined many of these techniques and serves as an example and benchmark for many other Prolog systems in this area: https://xsb.com/xsb-prolog https://xsb.com/xsb-prolog The nice thing is that this approach allows you to use Datalog, and at the same time gives you a Turing-complete programming language that is comparatively easy to grasp once you understand Datalog, while sharing many of the same advantages and being syntactically only a slight extension of it.
- mycall 7y ago
  A turning complete query language sounds like a recipe for DoS attacks.
  - maweki 7y ago
    It is only Turing complete if you allow new rules. Usually a client would only be allowed to formulate query goals. In that sense, GraphQL is Turing complete as well, as the underlying implementation could just simulate a Turing machine.
    - onion2k 7y ago
      What I read from your post here is that GraphQL is safe by default and would require effort to make it dangerous while Datalog is dangerous by default and would require configuration to make it safe. I know which one I'd rather put on a server.
      - maweki 7y ago
        You have read that incorrectly. A Datalog/Prolog query does not define new rules. That's like calling arbitrary code on remote machines. You would never allow that. But IF you were allowed to define new rules, THEN you could simulate a turing machine or create infinite reductions.
muydeemer 7y ago
You might want to check out Grakn (https://github.com/graknlabs/grakn/ https://github.com/graknlabs/grakn/) - its query language is an implementation of recursive datalog with negation and comes with lazy execution. I am one of its developers.
lordgrenville 7y ago
Certainly not the best, but worth mentioning the Python implementation pydatalog. https://sites.google.com/site/pydatalog/home https://sites.google.com/site/pydatalog/home

zdragnar 7y ago

My last and only experience with Datalog (or a variation thereof) was (I believe) Logicblox, which (at least at the time) had zero support for pagination. In spite of all the supposed benefits of the system, that makes it fundamentally unsuitable imho.

Karrot_Kream 7y ago

This was (is?) what the semantic web dream was all about, and I find it funny that it took a corporation (FB) developing a clone before others discovered the concept. Semantic web data would be published as RDF data and clients would consume this data using a SPARQL query engine to get whichever shape of data that they desired.

triska 7y ago
To clarify: I mean that Prolog was under consideration to be used for what SPARQL was then developed, as a more readable and simpler query and also modeling language. Several researchers working in this area considered the development of SPARQL to be a missed opportunity for better formalisms, since Prolog could have been used instead. And, yes, to many who have worked with RDF, SPARQL and the various notations that have been developed for semantic web technologies, Prolog seems like a dream that shows what these technologies could have been, and can become in the future, i.e., easily processable, with a uniform and simple syntax that already has an ISO standard, and amenable to formal reasoning based on well-known logical rules.
- j-pb 7y ago
  > easily processable > formal reasoning based on well known logical rules Oof, I do not know any serious researcher of logic who would support that claim. Prolog is, due to its age and heritage, inherently side/effectful and undecidable/turing-complete. SPARQL has big fat warts, for sure, design by committee, bulky syntax, way too long spec, way too many capabilities, and questionable decidability (looking at you MAYBE clause), BUT at its heart it's non recursive conjunctive queries over regular path expressions. CJ over PathRegex are a really elegant way to describe arbitrarily nested datastructures with flat queries, and are a lot more intuitive and concise than the corresponding datalog query. Edit: Not saying that prolog doesn't have its place btw, it's a neat language with awesome capabilities, but is NOT a query language.
  - YeGoblynQueenne 7y ago
    That's right- Prolog is not a query language. But the claim I believe is that _Datalog_ is a subset of Prolog that is a query language. That claim is true by design. Also, given bottom-up evaluation, Datalog programs are guaranteed to terminate and, restricted to definite clauses with no function symbols (of arity more than 0) they are also amenable to formal proofs of correctness, perhaps more so than Prolog itself. EDIT: Oh. I assume that by "formal reasoning" you and triska are discussing formal proofs of correctness- otherwise I don't understand the disagreement. Resolution is a well-known logical rule (an inference rule) and it's amenable to formal reasoning, for sure.

deleted 7y ago

[deleted]

j-pb 7y ago

> notations which are no longer a subset of ISO Prolog and therefore also not Datalog. This is false. Datalog is not (or no longer) about prolog like syntax, Datalog as used nowadays in research, describes the semantics for a logic which includes conjunctive queries and recursion, often denoted as an abstract syntax consisting of rules with a body and head, no ascii syntax attached. > Thus, they also do not immediately benefit from recent advances in Prolog systems in that they cannot directly be parsed and interpreted by them. This is like saying, that Javascript can benefit from updates to the Java virtual machine. Prolog and Datalog require radically different evaluation strategies and implementations.