Le problème est le suivant : partant d’une table contenant des intervalles (périodes de temps, plage d’entiers ou autres…), c’est à dire une information continue bornée par deux colonnes (DEBUT et FIN par exemple), comment faire en sorte d’agréger ces intervalles lorsque certains se recoupent ?
Ce problème est assez générique. Par exemple il permet de savoir s’il y a une interruption dans la continuité d’un système résultant de multiples périodes.
Pour bien comprendre comment résoudre ce problème partons d’un exemple simple et d’un algorithme « force brute ».
Voici la table qui nous servira de modèle :
CREATE TABLE TIMELINE (DEBUT INT, FIN INT)
Nous allons tout d’abord y insérer uniquement deux palges dont la particularité est qu’elle se recouvrent par la fait que la fin de l’une est le début de l’autre :
INSERT INTO TIMELINE VALUES (5, 10)
Il semble à priori évident que la solution si elle existe, se trouve dans la combinaison de tous les débuts de toutes les plages par la fin de toutes ces mêmes plages.
D’où une première requête très simple faisant un produit cartésien :
SELECT DISTINCT PRE.DEBUT, DER.FIN
FROM TIMELINE PRE --> PRE pour premier
CROSS JOIN TIMELINE DER --> DER pour dernier
DEBUT FIN
----------- -----------
1 5
1 10
5 5
5 10
Dès à présent il nous saute aux yeux que la 3e ligne n’apporte rien car sa « durée » (ou distance, longueur) est zéro.
Ce genre de cas peut être éliminé par une non équi jointure plutôt que par le produit cartésien, ce qui apporte l’avantage de traiter dès le départ moins de lignes :
SELECT DISTINCT PRE.DEBUT, DER.FIN
FROM TIMELINE PRE
INNER JOIN TIMELINE DER
ON PRE.DEBUT < DER.FIN
DEBUT FIN
----------- -----------
1 5
1 10
5 10
Il s’agit maintenant d’éliminer les périodes pour lesquelles le début de l’une est supérieur au début de l’autre avec la même fin.
Ce qui peut être fait avec la condition supplémentaire suivante :
SELECT DISTINCT PRE.DEBUT, DER.FIN
FROM TIMELINE PRE
INNER JOIN TIMELINE DER
ON PRE.DEBUT < DER.FIN
AND NOT EXISTS (SELECT *
FROM TIMELINE SI1 --> SI1 pour Sous Intervalle 1
WHERE SI1.DEBUT < PRE.DEBUT
AND PRE.DEBUT <= SI1.FIN)
DEBUT FIN
----------- -----------
1 5
1 10
Bien entendu cela doit aussi être fait pour la borne de fin, ce qui conduit à l’amélioration suivante :
SELECT DISTINCT PRE.DEBUT, DER.FIN
FROM TIMELINE PRE
INNER JOIN TIMELINE DER
ON PRE.DEBUT < DER.FIN
AND NOT EXISTS (SELECT *
FROM TIMELINE SI1
WHERE (SI1.DEBUT < PRE.DEBUT
AND PRE.DEBUT = SI1.FIN)
OR (SI1.DEBUT = DER.FIN
AND DER.FIN < SI1.FIN))
DEBUT FIN
----------- -----------
1 10
A ce stade notre résultat semble être parfait, mais il n’en est rien, car notre jeu de données est insufisant à traduire toutes les problématiques.
Ajoutons y quelques lignes afin de savoir quand il fonctionne et quand il est en echec.
Insertion d’un intervalle inclus :
INSERT INTO TIMELINE VALUES (2, 4)
La requête précédente nous donne :
DEBUT FIN
----------- -----------
1 4
1 10
2 4
2 10
Ce qui est un résultat faux, mais se corrige en considérant que la comparaisons entre les bornes peut se faire par inégalité comme ceci :
SELECT DISTINCT PRE.DEBUT, DER.FIN
FROM TIMELINE PRE
INNER JOIN TIMELINE DER
ON PRE.DEBUT < DER.FIN
AND NOT EXISTS (SELECT *
FROM TIMELINE SI1
WHERE (SI1.DEBUT < PRE.DEBUT
AND PRE.DEBUT <= SI1.FIN)
OR (SI1.DEBUT <= DER.FIN
AND DER.FIN < SI1.FIN))
Insérons maintenant un intervalle englobant un autre intervalle :
INSERT INTO TIMELINE VALUES (0, 6)
La requête précédente, nous donne :
DEBUT FIN
----------- -----------
0 10
Ce qui est un résultat prévisible du fait des inégalités introduite par l’amélioration précédente.
Insérons maintenant un intervalle dissocié de tous les autres. Notre résultat devrait avoir deux lignes : le résultat précédent plus cette nouvelle ligne.
INSERT INTO TIMELINE VALUES (15, 20)
Or il n’en est rien :
DEBUT FIN
----------- -----------
0 10
0 20
15 20
Pour éliminer ce dernier effet de bord nous devons considérer qu’un intervalle doit être une continuité d’intervalle. Ou encore que pour tout intervalle il ne doit pas exister un non intervalle inclus. Cette double négation est-celle là même qui forme la division relationnelle selon la méthode du double NOT EXISTS… La requête finale s’écrit donc :
SELECT DISTINCT PRE.DEBUT, DER.FIN
FROM TIMELINE PRE
INNER JOIN TIMELINE DER
ON PRE.DEBUT < DER.FIN
WHERE NOT EXISTS (SELECT *
FROM TIMELINE SI1
WHERE (SI1.DEBUT < PRE.DEBUT
AND PRE.DEBUT <= SI1.FIN)
OR (SI1.DEBUT <= DER.FIN
AND DER.FIN < SI1.FIN))
AND NOT EXISTS (SELECT *
FROM TIMELINE SI2 --> SI2 pour Sous Intervalle 2
WHERE PRE.DEBUT < SI2.DEBUT
AND SI2.DEBUT <= DER.FIN
AND NOT EXISTS (SELECT *
FROM TIMELINE SI3 --> SI3 pour Sous Intervalle 3
WHERE SI3.DEBUT < SI2.DEBUT
AND SI2.DEBUT <= SI3.FIN))
Au fait, nous pouvons écrire cette requête sous forme de CTE :
WITH
T_INTERVALLES AS
(SELECT PRE.DEBUT AS D1, PRE.FIN AS F1,
DER.DEBUT AS D2, DER.FIN AS F2
FROM TIMELINE PRE
INNER JOIN TIMELINE DER
ON PRE.DEBUT < DER.FIN)
SELECT DISTINCT D1, F2
FROM T_INTERVALLES AS I
WHERE NOT EXISTS (SELECT *
FROM TIMELINE SI1
WHERE (SI1.DEBUT < D1
AND D1 <= SI1.FIN)
OR (SI1.DEBUT <= F2
AND F2 < SI1.FIN))
AND NOT EXISTS (SELECT *
FROM TIMELINE SI2 --> SI2 pour Sous Intervalle 2
WHERE D1 < SI2.DEBUT
AND SI2.DEBUT <= F2
AND NOT EXISTS (SELECT *
FROM TIMELINE SI3 --> SI3 pour Sous Intervalle 3
WHERE SI3.DEBUT < SI2.DEBUT
AND SI2.DEBUT <= SI3.FIN))
D’autres formulation de ce calcul existe sous forme de requête en table dérivée comme sous forme récursive.
Notons néanmoins que cette requête facile à expliquer possède l’inconvénient d’un coût assez élevé.
Tentons de comprendre l’évolution de son coût en fonction du volume des données.
-- ce code sert à insérer 400 lignes soit environ 8 Ko de données à chaque appel. (Syntaxe T-SQL/SQL Server)
DECLARE @NB INT, @DEB INT, @FIN INT;
SET @NB = 400;
WHILE @NB > 0
BEGIN
SET @DEB = 100000 * RAND();
SET @FIN = @DEB + 1000 * RAND();
INSERT INTO TIMELINE VALUES (@DEB, @FIN);
SET @NB = @NB - 1;
END
Voici les résultats de consommation d’IO (MS SQL Server)
-------------------------------------------------------------
Lignes| 400 | 800 | 1200 | 1600 |
-------------------------------------------------------------
IO | 236 360 | 776 004 | 1 670 043 | 2 943 618 |
-------------------------------------------------------------
-------------------------------------------------------------
Lignes| 2000 | 2400 | 2800 | 3200 |
-------------------------------------------------------------
IO | 4 519 013 | 6 641 549 | 9 021 330 | 11 847 356 |
-------------------------------------------------------------
Il existe bien entendu d’autres formulation de ce type de requête notamment de manière récursive. Il est aussi possible d’indexer les colonnes pour obtenir de meilleures performances. Mais l’influence de la distribution des données et du volume des lignes à traiter étant très forte il est difficile de donner des métriques précises.
Voici par exemple une solution donnée par Snodgrass :
WITH T
AS (SELECT F.DEBUT, L.FIN
FROM TIMELINE AS F
JOIN TIMELINE AS L
ON F.FIN <= L.FIN
CROSS JOIN TIMELINE AS E
GROUP BY F.DEBUT, L.FIN
HAVING COUNT(CASE
WHEN (E.DEBUT < F.DEBUT AND F.DEBUT <= E.FIN)
OR (E.DEBUT <= L.FIN AND L.FIN < E.FIN)
THEN 1
END) = 0)
SELECT DEBUT, MIN(FIN) AS FIN
FROM T
GROUP BY DEBUT
Exercice :
Voici un jeu d’essai assez simple représentant tous les cas de figure :
INSERT INTO TIMELINE VALUES (0, 5)
INSERT INTO TIMELINE VALUES (6, 10)
INSERT INTO TIMELINE VALUES (20, 25)
INSERT INTO TIMELINE VALUES (25, 30)
INSERT INTO TIMELINE VALUES (40, 55)
INSERT INTO TIMELINE VALUES (54, 60)
INSERT INTO TIMELINE VALUES (70, 80)
INSERT INTO TIMELINE VALUES (74, 76)
INSERT INTO TIMELINE VALUES (100, 120)
INSERT INTO TIMELINE VALUES (110, 130)
INSERT INTO TIMELINE VALUES (120, 140)
INSERT INTO TIMELINE VALUES (200, 250)
INSERT INTO TIMELINE VALUES (250, 280)
INSERT INTO TIMELINE VALUES (280, 290)
INSERT INTO TIMELINE VALUES (300, 390)
INSERT INTO TIMELINE VALUES (310, 380)
INSERT INTO TIMELINE VALUES (330, 360)
Qui doit conduire à la solution :
DEBUT FIN
----------- -----------
0 5
6 10
20 30
40 60
70 80
100 140
200 290
300 390
Autre solution…
Voici une manière récursive de traiter le problème :
WITH
T0 AS -- suprime les périodes incluses et calcule la durée
(SELECT DISTINCT Tout.*
FROM TIMELINE AS Tout
WHERE NOT EXISTS(SELECT *
FROM TIMELINE AS Tin
WHERE Tout.DEBUT >= Tin.DEBUT AND Tout.FIN < Tin.FIN)),
T1 AS -- ancres : périodes de tête...
(SELECT Ta.*, 1 AS ITERATION
FROM T0 AS Ta
WHERE NOT EXISTS(SELECT *
FROM T0 AS Tb
WHERE Tb.FIN >= Ta.DEBUT
AND Tb.FIN < Ta.FIN)
UNION ALL -- itération sur période dont le debut est inclus dans les bornes de la période ancre
SELECT T1.DEBUT, T0.FIN, T1.ITERATION + 1
FROM T1
INNER JOIN T0
ON T1.DEBUT < T0.DEBUT
AND T1.FIN >= T0.DEBUT
AND T1.FIN < T0.FIN),
T2 AS
(SELECT *, ROW_NUMBER() OVER(PARTITION BY DEBUT ORDER BY FIN - DEBUT DESC) AS N1,
ROW_NUMBER() OVER(PARTITION BY FIN ORDER BY FIN - DEBUT DESC) AS N2
FROM T1)
SELECT DEBUT, FIN
FROM T2
WHERE N1 = 1 AND N2 = 1;
--------
Frédéric Brouard, SQLpro - ARCHITECTE DE DONNÉES, http://sqlpro.developpez.com/
Expert bases de données relationnelles et langage SQL. MVP Microsoft SQL Server
www.sqlspot.com : modélisation, conseil, audit, optimisation, tuning, formation
* * * * * Enseignant CNAM PACA - ISEN Toulon - CESI Aix en Provence * * * * *
