Graph databases

Abstract

There is provided a non-transitory machine-readable storage medium encoded with instructions executable by a processor. The machine-readable storage medium comprises a graph database comprising first-level vertices and first-level edges, each first-level edge linking two first-level vertices, wherein each first-level vertex represents an entity and each first-level edge represents a relationship between two entities. The machine-readable storage medium further comprises instructions to: responsive to a generation of a result set for a query on the graph database, add a second-level vertex to the graph database, wherein the second-level vertex represents the result set of the query; and add a second-level edge to the graph database, wherein the second-level edge connects the second-level vertex to a first-level vertex.

1 . A non-transitory machine-readable storage medium encoded with instructions executable by a processor, the machine-readable storage medium comprising:
 a graph database comprising first-level vertices and first-level edges, each first-level edge linking two first-level vertices, wherein each first-level vertex represents an entity and each first-level edge represents a relationship between two entities; and   instructions to:
 responsive to a generation of a result set for a query on the graph database, add a second-level vertex to the graph database, wherein the second-level vertex represents the result set of the query; and add a second-level edge to the graph database, wherein the second-level edge connects the second-level vertex to a first-level vertex. 
   
     
     
         2 . A non-transitory machine-readable storage medium in accordance with  claim 1 , wherein each second-level edge connects a second-level vertex to a first-level vertex which represents an entity comprised in the result set represented by the connected second-level vertex. 
     
     
         3 . A non-transitory machine-readable storage medium in accordance with  claim 1 , wherein each first-level vertex is associated with a type, and wherein the graph database is a multi-partite graph database, such that the first-level vertices are partitionable into two or more independent sets based on the type of the first-level vertices. 
     
     
         4 . A non-transitory machine-readable storage medium in accordance with  claim 1 , wherein each second-level edge represents a containment relationship. 
     
     
         5 . A non-transitory machine-readable storage medium in accordance with  claim 1 , further comprising instructions to:
 responsive to a generation of a further result set, for a further query on the graph database, add a further second-level vertex to the graph database, wherein the further second-level vertex represents the further result set; add a further second-level edges to the graph database, wherein the further second-level edge connects the further second-level vertex to a first-level vertex; and add a third-level edges to the graph database, wherein the third-level edge connects the further second-level vertex to a second-level vertex.   
     
     
         6 . A non-transitory machine-readable storage medium in accordance with  claim 5 , wherein each third-level edge represents a parent-child relationship. 
     
     
         7 . A non-transitory machine-readable storage medium in accordance with  claim 5 , wherein the inputs to the further query comprise the first-level vertices and the second-level vertex. 
     
     
         8 . A non-transitory machine-readable storage medium in accordance with  claim 1 , further comprising instructions to:
 responsive to a change to an entity represented by a first-level vertex:
 associate a change indication with the first-level vertex representing the changed entity; 
 associate a change indication with each second-level vertex connected, by a second-level edge, to the first-level vertex representing the changed entity, and with each second-level edge connected to the first-level vertex representing the changed entity; and 
 associate a change indication with each second-level vertex connected, by a third-level edge, to a second-level vertex having an associated change indication. 
   
     
     
         9 . A non-transitory machine-readable storage medium in accordance with  claim 8 , further comprising instructions to associate a change indication with each third-level edge connecting two second-level vertices which each have an associated change indication. 
     
     
         10 . A non-transitory machine-readable storage medium in accordance with  claim 8 , wherein the change to an entity comprises one of: addition of the entity to the graph database; removal of the entity from the graph database; a change in the value of an attribute of the entity. 
     
     
         11 . A non-transitory machine-readable storage medium in accordance with  claim 8 , further comprising instructions to:
 responsive to a generation of a further result set, for a further query on the graph database:
 add a further second-level vertex to the graph database, wherein the further second-level vertex represents a result set of the further query; 
 add a further second-level edge to the graph database, wherein the further second-level edge connects the further second-level vertex to a first-level vertex; 
 determine, in respect of each first-level vertex connected to the further second-level vertex, whether that first-level vertex has an associated change indication; 
 if a first-level vertex connected to the further second-level vertex has an associated change indication, recalculate second-level edges which have associated change indications based on the changed entity. 
   
     
     
         12 . A non-transitory machine-readable storage medium in accordance with  claim 11 , wherein the graph database comprises at least one third-level edge connecting two second-level vertices, further comprising instructions to:
 responsive to the determination, in respect of each first-level vertex connected to the further second-level vertex, whether that first-level vertex has an associated change indication, if a first-level vertex connected to the further second-level vertex has an associated change indication, recalculate third-level edges which have associated change indications based on the changed entity.   
     
     
         13 . A non-transitory machine-readable storage medium in accordance with  claim 1 , wherein the graph database comprises a plurality of second-level vertices, each of which is connected to at least one first-level vertex by a second-level edge, the machine-readable storage medium further comprising instructions to:
 determine whether a first second-level vertex of the plurality is related to a second second-level vertex of the plurality by determining whether a path exists between the first second-level vertex and the second second-level vertex.   
     
     
         14 . A method, performed in relation to a graph database comprising first-level vertices and first-level edges, each first-level edge linking two first-level vertices, wherein each first-level vertex represents an entity and each first-level edge represents a relationship between two entities, the method comprising:
 querying the graph database to generate a result set;   responsive to the generation of the result set, adding a second-level vertex to the graph database, wherein the second-level vertex represents the result set of the query; and adding a second-level edge to the graph database, wherein the second-level edge connects the second-level vertex to a first-level vertex.   
     
     
         15 . Apparatus comprising:
 a processor;   a storage coupled to the processor, storing a graph database comprising first-level vertices and first-level edges, each first-level edge linking two first-level vertices, wherein each first-level vertex represents an entity and each first-level edge represents a relationship between two entities; and   an instruction set to cooperate with the processor and the storage to:
 responsive to a generation of a result set for a query on the graph database, add a second-level vertex to the graph database, wherein the second-level vertex represents the result set of the query; and add a second-level edge to the graph database, wherein the second-level edge connects the second-level vertex to a first-level vertex.