Ensembles, relations et fonctions¶

Modéliser un domaine métier commence par définir des ensembles et des relations — avant d'écrire une ligne de code.

Pourquoi les ensembles avant le code¶

Un système de gestion de commandes manipule des utilisateurs, des produits, des commandes, des états. Avant de choisir un ORM ou un schéma de base de données, la question fondamentale est : quelles entités existent, quelles relations les lient, quelles contraintes ces relations doivent respecter ?

La théorie des ensembles donne un vocabulaire précis pour répondre a ces questions. Un type de données est un ensemble. Une relation entre tables est une relation mathématique. Une fonction de transformation est une fonction mathématique. Cette équivalence n'est pas metaphorique — elle est opérationnelle : les propriétés mathématiques se traduisent directement en contraintes implementables et verifiables.

Ensembles et opérations fondamentales¶

Définitions de base¶

Un ensemble est une collection non ordonnée d'éléments distincts. Notations :

• En extension : \(A = \{1, 2, 3, 4\}\)
• En comprehension : \(A = \{x \in \mathbb{N} \mid x \leq 4\}\)
• Ensemble vide : \(\emptyset = \{\}\)
• Appartenance : \(x \in A\), \(x \notin A\)
• Inclusion : \(A \subseteq B\) (tout élément de A est dans B), \(A \subset B\) (inclusion stricte)
• Cardinalite : \(|A|\) = nombre d'éléments

En informatique : les types primitifs sont des ensembles (bool = {true, false}, uint8 = {0, ..., 255}). Les enumerations sont des ensembles finis. Les types somme (union discriminee) et produit (structures) ont une interpretation ensembliste directe.

Opérations binaires¶

Soient \(A\) et \(B\) deux ensembles inclus dans un univers \(U\).

Union : \(A \cup B = \{x \mid x \in A \text{ ou } x \in B\}\) Exemple : SELECT * FROM a UNION SELECT * FROM b

Intersection : \(A \cap B = \{x \mid x \in A \text{ et } x \in B\}\) Exemple : utilisateurs actifs ET ayant passe une commande ce mois

Différence : \(A \setminus B = \{x \mid x \in A \text{ et } x \notin B\}\) Exemple : SELECT * FROM a LEFT JOIN b ON ... WHERE b.id IS NULL

Complement : \(A^c = U \setminus A = \{x \in U \mid x \notin A\}\)

Différence symetrique : \(A \triangle B = (A \setminus B) \cup (B \setminus A)\) Exemple : éléments present dans l'un mais pas l'autre — utile pour la synchronisation, la détection de drift

Produit cartesien¶

Si \(|A| = m\) et \(|B| = n\), alors \(|A \times B| = m \times n\).

Le produit cartesien est le fondement du modèle relationnel. Une table SQL avec des colonnes de types \(T_1, T_2, \ldots, T_n\) est un sous-ensemble de \(T_1 \times T_2 \times \ldots \times T_n\). Une jointure sans condition de join produit le produit cartesien — d'ou son coût explosif quand les tables sont grandes.

Ensemble des parties¶

L'ensemble des parties de \(A\), note \(\mathcal{P}(A)\) ou \(2^A\), est l'ensemble de tous les sous-ensembles de \(A\).

Si \(A = \{1, 2, 3\}\) alors \(\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}\)

Si \(|A| = n\), alors \(|\mathcal{P}(A)| = 2^n\).

Application : les permissions d'un système peuvent être modelisees comme des sous-ensembles d'un ensemble de capacités. Avec 30 permissions possibles, il y a \(2^{30} \approx 10^9\) combinaisons — trop nombreuses pour être listees, mais structurées par les opérations ensemblistes.

Relations¶

Définition¶

Une relation \(R\) de \(A\) vers \(B\) est un sous-ensemble du produit cartesien \(A \times B\). On écrit \(xRy\) ou \((x, y) \in R\) pour indiquer que \(x\) est en relation avec \(y\).

Une relation de \(A\) vers \(A\) est une relation sur \(A\) (relation homogène). La plupart des propriétés structurelles intéressantes s'appliquent aux relations homogènes.

