I've been developing a new feature for Hiperspace that includes the extension of the Node and Edge model to include a new type of TransitativeEdge that can be transitively extended to project relationships as a Butterfly graph that that shows end-to-end relationships between nodes as relations that do not need recursive query to examine.
If you wanted to show the costs for an organization of operating a service, you'd need to include costs associated with
- The activities performed with the service
- The activities performed by other functions to support the fron-line activities
- The applications, databases and other software used by the service
- The hardware the software is hosted on
- The costs space within a data-centre and power usage
Aggregating all this information would require a traversal of the entire graph of information, and allocation of proportion of the costs. The aggregation would cover a number of disciplines and potentially a number of steps to accumulate the information.
The problem of finding relevant information can be simplified using a graph-view that treats all the data as nodes and edges, but still leaves the problem of how to recursively query the data. Transitive-Edge addresses this problem by folding the entire graph of edges into a single relation that can be queries directly. If Cost is transitative then A -> B -> C -> D can be transitatively projected as A -> D.
Transitive-Edge
Transitive Edge uses the principle that an edge can be projected to a transitive-edge provided it follows one of the rules of the transitive route. For our purposes, those rules can be simplified to a set {from-type, edge-type, to-type}. ForFamily-tree is a good simple example, that uses just three Edge types {father, mother, child}, but a whole family tree can be projected from them using the Transitive Edge relation.
In this example Mark is the child of Mary is the child of Jane is the child of Eve through the Mother Edge. Mark has a transitive Edge relation to Eve because each of the edges between them follows the relation route.
The data-mode extends the Node and Edge model adding four additional field
| Role | Name | Description |
|---|---|---|
| Projects | Edge | The final Edge that is transitively projected to a high-level relationship |
| Extends | Source | The Transitive Edge that has been e3xtended to provide this connection |
| Length | The shortest number of Edges that have been traversed for this view, in the example Mark -> Eve the length is 3 | |
| Width | The number of distinct routes that are summarized by this Transitive Edge |
While Length and Width are mostly anecdotal in this example, they are very useful when considering cost allocation for application usage.
Implementation
The Hiperspace architecture makes it relatively simple and extremely fast to project these transitive edges without the need to store them in an intermediate database. The Hiperspace Graph.PathFunctions.Paths() function takes the following parameters
| Parameter | Type | Description |
|---|---|---|
| root | Node, or any element that can be viewed as a Node | the topic of the search for Transitive Edges |
| route | A Route model, with rules | the Transudative Route model used to project Edges as Transitive Edges |
| length | int | The maximum number of edges to consider in the parallel search for Transitive Edges |
| targets | Set of Node TypeName | the end target types that should be returned |
Derived Edge
For family-trees, a further derivation is possible to define {Brother, Sister, Grandmother, Grandfather, Aunt, Uncle, Cousin} edges from the transitive relations for a person by examining the Transitive-Edge or Edges that are referenced by it.
| Length | Width | Edges | Name |
|---|---|---|---|
| 2 | 2 | Parent -> Child | Brother, Sister (depending on gender). Width is 2 since the routes are by Mother and Father |
| 2 | 1 | Parent -> Child | Half-Brother , Half-Sister. Width is 2 since the route is either by Mother or Father |
| 2 | Parent -> Parent | Grandmother, Grandfather | |
| 3 | Parent -> Parent -> Child | Aunt, Uncle | |
| 3 | Parent -> Child -> Child | Neice, Nephew | |
| .. | .. | .. | .. |
Family-trees normally include a line between two people for marriage, but there is not a unique phrase to describe the relationship, somewhat amusingly ChatGPT can be persuaded to hallucinate that this relationship is Bonkers.