Les données cycliques

L’auto-jointure

On qualifie de cyclique une structure de données qui fait directement ou non, référence à elle-même. On parle aussi de relation récursive.

On qualifie de auto-jointure une jointure d’une table avec elle-même.

Soit la relation Personnes suivante :

Personnes (numero, nom, prenom, responsable*)

Cette relation est cyclique car elle contient une colonne responsable qui fait référence à la clé primaire numero de la table Personnes elle-même.

Le rôle de cette colonne est de désigner le responsable direct de chaque personne, s’il existe.

erDiagram

    Personnes {
        int numero PK
        string nom
        int responsable FK
    }
    
    Personnes |o--o{ Personnes : "responsable"

SELECT *
FROM Personnes

Résultat :

Personnes
numero	nom	responsable
p1	Mercier
p2	Durant
p3	Noirons	p1
p4	Dupont	p1
p5	Verger	p4
p6	Dupond	p4
p7	Dermiez	p6
p8	Anciers	p2

Graphiquement, on peut représenter la relation Personnes sous forme de graphe orienté :

La table Personnes permet de répondre à la question suivante :

Donner, pour chaque personne S (pour subordonné) ayant un responsable R, le numero et le nom de celui-ci :

SELECT S.numero AS numeroS, R.numero AS numeroR, R.nom AS nomR
FROM Personnes S, Personnes R
WHERE S.responsable = R.numero;

Résultat :

Personnes
numeroS	numeroR	nomR
p3	p1	Mercier
p4	p1	Mercier
p5	p4	Dupont
p6	p4	Dupont
p7	p6	Dupond
p8	p2	Durant

Cette requête construit des couples de Personnes, la première étant la personne subordonnée S et la seconde son responsable R

Elle réalise donc une jointure de la table Personnes avec elle-même, ce qu’on appelle une auto-jointure

Aide

Il faut imaginer que la table Personnes est dupliquée en deux tables S et R qui sont ensuite jointes, comme si elles étaient deux tables distinctes.

Requêtes cycliques

Donner pour chaque personne dont le nom est Dupont, son numéro ainsi que le numéro et le nom de son responsable s’il existe :

SELECT S.numero AS numeroS, S.nom AS nomS, R.numero AS numeroR, R.nom AS nomR
FROM Personnes S, Personnes R
WHERE S.responsable = R.numero AND S.nom = 'Dupont'
UNION
SELECT numero, nom, '__' , '__'
FROM Personnes
WHERE responsable IS NULL AND Nom = 'Dupont' ;

Résultat :

Personnes
numeroS	nomS	numeroR	nomR
p4	Dupont	p1	Mercier

Donner, pour chaque personne subordonnée à la personne de numéro p4 , son numéro et son nom. On ignorera les personnes qui n’ont pas de responsable.

SELECT SS.numero, SS.nom
FROM Personnes R, Personnes S, Personnes SS
WHERE R.numero = 'p4'
AND R.numero = S.responsable
AND S.numero = SS.responsable ;

Résultat :

Personnes
numero	nom
p7	Dermiez

Remarques :

• Nous obtenons ici les subordonnées de niveau 2 en effectuant une double jointure
• Il est impossible d’effectuer des jointures récursivement
• Cette requête montre que SQL ne permet pas d’obtenir facilement les responsables directs et indirects d’une personne déterminée sans recourir à la programmation procédurale

Un autre exemple

On modélise une nomenclature de produits.

Chaque produit est composé de sous-produits, qui sont eux-même composés de sous-produits, etc.

PRODUIT (NPRO, LIBELLE, PRIX_U, POIDS_U)
COMPOSITION (COMPOSE, COMPOSANT, QTE)

Remarques

• Un produit est identifié par son numéro NPRO, son libellé LIBELLE, son prix unitaire PRIX_U et son poids unitaire POIDS_U.
• La relation COMPOSITION décrit la composition des produits : Chaque ligne de la relation COMPOSITION indique que le produit identifié par COMPOSE est composé du produit identifié par COMPOSANT en quantité QTE.
• Seuls les produits composés ont une entrée dans la relation COMPOSITION.
• Un produit peut être composé de plusieurs produits, et un produit peut être le composant de plusieurs produits.
• La relation COMPOSITION est une relation réflexive : un produit peut être composé de lui-même.
• La relation COMPOSITION est une relation symétrique : si le produit A est composé du produit B, alors le produit B est le composant du produit A.
• Seuls les composants finaux ont un prix et un poids unitaires.

La table COMPOSITION représente les relations de composition entre produits

Une ligne (h, b, q) indique que le produit b est un composant du produit h, et qu’il faut q unités de b pour fabriquer 1 unité de h

Les matières premières ont un prix et un poids unitaires fixés.

Le prix et le poids des autres produits peuvent être déterminés à partir des caractéristiques de leurs composants :

Produits
NPRO	LIBELLE	PRIX_U	POIDS_U
p1	A-200
p2	A-056
p3	B-661
p4	B-122
p5	B-326
p6	D-822	3.5	0.7
p7	D-507	8	0.25
p8	G-993	5	1.15
p9	F-016
p10	J-500
p11	J-544	0.5	0.9
p12	L-009	1.7	2.3

Produits
COMPOSE	COMPOSANT	QTE
p1	p2	2
p1	p3	1
p1	p4	2
p2	p7	8
p2	p8	2
p3	p8	5
p4	p8	4
p4	p9	5
p4	p10	5
p5	p4	2
p5	p6	7
p9	p11	2
p10	p11	4
p10	p12	3

Donner les informations relatives aux produits p4 ainsi que sa composition :

SELECT H.NPRO, H.LIBELLE , C.QTE, B.LIBELLE AS libelleB
FROM PRODUIT H, COMPOSITION C, PRODUIT B
WHERE C.COMPOSE = H.NPRO
AND C.COMPOSANT = B.NPRO
AND H.NPRO = 'p4' ;

Résultat :

Composition
NPRO	LIBELLE	QTE	libelleB
p4	B-122	4	G-993
p4	B-122	5	F-016
p4	B-122	5	J-500

Dans cette requête, H et B désigne respectivement le produit composé (haut) et le produit composant (bas)

Encore une fois, on réalise une auto-jointure de la table PRODUIT pour obtenir les informations relatives à la composition du produit p4.

Aide à la compréhension

Il faut imaginer que la table PRODUIT est dupliquée en deux tables H et B qui sont ensuite jointes, comme si elles étaient deux tables distinctes.

Avec la syntaxe JOIN

SELECT H.NPRO, H.LIBELLE , C.QTE, B.LIBELLE
FROM PRODUIT H
JOIN COMPOSITION C
ON C.COMPOSE = H.NPRO
JOIN PRODUIT B
ON C.COMPOSANT = B.NPRO
WHERE H.NPRO = 'p4' ;

Résultat :

Produits
NPRO	LIBELLE	QTE
p4	G-993	4
p4	F-016	5
p4	J-500	5

Un autre exemple, plus complexe :

Donner le prix et poids unitaires d’un produit fini ou semi-fini dont tous les composants ont un poids et un prix unitaires.

SELECT

  PH.NPRO,
  SUM(QTE*PB.PRIX_U),
  SUM(QTE*PB.POIDS_U)

FROM PRODUIT PH, COMPOSITION C, PRODUIT PB

WHERE
  PH.NPRO = C.COMPOSE
  AND C.COMPOSANT = PB.NPRO
  AND NOT EXISTS (
      SELECT *
      FROM COMPOSITION CC, PRODUIT BB
      WHERE
          CC.COMPOSANT = BB.NPRO
          AND CC.COMPOSE = PH.NPRO
          AND (BB.PRIX_U is null OR BB.POIDS_U is null)
      )
GROUP BY PH.NPRO
;

Résultat :

Produits
NPRO	SUM(QTE*PB.PRIX_U)	SUM(QTE*PB.POIDS_U)
p10	7.1	10.5
p2	74	4.3
p3	25	5.75
p9	1	1.8

Conclusion

• Les requêtes cycliques ou récursives sont des requêtes qui font référence d’une table à elle-même.
• Elles sont souvent utilisées pour modéliser des structures de données hiérarchiques ou des relations de composition.
• En SQL, il est possible de réaliser des requêtes cycliques en effectuant des auto-jointures de tables.
• Les requêtes récursives sont plus complexes à réaliser et nécessitent souvent de recourir à des procédures stockées ou à des langages de programmation.