Propriétés des relations¶

Soit \(R\) une relation sur un ensemble \(A\).

Ordres¶

Un ordre partiel est une relation reflexive, antisymetrique et transitive. Notation : \(\leq\) ou \(\subseteq\).

Un ordre total est un ordre partiel ou de plus toute paire d'éléments est comparable (relation totale). Tout entier est comparable à tout autre entier — la relation \(\leq\) sur \(\mathbb{Z}\) est un ordre total. En revanche, la relation de divisibilite sur \(\mathbb{N}\) est un ordre partiel : 3 et 5 ne sont ni l'un diviseur de l'autre.

Application système : les versions de dépendances (semver) forment un ordre partiel. Un ensemble de contraintes de versions peut être insatisfaisable si les intervalles ne se chevauchent pas — c'est un problème de satisfiabilite d'un système de contraintes sur un ordre partiel.

Treillis : un ordre partiel ou toute paire d'éléments admet une borne supérieure minimale (supremum) et une borne inférieure maximale (infimum). Les treillis apparaissent dans l'analyse de types, les lattices de sécurité (Bell-LaPadula), et les CRDT (structures de données replicables sans coordination).

graph TD
    ABC["{a,b,c}"]
    AB["{a,b}"]
    AC["{a,c}"]
    BC["{b,c}"]
    A["{a}"]
    B["{b}"]
    C["{c}"]
    E["∅"]

    ABC --> AB
    ABC --> AC
    ABC --> BC
    AB --> A
    AB --> B
    AC --> A
    AC --> C
    BC --> B
    BC --> C
    A --> E
    B --> E
    C --> E

Treillis de l'ensemble des parties de {a,b,c} ordonné par inclusion.

Relations d'équivalence et classes d'équivalence¶

Une relation d'équivalence est reflexive, symetrique et transitive. Elle partitionne l'ensemble en classes d'équivalence — des sous-ensembles disjoints dont l'union est l'ensemble complet.

Notation : \(x \sim y\) (\(x\) et \(y\) sont équivalents). La classe d'équivalence de \(x\) est \([x] = \{y \mid y \sim x\}\).

Exemples applicatifs :

• Egalite modulo \(n\) : les entiers modulo 7 forment 7 classes d'équivalence. La cryptographie RSA repose sur l'arithmetique modulaire.
• Canonicalisation d'URLs : toutes les URLs qui résolvent vers la même ressource sont équivalentes pour la mise en cache.
• Deduplication de logs : deux messages de log avec le même template mais des parametres différents appartiennent à la même classe — utile pour l'agrégation.

Fonctions¶

Définition et types¶

Une fonction \(f : A \to B\) associe à chaque élément de \(A\) (le domaine) exactement un élément de \(B\) (le codomaine). L'ensemble des valeurs effectivement prises par \(f\) est l'image \(\text{Im}(f) \subseteq B\).

Une fonction injective ne "fusionne" pas deux entrees sur la même sortie — elle préservé la distinction. Une fonction surjective couvre tout le codomaine — chaque valeur de sortie possible est atteinte.

Composition de fonctions¶

Si \(f : A \to B\) et \(g : B \to C\), alors la composition \(g \circ f : A \to C\) est définie par \((g \circ f)(x) = g(f(x))\).

La composition est associative : \(h \circ (g \circ f) = (h \circ g) \circ f\).

from functools import reduce
from typing import Callable, TypeVar

T = TypeVar('T')

def compose(*fns: Callable) -> Callable:
    """Compose des fonctions de droite a gauche."""
    return reduce(lambda f, g: lambda x: f(g(x)), fns)

# Exemple : pipeline de transformation de donnee
normaliser = lambda s: s.strip().lower()
supprimer_accents = lambda s: s.encode('ascii', 'ignore').decode()
truncate = lambda s: s[:50]

# La composition est une nouvelle fonction
nettoyer = compose(truncate, supprimer_accents, normaliser)

resultat = nettoyer("  Entrée COMPLEXE avec Accents  ")

# Les middlewares HTTP sont des compositions de fonctions
# handler : Request -> Response
# middleware : (Request -> Response) -> (Request -> Response)

