Why do the composition of relations and the matrix product look so alike? For reference:

Matrix product:
$A : X\times Y \rightarrow R$
$B : Y\times Z \rightarrow R$
$AB := (x,z) \mapsto \int_{y\in Y} A(x,y)B(y,z) d\mu : X\times Z \rightarrow R$
To make the pattern clearer I generalized matrices $A$ and $B$ over any (semi-)ring $R$ to have indices ranging over arbitrary sets instead of just finite ones. In this case we need to give $Y$ a measure. What you get is the $L^2$ inner product.

Relation composition:
$S \subseteq X\times Y$
$T \subseteq Y\times Z$
$S \circ T := \{(x,z)\ |\ \exists y \in Y.\ (x,y) \in S\ \land\ (y,z) \in T\} \subseteq X\times Z$

Thinking in terms of monoids might be an easy way out, but we are losing a lot of structure doing that and I believe that if there's anything deep going on here, it lies in the $\ \exists \leftrightarrow \int\ $, $\ \land \leftrightarrow \cdot\ $ connection.
What is the thing that generalizes both of these? What is going on here?
Thanks in advance!
 A: Composition can be written this way in any rigid monoidal category. It would take awhile to spell out all the axioms (see the link for details) but basically this is a generalization of the structure that the category of finite-dimensional vector spaces possesses by virtue of having both a tensor product $\otimes$ and a dualization $V \mapsto V^{\ast}$, which also applies to the category of sets and relations (and various generalizations of this). The axioms produce for any pair of objects $V, W$ an object $[V, W] = V^{\ast} \otimes W$ whose "underlying set"
$$\text{Hom}(1, [V, W]) \cong \text{Hom}(V, W)$$
can be identified with the set of morphisms $V \to W$; this is the internal hom. Here $1$ is the unit of the tensor product. Composition can then be lifted to internal homs as a certain collection of morphisms
$$\circ : \text{Hom}(U, V) \otimes \text{Hom}(V, W) \to \text{Hom}(U, W)$$
which can be defined by writing the LHS as $U^{\ast} \otimes V \otimes V^{\ast} \otimes W$ and then applying a map $\text{ev} : V \otimes V^{\ast} \to 1$ which generalizes the trace. It is a pleasant exercise to verify that this produces the trace formula for matrix multiplication as a special case, as well as the formula you give for composition of relations.
For a nice diagrammatic introduction to these ideas you can check out my old posts Introduction to string diagrams and String diagrams, duality, and trace.
A: After being given a hint, I'm gonna give myself a different and very simple answer here.
The idea is to think of a relation $S \subseteq X\times Y$ as a function $S : X\times Y\rightarrow 2$, and pick our semi-ring $R$ to be $(2,\vee,\wedge) = (2,\max,\min)$.
We can take $\mu : Y \rightarrow 2$ to be just constant $1$ for nonempty measurable sets.
Then
$$\int_{y\in Y} S(x,y)\wedge T(y,z) d\mu
= \int_{y\in Y'}S(x,y)\wedge T(y,z) d\mu
$$
where $Y'$ is the subset of $Y$ where $S(x,y)\wedge T(y,z) = 1$.

I hope it's clear with that, but just in case I'm going to give a silly example with finite sets to make it visual.
Say we have the relations (as matrices):
$S:=\left(\begin{matrix}
1 & 0 & 0 \\
1 & 0 & 0 \\
0 & 1 & 0
\end{matrix}\right)$
and
$T:=\left(\begin{matrix}
0 & 1 & 0 \\
0 & 1 & 0 \\
0 & 1 & 1
\end{matrix}\right)$.
Then doing the matrix product substituting $+$ with $\max$ and $\cdot$ with $\min$ we have
$$ST = 
\left(\begin{matrix}
0 & 1\wedge1\ \vee\ 0\wedge1\ \vee\ 0\wedge1 & 0 \\
0 & 1\wedge1\ \vee\ 0\wedge1\ \vee\ 0\wedge1 & 0 \\
0 & 0\wedge1\ \vee\ 1\wedge1\ \vee\ 0\wedge1 & 0
\end{matrix}\right)
=
\left(\begin{matrix}
0 & 1 & 0 \\
0 & 1 & 0 \\
0 & 1 & 0
\end{matrix}\right)$$
Cheers!
