1. Motivation
Here are two equivalent categories. The first category, \mathsf{Fib} := \mathsf{Set}^{\mathsf{Arr}} (for fibered), is the category of copresheaves on the walking arrow category \mathsf{Arr} = \bullet \to \bullet. An object of this category consists of two sets and a map between them, and a morphism is a commuting square.
The second category, which I will call \mathsf{Ind} (for indexed), is the category of elements of the functor \mathsf{Set}^{-} \colon \mathsf{Set}^{\mathrm{op}} \to \mathsf{Cat}. An element of this category consists of a set X and a function F \colon X \to \mathsf{Set}, and a morphism from (X,F) to (Y,G) consists of a function h \colon X \to Y along with for every x \in X, a function \alpha_x \colon F(x) \to G(h(x)).
The equivalence between \mathsf{Fib} and \mathsf{Ind} is an example of the Grothendieck construction. In brief, we can send an object (X, F \colon X \to \mathsf{Set}) of \mathsf{Fib} to an object \pi_1 \colon \sum_{x \in X} F(x) \to X of \mathsf{Ind}, and in the reverse direction send an object f \colon Y \to X to (X, f^{-1} \colon X \to \mathsf{Set}).
However, although these are equivalent mathematically, they are not equivalent computationally. Often the indexed point of view is more natural. For instance, it is more natural to have a list of ports for each box in a wiring diagram (the indexed perspective), rather than having a global list of ports and a function from ports to boxes (the fibered perspective).
Additionally, in the indexed perspective, it is easy to change \mathsf{Ind} to the Grothendieck construction for \mathsf{Set}_{\cong}^{-} and get morphisms which have be “locally isomorphic”, i.e. \alpha_x \colon F(x) \to G(h(x)) is always an isomorphism. Analogously, we could do “locally injective”, “locally surjective”, or even more exotic things like “locally partial”, “locally relational”, or even “locally dual”, where we have the map going in the opposite direction \alpha_x \colon G(h(x)) \to F(x) (in which case we get \mathsf{Poly})!
We could even switch to a totally different category, like (\mathbb{R}, \leq). The Grothendieck construction on \mathbb{R}^{-} gives us the category of pairs (X, F \colon X \to \mathbb{R}), and morphisms (X,F) \to (Y,G) given by functions h \colon X \to Y such that F(x) \leq G(h(x)) for all x \in X.
In short, the indexed perspective is both more natural, and gives us a lot of degrees of freedom to play with.
The one current advantage that the fibered perspective has going for it is that it’s a normal C-set category, and we have an implementation in AlgebraicJulia for C-sets, but we don’t have an implementation for all of this fancy indexed stuff. So when we implement wiring diagrams, we use the fibered perspective; we have a set of all ports and then a map from ports to boxes.
In order to remedy this situation, I want to come up with a theory that lets us talk about the indexed perspective. I have a lot of other things that I need to be doing, so I’m actually hoping that someone else works out the details of this based on the sketch I give in this post, possibly @KevinArlin.
2. The story so far
I think that I can get what I want from an extension of the theory of ACSets to have category-typed attributes.
To recap briefly, the theory of ACSets is essentially the following. Going back to Functorial Data Migration it is known that you can represent databases with only foreign keys columns using C-sets, and databases with columns that have actual data in them (like strings or integers) can be represented by slice categories \mathsf{Set}^C / A, where the C-set A tells you what types are in your data columns. The difficulty with this picture is that actually writing down the C-set A can be somewhat challenging.
To see why, an example is useful. Let C be the schema for graphs, i.e. \{E,V, (\mathrm{src}, \mathrm{tgt}) \colon E \to V\}. If we want to decorate each vertex by a string, one might suppose that we would let A(V) = \mathtt{String}, A(E) = 1, because we aren’t decorating edges by anything. But the problem is that we can’t define A(\mathrm{src}) \colon 1 \to \mathtt{String}. In order to fix this, we actually need A(E) = \mathtt{String} \times \mathtt{String}, with A(\mathrm{src}) = \pi_1 and A(\mathrm{tgt}) = \pi_2.
The contribution of the ACSet paper was to come up with a simpler way of describing the data attributes of C-sets, to make what we call “attributed C-sets”.
Currently I have a way of doing “category-typed attributes” that is at the level of slice categories; it is yet an open problem to come up with convenient presentations for category-typed attributes.
The slice story for category-typed attributes is a fairly straightforward extension of the slice story for set-typed attributes. We start with a schema category C, and then we consider a functor A \colon C \to \mathsf{Cat}. We can then take the lax comma category \mathsf{Set}^C // A along the inclusion \mathsf{Set}^C \to \mathsf{Cat}^C. An object of \mathsf{Set}^C // A is a functor F \colon C \to \mathsf{Set} along with a natural transformation \alpha \colon F \to A. A morphism from (F, \alpha) to (G, \beta) is a diagram
where \aleph is a modification.
This allows morphisms to only “laxly” preserve attributes. I.e., for each c \in C, x \in F(c), there is a morphism \aleph_{c,x} \colon \alpha_c(x) \to \beta_c(\gamma_c(x)) in A(c).
To help understand this, let’s do an example.
Let C be the schema for graphs, and define A \colon C \to \mathsf{Cat} by
Just like before, A(\mathrm{src}) and A(\mathrm{tgt}) are the two obvious projections. The category structure on A(E) can be given by an appropriate Grothendieck construction.
An object of \mathsf{Set}^C // A consists of a graph where each vertex has a set of input ports and a set of output ports, and where each wire is decorated with an output port of its source, and an input port of its target. In other words, this is a wiring diagram (without boundary).
A morphism of these maps vertices to vertices and edges to edges, but does not have to preserve the sets of input and output ports. Rather, if v \mapsto v', then we get a function from the input ports of v to the input ports of v', and so on.
We then can require that this function is a bijection by making A(V) = \mathsf{Set}_{\cong}^{\{I,O\}}, and so on.
What remains to be done is to come up with a way of writing down the schema for one of these things in a more convenient way than specifying A manually, just as we have a profunctor schema for ACSets. As the profunctor schema for ACSets involved double categories, this likely involves some kind of 3-category, which scares me a little bit…
I’m going to conclude by mentioning something that I noticed which might help the process of defining finite presentations for these things. The category A(E) that we defined earlier is the Grothendieck construction of a representable functor out of \Set^{\{I,O\} + \{I,O\}}. So categories that are given by Grothendieck constructions of representable functors out of C-set categories might be relevant.