def auth_middleware(handler):
    def wrapped(request):
        if not request.headers.get('Authorization'):
            return Response(401, 'Unauthorized')
        return handler(request)
    return wrapped

def logging_middleware(handler):
    def wrapped(request):
        print(f"→ {request.method} {request.path}")
        response = handler(request)
        print(f"← {response.status}")
        return response
    return wrapped

# app = logging_middleware(auth_middleware(core_handler))
# Correspond mathematiquement a : logging ∘ auth ∘ core

Fonction inverse¶

Une fonction bijective \(f : A \to B\) admet une inverse \(f^{-1} : B \to A\) telle que \(f^{-1} \circ f = \text{id}_A\) et \(f \circ f^{-1} = \text{id}_B\).

Seules les bijections sont inversibles. Une fonction injective non surjective peut être inversee sur son image mais pas sur tout \(B\). Une fonction non injective (plusieurs entrees vers la même sortie) ne peut pas être inversee — l'information a été perdue.

Application : les fonctions de hachage ne sont pas bijectives (plusieurs entrees peuvent donner le même hash, et la sortie est plus petite que le domaine) — elles sont donc fondamentalement non inversibles, ce qui fonde leur utilisation en cryptographie.

Applications : systèmes de types et modélisation de données¶

Le système de types comme théorie des ensembles¶

Chaque type est un ensemble. Chaque valeur est un élément. Les constructions du langage correspondent à des opérations ensemblistes :

from typing import Union, Literal

# Type somme : un seul element d'une union
Statut = Literal['actif', 'inactif', 'suspendu']
# Statut = {'actif', 'inactif', 'suspendu'} — ensemble fini

# Type produit : combinaison de types
from dataclasses import dataclass

@dataclass
class Utilisateur:
    id: int          # element de ℕ
    email: str       # element de Σ* (mots sur un alphabet)
    statut: Statut   # element de {'actif', 'inactif', 'suspendu'}
    # Utilisateur ⊆ ℕ × Σ* × Statut

Modélisation de données : relations et cardinalites¶

Les cardinalites des relations de base de données sont des propriétés de fonctions :

Une relation N:M ne peut pas être représentée par une simple fonction — elle nécessité une table d'association (table de jointure) qui materialise la relation comme un sous-ensemble du produit cartesien.

Partitionnement et sharding¶

Le sharding d'une base de données est une partition de l'ensemble des données. Une partition de \(A\) est un ensemble de sous-ensembles disjoints de \(A\) dont l'union est \(A\) — exactement la structure des classes d'équivalence d'une relation d'équivalence.

def shard_key(user_id: int, nb_shards: int) -> int:
    """Partitionne les utilisateurs en nb_shards groupes disjoints."""
    return user_id % nb_shards
    # Relation d'equivalence : user_a ~ user_b si user_a % nb_shards == user_b % nb_shards
    # Produit nb_shards classes d'equivalence disjointes

Pour que le sharding soit équilibre, la fonction de shard doit être "presque surjective" — chaque shard reçoit approximativement le même nombre de clés. Le hachage cohérent (consistent hashing) optimise cette propriété en minimisant la redistribution lors de l'ajout ou de la suppression de nœuds.

Clôture et fermeture transitive¶

La fermeture transitive d'une relation \(R\) est la plus petite relation transitive contenant \(R\). Notation : \(R^+\).

En pratique : si on a une relation "dépend de" entre modules, la fermeture transitive donne toutes les dépendances transitives. Calculer la fermeture transitive d'un graphe de dépendances détecté les dépendances circulaires (cycles dans le graphe).

-- Fermeture transitive en SQL (CTE recursive)
WITH RECURSIVE dependances_transitives AS (
    -- Cas de base : dependances directes
    SELECT source, cible FROM dependances
    UNION ALL
    -- Etape : etendre par transitivite
    SELECT dt.source, d.cible
    FROM dependances_transitives dt
    JOIN dependances d ON dt.cible = d.source
)
SELECT DISTINCT source, cible FROM dependances_transitives;

Formulaire de référence¶