31–40 of 56 posts
Earlier quoted context omitted.
I'm sad their last commit was 2 years ago, seemed like a really cool idea
The authors spun it out into a startup, Feldera. A paper describing their idea also won Best Paper at VLDB 2023. The idea is very far from dead.
Earlier quoted context omitted.
1. Datomic - While not open-source, it has an open-source version called Datomic Free, which is a distributed database designed to enable scalable, flexible, and intelligent data storage and queries. Datomic's query language is closely inspired by Datalog. 2. DataScript - An open-source in-memory database and query engine for Clojure, ClojureScript, and JavaScript that is heavily influenced by Datalog and Datomic. 3.…
CodeQL is another datalog with the domain of code analysis as its use case. Too bad you cannot create a custom fact database with CodeQL. Otherwise, the implementation of CodeQL is pretty advanced and efficient.
I wish people would stop referring to Datomic as datalog. Datomic is many things, but only the query format (Horn clauses with unification of variables, similar to prolog) has anything to do with datalog. Real datalog is far more interesting since it implicitly encodes recursion allowing you to chain rules. Rule A derives new facts, which rule B uses to derive new facts, which rules A and C use to derive new facts, a…
Sounds cool. What's the complexity of running this kind of recursive reasoning? Reasonable? Can you suggest any tools to not have to implement it ourselves?
Percival (https://github.com/ekzhang/percival) has some very nice examples showing how you can interactively write and test rules on top of a datalog interpreter.
Bud (http://bloom-lang.net/bud/) is Hellerstein's proof of concept playground. It has bit-rotted in the past few years, but the examples are readable even if you can't easily get it working.
The complexity can be quite good. You can syntactically determine when you've written linear recursion (equivalent to a for loop) vs not. Otherwise, the complexity is what you'd expect from incremental view maintenance in a normal SQL database. Which is to say O(n^k) with k being the number of relations joined, but usually much, much less with appropriate indexes and skew in the data. All the usual tricks concerning data normalization and indexes from databases apply.
For the idiot in the thread, why would I use datalog (which I've never heard of before) over SQL? Having looked quickly at it just now it seems (Wikipedia article) similar to Web Ontology Language (OWL), though I believe datalog may have been around long before owl.
The more interesting answer is to think of datalog as making it easy to encode nearly all of your application logic as a bunch of self-referencing, incrementally updated, materialized views. Some examples:
# view of Users table for currently logged in user
LoggedInUserView(name, email, id) :- Users(id:
payload["userId"], name, email), Cookies(name: "login", payload).
# view of Users for admin
AdminUserView(name, email, id) :- Users(id, name, email), Cookies(name: "login", payload), payload["isAdmin"] = true.
# posts a user can see
PostsView(title, content, id) :- Posts(title, content, public: true).
PostsView(title, content, id) :- Posts(title, content, author: payload["userId"]), Cookies(name: "login", payload).
The examples above can be neatly replicated in Supabase or Postgraphile (the OG of auto-generated GraphQL over Postgres), but you can do a lot more with datalog as a language. The Hellerstein paper mentioned above is a good starting place.
It's a shame that there doesn't seem to be any decent open-source implementation of Datalog. If you go for full Prolog instead of Datalog, there are several (Scryer Prolog being my personal favourite).
1. Datomic - While not open-source, it has an open-source version called Datomic Free, which is a distributed database designed to enable scalable, flexible, and intelligent data storage and queries. Datomic's query language is closely inspired by Datalog. 2. DataScript - An open-source in-memory database and query engine for Clojure, ClojureScript, and JavaScript that is heavily influenced by Datalog and Datomic. 3.…
Now the website isn't even loading... has the project been shuttered? I know LogicBlox was acquired by Predictix a long time ago, and recently Infor acquired Predictix. Hoping the project is still a going concern, there was some very cool tech in there.
Datalog feels so much more intuitive than SQL or any other query language I've used. I'm able to write concise, complex expressions pretty easily. In a SQL-based system, there seems to be a (low) complexity metric where it's easier to write/debug/maintain what was supposed to be a 'declarative' SQL query in a functional/imperative language instead. It feels like datalog is the next evolution of a declarative query la…
However, they made an explicit design decision to not include a query optimizer and execute the clauses as they were written. This is usually fine since the author has some idea of what the best order is, but there are O(2^k) different permutations of clauses so doing it by hand will fail at some point (if you want the optimal ordering).
I wish people would stop referring to Datomic as datalog. Datomic is many things, but only the query format (Horn clauses with unification of variables, similar to prolog) has anything to do with datalog. Real datalog is far more interesting since it implicitly encodes recursion allowing you to chain rules. Rule A derives new facts, which rule B uses to derive new facts, which rules A and C use to derive new facts, a…
Sounds cool. What's the complexity of running this kind of recursive reasoning? Reasonable? Can you suggest any tools to not have to implement it ourselves?
> We present a novel approach to parallel materialisation (i.e., fixpoint computation) of datalog programs in centralised, main-memory, multi-core RDF systems. Our approach comprises an algorithm that evenly distributes the workload to cores, and an RDF indexing data structure that supports efficient, ‘mostly’ lock-free parallel updates.
> Materialisation is PTIME-complete in data complexity and is thus believed to be inherently sequential. Nevertheless, many practical parallelisation techniques have been developed [...]
There have been several papers and patents describing their approach, e.g. http://www.cs.ox.ac.uk/dan.olteanu/papers/mnpho-aaai14.pdf
It's a shame that there doesn't seem to be any decent open-source implementation of Datalog. If you go for full Prolog instead of Datalog, there are several (Scryer Prolog being my personal favourite).
you can use Datalig within Flix https://flix.dev/
I wish people would stop referring to Datomic as datalog. Datomic is many things, but only the query format (Horn clauses with unification of variables, similar to prolog) has anything to do with datalog. Real datalog is far more interesting since it implicitly encodes recursion allowing you to chain rules. Rule A derives new facts, which rule B uses to derive new facts, which rules A and C use to derive new facts, a…
> Why is that a big deal? When rules are run automatically, you can build live, reactive systems, not just a database that sits around waiting for you to query it.
There was at least one serious attempt to bring these worlds together: https://github.com/sixthnormal/clj-3df