La jointure manquante !

SQLPro

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. ♪

- Titre : La jointure manquante !

- Auteur : SQLPro

- Parution : 26 août 2003

- Licence : Copyright ® 2003 Frédéric Brouard. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- Préambule

- 1. Numéroter des lignes et toutes les requêtes qui en découlent

- 1-1. RÉPONSE 1

- 1-2. RÉPONSE 2

- 1-3. RÉPONSE 3

- 1-4. RÉPONSE 4

- 1-5. Requêtes associées

- 2. Affecter des lignes à des places

- 3. La solution, la jointure linéaire !

- 4. Syntaxe et règles de la jointure linéaire

- 5. CONCLUSION

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     DURAND

Cré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         7

En 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         7

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 :

CLI_NOM       RANG  NOMBRE
------------- ----- ------
DULIN         1     1
DUMOULIN      2     1
DUPOND        3     1
DUPONT        4     1
DURAND        5     2
DUVAL         7     1

Qui 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     1

Mais 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 RANG

Requê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 RANG

Requê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 RANG

Requê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 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 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
C05

Cré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 :

CLI_ID  CLI_NOM      CLI_NUM
------- ------------ -------
17      DURAND       1
192     DUPONT       2
44      DUVAL        3
11      DUMOULIN     4
741     DULIN        5
82      DUPOND       6
177     DURAND       7

PLC_REF  PLC_NUM
-------- -------
A01      1
A02      2
A03      3
A04      4
A05      5
B01      6
B02      7
B03      8
B04      9
B05      10
C01      11
C02      12
C03      13
C04      14
C05      15

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_NUM

Qui donne :

CLI_NOM      PLC_REF
------------ -------
DURAND       A01
DUPONT       A02
DUVAL        A03
DUMOULIN     A04
DULIN        A05
DUPOND       B01
DURAND       B02

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
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.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 :

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 1000

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 :

CLI_NOM                T_I_ENT
----------             ------------
DULIN                  1
DUMOULIN               2
DUPOND                 3
DUPONT                 4
DURAND                 5
DURAND                 6
DUVAL                  7

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 */
ORDER  BY 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 à 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_ENT

qui 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        1000

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
ORDER BY 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 !

Téléchargez l'article au format PDF