ACSets: Algebraic Databases Skill

"The category of simple graphs does not even have a terminal object!" — AlgebraicJulia Blog, with characteristic ironic detachment

What Are ACSets?

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.

C-set = Functor X: C → Set where C is a small category (schema)

┌─────────────────────────────────────────────────────────────┐
│  Schema (Small Category C)                                  │
│  ┌─────┐  src   ┌─────┐                                     │
│  │  E  │───────▶│  V  │                                     │
│  │     │  tgt   │     │                                     │
│  └──┬──┘───────▶└─────┘                                     │
│     │                                                       │
│     │ A C-set X assigns:                                    │
│     │   X(V) = set of vertices                              │
│     │   X(E) = set of edges                                 │
│     │   X(src): X(E) → X(V)                                 │
│     │   X(tgt): X(E) → X(V)                                 │
└─────────────────────────────────────────────────────────────┘

Core Concepts

1. Schema Definition

using Catlab.CategoricalAlgebra

@present SchGraph(FreeSchema) begin
  V::Ob
  E::Ob
  src::Hom(E,V)
  tgt::Hom(E,V)
end

@acset_type Graph(SchGraph, index=[:src,:tgt])

2. Symmetric Graphs (Undirected)

@present SchSymmetricGraph <: SchGraph begin
  inv::Hom(E,E)

  compose(inv,src) == tgt
  compose(inv,tgt) == src
  compose(inv,inv) == id(E)
end

@acset_type SymmetricGraph(SchSymmetricGraph, index=[:src])

3. Attributed ACSets (with Data)

@present SchWeightedGraph <: SchGraph begin
  Weight::AttrType
  weight::Attr(E, Weight)
end

@acset_type WeightedGraph(SchWeightedGraph, index=[:src,:tgt]){Float64}

GF(3) Conservation for ACSets

Integrate with Music Topos 3-coloring:

# Map ACSet parts to trits for GF(3) conservation
function acset_to_trits(g::Graph, seed::UInt64)
    rng = SplitMix64(seed)
    trits = Int[]
    for e in parts(g, :E)
        h = next_u64!(rng)
        hue = (h >> 16 & 0xffff) / 65535.0 * 360
        trit = hue < 60 || hue >= 300 ? 1 :
               hue < 180 ? 0 : -1
        push!(trits, trit)
    end
    trits
end

# Verify conservation: sum(trits) ≡ 0 (mod 3)
function gf3_conserved(trits)
    sum(trits) % 3 == 0
end

