Cet article a pour but de présenter un nouveau type de jointure pour SQL. Il s'agit d'un travail préparatoire à un article plus complet, notamment en trouvant dans l'algèbre relationnelle l'outil adéquat pour exprimer une telle jointure.
Au vu des problèmes que me posent régulièrement collègues et internautes, j'ai tenté de résoudre au cas par cas une famille de problèmes assez difficiles à exprimer par des requêtes SQL simples. Je suis arrivé à la conclusion qu'il était intéressant de prévoir de rajouter à SQL un nouveau type de jointure, la jointure "LINÉAIRE". Nous allons dans un premier temps poser les différents problèmes et voir comment nous pouvons les résoudre en introduisant ce nouvel opérateur. Dans l'immédiat je ne m'aventurerais pas dans l'algèbre relationnelle pour déterminer si le bon docteur Codd a manqué à sa tâche. Je réserve donc aux théoriciens une belle bataille en perspective pour déterminer l'opportunité de cette opération et les moyens de la représenter...
PLEASE : you can have the english translation of this paper by clicking HERE
1. Numéroter des lignes et toutes les requêtes qui en découlent
Soit la table T_CLIENT_CLI (CLI_ID, CLI_NOM) comme suit :
C'est à dire une numérotation franche et directe sans tenir compte des doublons ou de l'ambiguïté des informations sélectionnées. C'est un peu ce que font les colonnes d'auto incrémentation de certains SGBDR.
1.3. RÉPONSE 3
Enfin on peut raffiner cette dernière solution en introduisant un comptage pour faire disparaître les doublons :
Mais quelle est sont les requêtes nécessaires pour parvenir aux différentes solutions proposées ?
1.5. Requêtes associées
Dans le principe, les requêtes pour répondre à ce genre de demande nécessitent une auto non équi jointure afin de faire le dénombrement de tuples dont les valeurs précèdent le tuple en cours.
Requête de la réponse 1 :
SELECT T1.CLI_NOM, COUNT(T2.CLI_ID) + 1 AS RANG
FROM T_CLIENT_CLI T1
LEFTOUTERJOIN T_CLIENT_CLI T2
ON T1.CLI_NOM > T2.CLI_NOM
GROUP BY T1.CLI_ID, T1.CLI_NOM
ORDERBY RANG
Requête de la réponse 2 :
SELECT T1.CLI_NOM, COUNT(T2.CLI_ID) + 1 AS RANG
FROM T_CLIENT_CLI T1
LEFTOUTERJOIN T_CLIENT_CLI T2
ON T1.CLI_NOM || CAST(T1.CLI_ID AS CHAR(16))
> T2.CLI_NOM || CAST(T2.CLI_ID AS CHAR(16))
GROUP BY T1.CLI_ID, T1.CLI_NOM
ORDERBY RANG
Requête de la réponse 3 :
SELECT T1.CLI_NOM, RANG, NOMBRE
FROM (SELECTDISTINCT T1.CLI_NOM, COUNT(T2.CLI_ID) + 1 AS RANG
FROM T_CLIENT_CLI T1
LEFTOUTERJOIN T_CLIENT_CLI T2
ON T1.CLI_NOM > T2.CLI_NOM
GROUP BY T1.CLI_ID, T1.CLI_NOM)
T1
INNERJOIN (SELECT CLI_NOM, COUNT(CLI_ID) AS NOMBRE
FROM T_CLIENT_CLI T1
GROUP BY CLI_NOM) T2
ON T1.CLI_NOM = T2.CLI_NOM
ORDERBY RANG
Requête de la réponse 4 :
SELECT T2.CLI_NOM, COUNT(T1.CLI_NOM) AS RANG, NOMBRE
FROM (SELECTDISTINCT CLI_NOM
FROM T_CLIENT_CLI) T1
LEFTOUTERJOIN (SELECTDISTINCT CLI_NOM
FROM T_CLIENT_CLI) T2
ON T1.CLI_NOM <= T2.CLI_NOM
INNERJOIN (SELECT CLI_NOM, COUNT(CLI_ID) AS NOMBRE
FROM T_CLIENT_CLI
GROUP BY CLI_NOM) T3
ON T2.CLI_NOM = T3.CLI_NOM
GROUP BY T2.CLI_NOM, T3.NOMBRE
ORDERBY RANG
Le moins que l'on puisse dire, c'est que ce genre de requêtes ne vient pas à l'esprit du débutant. Que dire alors du développeur confronté à ce problème dans un contexte de tables bien plus étoffées que celle de notre exemple ? Il y a fort à parier que ce dernier passe la main et se fend d'une jolie procédure au mieux stockée, au pire sur le poste client !
2. Affecter des lignes à des places
La deuxième famille de problèmes qui mérite notre attention dans ce cadre, concerne les problèmes d'affectation, problèmes chers à tous les enseignants en début d'année scolaire par exemple. La question est : partant d'une table constituant une population et d'une autre constituée de place (chaque place étant destinée à recevoir un élève, un spectateur…) comment assigner une place à chaque élément de la population ?
Reprenons notre table des clients et ajoutons une table des fauteuils modélisant les places d'un théâtre T_PLACE_PLC (PLC_REF). Les places de théâtre étant numérotées comme vous le savez par des lettres (le rang) et des chiffres (ordre dans le rang). Pour notre démonstration nous nous limiterons à trois rangs et 5 places par rang, c'est à dire un théâtre de poche !
Le problème est on ne peut plus simple : comment affecter les clients aux premiers sièges ?
Il semble à l'évidence que le plus simple serait de numéroter les lignes des clients puis les lignes des sièges et d'effectuer une jointure avec cette numérotation. Quelque chose comme :
Néanmoins nous n'avons pas ces colonnes à disposition… Comment faire ? Il suffit d'appliquer ce que nous venons de voir dans l'exemple précédent, à la fois pour les clients, mais aussi pour les fauteuils et de joindre le tout sur les colonnes de numérotation ainsi générées.
Je vous livre la requête telle quelle, sa mise au point étant assez joyeuse !!!
SELECT CLI_NOM, PLC_REF
FROM (SELECT T1.CLI_NOM, COUNT(T2.CLI_ID) + 1 AS RANG
FROM T_CLIENT_CLI T1
LEFTOUTERJOIN T_CLIENT_CLI T2
ON T1.CLI_NOM || CAST(T1.CLI_ID AS CHAR(16))
> T2.CLI_NOM || CAST(T2.CLI_ID AS CHAR(16))
GROUP BY T1.CLI_ID, T1.CLI_NOM) C
INNERJOIN (SELECT T3.PLC_REF, COUNT(T4.PLC_REF) + 1 AS RANG
FROM T_PLACE_PLC T3
LEFTOUTERJOIN T_PLACE_PLC T4
ON T3.PLC_REF > T4.PLC_REF
GROUP BY T3.PLC_REF) P
ON C.RANG = P.RANG
Et encore avons nous tenu compte que la colonne PLC_REF est une clef candidate de la table T_PLACE_PLC...
3. La solution, la jointure linéaire !
La condition primale est de disposer d'une table très simple dotée d'une seule colonne et remplie avec la suite des nombres entiers : T_I_ENT (ENT_I). Bien entendu on se limitera par exemple à une plage allant de 0 à 1000 voire plus selon ses besoins :
Notons au passage qu'il est inutile de saisir tous les nombres de 1 à 1000, les dix premiers suffisent et une simple requête d'insertion jouera le rôle d'insertion complémentaire :
Dès lors la juxtaposition de la projection du nom de la table client ordonné par client avec la projection de la table des entiers ordonnés répond à notre attente :
C'est pourquoi je propose le nouvel opérateur de jointure linéaire : LINEAR JOIN permettant de faire correspondre à la ligne de rang un de la table de gauche, la ligne de rang un + offset de la table de droite et ainsi de suite.
4. Syntaxe et règles de la jointure linéaire
La jointure linéaire répond à la syntaxe suivante :
SELECT <liste de sélection>
FROM <table gauche>
[LEFT | RIGHT] LINEAR JOIN <table droite> [OFFSET <offset value>]
Dans notre précédent exemple, il suffit donc de faire :
SELECT CLI_NOM, T_I_ENT
FROM T_CLIENT_CLI
LINEAR JOIN T_I_ENT OFFSET 1 /* élimination de la première ligne, un zéro */
ORDERBY CLI_NOM, T_I_ENT
Quelques explications :
le mot clef OFFSET permet d'indiquer à partir de quelle ligne prendre en compte la première ligne de la table de droite associée à la première ligne de la table de gauche
la clause ORDER BY opère séparément avant la jointure linéaire pour les tables jointes
la jointure peut être externe à gauche (LEFT LINEAR JOIN) ou a droite (RIGHT LINEAR JOIN), mais pas des deux côtés. Par défaut elle est interne
Exemple de jointure linéaire externe droite :
SELECT CLI_NOM, T_I_ENT
FROM T_CLIENT_CLI
RIGHT LINEAR JOIN T_I_ENT
ORDERBY CLI_NOM, T_I_ENT
Pour résoudre notre problème d'affectation des places de théâtre, il suffit de faire :
SELECT CLI_NOM, PLC_REF
FROM T_CLIENT_CLI
LINEAR JOIN T_I_ENT
LINEAR JOIN T_PLACE_PLC
ORDERBY CLI_NOM, T_I_ENT, PLC_REF
Je ne sais pas ce que vous en pensez mais je trouve cette écriture plus simple et facile à comprendre !
5. CONCLUSION
Ces requêtes s'apparentent aux T-JOIN (théta jointures) du Docteur Codd en vue d'obtenir une correspondance optimale des inégalités (typiquement le problème d'affectation des élèves dans des salles de capacités données). Je laisse à votre sagacité la représentation d'une telle jointure en algèbre relationnelle !
