Object eversion, ZigZag, and the RDBMS

John Ohno
John Ohno
Jan 1, 2019 · 3 min read

Object eversion was an idea we* invented for ZigZag (a generalization of tabular databases from 2 to n dimensions) but it occurs to me that it might be a convenient alternative to object-relational wrappers for codd-style RDBMS in prototype languages like JavaScript and lua (and languages that just support metatables like python), if you don’t mind fragging all your tables.

The idea is basically this:

An object doesn’t contain attributes, but is instead a point where the values of its attributes intersect. (Sort of like words in vector space.)

Traditional objects (left) vs everted objects (right)

In RDBMS terms: an object corresponds to some foreign key, & valid object members are rows in any tables where that foreign key is present (where the name of the member corresponds to the table name). So, in a language that lets you lookup if a property exists at runtime, that’s your object member lookup.

In ZigZag terms: an object is some cell, and valid object members (other than value) are any cells connected poswardly along some dimension (where the name of the member correponds to the dimension name).

This is fast in ZigZag where it’s just named linked lists so you’re doing a hash lookup + pointer dereference. In an actual RDBMS, this is liable to be slow, but importantly, it does not break the idiomatic style of RDBMS table layout.

(In ZigZag, the remainder of a rank is used as an array in many cases, but in an RDBMS you can use an actual array, enforce types where ZigZag would not, etc.)

I’m not suggesting an RDBMS-backed ZigZag. (It’s been done.) It’s trivial but slow as molasses, because many common operations involve getting the rank head, rank tail, or whole rank. When cell lookup is constant time, this is fine — O(n) operation and n is never huge in zigzag in the situations we’ve used it in. Add latency to that lookup & it becomes a nightmare.

We had a stateless ZigZag frontend that communicated with a remote ZigZag backend once. It worked great on the lan, but took minutes to render a just the visible cells on a small slice over the network from California, because we had one round trip per cell lookup (and that round trip took something like a tenth of a second).

What you can do, if you don’t expect multiple simultaneous users, is represent the slice in an RDBMS, dump the whole slice to the client (which gets its representation internally), & commit modifications in real time to both the backend & the in-memory representation (so you get transactions & a journal of changes).

Unfortunately, with this method, you run the risk of desynchronization with writes if you don’t model local and remote writes identically. To avoid drift, you can instead pull a fresh copy of the slice from the remote database after every write.

If you expect multiple simultaneous users, then you can update a timestamp with every write & check that timestamp with every frame (rather than every cell), grabbing a new complete dump if it’s changed since your last one. (So, every move takes at least roundtrip time and at most 2x roundtrip time plus negligable transfer time of a slice — a huge improvement over roundtrip time per cell).

*Note that we (myself & my partner on the project) invented the term ‘object eversion’ to describe a pattern that was already happening in Rob Smith’s already-implemented ZZOGL/FloatingWorld codebase, extended out the theory behind it, & were the first to make cell objects that treated posward connections as object members in a way that consistent with python language features. So, we ‘invented’ object eversion in the same way that Alan Kay ‘invented’ object orientation (trying to explain something he saw in Simula) & Mark Miller ‘invented’ general enfilade theory (looking at Steve Witham’s implementation of Ted’s ‘model T enfilade’ in the Jot prototype).

John Ohno

Written by

John Ohno

Resident hypertext crank. Author of Big and Small Computing: Trajectories for the Future of Software. http://www.lord-enki.net

More From Medium

More from John Ohno

More from John Ohno

More from John Ohno

New ways to write

Jan 17 · 9 min read

99

More from John Ohno

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade