Un peu de Sql : Union d’intervalles

On dispose d’un ensemble de ressources et de leurs disponibilités modélisées par une liste d’intervalles disjoints { BegDate , EndDate }. Concrètement, cet exercice s’applique sur une unique table :

create table dbo.tResourceAvailability
(
	ResourceID int not null,
	BegDate datetime not null,
	EndDate datetime not null,
);

Etant donné un ensemble de ResourceID (typiquement obtenu via d’autres tables et contraintes), il faut construire l’union des intervalles de disponibilité.

Cela ne semble pas excessivement compliqué. Mais ce n’est pas non plus trivial. Bref, c'est une bonne illustration d'un aspect du métier de développeur : résoudre un problème simple, avec une solution qui, si possible, l’est aussi… à condition de la trouver.

La première chose à faire en abordant un problème de ce type est de tout faire pour bien le visualiser mentalement. Un problème bien « vu » est souvent un problème résolu. En l’occurrence, il est judicieux de créer un jeu d’essai sur la base de la table ci-dessus. Un tel jeu d’essai doit être à la fois complet et simple... et parfois on peine. Ici ce n’est pas le cas : on peut se contenter de 5 ressources et de quelques créneaux répartis sur une plage d’une vingtaine « d’instants ».

La table ci-dessous présente le terrain de jeux :

  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
P0   B   E         B     E              
P1     B     E       B E                
P2   B     E           B   E       B E  
P3     B E                              
P4               B     E         B E    

Et ce que nous cherchons à obtenir est la ligne « d’union » ci-dessous :

U   B       E   B         E     B   E  

Tiens ! Tout se passe comme si l’on ne retenait que certains B ou certains E.

Tilt !... « Retenir » = « Filtrer »… = condition d’une clause where… cela semble compatible avec du Sql…

Il suffit de se poser la question : « Qu’est-ce qui fait que je garde tel B ou tel E ? ».

Prenez une minute pour regarder les deux tableaux ci-dessus…

Réponse : Les seuls B (ou E) à conserver sont ceux qui ne sont pas compris dans un autre intervalle.

On « voit » le problème à résoudre là… et on en entrevoit même la solution, il est temps de passer à l’action :

insert into dbo.tResourceAvailability( ResourceID, BegDate, EndDate )
 values( 0, '2001', '2003' ), ( 0, '2008', '2011' ),
       ( 1, '2002', '2005' ), ( 1, '2009', '2010' ),
	 ( 2, '2001', '2004' ), ( 2, '2010', '2012' ), ( 2, '2016', '2017' ),
	 ( 3, '2002', '2003' ), 
	 ( 4, '2007', '2010' ), ( 4, '2015', '2016' );

J’utilise une syntaxe d’insertion de lignes multiples standard Sql (mais disponible qu’à partir de Sql Server 2008), je ne mets que des années pour simplifier… et je procède tout doucement, étape par étape, en commençant par un select simple :

declare @T datetime = '2008';
select count(*)
	from dbo.tResourceAvailability a
	where BegDate <= @T and @T <= EndDate;

Cela calcule le nombre d’intervalles rencontrés à cette date. L’idée est la suivante (regarder le tableau) : pour un B que l’on doit conserver (par exemple 2007), le calcul donnera un (il se rencontrera lui-même), et pour un B qui ne doit pas être conservé, le calcul donnera 2 ou plus (outre lui-même, d’autres intervalles le contiennent). On progresse non ?

Oui mais… Le calcul donne 2 aussi pour 2001… car deux intervalles débutent pile sur cette date. Il est donc nécessaire d’affiner un peu. Idée : on change légèrement la condition de façon à, lorsque l’on cherche un B, ignorer les B strictement identiques à celui que l’on cherche. On enlève donc au moins un au résultat du calcul précédent, et les B que l’on garde seront ceux pour lequel on aura 0 intersection (et non plus une seule). On procède symétriquement pour E, on a donc deux requêtes légèrement différentes pour les B et les E :

declare @B datetime = '2005';
select count(*)
	from dbo.tResourceAvailability a
	where BegDate < @B and @B <= EndDate
	
declare @E datetime = '2012';
select count(*)
	from dbo.tResourceAvailability a
	where BegDate <= @E and @E < EndDate

J’ai utilisé l’opérateur count pour mieux « voir » mes requêtes, ce que je cherche à filtrer est tous les B et E qui ont un compte de 0, c’est-à-dire ceux qui n’existent pas.

select year(BegDate)
  from dbo.tResourceAvailability a
  where not exists( select * 
    from dbo.tResourceAvailability f 
    where BegDate < a.BegDate and a.BegDate <= EndDate );
Résultat :  2001  
   2001  ==> Doublon : un distinct le fera disparaitre.
   2007  
   2015  
select year(EndDate)
  from dbo.tResourceAvailability a
  where not exists( select * 
    from dbo.tResourceAvailability 
    where BegDate <= a.EndDate and a.EndDate < EndDate );
Résultat :  2005
   2012
   2017

Ce qui est presque parfait puisque nous cherchons à obtenir la liste d’intervalles suivante : 2001 – 2005, 2007 – 2012, 2015 - 2017

Nous avons le résultat final, mais « en deux morceaux ». Comment les réunir ? Avec une « union ». C’est une opération ensembliste on ne peut plus simple :

select year(BegDate)
  from dbo.tResourceAvailability a
  where not exists( select * 
    from dbo.tResourceAvailability 
    where BegDate < a.BegDate and a.BegDate <= EndDate )
union
select year(EndDate)
  from dbo.tResourceAvailability a
  where not exists( select * 
    from dbo.tResourceAvailability 
    where BegDate <= a.EndDate and a.EndDate < EndDate );
Résultat :  2001
   2005
   2007
   2012
   2015
   2017

On obtient tous les B, puis tous les E. Le doublon a disparu (2001) car c’est le comportement par défaut de l’union (pour ne pas filtrer les doublons, il faut explicitement utiliser union all). Il ne reste plus qu’à ordonner ces éléments en remarquant que l’on a nécessairement une séquence B, E, B, E, etc. Pour la rendre plus lisible, on le précise :

select 'B', year(BegDate)
  from dbo.tResourceAvailability a
  where not exists( select * 
    from dbo.tResourceAvailability 
    where BegDate < a.BegDate and a.BegDate <= EndDate )
union
select 'E', year(EndDate)
  from dbo.tResourceAvailability a
  where not exists( select * 
    from dbo.tResourceAvailability 
    where BegDate <= a.EndDate and a.EndDate < EndDate )
order by 2;
Résultat :  B  2001
   E  2005
   B  2007
   E  2012
   B  2015
   E  2017

On approche mais ce n’est pas encore idéal car on souhaite une forme de réponse similaire à celle de la donnée source : une liste d’intervalle, donc deux colonnes B et E. Transformer des lignes en colonnes, c’est le rôle de l’opérateur pivot, à condition de s’appuyer une fonction d’agrégation (count, sum, max, avg, etc.) : il ne nous est d’aucune utilité ici (en règle général, n’allez chercher l’opérateur pivot que s’il y a une agrégation possible ou souhaitable). Il nous faut trouver autre chose pour « mélanger » ces deux requêtes :

| 2001 |
  | 2012 |
  | 2001, 2005 |
| 2005 |
 x  | 2015 |
 ==>  | 2007, 2012 |
| 2007 |
  | 2017 |
  | 2015, 2017 |

Problème simple non ? Cherchez un peu…

……………

Le principe est de se servir de B comme « générateur », et de chercher la fin de l’intervalle correspondant :

select B = a.BegDate,
  	 E = << Take the first EndDate greater than a.BegDate >>
  from dbo.tResourceAvailability a
  where not exists( select * 
    from dbo.tResourceAvailability 
    where BegDate < a.BegDate and a.BegDate <= EndDate )

Ce qui revient à prendre la plus petite date supérieure à la date de début, et donne la requête finale suivante :

select distinct 
  B = BegDate,
  E = (select min(EndDate)
         from dbo.tResourceAvailability ae
	   where ae.EndDate > a.BegDate 
		and not exists( select * 
					from dbo.tResourceAvailability 
					where BegDate <= ae.EndDate 
and ae.EndDate < EndDate ))
  from dbo.tResourceAvailability a
  where not exists( select * 
			    from dbo.tResourceAvailability
			    where BegDate < a.BegDate and a.BegDate <= EndDate )

Une remarque sur les tris : Les dates obtenues peuvent être dans l’ordre croissant. C’est un hasard et il ne faut en aucun cas s’y fier  si vous voulez trier, triez explicitement (avec un order by).