Corrigé X-ENS 2026 Informatique B MP-PC-PSI — Partie III (Q15 à Q16) : Représentation relationnelle du graphe

Q15. On cherche les arcs qui violent l'un des deux invariants ; ceux-ci sont vérifiés si et seulement si la requête ne renvoie aucune ligne. Chaque arc est joint deux fois à la table sommets, une fois pour sa source, une fois pour sa cible (deux alias).

SELECT a.source, a.cible
FROM arcs AS a
     JOIN sommets AS s ON a.source = s.id
     JOIN sommets AS t ON a.cible = t.id
WHERE s."époque" > t."époque"
   OR (s."époque" = t."époque" AND s.sortie < t.sortie);

La double jointure produit une ligne par arc, portant les époques et sorties de ses deux extrémités. La condition du WHERE est la négation de « A3 et A4 » pour l'arc : A3 est faux quand $\text{eˊpoque}[s]>\text{eˊpoque}[t]$ ; A4 est faux quand son hypothèse est vraie et sa conclusion fausse, c'est-à-dire $\text{eˊpoque}[s]=\text{eˊpoque}[t]$ et $\text{sortie}[s]<\text{sortie}[t]$. La requête renvoie donc exactement les arcs fautifs ; une réponse vide certifie les deux invariants. Si l'on préfère un verdict chiffré, on remplace la première ligne par SELECT COUNT(*) et l'on vérifie que le nombre vaut 0. On remarque que cette condition est exactement le filtre de la ligne 5 d'accessible (partie I), appliqué à chaque arc. Les noms de colonnes accentués du schéma sont écrits entre guillemets doubles (identifiants délimités de la norme SQL) ; SQLite les accepte aussi nus (s.époque), comme les nomme le sujet. Essai : base SQLite remplie de 3 000 graphes aléatoires avec des époques et sorties arbitraires ; la requête renvoie à chaque fois exactement les arcs fautifs calculés en Python.