--- name: acsets-relational-thinking description: ACSets (Attributed C-Sets) for categorical database design and DPO rewriting version: 1.0.0 --- # SKILL: ACSets Relational Thinking **Version**: 2.0.0 **Trit**: 0 (ERGODIC) **Domain**: database, category-theory, rewriting **Source**: Topos Institute RelationalThinking Course + AlgebraicJulia --- ## Overview ACSets (Attributed C-Sets) are **functors X: C → Set** where C is a small category (schema). This skill integrates: 1. **RelationalThinking Course** - Topos Institute's pedagogical approach 2. **DPO Rewriting** - Double Pushout graph transformation 3. **Self-Play Loop** - Query → Execute → Evaluate → Refine 4. **GF(3) Conservation** - Triadic skill composition --- ## Core Concept: C-Set as Functor ``` Schema (Category C) Instance (Functor X: C → Set) ┌─────────────────┐ ┌─────────────────────────────┐ │ E ──src──→ V │ X │ X(E) = {e1, e2, e3} │ │ ←──tgt── │ ───→ │ X(V) = {v1, v2} │ └─────────────────┘ │ X(src): e1↦v1, e2↦v1, e3↦v2│ │ X(tgt): e1↦v2, e2↦v2, e3↦v1│ └─────────────────────────────┘ ``` --- ## Schema Definition ### Basic Graph Schema ```julia using Catlab.CategoricalAlgebra @present SchGraph(FreeSchema) begin V::Ob # Vertices (object) E::Ob # Edges (object) src::Hom(E, V) # Source morphism tgt::Hom(E, V) # Target morphism end @acset_type Graph(SchGraph, index=[:src, :tgt]) ``` ### Entity-Subtype Hierarchy (from RelationalThinking Ch8) ```julia @present SchKitchen(FreeSchema) begin Entity::Ob Food::Ob food_in_on::Hom(Food, Entity) food_is_entity::Hom(Food, Entity) Kitchenware::Ob ware_in_on::Hom(Kitchenware, Entity) ware_is_entity::Hom(Kitchenware, Entity) BreadLoaf::Ob bread_loaf_is_food::Hom(BreadLoaf, Food) Knife::Ob knife_is_ware::Hom(Knife, Kitchenware) end @acset_type Kitchen(SchKitchen) ``` --- ## DPO Rewriting (Double Pushout) ### The Pattern: L ← K → R ``` L ←──l── K ──r──→ R │ │ │ match│ │ │ ↓ ↓ ↓ G ←───── D ──────→ H pushout pushout complement ``` - **L** = Find (what to match) - **K** = Keep (overlap preserved) - **R** = Replace (new structure) - **G** = Host graph - **H** = Result graph ### Rule Definition ```julia using AlgebraicRewriting # Slice bread rule: adds BreadSlice when knife + loaf present slice_bread = @migration(SchKitchen, begin L => @join begin loaf::BreadLoaf knife::Knife end R => @join begin loaf::BreadLoaf slice::BreadSlice food_in_on(bread_slice_is_food(slice)) == food_in_on(bread_loaf_is_food(loaf)) knife::Knife end K => @join begin loaf::BreadLoaf knife::Knife end end) rule = make_rule(slice_bread, yKitchen) ``` ### Apply Rewrite ```julia matches = get_matches(rule, state) new_state = rewrite_match(rule, matches[1]) ``` --- ## Self-Play Loop The ACSet self-refinement monad: ``` Query₀ → Execute → Evaluate → Mine Patterns → Refine → Query₁ → ... ``` ### Implementation ```julia struct SelfRefinementLoop schema::Presentation state::ACSet patterns::Vector{Pattern} generation::Int end function step!(loop::SelfRefinementLoop, rule::Rule) # Find matches matches = get_matches(rule, loop.state) # Evaluate each match evaluations = [evaluate_match(m, loop.patterns) for m in matches] # Mine new patterns from successful evaluations new_patterns = mine_patterns(evaluations) append!(loop.patterns, new_patterns) # Apply best match best = argmax(e -> e.score, evaluations) loop.state = rewrite_match(rule, matches[best.index]) loop.generation += 1 loop end ``` ### Convergence Criterion ```julia function converged(loop::SelfRefinementLoop; threshold=0.95) recent = loop.patterns[end-10:end] stability = std([p.score for p in recent]) stability < (1 - threshold) end ``` --- ## GF(3) Integration ### Trit Assignment ```julia 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 # Conservation check gf3_conserved(trits) = sum(trits) % 3 == 0 ``` ### Synergistic Triads Containing ACSets ``` clj-kondo-3color (-1) ⊗ acsets (0) ⊗ rama-gay-clojure (+1) = 0 ✓ three-match (-1) ⊗ acsets (0) ⊗ gay-mcp (+1) = 0 ✓ slime-lisp (-1) ⊗ acsets (0) ⊗ cider-clojure (+1) = 0 ✓ hatchery-papers (-1) ⊗ acsets (0) ⊗ frontend-design (+1) = 0 ✓ ``` --- ## Orthogonal Bundles ACSets participates in the **STRUCTURAL** bundle: | Direction | Skills | Behavior | |-----------|--------|----------| | STRUCTURAL | clj-kondo(-1) ⊗ acsets(0) ⊗ rama-gay(+1) | Schema validation → transport → generation | | TEMPORAL | three-match(-1) ⊗ unworld(0) ⊗ gay-mcp(+1) | Reduction → derivation → coloring | | STRATEGIC | proofgeneral(-1) ⊗ glass-bead(0) ⊗ rubato(+1) | Verification → hopping → composition | --- ## Visual Conventions (from RelationalThinking) | Concept | Visual | |---------|--------| | Schema object | Gray circle | | Schema morphism | Colored arrow (cyan=src, blue=tgt) | | Instance element | Filled shape | | Morphism mapping | Slot/containment | | Pushout | Merged regions with distinct colors | | DPO rule | Thought bubble (L,K,R) | --- ## Commands ```bash # Schema operations just acset-schema FILE # Display schema diagram just acset-instance FILE # Display instance elements just acset-morphism F G # Show homomorphism F → G # DPO rewriting just acset-rule RULE STATE # Apply rewrite rule just acset-matches RULE STATE # Find all matches just acset-chain RULES STATE # Chain multiple rewrites # Self-play just acset-selfplay SCHEMA # Run self-refinement loop just acset-patterns STATE # Mine patterns from state just acset-converge SCHEMA # Run until convergence # GF(3) operations just acset-trits STATE SEED # Color state with seed just acset-gf3 STATE # Check GF(3) conservation just acset-triads # Show synergistic triads ``` --- ## References ### Topos Institute - [RelationalThinking Book](https://toposinstitute.github.io/RelationalThinking-Book/) - [RelationalThinking Code](https://github.com/ToposInstitute/RelationalThinking-code) ### AlgebraicJulia - [Catlab.jl](https://github.com/AlgebraicJulia/Catlab.jl) - [ACSets.jl](https://github.com/AlgebraicJulia/ACSets.jl) - [AlgebraicRewriting.jl](https://github.com/AlgebraicJulia/AlgebraicRewriting.jl) ### Papers - Patterson et al. "Categorical data structures for technical computing" (Compositionality 2022) - Aguinaldo et al. "Categorical Representation Language for Knowledge-Based Planning" (AAAI 2023) --- ## Related Skills - `rama-gay-clojure` (+1) - Scalable backends with color tracing - `clj-kondo-3color` (-1) - Schema validation/linting - `glass-bead-game` (0) - World hopping across schemas - `unworld` (0) - Derivational chains for state evolution - `discohy-streams` (0) - DisCoPy categorical color streams --- **Skill Name**: acsets-relational-thinking **Type**: Category-Theoretic Database / DPO Rewriting **Trit**: 0 (ERGODIC) **GF(3)**: Conserved via triadic composition ## Scientific Skill Interleaving This skill connects to the K-Dense-AI/claude-scientific-skills ecosystem: ### Annotated Data - **anndata** [○] via bicomodule ### Bibliography References - `general`: 734 citations in bib.duckdb ## SDF Interleaving This skill connects to **Software Design for Flexibility** (Hanson & Sussman, 2021): ### Primary Chapter: 2. Domain-Specific Languages **Concepts**: DSL, wrapper, pattern-directed, embedding ### GF(3) Balanced Triad ``` acsets-relational-thinking (−) + SDF.Ch2 (−) + [balancer] (−) = 0 ``` **Skill Trit**: -1 (MINUS - verification) ### Secondary Chapters - Ch5: Evaluation - Ch3: Variations on an Arithmetic Theme - Ch4: Pattern Matching - Ch10: Adventure Game Example ### Connection Pattern DSLs embed domain knowledge. This skill defines domain-specific operations. ## Cat# Integration This skill maps to **Cat# = Comod(P)** as a bicomodule in the equipment structure: ``` Trit: 0 (ERGODIC) Home: Span Poly Op: ⊗ Kan Role: Adj Color: #26D826 ``` ### GF(3) Naturality The skill participates in triads satisfying: ``` (-1) + (0) + (+1) ≡ 0 (mod 3) ``` This ensures compositional coherence in the Cat# equipment structure.