# Concepts catégoriques — Catrust

Ce guide explique les fondements mathématiques du moteur, sans supposer de connaissance préalable en théorie des catégories.

---

## Vue d'ensemble

Catrust implémente **CQL (Categorical Query Language)**, un langage de requêtes et de migrations fondé sur la théorie des catégories. L'idée centrale : les bases de données et leurs transformations ont une structure mathématique précise qui permet de raisonner formellement sur elles.

```
Concept CQL       →   Concept SQL        →   Concept catégorique
──────────────────────────────────────────────────────────────────
Schema            →   CREATE TABLE       →   Catégorie
Instance          →   Données (SELECT *)  →   Foncteur Schema → Set
Mapping           →   Migration ETL      →   Foncteur Schema → Schema
Δ (delta)         →   SELECT … JOIN      →   Pullback / foncteur inverse
Σ (sigma)         →   INSERT INTO …      →   Extension de Kan gauche
Path equation     →   CHECK constraint   →   Quotient de catégorie
```

---

## 1. Le Typeside — les briques élémentaires

Un **Typeside** définit les types primitifs disponibles dans le système. C'est l'équivalent des types SQL (`VARCHAR`, `INTEGER`…), mais indépendant de tout backend.

Catrust fournit quatre types de base :

| `BaseType` | SQL | Neo4j | Rust |
|------------|-----|-------|------|
| `String`   | `TEXT` / `VARCHAR` | `String` | `String` |
| `Integer`  | `INTEGER` | `Integer` | `i64` |
| `Float`    | `DOUBLE PRECISION` | `Float` | `f64` |
| `Boolean`  | `BOOLEAN` | `Boolean` | `bool` |

On peut étendre le typeside avec `BaseType::Custom("Date")` pour des types définis par l'utilisateur.

**Mathématiquement** : un Typeside est une théorie algébrique multi-sortée. Les "sorts" sont les types, les "opérations" sont les fonctions entre types (`length: String → Int`), et les "équations" sont les lois (`length("") = 0`).

```rust
// Le typeside SQL par défaut (suffisant pour la plupart des cas)
let ts = Typeside::default_sql();
assert!(ts.has_type(&BaseType::String));
```

---

## 2. Le Schema — la catégorie

Un **Schema** est une **catégorie finiment présentée**. Concrètement, c'est un graphe orienté plus des équations.

### Composants

| Composant | Rôle | Analogie SQL |
|-----------|------|--------------|
| **Node** | Un objet de la catégorie = une entité = une table | `CREATE TABLE` |
| **Edge (FK)** | Un morphisme entre entités = une clé étrangère | `FOREIGN KEY` |
| **Edge (Attribut)** | Un morphisme vers un type = une colonne | Colonne typée |
| **PathEquation** | Contrainte : deux chemins sont égaux | `CHECK` + trigger |

### Visualisation

```
Employee ──works_in──▶ Department
   │                       │
   │ emp_name          dept_name
   ▼                       ▼
 String                  String
```

Ce diagramme **est** le schéma. Chaque boîte est un nœud, chaque flèche est une arête.

### Code

```rust
let mut schema = Schema::new("Company");
schema
    .add_node("Employee")
    .add_node("Department")
    .add_fk("works_in", "Employee", "Department")   // FK : morphisme entre entités
    .add_attribute("emp_name", "Employee", BaseType::String)  // attribut
    .add_attribute("dept_name", "Department", BaseType::String);
```

### Les équations de chemins

Une **path equation** exprime que deux façons de naviguer dans le schéma mènent au même résultat.

**Exemple** : si `employee.department.manager = employee.direct_manager`, alors quel que soit l'employé, le manager de son département est son manager direct.

```rust
schema.add_path_equation(
    Path::new("Employee", vec!["department", "manager"]),  // lhs
    Path::new("Employee", vec!["direct_manager"]),          // rhs
);
```

**Mathématiquement** : ce quotient de la catégorie libre transforme le schéma en une présentation algébrique. C'est ce qui permet au `PathOptimizer` d'éliminer des JOINs.

---

## 3. L'Instance — le foncteur

Une **Instance** d'un schéma S est un **foncteur** `I : S → Set`. En pratique :

- Pour chaque **nœud** A : `I(A)` est un ensemble de lignes (comme une table SQL)
- Pour chaque **FK** `f : A → B` : `I(f)` est une fonction qui, à chaque ligne de `I(A)`, associe une ligne de `I(B)`
- Pour chaque **attribut** `a : A → T` : `I(a)` est une fonction qui donne la valeur d'attribut

### La propriété fonctorielle

L'Instance doit respecter la **composition** : si on a `A --f--> B --g--> C`, alors `I(g ∘ f) = I(g) ∘ I(f)`. En pratique, suivre deux FK successives donne le même résultat qu'appliquer la composition directement.

C'est ce que fait `instance.follow_path()` : évaluer la composition de morphismes.

```rust
// Suivre Employee --works_in--> Department
let dept_id = instance.follow_path("Employee", emp_row_id, &["works_in"], &schema);

// Suivre Employee --works_in--> Department --manager--> Employee
let manager_id = instance.follow_path("Employee", emp_row_id, &["works_in", "manager"], &schema);
```

### Insertion de données

```rust
let dept_id = instance.insert("Department",
    HashMap::from([("dept_name".into(), Value::String("Engineering".into()))]),
    HashMap::new(),  // pas de FK sortantes
);

instance.insert("Employee",
    HashMap::from([
        ("emp_name".into(), Value::String("Alice".into())),
        ("salary".into(),   Value::Integer(90000)),
    ]),
    HashMap::from([("works_in".into(), dept_id)]),  // FK vers Department
);
```

