[HN Gopher] Datalog in miniKanren
___________________________________________________________________
Datalog in miniKanren
Author : deosjr
Score : 129 points
Date : 2025-06-15 16:16 UTC (1 days ago)
(HTM) web link (deosjr.github.io)
(TXT) w3m dump (deosjr.github.io)
| deosjr wrote:
| Seems like interest in Datalog is high this week, so I thought
| I'd share a write-up of a minimal Datalog implementation I did a
| while ago.
|
| Runs in the browser using Hoot (https://spritely.institute/hoot/)
| which compiles Guile Scheme to WebAssembly.
| davexunit wrote:
| Wow this might be the coolest use of Hoot I've seen! I need to
| run this for myself soon.
| deosjr wrote:
| Thanks Dave, high praise! I was inspired after seeing you all
| take over the declarative & minimalist programming room at
| FOSDEM this year.
|
| If you thought this was cool, wait until you see what I ended
| up using it for: https://deosjr.github.io/dynamicland/ I
| personally think this is much cooler :) But it needs some
| more explaining before I can broadly share, I think.
|
| Now that I have you here, a question: am I correct in
| thinking that in Hoot, eval in the browser does not currently
| work with macros?
| davexunit wrote:
| I'm glad you felt inspired! This Dynamicland implementation
| looks awesome. I look forward to this being shared to a
| wider audience. :)
|
| Regarding your question, as of Hoot 0.6.1 we now have a
| psyntax-based macro expander integrated with eval so you
| can use syntax-rules and syntax-case. There are still rough
| edges, though. I'm currently focused on some non-Hoot tasks
| but the next Hoot priority is to implement a Guile-like
| REPL and really kick the tires on the interpreter before
| the 0.7.0 release.
| fithisux wrote:
| What scheme is this?
| deosjr wrote:
| Guile Scheme. See
| https://github.com/deosjr/deosjr.github.io/blob/master/dynam...
| for more.
| upghost wrote:
| Datalog is a syntactic subset of Prolog[1], which this is... not.
|
| I think the most misunderstood thing about Prolog (and Datalog,
| the functor-free subset of pure Prolog) is that the syntax is
| _really, really_ important.
|
| It's like, the whole gimmick of the language. It is designed to
| efficiently and elegantly query and transform itself. If you lose
| the syntax you lose all of intermediate and advanced Prolog (and
| Datalog).
|
| [1]: https://en.m.wikipedia.org/wiki/Datalog
| kragen wrote:
| Semantics are more important than syntax. Prolog's flexible
| syntax is a nice-to-have rather than essential when you're in
| Lisp. And Datalog is purely first-order, so the advanced Prolog
| you're talking about doesn't exist in it.
|
| However, syntax does matter, and this is not acceptable
| (dl-find (fresh-vars 1 (lambda (?id)
| (dl-findo dl ((,?id reachable ,?id)))))))
|
| as a way to ask reachable(Id, Id).
|
| I think you could, however, write a bit more Scheme and be able
| to ask (?id reachable ?id)
|
| which would be acceptable.
|
| However, the ordering betrays a deeper semantic difference with
| orthodox Datalog, which is about distinct N-ary relations, like
| a relational database, not binary relations. This
| implementation seems to be specific to binary relations, so
| it's not really Datalog for reasons that go beyond mere syntax.
|
| On the other hand, this (from the initial goal) would be
| perfectly fine: (dl-rule! dl (reachable ,?x
| ,?y) :- (edge ,?x ,?z) (reachable ,?z
| ,?y))
|
| The orthodox Datalog syntax is: reachable(X,
| Y) :- edge(X, Z), reachable(Z, Y).
| jitl wrote:
| Shouldn't lisp macros make it easy to present such a nice
| syntax? Perhaps the author could easily implement that bit,
| if not the wide rows. Or is that the point you're making?
|
| There is a dl-rule here: https://github.com/deosjr/deosjr.git
| hub.io/blob/15b5f7e02153...
| kragen wrote:
| I don't think you need Lisp macros for it; you could use
| just a regular Lisp function. I don't think the standard
| R5RS macros are powerful enough to grovel over the query
| expression to make a list of the free variables, but then,
| standard Scheme also doesn't have records. I think Guile
| has a procedural macro system that you could use, but I
| don't think it would be a good idea.
|
| Yes, I think the semantic divergence is more fundamental.
| Triple stores and graph databases and binary relations are
| awesome, but they aren't what Datalog is.
| deosjr wrote:
| Thank you for the feedback! I agree with all of the above.
|
| Should've probably been a bit more clear on the dl-find
| syntax; I find it just as unacceptable as you do. It is the
| result of laziness: my intended use of this minimal Datalog
| does not include any querying whatsoever but abuses fixpoint
| analysis for side-effects (see https://github.com/deosjr/deos
| jr.github.io/blob/master/dynam... which I intend to go over
| in a future post). I initially had it working like you
| described but butchered it for the above and haven't repaired
| it yet (see https://github.com/deosjr/whistle?tab=readme-ov-
| file#datalog). This version relied on some monstrous eval-
| hacking using a homebrew Lisp, which I've mostly cleaned up
| now in this version (https://github.com/deosjr/whistle/blob/m
| ain/datalog/datalog.... is a crime, for example).
|
| The semantics are indeed limited to binary relations atm,
| which I agree is the main thing that disqualifies this as a
| proper Datalog. iirc the tutorial on Datalog that I based
| this implementation on only handled triples as well so I
| stopped there, but extending to N-ary relations is on my list
| to look into for sure.
| kragen wrote:
| This sounds very interesting! I'll have to take a look.
|
| I am always worried about posting comments like mine
| because often people get defensive when I try to engage, as
| I see it, on substance. Responses like yours make it all
| worthwhile!
| deosjr wrote:
| I appreciate it; this kind of exchange is exactly why I
| read HackerNews. If you have any good sources on
| extending Datalog to N-ary relations, I'd love to know.
| Just had a look at the implementation I based mine on and
| it exclusively talks about triples:
| https://www.instantdb.com/essays/datalogjs
|
| Coming from Prolog I'd like to get closer to the original
| if possible :)
| thesz wrote:
| They use triples as triplets can represent any n-tuple
| facts.
|
| E.g., if you have a fact id=(a,b,c,d), you can record
| triples (id, 1, a), (id, 2, b), (id, 3, c) and (id, 4, d)
| and reconstruct original fact.
|
| Look at it as columnar storage in databases.
|
| Then, if your query only needs a third value from a
| 4-tuple facts, you can get only those, ignoring first,
| second and fourth values. This is what columnar storage
| engines do.
|
| In fact, I read that one of most efficient datalog
| engines use relational query execution under the hood.
|
| Take a look here: https://github.com/philzook58/awesome-
| egraphs
|
| The paper you'll most probably find interesting is
| "Better Together: Unifying Datalog and Equality
| Saturation," but there are many others interesting things
| there.
| deosjr wrote:
| Cheers, this is super useful. I will have to do some
| reading. Being able to build up n-ary predicates using
| triples that way makes a lot of sense.
| kragen wrote:
| Datalog always supports N-ary relations! It's not an
| extension.
|
| The Wikipedia article recommends
| https://search.worldcat.org/title/30546436 "Foundations
| of Databases" by Abiteboul, Hull, and Vianu, from 01995,
| and https://archive.org/details/logicdatabases0000symp/pa
| ge/n5/m... "Logic and Data Bases [sic]" by Gallaire and
| Minker from 01978. Some poking at Google Scholar also
| turns up, in rough order of how promising they look
| (without having read them that I can recall):
|
| https://dl.acm.org/doi/pdf/10.1145/6012.15399 "Magic Sets
| and Other Strange Ways to Implement Logic Programs",
| Bancilhon, Maier, Sagiv, & Ullman (yes, that Ullman),
| 01985 (15 pp.)
|
| https://citeseerx.ist.psu.edu/document?repid=rep1&type=pd
| f&d... "What You Always Wanted to Know About Datalog (And
| Never Dared to Ask)", Ceri, Gottlob, and Tanca, 01989 (21
| pp.)
|
| https://web.cecs.pdx.edu/harry/earley/datalog.pdf
| "Optimizations to Earley Deduction for DATALOG Programs",
| Porter, 01985 (12 pp.)
|
| https://dl.acm.org/doi/pdf/10.1145/308386.308420
| "Optimizing Existential Datalog Queries", Ramakrishhnan,
| Beers, & Krishnamurthy, 01988 (14 pp.)
|
| https://dl.acm.org/doi/pdf/10.1145/298514.298542 "On the
| Expressive Power of Datalog: Tools and a Case Study",
| Kolaitis & Vardi, 01990
|
| https://dl.acm.org/doi/pdf/10.1145/93605.98724 "A
| Framework for the Parallel Processing of Datalog
| Queries", Ganguly, Silberschatz, & Tsur, 01990
|
| https://deepblue.lib.umich.edu/bitstream/handle/2027.42/3
| 116... "Datalog vs First-Order Logic", Ajtai & Gurevich,
| 01993
|
| https://lat.inf.tu-
| dresden.de/teaching/ss2014/Seminar/Papers... "Equivalence
| of Datalog Queries is Undecidable", Shmueli, 01993
|
| It also turned up "Portability of Syntax and Semantics in
| Datalog" which turned out to be an unrelated NLP AI
| system called Datalog.
|
| Bancilhon, Maier, Sagiv, & Ullman give as their reference
| for Datalog "Maier and Warren [1985]", which turns out to
| be "D. Maier and D. S. Warren [1985]. Introduction to
| Logic Programming, unpublished memorandum, Oregon
| Graduate Center," which I can't find a copy of easily.
| But given that Maier is a shared author we can probably
| trust their summary of what Datalog is.
|
| Ceri, Gottlob, and Tanca reference "[120], [15], [16],"
| which are respectively:
|
| J. D. Ullman, "Implementation of logic query languages
| for databases," ACM Trans. Database Syst., vol. 10, no.
| 3, 1985
|
| F. Bancilhon and R. Ramakrishnan, "An amateur's
| introduction to recursive query processing," in Proc.
| ACM-SIGMOD Conf., May 1986.
|
| -, "Performance evaluation of data intensive logic
| programs," in Foundations of Deductive Databases and
| Logic Programming, J. Minker, Ed. Washington, DC, 1986.
|
| The Ullman paper is
| https://dl.acm.org/doi/pdf/10.1145/3979.3980,
| "Implementation of Logical Query Languages for
| Databases", ACM Transactions on Database Systems, Vol.
| 10, No. 3, September 1985, Pages 289-321 (33 pp.). Ceri,
| Gottlob, and Tanca screwed up the title.
| https://dl.acm.org/doi/10.1145/971699.320000 probably
| isn't it; the journal name, volume number, and issue
| number don't match, although it's the right author and
| year. That seems to be the oldest published Datalog
| paper, although the word "Datalog" hadn't been invented
| yet and doesn't appear in the paper.
|
| I think I'm going to read the Bancilhon, Maier, Sagiv, &
| Ullman paper first, because it's shorter and has a more
| readable-sounding title, and then maybe Ceri, Gottlob,
| and Tanca, and then maybe Ullman, and then maybe a
| relevant chapter or two of Gallaire and Minker.
| j-pb wrote:
| Most database literature simply uses Datalog to mean the query
| language fragment of conjunctive queries + recursion/fixpoint-
| iteration and potentially stratified negation.
|
| Yes it started out as a Prolog subset, but the definition as
| the fragments it supports has become much more prevalent,
| mainly to contrast it to non-recursive fragments with arbitrary
| negation (e.g. SQL).
|
| This usage dates back to database literature of the 80s by
| Ullman et. al.
___________________________________________________________________
(page generated 2025-06-16 23:01 UTC)