Graph Bisimulation
Graph Bisimulation is the important topic of the Web Data Management. Moreover, freestudy9 has all kind of important information and topic related to it.
 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 selfloop.
 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’.
Related Terms
Web Data Management, XLink Example, XPointer with Example, DTD
Leave a Reply