Graph pattern matching is the task of finding all matches (occurrences) of a pattern graph P in a host graph G. Formally, the goal is to compute the set of matches given by {m: P → G | m is a graph homomorphism}. In categorical terms, this is the set Hom(P,G). If we fix the host graph G, we get the functor Hom(_,G): Graph → Set. For any pattern P, Hom(_,G) sends P to the set of matches of P in G. The functor Hom(_,G) is contravariant. Thus, embedding a pattern P in Q means the match set of Q is included in P (modulo a translation of P into Q). In other words, every match of Q in G can be translated into a match of P in G.
One view of compositionality for graph pattern matching is to decompose a pattern P into a span P2 ← P1 → P3 such that P is the pushout over this span. What does this mean for the corresponding match sets? Well, that's easy to answer now since we know we are dealing with Hom(_,G). If we look at the properties of this functor, we see that it sends colimits to limits. This means also that it maps a pushout of pattern graphs to a pullback of their corresponding match sets. Therefore, we can decompose the pattern matching task by finding the respective match sets of P1, P2 and P3 individually and composing them to the final match set Hom(P2,G) ×Hom(P1,G) Hom(P3,G). With some basic notions from category theory we achieved a quick compositionality result for graph pattern matching, neat.
What is this useful for? It can be used as a basis for operationalization and optimization of graph pattern matching. This has applications in graph databases and model transformations. For scalability of graph pattern matching w.r.t. the size of the host graph, the covariant functor Hom(P,_) is also very interesting.
The observation that a structural model (in this case pattern graphs) is related to its corresponding semantical model (in this case match sets) by a contravariant functor is not at all uncommon. Structure and semantics of behavioral models like Petri nets or Reo connectors are related in a similar way, as they form pairs of adjoint functors. This is not surprising because, as Saunders Mac Lane put it: ‘adjoint functors arise everywhere’.
