La jointure manquante !

Date de publication : 26/08/2003

Par SQLPro (autres articles) (CV)
 

niveau : intermédiaire

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.


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

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 5eme rang, tandis que DUVAL occupe non pas le 6eme, mais le 7eme 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 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
       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 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 !

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


Livres
SQL - développement
SQL - le cours de référence sur le langage SQL
Avant d'aborder le SQL
Définitions
SGBDR fichier ou client/serveur ?
La base de données exemple (gestion d'un hôtel)
Modélisation MERISE
Mots réservés du SQL
Le SQL de A à Z
Les fondements
Le simple (?) SELECT
Les jointures, ou comment interroger plusieurs tables
Groupages, ensembles et sous-ensembles
Les sous-requêtes
Insérer, modifier, supprimer
Création des bases
Gérer les privilèges ("droits")
Toutes les fonctions de SQL
Les techniques des SGBDR
Les erreur les plus fréquentes en SQL
Les petits papiers de SQLPro
Conférence Borland 2003
L'héritage des données
Données et normes
Modélisation par méta données
Optimisez votre SGBDR et vos requêtes SQL
Le temps, sa mesure, ses calculs
QBE, le langage de ZLOOF
Des images dans ma base
La jointure manquante
Clefs auto incrémentées
L'indexation textuelle
L'art des "Soundex"
Une seule colonne, plusieurs données
La division relationnelle, mythe ou réalité ?
Gestion d'arborescence en SQL
L'avenir de SQL
Méthodes et standards
Les doublons
SQL Server
Eviter les curseurs
Un aperçu de TRANSACT SQL V 2000
SQL Server 2000 et les collations
Sécurisation des accès aux bases de données SQL Server
Des UDF pour SQL Server
SQL Server et le fichier de log...
Paradox
De vieux articles publiés entre 1995 et 1999 dans la défunte revue Point DBF

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. Cette page est déposée.

 
 
Developpez.com

Nous contacter

Participez

Informations légales

 
Services

Forum SGBD & SQL

Blogs

Hébergement

 
Partenaires

Hébergement Web