Graphs with relationships that change over time?

[seanlaff (Sean Lafferty)]

I’m looking for insight on the best way to solve a metadata-over-time problem.

Image a graph where you have VMs and Hosts. VMs run on a host… but over time, the VMs move between hosts.

We need to be able to show which host a VM was running on at a specific time. In my ideal world, I could put tuples of [startTime, endTime] as a facet (edge attribute) on the relationship, however dgraph only supports scalar type facets.

As a workaround, we’ve tried adding multiple of the same relationships (with different facets) however it appears dgraph updates the existing relationship rather than make a new one.

Another idea we had was placing an intermediary node to act as a “relationship” that could hold more information, but that became pretty nasty to query against.

Are there any patterns for “temporally aware” graphs?

[martinmr (Martin Martinez Rivera)]

Another idea we had was placing an intermediary node to act as a “relationship” that could hold more information, but that became pretty nasty to query against.

This shouldn’t be the case if the graph is designed properly but maybe there’s some missing info. I have a rough idea of how to do this.

First, the types would be something like:

type Host {
  name # string
}

type VM {
  name # string
  host_info # [uid] to objects of type HostInfo
}

type HostInfo {
  host # uid value pointing to the host.
  start_time
  end_time
}

Also, let’s assume for this example that a VM is in the host during the range [start_time, end_time) (i.e, if t==end_time the VM has left this host).

So to get the host where the VM with id vm_id was at time t, the query could be written as.

{
  var(func: uid(<vm_id>)) {
    host_info @filter(ge(start_time, t) AND lt(end_time, t)) {
      host {
        A as uid # A is the set of hosts (it should have at most one element).
      }
    }
  }

  host(func: uid(A), first: 1) {
    uid
    name
  }
} 

Let me know if that’s helpful or if I made any incorrect assumptions.

[marvin-hansen]

@seanlaff Have you tried a TimeTree?

When you model host as an attribute, then an “event” can be seen as anything that affects an instance, which then get inserted into the time tree. Structurally, you can then query the TimeTree and figure out about everything that happened between time X and Y.

https://medium.com/ft-product-technology/adventures-with-neo4j-and-timetrees-5413f97f8a82

[seanlaff (Sean Lafferty)]

@martinmr @marvin-hansen Thanks for the suggestions and detailed write-ups! Both seem interesting, I will spend some time experimenting