Minikanren based database querying

[Amirouche Boubekki]

Héllo,

My initial plan was to work on multithread support for wiredtiger but
this sounds more complex and less fun than doing some minikanren.

For those that don't know minikanren [1], it's an embedded Domain
Specific Language for logic programming. It's similar in principle to
prolog. You might be wondering how this relates to database
programming. Well, there's two sides:

* First, you might want to store logic facts inside database persisted
  to disk because your dataset doesn't fit into memory
* Second, you might want to take advantage of the declarative nature
  of minikanren programs

For this exercise I've chosen to work on tuple database so called
(uid, attribute, identifier) aka. uav database, because it's the
database that is the most flexible and can span various usecases from
relational, graph or hierarchical problems to key/value or document
based kind of problems. And it can be loosely typed.

To picture how it looks like imagine a giant list of (u a v) tuples
like the following, that stores messages from a blogging application:

```
(define database '(("uid1" type post)
                   ("uid1" blog/post "uav db is a tuple db")
                   ("uid1" blog/create-at 0)

                   ("uid2" type tag)
                   ("uid2" tag/name "scheme")

                   ("uid3" type taglink)
                   ("uid3" taglink/tag "uid2")
                   ("uid3" taglink/post "uid1")))
```

In wiredtiger, `uid` and `attribute` compose the *key*, and the
`value` unique *value* column of the entry.

There is three primitive queries that can be run against such database:

* `(uav-ref dbc uid attribute)` retrieve the value associated with
  `(UID . ATTRIBUTE)` pair.
* `(uav-ref* dbc uid)` retrieve all the `(attribute . value)` pairs
  associated with `UID` aka. retrieve the document with `UID` as
  unique identifier.
* `(uav-index-ref dbc attribute value)` retrieve all `uid` for which a
  `(uid ATTRIBUTE VALUE)` tuple exists in the database.

I will skip the translation of the last two procedures into minikanren
procedures that makes it possible to solve logic problems backed by a
database and go straitgh to the higher level interface that use a
pattern matching-like interface to query the tuples.

This interface is less powerful that the raw minikanren interface in the
sens that it doesn't allow so far to create recursive queries but allows
to express SQL queries in a terse and nice syntax.

For instance, to query all blog posts that have the a given tag, one can
use the following query

```
(define (query:posts-with-tag* name)
 (query* uid? where ((tag?? tag/name name)
                     (taglink?? tag/link tag??)
                     (taglink?? tag/post uid?))))
```

The where clause declare the pattern that should be looked for. The
symbols that ends with a single question mark e.g. `tag?` are return
variables. symbols that ends with two question marks e.g. `taglink??`
are internal variables matched during querying.  (In the underlying
implementation `taglink??` is a minikanren variable instantiated with
`fresh`)

The above query translates in plain english line by line as:

* Given a tag with uid `tag??` and `tag/name` equal to the value `name`
* Find a tuple with `taglink??` uid where `tag/link` is associated with 
`tag??`
* Such as there is also a tuple with `taglink??` uid where `tag/post`
  is associated with `uid?`

And return `uid?`.

The above query can be written using the primitives like that:

```
(define (query:posts-with-tag name)
  (let* ((tag?? (uav-index-ref dbc 'tag/name name))
         (taglink?? (uav-index-ref dbc 'tag/link tag??)))
    (map (cut uav-ref dbc <> 'tag/post) taglink??)))
```

There is small webapp that make use of this, that can be found over git 
[2]. It only requires wiredtiger built from sources (develop branch) 
[3].


All the best!


[1] http://minikanren.org/
[2] https://git.framasoft.org/a-guile-mind/nanoblog.git
[3] https://github.com/wiredtiger/wiredtiger.git