Skip to content

Instantly share code, notes, and snippets.

@imranansari

imranansari/Time & Versioning in Graphs.md

Created October 12, 2016 21:34
Show Gist options
  • Save imranansari/1fb97b6137b88b5d2a36e00b901eff15 to your computer and use it in GitHub Desktop.
Save imranansari/1fb97b6137b88b5d2a36e00b901eff15 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
Time & Versioning in Graphs.md

= Time & Versioning in Graphs

== Time as Attributes

  • Long (Seconds or Milliseconds since Epoch)
  • String ISO-XXX -> comparable
  • Simple String yyyy-mm-dd

Issues:

  • TimeZones?
  • LocalTime / LocalDate ?

== Time Tree

also supported elsewhere

== Time-Based Versioned Graphs - Ian Robinson

http://iansrobinson.com/2014/05/13/time-based-versioned-graphs/ http://www.neo4j.org/graphgist?608bf0701e3306a23e77

May 13th, 2014 | Published in Cypher, Graph Databases, Neo4j by Ian Robinson

Many graph database applications need to version a graph so as to see what it looked like at a particular point in time. Neo4j doesn’t provide intrinsic support either at the level of its labelled property graph model or in its Cypher query language for versioning. Therefore, to version a graph we need to make our application graph data model and queries version aware.

I’ll say this up front: versioning necessarily creates a lot more data – both more nodes and more relationships. In addition, queries will tend to be more complex, and slower, because every MATCH must take account of one or more versioned elements. Given these overheads, apply versioning with care. Perhaps not all of your graph needs to be versioned. If that’s the case, version only those portions of the graph that require it.

In this post I’m going to discuss what I consider to be the easiest form of versioning – time-based versioning. Time-based versioning gives us a universal versioning scheme: pick an instant, convert it to a long value, and the resulting version number applies to all parts of the graph. Version-number-based versioning, where each entity has its own independently varying version number (and scheme even), is more complex to implement. I’ll be dealing with that in a future post.

== Persistent Datastructures

http://en.wikipedia.org/wiki/Persistent_data_structure#Trees

only works for trees shallow copy of changed paths root node represent version

also used in Clojure (Rich Hickey)

== Versioning using Namespaced Relationship Types -Craig Taverner AmanziTel

persistent data structures of arbitrary graphs

namespaced relationships

with version property (traverse :REL with version >= X) <- inlined properties would help a lot

Generic graphs - No rooted trees

  • No single node per version
  • No obvious place to start traversals
  • Need a domain specific solution
  • Rooted tree becomes an example domain
  • At neo4j level: Versioned namespaces
  • At application/library/modeling level: Rooted trees (or other structures)

== Intermediate Version Nodes - Graphrica Tom Zeppenfield

Network versioning using relationnodes

In this gist I’d like to put in my 2 cents by introducing another approach using relationnodes. This is more about structure of a network than about states of nodes, but it treats versioning differently. As Ian states in his blog, there’s always a trade-off to be made, since versioning causes an extra load on storage and processing.

== A MODEL FOR TEMPORAL VERSIONING IN NEO4J

http://gidography.com/?p=132

05/09/2014

The Neo4j graph database has excellent capabilities for modelling interconnected, unstructured, high volume data. In the Neo4j graph database there is, though, no embedded functionality for handling versioning of data in the sense, that the CYPHER query language and the core database engine does not currently support versioning.

Visioning of data can consist of either a temporal versioning or an actual version management. Temporal versioning enables queries with a time dimension, i.e. executing a query in the database given the state of the database at a certain point in time. Version Management, on the other hand, does not have an explicit temporal dimension, but reflects different alternative states or version of data. This concept is known from source code versioning and from professional long transaction GIS systems handling multiple concurrent versions of planning data.

== Versioning with Neo4j - Antiquity

Neo4j is a very known graph database implementation and production ready,

Using Antiquity in conjunction with Neo4j is very simple, The only thing required is to initialize a Neo4j blueprints graph instance as the base graph and wrap it with Antiquity's graph implementation,

https://github.com/indexiatech/antiquity/wiki/Versioning-with-Neo4j

== Time-Machine Style Versioning David Montag

https://github.com/dmontag/neo4j-versioning

Implements time machine style versioning. Every change to the graph bumps the version number used. The graph can then be viewed at any given version number. With fairly little effort, this library can be modified to provide timestamp-based versioning instead.

Implementation-wise, it stores a validity range on relationships, and also keeps versioned copies of node properties. Indices and relationship properties are currently not versioned.

== Kurt Bollacker

Discussion:

  • RDF as Archival Graph +
  • Projection to Property Graph as Runtime Graph

== Thomas Baum AMD

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment