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

 

Sexe aléatoire, nullité et Sql

Avec un titre comme ça, je suis sûr d’avoir 2 ou 3 lecteurs. Je lis actuellement « Sql for smarties » de Joe Celko. Tout n’est pas parfait dans ce livre, mais il y a certaines choses amusantes que je découvre avec plaisir : par exemple que le genre est normalisé par ISO 5218 « Information technology — Codes for the representation of human sexes ». Il s’agit d’un chiffre unique désigné dans le standard par « SEX » dont les quatre valeurs possibles sont :

  • 0 = inconnu (unknown),
  • 1 = homme (male),
  • 2 = femelle (female),
  • 9 = non applicable (not applicable).

Note 1 : Les rédacteurs du standard ont pris la peine de préciser que le fait que Homme était 1 et la Femme 2 n’avait aucune signification particulière... que cela était dû aux pays qui ont « poussé » ce standard. Et vous reconnaissez le premier chiffre du numéro de sécurité sociale français : c’est une preuve irréfutable du rayonnement culturel de la France dans le monde.

Note 2 : Sexe « non applicable » ne recouvre pas d’accident biologique particulier, il s’agit d’une valeur à utiliser pour des personnes morales (une entreprise n’est donc ni homme ni femme – bien au contraire aurait ajouté Pierre Dac).

Note 3 : Je viens, l’air de rien, de vous faire économiser 92 francs suisses, soit environ 65 euros. C’est en effet le prix à payer pour le PDF officiel de la norme ISO 5218. C’est scandaleux mais c’est comme ça : les standard ISO sont payants.

Revenons au SEX (avec ce billet, ce blog va perdre des points de ranking) et à SQL pour insister sur « l’inconnu » et le « non applicable ». Ces deux notions se cachent habituellement derrière le NULL, ici elles ont été explicitées et c’est une bonne chose d’un point de vue lisibilité/expressivité ainsi qu’en terme de mise en œuvre (moins on utilise de colonne NULLABLE, mieux on se porte et je ne vais pas faire ici le topo classique de la logique ternaire et des problèmes subtils introduits par le NULL car on les trouve partout).

Une autre découverte pour moi de la lecture du livre de Joe Celko est un aspect de l’instruction CASE que j’ignorais. Supposons que l’on veuille initialiser une valeur aléatoire pour un SEX. Nous avons 4 valeurs à tirer au sort (de façon équiprobable), le code suivant semble correct :

select case CAST( (4*rand()) as int )
          when 0 then '0' -- Unknown
          when 1 then '1' -- Male
          when 2 then '2' -- Female
          when 3 then '9' -- Unapplicable
       end

Et pourtant il ne l’est pas. Ci-dessous un test tout bête : il remplit 200 000 lignes d’une table avec une colonne SEX aléatoire selon le code précédent.

create table dbo.tTest( Sex char );
-- Caution: Declare and initialize in the same statement like this 
-- works only on Sql Server 2008, not 2005. 
declare @i int = 200000; 
while @i > 0
begin
	insert into dbo.tTest( Sex )
		select	case CAST( (4*rand()) as int )
					when 0 then '0' -- Unknown
					when 1 then '1' -- Male
					when 2 then '2' -- Female
					when 3 then '9' -- Unapplicable
				end
	set @i = @i-1;
end

Et on affiche le contenu de la table résultante avec le compte et la probabilité résultante.

select 	Sex, 
        COUNT(*), 
        Prob = cast(COUNT(*) as float)/200000 
    from dbo.tTest
   group by Sex
   order by 1;

Première observation : NULL apparait.

Deuxième constat : les nombres respectifs de valeurs (et donc leurs probabilités) ne sont pas équitablement répartis.

SexCountProb
NULL 63338 0,31669
0 50067 0,250335
1 37320 0,1866
2 27918 0,13959
9 21357 0,106785

Les matheux auront compris. L’instruction CASE est, en fait, réécrite ainsi :

select	case 
		when CAST( (4*rand()) as int ) = 0 then '0' -- Unknown
		when CAST( (4*rand()) as int ) = 1 then '1' -- Male
		when CAST( (4*rand()) as int ) = 2 then '2' -- Female
		when CAST( (4*rand()) as int ) = 3 then '9' -- Unapplicable
	end

Ce qui ne correspond pas du tout à l’idée initiale, et pouf pas marche.

La solution est évidemment de capturer la valeur fournie par la fonction rand() dans une variable:

declare @p int = CAST( (4*rand()) as int );
select	case @p
			when 0 then '0' -- Unknown
			when 1 then '1' -- Male
			when 2 then '2' -- Female
			when 3 then '9' -- Unapplicable
		end

N'incriminez pas SQL Server : ce sont les spécifications de SQL. C’est comme ça et pas autrement que le CASE doit être implémenté, la forme « classique » du switch-case que l’on connait dans de nombreux langages n’est pas celle réellement supportée par SQL, elle n’est qu’un sucre syntaxique autour du « râteau de si ». SQL ne connait vraiment que le râteau !

Pour finir, un exercice : montrer en calculant les probabilités formellement que le comportement observé (NULL et probabilités différentes) est parfaitement logique.