When I say 'some kind of key/value index' I know I've just been arguing that we probably need something better than key/value stores in order to handle fully relational data. And I think we do.

The old database system Pick used to have, instead of a filesystem, a key/value store where the values could be lists, to give multiple values.

That's *maybe* a better approximation of mathematically correct relational storage but it would be nice to actually get it *right*.

Also when I say 'relational storage' I mean something like 'recursively structured relational'.

Because we've all been Stockholm Syndromed by SQL databases to think that a relation has to be

1) strictly n-ary, no mixed arities and
2) a non-nestable unit, ie you can't put a table inside another table
3) and if you need more than that you have to use a noSQL key/value store

when none of those restrictions actually apply to the pre-Codd mathematical idea of (binary) relations

But imagine if you had a generalised recursive-relational store!

So. Many. Times. you have a key-value store - like, say, the Windows Registry (though that's a slightly mutant one) - and you want to put multiple values into one key. So what do you end up doing? You end up making it a string and hashing up your own ad-hoc format to separate multiple values and then you have a parser to write and security errors and urrrgh and it all just didn't have to happen if your store was *relational*.

An interesting thing is that - if you can restrict your data to just strings, which is a BIG if - then both the Unix file system and the Windows Registry are relational in this sense, and in the sense that raw key/value stores like JSON are not. You can put any number of subfolder names you like in a folder (or subkey in a key), and you can query them for existence and even if they have nothing inside you can get a return value *about that folder* via files or values.

Eg the requirements for a fully consistent relational store are that you can add and remove at least the following two paths:

(a b) or a.b
(a b c) or a.b.c

as they represent two separate, non-overlapping, logical statements. This separation is impossible (directly) in raw key-value store because the existence of (a b c) depends on its container (a b). We need to set some flag inside (a b) that's not one of it's subkeys.

One way to do this though might be with a generalised metakey.

Eg reserve one key symbol, eg _ or something, to store metadata about each node, including whether the node is 'active' or it has been retracted - since retracting a node's path as a logical statement is not the same as deleting a node and all its children.

A simpler way of saying this: Each node in a truly relational store must be able to set and unset the path () from itself. This requires extra conventions in a raw key/value store.

This is the reason for my thinking that I need two distinct null values, EMPTY and NIL. Empty is what you get when the store does not contain your path; Nil (plus any child keys) is what you get when the store contains your path.

But Nil can be added to/removed from any relation so it's maybe not the best name.

This is also why I get very confused about Childs' Extended Set Theory, which is really just a calculus of binary relations: I believe a set containing just NIL in his formulation would be { (NULL . NULL) } which is fine but it's also indistinguishable from { (NULL . NULL) } which is what I would put if I wanted to store, eg { (()) } instead of { () }. Or would I put { (NULL . { (NULL . NULL) } } and about then my head starts really hurting.

@natecull I guess you know about the stuff people did already on https://en.wikipedia.org/wiki/Tuple_space ?

@bremner Linda and ObjectSpaces both seem pretty neat, though I've never used them.

@natecull As an undergrad I built a prototype Linda implimentation, but it was kindof crappy and I'm not sorry the code is lost. 😏