Préambule▲
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'aventurerai 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 :
CLI_ID CLI_NOM
------- ------------
17 DURAND
192 DUPONT
44 DUVAL
11 DUMOULIN
741 DULIN
82 DUPOND
177 DURANDCréation du jeu d'essai :
CREATE TABLE T_CLIENT_CLI
(CLI_ID INTEGER,
CLI_NOM VARCHAR(10))
INSERT INTO T_CLIENT_CLI (CLI_ID, CLI_NOM)
VALUES (17, 'DURAND')
INSERT INTO T_CLIENT_CLI (CLI_ID, CLI_NOM)
VALUES (192, 'DUPONT')
INSERT INTO T_CLIENT_CLI (CLI_ID, CLI_NOM)
VALUES (44, 'DUVAL')
INSERT INTO T_CLIENT_CLI (CLI_ID, CLI_NOM)
VALUES (11, 'DUMOULIN')
INSERT INTO T_CLIENT_CLI (CLI_ID, CLI_NOM)
VALUES (741, 'DULIN')
INSERT INTO T_CLIENT_CLI (CLI_ID, CLI_NOM)
VALUES (82, 'DUPOND')
INSERT INTO T_CLIENT_CLI (CLI_ID, CLI_NOM)
VALUES (177, 'DURAND')La question est : comment obtenir en réponse les noms de nos clients par ordre alphabétique avec leur rang (depuis 1, jusqu'à n) ?
1-1. RÉPONSE 1▲
Si l'on applique strictement cette question, alors la réponse est :
CLI_NOM RANG
------------- -----
DULIN 1
DUMOULIN 2
DUPOND 3
DUPONT 4
DURAND 5
DURAND 5
DUVAL 7En effet, les deux DURAND se trouvant ex æquo occupent le 5e rang, tandis que DUVAL occupe non pas le 6e, mais le 7e rang !
1-2. RÉPONSE 2▲
Une autre solution possible est :
CLI_NOM RANG
------------- -----
DULIN 1
DUMOULIN 2
DUPOND 3
DUPONT 4
DURAND 5
DURAND 6
DUVAL 7C'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 :
CLI_NOM RANG NOMBRE
------------- ----- ------
DULIN 1 1
DUMOULIN 2 1
DUPOND 3 1
DUPONT 4 1
DURAND 5 2
DUVAL 7 1Qui a le mérite d'être plus propre sans correspondre toutefois à la demande initiale !
1-4. RÉPONSE 4▲
En poussant les choses à l'extrême, on peut exiger que la numérotation de rang soit stricte et sans « trou », comme ceci :
CLI_NOM RANG NOMBRE
------------- ----- ------
DULIN 1 1
DUMOULIN 2 1
DUPOND 3 1
DUPONT 4 1
DURAND 5 2
DUVAL 6 1Mais quelles 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-équijointure 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
LEFT OUTER JOIN T_CLIENT_CLI T2
ON T1.CLI_NOM > T2.CLI_NOM
GROUP BY T1.CLI_ID, T1.CLI_NOM
ORDER BY RANGRequête de la réponse 2 :
SELECT T1.CLI_NOM, COUNT(T2.CLI_ID) + 1 AS RANG
FROM T_CLIENT_CLI T1
LEFT OUTER JOIN 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
ORDER BY RANGRequête de la réponse 3 :
SELECT T1.CLI_NOM, RANG, NOMBRE
FROM (SELECT DISTINCT T1.CLI_NOM, COUNT(T2.CLI_ID) + 1 AS RANG
FROM T_CLIENT_CLI T1
LEFT OUTER JOIN T_CLIENT_CLI T2
ON T1.CLI_NOM > T2.CLI_NOM
GROUP BY T1.CLI_ID, T1.CLI_NOM)
T1
INNER JOIN (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
ORDER BY RANGRequête de la réponse 4 :
SELECT T2.CLI_NOM, COUNT(T1.CLI_NOM) AS RANG, NOMBRE
FROM (SELECT DISTINCT CLI_NOM
FROM T_CLIENT_CLI) T1
LEFT OUTER JOIN (SELECT DISTINCT CLI_NOM
FROM T_CLIENT_CLI) T2
ON T1.CLI_NOM <= T2.CLI_NOM
INNER JOIN (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
ORDER BY RANGLe 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 celui de notre exemple ? Il y a fort à parier que ce dernier passe la main et se fende 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 cinq places par rang, c'est-à-dire un théâtre de poche !
PLC_REF
-------
A01
A02
A03
A04
A05
B01
B02
B03
B04
B05
C01
C02
C03
C04
C05Création du jeu d'essai :
CREATE TABLE T_PLACE_PLC
(PLC_REF CHAR(3))
INSERT INTO T_PLACE_PLC (PLC_REF) VALUES ('A01')
INSERT INTO T_PLACE_PLC (PLC_REF) VALUES ('A02')
INSERT INTO T_PLACE_PLC (PLC_REF) VALUES ('A03')
INSERT INTO T_PLACE_PLC (PLC_REF) VALUES ('A04')
INSERT INTO T_PLACE_PLC (PLC_REF) VALUES ('A05')
INSERT INTO T_PLACE_PLC (PLC_REF) VALUES ('B01')
INSERT INTO T_PLACE_PLC (PLC_REF) VALUES ('B02')
INSERT INTO T_PLACE_PLC (PLC_REF) VALUES ('B03')
INSERT INTO T_PLACE_PLC (PLC_REF) VALUES ('B04')
INSERT INTO T_PLACE_PLC (PLC_REF) VALUES ('B05')
INSERT INTO T_PLACE_PLC (PLC_REF) VALUES ('C01')
INSERT INTO T_PLACE_PLC (PLC_REF) VALUES ('C02')
INSERT INTO T_PLACE_PLC (PLC_REF) VALUES ('C03')
INSERT INTO T_PLACE_PLC (PLC_REF) VALUES ('C04')
INSERT INTO T_PLACE_PLC (PLC_REF) VALUES ('C05')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 :
|
Sélectionnez |
Sélectionnez |
Dès lors, la solution saute aux yeux :
SELECT CLI_NOM, PLC_REF
FROM T_CLIENT_CLI
JOIN T_PLACE_PLC
ON CLI_NUM = PLC_NUMQui donne :
CLI_NOM PLC_REF
------------ -------
DURAND A01
DUPONT A02
DUVAL A03
DUMOULIN A04
DULIN A05
DUPOND B01
DURAND B02Né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
LEFT OUTER JOIN 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
INNER JOIN (SELECT T3.PLC_REF, COUNT(T4.PLC_REF) + 1 AS RANG
FROM T_PLACE_PLC T3
LEFT OUTER JOIN T_PLACE_PLC T4
ON T3.PLC_REF > T4.PLC_REF
GROUP BY T3.PLC_REF) P
ON C.RANG = P.RANGEt 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 :
ENT_I
-------
0
1
2
3
4
5
6
7
8
9
10
...CREATE TABLE T_I_ENT
(ENT_I INTEGER)
INSERT INTO T_I_ENT (ENT_I) VALUES (0)
INSERT INTO T_I_ENT (ENT_I) VALUES (1)
INSERT INTO T_I_ENT (ENT_I) VALUES (2)
INSERT INTO T_I_ENT (ENT_I) VALUES (3)
INSERT INTO T_I_ENT (ENT_I) VALUES (4)
INSERT INTO T_I_ENT (ENT_I) VALUES (5)
INSERT INTO T_I_ENT (ENT_I) VALUES (6)
INSERT INTO T_I_ENT (ENT_I) VALUES (7)
INSERT INTO T_I_ENT (ENT_I) VALUES (8)
INSERT INTO T_I_ENT (ENT_I) VALUES (9)
INSERT INTO T_I_ENT (ENT_I) VALUES (10)
...
INSERT INTO T_I_ENT (ENT_I) VALUES (1000)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 :
INSERT INTO T_I_ENT (ENT_I)
SELECT DISTINCT I1.ENT_I + (I2.ENT_I * 10) + (I3.ENT_I * 100)
FROM T_I_ENT I1
CROSS JOIN T_I_ENT I2
CROSS JOIN T_I_ENT I3
CROSS JOIN T_I_ENT I4
WHERE I1.ENT_I + (I2.ENT_I * 10) + (I3.ENT_I * 100) BETWEEN 0 AND 1000Dè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 :
CLI_NOM T_I_ENT
---------- ------------
DULIN 1
DUMOULIN 2
DUPOND 3
DUPONT 4
DURAND 5
DURAND 6
DUVAL 7C'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 */
ORDER BY CLI_NOM, T_I_ENTQuelques 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 à 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
ORDER BY CLI_NOM, T_I_ENTqui donne :
CLI_NOM T_I_ENT
---------- ------------
DULIN 0
DUMOULIN 1
DUPOND 2
DUPONT 3
DURAND 4
DURAND 5
DUVAL 6
NULL 7
NULL 8
...
NULL 1000Pour 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
ORDER BY CLI_NOM, T_I_ENT, PLC_REFJe 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 !