Gay.jl Color Bindings for @acset_colim (PR #990)

Since Catlab PR #990, @acset_colim exposes name→part bindings. Combine with Gay.jl for:

Named Part Coloring

using Gay

# Build ACSet with named parts
result, bindings = @acset_colim SchGraph begin
  e::E
  v1::V; v2::V
  src(e) == v1
  tgt(e) == v2
end

# Color each named part deterministically
seed = 0x114514
colors = Dict{Symbol, String}()
for (name, (ob, idx)) in bindings
    colors[name] = Gay.color_at(seed, idx)  # deterministic hex
end
# => Dict(:e => "#A855F7", :v1 => "#3B82F6", :v2 => "#10B981")

Two Modalities for XOR Validation

Modality 1: Different seeds (parallel verification)

seeds = [0x1, 0x2, 0x3]  # Three independent streams
colors_per_seed = [Gay.palette(s, length(bindings)) for s in seeds]

# XOR guarantee: if all three agree on structure, computation is stable
# Divergence → indicates floating-point or algorithmic instability

Modality 2: Same seed, staggered indices (convergence test)

seed = 0x114514

# Run same computation 3 times, color at indices 1, 2, 3
c1 = compute_and_color(data, seed, index=1)
c2 = compute_and_color(data, seed, index=2)
c3 = compute_and_color(data, seed, index=3)

# Convergence: c1 == c2 == c3 within bounded iterations → stable
# Divergence: colors differ → numerical instability detected automatically

Empty Block = Initial Object = Neutral Color

# Empty block produces initial object (fixed in PR #990)
init, _ = @acset_colim SchGraph begin end  # ∅

# Initial object gets neutral/zero color (the "0" in GF(3))
neutral_color = Gay.color_at(seed, 0)  # or special "initial" marker

Bidirectional Index with Color Tags

struct ColoredACSet{T}
    acset::T
    bindings::Dict{Symbol, Tuple{Symbol, Int}}
    colors::Dict{Symbol, String}
    seed::UInt64
end

function colored_acset_colim(schema, seed, block)
    acset, bindings = @acset_colim schema block
    colors = Dict(name => Gay.color_at(seed, idx)
                  for (name, (_, idx)) in bindings)
    ColoredACSet(acset, bindings, colors, seed)
end

# Lookup by name → part index → color (all directions)
# name → color: ca.colors[:v1]
# color → name: findfirst(==(hex), ca.colors)
# name → part: ca.bindings[:v1][2]

Instability Detection Pattern

function detect_instability(f, input, seed; tolerance=3)
    """
    Run f three times with same seed at staggered indices.
    If colors diverge beyond tolerance, flag instability.
    """
    results = [f(input) for _ in 1:3]
    colors = [Gay.color_at(seed, i) for i in 1:3]

    # Compare results - if they should be identical but aren't,
    # the divergent colors make the instability visually obvious
    for i in 1:3, j in i+1:3
        if results[i] ≠ results[j]
            @warn "Instability detected" color_i=colors[i] color_j=colors[j]
            return false
        end
    end
    true
end

This integrates the semantic naming from PR #990 with Gay.jl's deterministic coloring to create self-validating, visually debuggable ACSet constructions.

Specter-Style Bidirectional Navigation

Inspired by Nathan Marz's Specter library, navigate ACSets with paths that work for both select AND transform.

The Key Insight: comp-navs = alloc + field sets

From Marz: "comp-navs is fast because it's just object allocation + field sets"

# What comp_navs actually does:
comp_navs(a, b, c) = ComposedNav([a, b, c])  # That's it!
# No compilation, no interpretation, no optimization
# Just: allocate struct, set field, done

# All work happens at traversal via CPS:
nav_select(nav1, data,
    r1 -> nav_select(nav2, r1,
        r2 -> nav_select(nav3, r2, identity)))

This means:

• O(1) composition - constant time path building
• Inline caching - paths compiled once per callsite
• Near-hand-written speed - CPS eliminates intermediate allocations

ACSet Navigators

using SpecterACSet

# Navigate morphism values
acset_field(:E, :src)         # All source vertex IDs
acset_field(:E, :tgt)         # All target vertex IDs

# Filter parts by predicate
acset_where(:E, :src, ==(1))  # Edges where src == 1

# Navigate all parts of an object
acset_parts(:V)               # All vertex IDs
acset_parts(:E)               # All edge IDs

Bidirectional Example

g = @acset Graph begin V=4; E=3; src=[1,2,3]; tgt=[2,3,4] end

# Select: get all source vertices
select([acset_field(:E, :src)], g)  # → [1, 2, 3]

# Transform: shift all targets (same path!)
g2 = transform([acset_field(:E, :tgt)], t -> mod1(t+1, 4), g)
select([acset_field(:E, :tgt)], g2)  # → [3, 4, 1]

Integration with ∫G (Category of Elements)

Navigate the category of elements using paths:

# ∫G objects: (Ob, part_id) pairs
# Navigate to all elements
select([elements_of(:V)], g)  # → [(V,1), (V,2), (V,3), (V,4)]

# Navigate morphism structure
select([elements_of(:E), incident_to(:src, 1)], g)  # Edges from vertex 1

Cross-Domain Bridge (Sexp ↔ ACSet)

# ACSet → Sexp → Navigate → Transform → Sexp → ACSet
sexp = sexp_of_acset(g)

# Navigate sexp to find all morphism names
morphism_names = select([SEXP_CHILDREN, sexp_nth(1), ATOM_VALUE], sexp)

# Roundtrip back to ACSet
g2 = acset_of_sexp(Graph, sexp)

Higher-Order Functions on ACSets

From Issue #7, implement functional patterns:

Function	Description	Example
map	Transform parts	map(g, :E) do e; ... end
filter	Select parts by predicate	`filter(g, :V) {
fold	Aggregate over parts	fold(+, g, :E, :weight)

Open ACSets (Composable Interfaces)

# From Issue #89: Open versions of InterType ACSets
using ACSets.OpenACSetTypes

# Create open ACSet with exposed ports
@open_acset_type OpenGraph(SchGraph, [:V])

# Compose via pushout
g1 = OpenGraph(...)  # ports: v1, v2
g2 = OpenGraph(...)  # ports: v3, v4
g_composed = compose(g1, g2, [:v2 => :v3])

Why Simple Graphs Are Badly Behaved

The category of simple graphs does not even have a terminal object. Under the standard definition (symmetric, irreflexive edge relation), there's no "universal" graph that every other graph maps to uniquely. This reveals hidden assumptions in the simple graph model.

Simple graph: G = (V, E) where E is a binary relation on V that is:

• Symmetric: E(v,u) whenever E(u,v)
• Irreflexive: E(v,v) for no vertex v

Category theorist's graph: G consists of:

• Vertex set G(V)
• Edge set G(E)
• Functions G(src), G(tgt): G(E) → G(V)

This allows:

• Multiple edges between vertices (multigraph)
• Self-loops
• Edges as first-class citizens with identity

C-Sets: The Mathematical Foundation

A C-set is a functor X: C → Set where C is a small category (schema).

Schema C (small category)     C-set X (functor C → Set)
──────────────────────────    ─────────────────────────
Objects c ∈ C          ────▶  Sets X(c)
Morphisms f: c → d     ────▶  Functions X(f): X(c) → X(d)

Terminology

Term	Definition
C-set	Functor C → Set (copresheaf)
Presheaf	Functor C^op → Set (contravariant)
Category action	C-set generalizes G-set (group action)

The Schema for Graphs

The schema Sch(Graph) is the category with:

• Two objects: E, V
• Two non-identity morphisms: src: E → V, tgt: E → V

    ┌───┐  src   ┌───┐
    │ E │───────▶│ V │
    │   │  tgt   │   │
    └───┘───────▶└───┘

A graph G is a Sch(Graph)-set, meaning:

• G(V) = set of vertices
• G(E) = set of edges
• G(src): G(E) → G(V) assigns source vertex to each edge
• G(tgt): G(E) → G(V) assigns target vertex to each edge

Creating Graphs in Catlab

using Catlab.CategoricalAlgebra
using Catlab.Graphs, Catlab.Graphics

# Create empty graph and add parts
g = Graph()
add_parts!(g, :V, 3)
add_parts!(g, :E, 4, src=[1,2,2,3], tgt=[2,3,3,3])

# Query incident edges (uses index)
incident(g, 3, :tgt)  # => [2, 3, 4]

# Graphs.jl-style convenience interface
g2 = Graph()
add_vertices!(g2, 3)
add_edges!(g2, [1,2,2,3], [2,3,3,3])

# Visualization
to_graphviz(g, node_labels=true, edge_labels=true)

Indexing for Efficient Queries

The index=[:src,:tgt] parameter creates inverse lookups:

@acset_type Graph(SchGraph, index=[:src,:tgt])

# Without index: O(|E|) to find edges incident to vertex
# With index: O(k) where k = number of incident edges

Symmetric Graphs (Undirected)

The schema for symmetric graphs extends the graph schema with an involution:

    ┌───┐  src   ┌───┐
    │ E │───────▶│ V │
    │   │  tgt   │   │
    │   │───────▶│   │
    │   │  inv   │   │
    │   │◀──────▶│   │
    └───┘        └───┘

Subject to equations:

inv ⨟ src = tgt
inv ⨟ tgt = src
inv² = id_E

Meaning of Equations

For every edge e ∈ G(E):

• e.inv.src = e.tgt (inverted edge starts where original ends)
• e.inv.tgt = e.src (inverted edge ends where original starts)
• e.inv.inv = e (involution is self-inverse)

@present SchSymmetricGraph <: SchGraph begin
  inv::Hom(E,E)

  compose(inv,src) == tgt
  compose(inv,tgt) == src
  compose(inv,inv) == id(E)
end

@acset_type SymmetricGraph(SchSymmetricGraph, index=[:src])

# Create symmetric 4-cycle
g = SymmetricGraph()
add_vertices!(g, 4)
add_edges!(g, [1,2,3,4], [2,3,4,1])
# Creates 8 edges: 4 original + 4 inverses

Indexing Optimization

Only src needs indexing. Target queries use: incident(g, v, :tgt) = incident(g, v, :src) .|> (e -> g[e, :inv])

Blog Post Series

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: Propositional logic of subgraphs

Half-Edge Graphs (Blog II)

Half-edges are paired by involution rather than having distinct source/target:

Schema Sch(HGraph):
    ┌───┐  vertex  ┌───┐
    │ H │─────────▶│ V │
    │   │   inv    │   │
    │   │◀────────▶│   │
    └───┘          └───┘

Equation: inv² = id_H

@present SchHalfEdgeGraph(FreeSchema) begin
  V::Ob
  H::Ob
  vertex::Hom(H,V)
  inv::Hom(H,H)

  compose(inv, inv) == id(H)
end

@acset_type HalfEdgeGraph(SchHalfEdgeGraph, index=[:vertex])

Dangling Edges

Fixed points h·inv = h are dangling edges — half-edges not paired with others, left at the boundary. Distinct half-edges h ≠ h' with h·inv = h' and same vertex are self-loops.

g = HalfEdgeGraph(3)
add_edges!(g, [1,2,3], [2,3,1])      # 6 paired half-edges
add_dangling_edges!(g, [1,1,3])      # 3 dangling half-edges (fixed points)

Schema Isomorphism: Symmetric ≅ Half-Edge

Functor F: Sch(SGraph) → Sch(HGraph):

V ↦ V
E ↦ H
src ↦ vertex
tgt ↦ inv ⨟ vertex
inv ↦ inv

This is an isomorphism (invertible). The two perspectives are mathematically equivalent but have different interpretations.

Rotation Systems (Topological Graph Theory)

A rotation system adds a permutation σ on half-edges where cycles = vertices:

@present SchRotationGraph <: SchHalfEdgeGraph begin
  σ::Hom(H,H)
  compose(σ, vertex) == vertex  # cycles stay at same vertex
end

The schema Sch(RotSys) with just H, α (involution), σ (permutation) is a group — making rotation systems group actions.

Key theorem: Rotation systems ↔ cellular embeddings in oriented surfaces (1-1 correspondence).

Reflexive Graphs (Blog III)

A reflexive graph has a distinguished self-loop at each vertex:

    ┌───┐  src   ┌───┐  refl
    │ E │───────▶│ V │───────▶│ E │
    │   │  tgt   │   │
    └───┘───────▶└───┘

Equations:
  refl ⨟ src = id_V
  refl ⨟ tgt = id_V

@present SchReflexiveGraph <: SchGraph begin
  refl::Hom(V,E)

  compose(refl, src) == id(V)
  compose(refl, tgt) == id(V)
end

C-Set Homomorphisms

A homomorphism α: X → Y of C-sets is a natural transformation:

For each object c ∈ C: function α_c: X(c) → Y(c)
For each morphism f: c → d: naturality square commutes

    X(c) ──α_c──▶ Y(c)
      │             │
   X(f)           Y(f)
      ▼             ▼
    X(d) ──α_d──▶ Y(d)

Graph homomorphism: vertex map + edge map preserving src/tgt.

Reflexive graph homomorphism: additionally preserves refl, so can "collapse" edges onto reflexive loops — enables quotient operations.

Products of Graphs

Products computed pointwise: (G × H)(c) = G(c) × H(c)

Type	Product Name	Behavior
Graph	Categorical product	Disconnected diagonal paths
ReflexiveGraph	Categorical product	Grid with connections (reflexive loops fill gaps)
SymmetricGraph	Direct/tensor product	May split into components (bipartite → 2 components)
SymmetricReflexiveGraph	Strong product	Full grid connectivity

Box product (graph theorist's "Cartesian product"): Pushout construction

function box_product(g::T, h::T)
  g₀, h₀ = T(nv(g)), T(nv(h))  # discrete subgraphs
  # ... pushout of inclusions with product projections
end

Terminal Objects and Generalized Elements

Terminal graph = self-loop.

• Graph without self-loops: no generalized elements (no morphisms from terminal)
• Reflexive graph: generalized elements = vertices (expected behavior)

This makes reflexive graphs more "geometric" — they discretize continuous spaces properly.

Propositional Logic of Subgraphs (Blog IV)

Sub-C-sets as propositions, logical connectives derived from adjoints.

Logical Connectives as Adjoints

Connective	Definition	Meaning
A ∧ B	Right adjoint of Δ	Greatest lower bound (meet)
A ∨ B	Left adjoint of Δ	Least upper bound (join)
⊤	Right adjoint of !	Top element (full subgraph)
⊥	Left adjoint of !	Bottom element (empty)
B ⇒ C	Right adjoint of (−) ∧ B	Implication (exponential)
¬A	A ⇒ ⊥	Negation (Heyting)

Two Types of Negation

¬A (not-A, conservative): x ∈ ¬A iff no element reachable from x is in A

x ∈ (¬A)(c) iff x·f ∉ A(c') for ALL f: c → c' in C

~A (non-A, liberal complement): x ∈ ~A iff some element reaching x is not in A

x ∈ (~A)(c) iff x' ∉ A(c') for SOME f: c' → c and x' ∈ f⁻¹·x

Always: ¬A ≤ ~A (negation ⊆ complement)

Boundary, Expansion, Contraction

Operation	Formula	For Graphs
Boundary	∂A = A ∧ ~A	Vertices in A connected to outside
Induced	¬¬A	Same vertices, all edges between them
Expansion	~¬A	A plus one layer outward
Contraction	¬~A	A minus one layer inward

Law of Excluded Middle

A ∨ ¬A = ⊤ holds iff graph is discrete (no edges).

For connected graphs: excluded middle fails. This isn't a bug — it's topology speaking through logic.

Devil's Avocado Synthesis (GF(3) Review)

−1 Critique (Negative)

• Missing complexity analysis: Subobject lattices can explode combinatorially
• Schema isomorphism "≅" underspecified: Equivalence vs strict isomorphism matters for implementation
• Rotation → surfaces jump too fast: Hides Edmonds algorithm, genus, non-orientable cases
• Dangling edges unmotivated: Application to open systems/composition unstated
• Products need worked examples: Claims without small computations leave readers unable to verify
• Subobject logic assumes topos background: "Adjoints give connectives" requires Lawvere familiarity
• ¬ vs ~ notation collision: Conflicts with standard pseudocomplement usage
• No connection to ACSets.jl code: Gap between categorical exposition and macros

+1 Appreciation (Positive)

• Schema isomorphism reveals deep identity: Source-target graphs = half-edge graphs in different clothes
• Rotation systems as groups: Invertibility + algebraic topology without coordinates
• Dangling edges model open systems: Boundary conditions, interfaces solved structurally
• Reflexive homomorphisms = quotients done right: Contraction/abstraction as natural transformations
• Two negations unify constructive/classical: Failure of excluded middle is topology through logic
• ∂A = A ∧ ~A: Boundary operator derived from pure logic (Stokes theorem intuition)
• Product proliferation is a feature: Each schema choice gives different tensor product

0 Neutral Integration

The skill presents the neutral synthesis: rigorous definitions with practical Catlab code, acknowledging both the elegant mathematical structure and the implementation gaps.

Key References

• Reyes, Reyes & Zolfaghari (2004): Generic Figures and Their Glueings — C-sets as category actions
• Spivak (2009): Higher-Dimensional Models of Networks — C-sets for scientific modeling
• Lando & Zvonkin (2004): Graphs on Surfaces — Rotation systems, σ/α notation
• Gross & Tucker (1987): Topological Graph Theory — Cellular embeddings theorem
• Hell & Nešetřil (2004): Graphs and Homomorphisms — Nonexpansive maps, reflexive graphs
• Lawvere (1986): Categories of Spaces — Topos-theoretic perspective on reflexive graphs
• Hammack, Imrich & Klavžar (2011): Handbook of Product Graphs — Product taxonomy

Citation

@article{patterson2022categorical,
  title={Categorical data structures for technical computing},
  author={Patterson, Evan and Lynch, Owen and Fairbanks, James},
  journal={Compositionality},
  volume={4},
  number={5},
  year={2022},
  doi={10.32408/compositionality-4-5}
}

GeoACSets: Spatial + Categorical

GeoACSets.jl combines ACSets with geospatial capabilities:

Use morphisms for structural navigation, geometry for filtering.

Operation	Complexity	When to Use
Morphism traversal	O(k)	Hierarchical containment
Spatial join	O(n log n)	Ad-hoc proximity queries

SpatialCity Schema

# 4-level hierarchy: Region → District → Parcel → Building
@present SchSpatialCity(FreeSchema) begin
    Region::Ob
    District::Ob
    Parcel::Ob
    Building::Ob

    district_of::Hom(District, Region)
    parcel_of::Hom(Parcel, District)
    building_on::Hom(Building, Parcel)

    GeomType::AttrType
    region_geom::Attr(Region, GeomType)
    footprint::Attr(Building, GeomType)
end

@acset_type SpatialCity(SchSpatialCity,
    index=[:district_of, :parcel_of, :building_on])

Traversal Patterns

# Downward: O(depth) via incident queries
buildings_in_region(city, region_id)

# Upward: O(1) via subpart lookups
region_of_building(city, building_id)

# Combine spatial + morphism
nearby = spatial_filter(city, :Building, :footprint,
    g -> LibGEOS.distance(g, query_point) < 100)
for b in nearby
    district = traverse_up(city, b, :building_on, :parcel_of)
end

OlmoEarth/Terra Extension (Spatio-Temporal)

GeoACSets needs extension for foundation model integration:

SchOlmoEarthPatch

@present SchOlmoEarthPatch(FreeSchema) begin
    Patch::Ob           # Variable-size spatial patch
    Timestep::Ob        # Monthly temporal unit
    Modality::Ob        # Sentinel-1/2, Landsat, Maps
    Token::Ob           # Encoded representation
    View::Ob            # For instance contrastive

    patch_timestep::Hom(Patch, Timestep)
    patch_modality::Hom(Patch, Modality)
    token_patch::Hom(Token, Patch)

    # Masking as structured decomposition
    MaskedPatch::Ob
    MaskConfig::Ob
    masked_patch::Hom(MaskedPatch, Patch)
    mask_state::Attr(MaskedPatch, MaskStateType)  # encode/decode/both/none
end

Masking as Span Decomposition

# OlmoEarth masking creates:
#   EncodeBag ← Apex (both) → DecodeBag

function create_masking_decomposition(patches, config_id)
    encode_bag = filter(p -> mask_state(p) ∈ [:encode_only, :both], patches)
    decode_bag = filter(p -> mask_state(p) ∈ [:decode_only, :both], patches)
    apex = filter(p -> mask_state(p) == :both, patches)
    (encode_bag, apex, decode_bag)
end

Instance Contrastive as Sheaf Condition

# Two views must agree on pooled representation
function verify_sheaf_condition(patches; threshold=0.99)
    pooled1 = patches[view1, :pooled_repr]
    pooled2 = patches[view2, :pooled_repr]
    cosine_sim(pooled1, pooled2) >= threshold
end

Gay.jl Label Ontology for ACSets

Gay.jl uses a categorical label system on GitHub issues. These map directly to ACSet concepts:

Ternary Trit Labels (GF(3) Colors)

Label	Color	Description
ternary:+	#286e49	Positive trit [+1]
ternary:0	#4a9235	Zero trit [0]
ternary:-	#28a628	Negative trit [-1]

ACSet-Specific Labels

Label	Color	Description
acset:rewriting	#5dda92	ACSet local rewriting gadgets
acset:adhesion	#d15252	Structured decomposition adhesions

Sheaf Condition Labels