acsets-algebraic-databases

# ACSets: Algebraic Databases Skill > *"The category of simple graphs does not even have a terminal object!"* > — AlgebraicJulia Blog, with characteristic ironic detachment ## bmorphism Contributions > *"Parametrised optics model cybernetic systems, namely dynamical systems steered by one or more agents. Then ⊛ represents agency being exerted on systems"* > — [@bmorphism](https://github.com/bmorphism), GitHub bio > *"universal topos construction for social cognition and democratization of mathematical approach to problem-solving to all"* > — [Plurigrid: the story thus far](https://gist.github.com/bmorphism/a400e174b9f93db299558a6986be0310) **Related repos**: - [plurigrid/act](https://github.com/plurigrid/act) - "building blocks for cognitive category theory" (active inference + ACT + enacted cognition) - [bmorphism/awesome-applied-category-theory](https://github.com/bmorphism/awesome-applied-category-theory) - ACT community resources ## 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 ```julia 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) ```julia @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) ```julia @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: ```julia # 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 ```julia 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)** ```julia 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)** ```julia 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 ```julia # 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 ```julia 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 ```julia 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"** ```julia # 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 ```julia 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 ```julia 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] ``` ### Cross-Domain Bridge (Sexp ↔ ACSet) ```julia # 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) { |v| degree(g,v) > 2 }` | | `fold` | Aggregate over parts | `fold(+, g, :E, :weight)` | ## Open ACSets (Composable Interfaces) ```julia # 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 ```julia 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: ```julia @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) ```julia