---

## 4. Le Mapping — un foncteur entre schémas

Un **Mapping** `F : S → T` est un **foncteur entre deux catégories-schémas**. Il assigne :

- À chaque nœud de S → un nœud de T
- À chaque arête de S → un chemin dans T

Et doit respecter la composition : si en S il existe un chemin `A → B → C`, alors en T les chemins images se composent de la même façon.

### Exemple visuel

```
Schema S (ancien)           Mapping F              Schema T (nouveau)
──────────────────      ─────────────────────    ─────────────────────
Person                  F(Person)  = Employee    Employee
Dept                    F(Dept)    = Department  Department
works_in                F(works_in)= department  department
person_name             F(person_name) = full_name  full_name
```

### Code

```rust
let mut mapping = Mapping::new("Migration", "OldCompany", "NewCompany");
mapping
    .map_node("Person",   "Employee")
    .map_node("Dept",     "Department")
    .map_fk("works_in",   Path::new("Employee", vec!["department"]))
    .map_attr_direct("person_name", "full_name")
    .map_attr_direct("dept_name",   "dept_label");

// Vérifier que F est bien un foncteur
mapping.validate(&schema_old, &schema_new).unwrap();
```

---

## 5. Les migrations : Δ, Σ, Π

Étant donné un mapping `F : S → T`, on peut migrer des données dans trois directions :

### Δ_F (Delta — Pullback)

**Direction** : `Instance(T) → Instance(S)`

**Intuition** : "voir les données de T à travers les lunettes de S". On ne crée pas de données, on les restructure.

**SQL équivalent** : `SELECT ... FROM T JOIN ...` (vue / sélection)

```rust
// T a des données → on les ramène dans la structure de S
let instance_s = migrate::delta(&mapping, &schema_s, &schema_t, &instance_t);
```

### Σ_F (Sigma — Left Kan Extension)

**Direction** : `Instance(S) → Instance(T)`

**Intuition** : "pousser les données de S vers T". C'est la migration directe.

**SQL équivalent** : `INSERT INTO T SELECT ... FROM S` (avec identification / déduplication)

```rust
// S a des données → on les envoie vers la structure de T
let instance_t = migrate::sigma(&mapping, &schema_s, &schema_t, &instance_s);
```

### Π_F (Pi — Right Kan Extension)

**Direction** : `Instance(S) → Instance(T)` (différent de Σ !)

**Intuition** : "jointure universelle". Produit fibré, plus contraignant que Σ.

**SQL équivalent** : requêtes avec produit cartésien filtré (JOINs complexes)

> Π est algorithmiquement plus coûteux que Σ et Δ. C'est la migration "maximalement cohérente".

### Relation entre les trois

```
Instance(S)  ──Σ_F──▶  Instance(T)
     ▲                       │
     │                       │
     └─────Δ_F───────────────┘

Σ ⊣ Δ ⊣ Π   (adjonctions en théorie des catégories)
```

`Σ` et `Π` sont respectivement l'adjoint gauche et droit de `Δ`. Cela garantit des propriétés de préservation : `Σ` préserve les colimites, `Π` préserve les limites.

---

## 6. Le Path Optimizer — réécriture catégorique

Les **path equations** du schéma sont exploitées pour simplifier les chemins (= éliminer des JOINs en SQL).

### Principe

Si le schéma contient l'équation :
```
employee.department.manager = employee.direct_manager
```

Alors le chemin long `employee.department.manager` (2 JOINs) peut être réécrit en `employee.direct_manager` (1 JOIN).

### Algorithme

C'est une **complétion de Knuth-Bendix** sur le monoïde libre des chemins :
1. Chaque path equation génère une règle de réécriture (long → court)
2. On applique les règles jusqu'à un point fixe (forme normale)
3. La terminaison est garantie car chaque réécriture **réduit strictement la longueur**

```rust
let optimizer = PathOptimizer::from_schema(&schema);

let path = Path::new("Employee", vec!["department", "manager", "department"]);
let result = optimizer.optimize(&path);
// result.optimized = Employee.direct_manager.department (1 JOIN de moins)
// result.joins_eliminated = 1
```

---

## 7. L'évaluateur in-memory

Catrust peut évaluer des requêtes CQL **directement en mémoire**, sans passer par une base de données.

### Algorithme d'évaluation

Pour une requête `FROM e : Employee WHERE ... RETURN ...` :

1. Itérer sur toutes les lignes de `Employee`
2. Pour chaque ligne, évaluer les clauses `WHERE` (suivre les FK, lire l'attribut, comparer)
3. Projeter les attributs demandés dans le résultat
4. Retourner l'instance résultat

C'est un `SELECT ... FROM ... WHERE` en mémoire, guidé par la structure catégorique.

```rust
let result = eval::eval_query(&query, &instance, &schema).unwrap();
println!("Lignes retournées : {}", result.rows_returned);
println!("Temps : {}µs", result.eval_time_us);

// Agrégations disponibles
let total = eval::sum(&result, "Entity", "salary");
let count = eval::count(&result, "Entity");
let distinct = eval::distinct(&result, "Entity", "dept_name");
```

---

## Références

Pour approfondir la théorie, voir la section "Références" du README principal. L'ordre recommandé :

1. **Lawvere & Schanuel** — *Conceptual Mathematics* — point d'entrée, zéro prérequis
2. **Milewski** — *Category Theory for Programmers* — pour les développeurs
3. **Spivak** — *Category Theory for the Sciences* — CQL et bases de données
4. **Spivak** — *Functorial Data Migration* (2012) — l'article fondateur
5. **Schultz, Spivak & Wisnesky** — *Algebraic Databases* (2017) — la formalisation complète