Probleme – Un rang, sans fonction de fenêtrage

1. La caractérisation. Le rang d'une note est

$$\mathrm{rang}(x)=1+\#\{y\text{ dans la meˆme matieˋre}:y>x\}.$$

C'est le pas décisif : « être le troisième » n'est pas une propriété qu'on lit sur une ligne, c'est un comptage sur les autres lignes. Une fois formulé ainsi, l'énoncé ne demande plus qu'un COUNT, et SQL sait le faire.

Le $1+$ vient de ce que le meilleur n'a personne au-dessus de lui : son rang est $1$, pas $0$. Et l'inégalité stricte $y>x$ donne des ex æquo de même rang, avec un saut ensuite — la convention usuelle des classements.

2. Les deux écritures.

-- (a) sous-requête corrélée : pour chaque ligne, on compte les meilleures
SELECT n1.matiere, n1.eleve, n1.valeur,
       1 + (SELECT COUNT(*) FROM Note n2
            WHERE n2.matiere = n1.matiere AND n2.valeur > n1.valeur) AS rang
FROM Note n1
ORDER BY n1.matiere, rang;

-- (b) auto-jointure externe : on rapproche chaque note de ses supérieures
SELECT n1.matiere, n1.eleve, n1.valeur, 1 + COUNT(n2.eleve) AS rang
FROM Note n1
LEFT JOIN Note n2 ON n2.matiere = n1.matiere AND n2.valeur > n1.valeur
GROUP BY n1.matiere, n1.eleve, n1.valeur
ORDER BY n1.matiere, rang;

Les deux rendent le même résultat, mesuré :

La jointure de (b) doit être externe, et c'est le piège de l'écriture. La note $17$ n'a aucune note supérieure : avec un JOIN, elle n'aurait aucun partenaire et disparaîtrait du résultat. On perdrait exactement les premiers de chaque matière — le résultat le plus faux possible pour un classement. C'est encore le défaut annoncé par le cours, dans un habit inattendu.

Corollaire : on compte COUNT(n2.eleve) et non COUNT(*), sans quoi la ligne fabriquée par la jointure externe compterait pour $1$ et le meilleur serait deuxième (exercice 21.3).

Le coût. La forme (a) exécute une sous-requête par ligne : $\Theta (n)$ comptages de $\Theta (n)$ lignes, soit $\Theta (n^2)$ sans index. La forme (b) construit une auto-jointure de $\Theta (n^2)$ couples avant de les regrouper. Les deux sont quadratiques — c'est le prix de ce détour, et c'est précisément ce que les fonctions de fenêtrage évitent, en triant une fois pour toutes en $\Theta (n\log n)$.

3. Le classement général. On calcule d'abord les moyennes pondérées, puis on applique la même caractérisation à ce résultat intermédiaire.

SELECT e.nom, t.ponderee,
       1 + (SELECT COUNT(*) FROM
              (SELECT eleve, SUM(valeur*coef)*1.0/SUM(coef) AS p
               FROM Note JOIN Matiere ON code = matiere GROUP BY eleve) u
            WHERE u.p > t.ponderee) AS rang
FROM (SELECT eleve, SUM(valeur*coef)*1.0/SUM(coef) AS ponderee
      FROM Note JOIN Matiere ON code = matiere GROUP BY eleve) t
JOIN Eleve e ON e.id = t.eleve
ORDER BY rang;

Mesuré : Cohen ($15,00$) rang $1$, Alaoui ($13,54$) rang $2$, Benali ($11,60$) rang $3$.

Ce que ce problème illustre au-delà de SQL : une requête déclarative se construit en traduisant une définition, pas en imaginant un parcours. On n'a jamais dit au moteur de trier ni de numéroter ; on a écrit ce qu'est un rang, et il s'est débrouillé. C'est le paradigme du chapitre chap:algo-prog, et le prix à payer se lit dans le paragraphe sur le coût : une définition élégante peut avoir une exécution quadratique, et personne ne le signale.