Acsets ("attributed C-sets") are a family of data structures generalizing both graphs and data frames. They are an efficient in-memory implementation of a category-theoretic formalism for relational databases.
This lightweight package provides
- data structures for acset schemas, acsets, and tabular columns
- serialization of acset schemas and acsets
Catlab.jl extends this package to offer many more features, beginning with homomorphisms between acsets and including limits and colimits of acsets, functorial data migration, and automated homomorphism finding. AlgebraicRewriting.jl goes further still to provide declarative rewriting for acsets.
Graphs, and their generalization as C-sets, are introduced with minimal prerequisites in a series of blog posts on the AlgebraicJulia blog:
- Graphs and C-sets I: What is a graph?
- Graphs and C-sets II: Half-edges and rotation systems
- Graphs and C-sets III: Reflexive graphs and C-set homomorphisms
- Graphs and C-sets IV: The propositional logic of subgraphs and sub-C-sets
These blog posts use Catlab.jl in addition to ACSets.jl.
The ideas behind this package are described in the paper:
Patterson, Lynch, Fairbanks. Categorical data structures for technical computing. Compositionality 4, 5 (2022). arXiv:2106.04703. DOI:10.32408/compositionality-4-5.