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

**P**such that

_{2}← P_{1}→ P_{3}**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

**P**,

_{1}**P**and

_{2}**P**individually and composing them to the final match set

_{3}**Hom(P**. With some basic notions from category theory we achieved a quick compositionality result for graph pattern matching, neat.

_{2},G) ×_{Hom(P1,G)}Hom(P_{3},G)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 puts it:

*‘adjoint functors arise everywhere’*.