Hi Marko, Get ready for monads <https://en.wikipedia.org/wiki/Monad_(functional_programming)>. I mentioned them in my post <https://groups.google.com/d/msg/gremlin-users/MPNdNOAnYbs/sbowvioiDgAJ> on algebraic property graphs. In functional programming, monads are a typical way of composing chains of stateful operations together in such that they do not violate functional purity. For example, an operation which adds a vertex to a graph can be thought of as a function f : Graph -> Graph that takes a graph as its input, adds a vertex, and returns the resulting graph as its output. The function f doesn't actually mutate the graph on disk, but it gives you an in-memory representation of the mutated graph, which can then be persisted to disk. Some things you need in order to make this work:
1) a snapshot of the state of the graph / database as it existed when the transaction was started 2) a transaction log, within the TinkerPop VM, containing all atomic changes that were made to the graph since the transaction was started 3) a view of the graph overlaid with the contents of the transaction log 4) the ability to persist the transaction log to the database Items (1) and (4) are pretty trivial if the underlying database itself supports transactions. Item (2) is easy if we use a basic state monad. More on that below. Item (3) requires some insight into how graphs and other data structures are represented in TinkerPop4, and this is where the interaction between the basic data model and the VM comes in. In terms of what I called the APG data model, there are three basic changes of state: 1) add an element of a given type. E.g. the edge with label knows and id 42 didn't exist before, and now it does. 2) remove an element of a given type. E.g. the edge with label knows and id 42 existed before, but now it doesn't. 3) mutate an existing element of a given type. E.g. the element with label knows and id 42 used to have Person vertex 1 as its out-element and Person vertex 4 as its in-element, but now it has Person vertex 6 as its in-element. In other words, we support *create*, *update*, and *delete* operations for typed elements. *Read* operations do not require appending to the transaction log. Now, given that we have mutated the graph in our transaction, but the graph on disk has not changed, how do we deliver a consistent view of the mutated graph to subsequent read operations in the same transaction? If we think of the graph as a set of relations (tables, indexes), then we just need to wrap each read operation, from each table, in such a way that the read operation respects the transaction log. For example, if we have a relation like V() that represents all vertices in the graph, and we have added a vertex, then the iterator for V() should be the raw V() iterator for the unmodified graph -- filtered to exclude all *delete* elements in the transaction log which are vertices -- concatenated with a filtered iterator over all *create* elements which are vertices. Once you have committed your transaction, the transaction log is empty, so these wrapped iterators provide exactly the same elements as the raw iterators. How do you build a transaction log within a traversal? With a state monad <https://en.wikipedia.org/wiki/Monad_(functional_programming)#State_monads>. A state monad will allow you to execute any basic VM instruction and carry the transaction log along with the computation. Most instructions are a no-op with respect to state, but those few instructions which do affect state must append to the transaction log. For example, a V() operation doesn't just give you an iterator over vertices; it gives you a pair of objects: the iterator over vertices, and also the transaction log . A create-vertex operation also gives you a pair of objects: the newly-created vertex, and also the state, in which we have appended a *create* element to the transaction log. In terms of language support, Java 8+ supports some things <https://dzone.com/articles/whats-wrong-java-8-part-iv> that happen to be monads, where the flatMap method is equivalent to the monadic bind operator. Of course, you can also implement your own monads in Java. Scala does not have a built-in monad concept or syntactic sugar either, although it does have better support for higher-kinded types in general. In any case, we only really need to implement one monad for the sake of transactions: call it State or Transaction. In plain old Java, this would look something like the following (ignoring applicative functors, which are awkward in Java): public class TransactionLog { private Iterable<Element> created; private Iterable<Element> updated; private Iterable<Element> deleted; public TransactionLog append(TransactionLog other) { ... } } public class State<A> { private TransactionLog log; private A object; public State(A object, TransactionLog log) { this.object = object; this.log = log; } public TransactionLog getLog() { return log; } public A getObject() { return object; } public <B> State<B> map(Function<A, B> mapper) { return new State(mapper.apply(object), log); } public <B> State<B> flatMap(Function<A, State<B>> mapper) { State<B> other = mapper.apply(object); return new State(other.object, log.append(other.log)); } } Btw. a type-friendly definition of Element would look something like this: public abstract class Type { public String name; } public class PrimitiveType extends Type { public Class valueClass; } public class TupleType extends Type { public List<Field> fields; } public class UnionType extends Type { public List<Field> alternatives; } public class Field { public String name; public Type type; } public class Element { public String id; public Type type; public Value value; } public abstract class Value { } public class PrimitiveValue<V> extends Value { public V value; } public class TupleValue extends Value { public List<Value> values; } public class UnionValue extends Value { public String fieldName; public Value value; } Josh On Mon, May 13, 2019 at 5:08 PM Marko Rodriguez <[email protected]> wrote: > Hello Josh (others), > > You mentioned a week or so ago that the n-tuple model should be able to > capture both indices and transactions. > > At the time, I scoffed at the notion. However, as you know, I have been > recently enlightened to how n-tuples can model indices and am using it > extensively in the spec. What I would like to contemplate now is how you > figure transactions being modeled? > > Thanks, > Marko. > > http://rredux.com <http://rredux.com/> > > > > >
