Skip to content

AlgebraicJulia/ACSets.jl

Repository files navigation

ACSets.jl

Stable Documentation Development Documentation Code Coverage CI/CD

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.

Learning

Graphs, and their generalization as C-sets, are introduced with minimal prerequisites in a series of blog posts on the AlgebraicJulia blog:

  1. Graphs and C-sets I: What is a graph?
  2. Graphs and C-sets II: Half-edges and rotation systems
  3. Graphs and C-sets III: Reflexive graphs and C-set homomorphisms
  4. 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.

Citation

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.