## 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.