Datalogl

A Datalog library for OCaml.

Datalog is a database query language based on logic programming. Datalogl is an OCaml implementation of Datalog with following features:

• Can use external databases for persistent storage (e.g. Irmin, LMDB (with OCaml bindings) or IndexedDB (when using js_of_ocaml).
• Supports incremental evaluation. The state of an evaluation can be reused and updated for more efficient recomputation of queries.
• Implemented in pure OCaml and can be used from MirageOS unikernels or web applications (via js_of_ocaml).

For more information and a short introduction to Datalog see the online documentation (TODO). The documentation can also be built locally with dune build @doc.

Related Software

c-cube/datalog

c-cube/datalog is another OCaml implementation of Datalog.

We implement a different algorithm (the Query-Subquery Algorithm) whereas c-cube/datalog implements Semi-Naive evaluation (bottom-up) and SLG (top-down).

Query-Subquery (QSQ) is a top-down evaluation algorithm like SLG. Unlike SLG, QSQ operates on entire sets of facts whereas SLG operates on individual tuples. This should make QSQ more efficient when working with large amounts of data. On the other hand, QSQ can not natively solve Datalog programs that contain negations (SLG can do this natively).

Another difference is that this library allows facts to be stored externally in a persistent database, whereas c-cube/datalog only allows in-memory facts.

ramsdell/ocaml-datalog

Another OCaml implementation of Datalog. Similar to c-cube/datalog this implements the SLG evaluation algorithm.

Developing

A suitable development environment can be created with Guix by running guix shell -D -f guix.scm.

From this environment you can run dune build to build the library and dune test to run the test cases.

Contributions are very welcome, either by mail or by pull requests to the repository hosted at codeberg (openEngiadina/ocaml-datalogl).

TODOs/Futurelog

Optimize based on EDB indices

The EDB should be able to indicate what kind of queries are cheap and what queries are expensive (e.g. due to presence of indices). This information can be used to optimize the evaluation order of literals in a clause.

This would also allow the EDB to contain functions, i.e. infinite relations that can only be computed in a certain order.

Better join

Currently we have implemented a horribly inefficient nested loop join. It would be much better to implement either a hash join or even better a merge join. A merge join would require the EDB to provide tuples in a sorted order. This is usually possible for Irmin, LMDB or IndexedDB.

Stratification

For stratified negation and aggregate functions (e.g. min, max).

ppx for Datalog programs

It is currently very tedious to write Datalog programs in OCaml (the AST needs to be defined manually). It may be nice to have a ppx thing with which one can express Datalog programs from OCaml more nicely without dropping down to parsing strings.

Unfortunately, I have no experience with ppx. Help with this would be very much appreciated.

Acknowledgments

This library was initially developed for the openEngiadina project and has been supported by the NLnet Foundation trough the NGI0 Discovery Fund.

Contact

pukkamustard [at] posteo [dot] net

License

AGPL-3.0-or-later