- A typing of a graph may be seen in some sense as a classification of its nodes, with nodes in a class sharing the same properties.
- Such a property is that they “point to” (or are “pointed by”) nodes in particular classes.
For instance, consider Figure.
- A set of nodes forms the class employee. From an employee node, one can follow works on, leads and possibly consults edges to some nodes that form the class project.
- This is the basis for typing schemes for graph data based on “simulation” and “bisimulation”.
- A simulation S of (E, r) with (E’, r’) is a relation between the nodes of E and E’ such that:
- S(r, r’) and
- if S(s, s’) and E(s, t, l) for some s, s’, t, l, then there exists t’ with S(t, t’) and E’(s’, t’, l’).
- The intuition is that we can simulate moves in E by moves in E’.
- Given (E, r), (E’, r’), S is a bisimulation if S is a simulation of E with E’ and S-1 is a simulation of E’ with E.
- To further see how this relates to typing, take a very complex graph E.
- We can describe it with a “smaller” graph E’ that is a bisimulation of E.
- There may be several bisimulations for E including more and more details.
- At one extreme, we have the graph consisting of a single node with a self-loop.
- At the other extreme, we have the graph E itself.
- This smaller graph E’ can consider as a type for the original graph E. In general, we say that some graph E has type E’ if there is a bisimulation of E and E’.