Les doublons : détection et éradication…

SQLPro

Les doublons sont des informations parasites qui polluent les données des bases. La plupart du temps ils sont générés lors des imports et fusions de données.
Voici différentes méthodes pour les détecter et les éradiquer.
Mais avant tout, commençons par définir les différents types de doublons… ♪

- Titre : Les doublons : détection et éradication…

- Auteur : SQLPro

- Parution : 23 juin 2004

- Licence : Copyright ® 2004 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.

Sommaire

- 1. Les différents types de doublons

- 2. Doublons absolus

- 2-1. Suppression par ajout d'une colonne discriminante

- 2-1-1. Utilisation d'un curseur

- 2-1-2. Utilisation d'une fonction de ranking

- 2-1-3. Suppression à l'aide d'une table temporaire

- 2-1-4. Suppression sans modification du schéma

- 3. Doublons relatifs

- 4. Quasi-doublons

1 - Les différents types de doublons

Nous devons distinguer les doublons absolus, les doublons relatifs et les quasi-doublons.

Les doublons absolus sont des tuples strictement identiques. Toutes les colonnes des lignes doublonnées doivent contenir les mêmes données. Compte tenu de la possibilité de présence d'une clef dans la plupart des tables, ces types de doublons ne se trouvent que dans les tables dépourvues de clef.

Exemple de doublons absolu :

NUM         NOM              PRENOM
----------- ---------------- --------
33          DUPONT           marc
33          DUPONT           marc
33          DUPONT           marc

Les doublons relatifs sont des tuples identiques sauf pour les valeurs composant la clef. À l'exception des colonnes formant la clef, les autres colonnes des lignes doublonnées doivent contenir les mêmes données. C'est le type de doublons le plus courant puisque la majorité des tables sont pourvues de clefs.

Exemple de doublons relatifs :

NUM         NOM              PRENOM
----------- ---------------- --------
47          DUPOND           alain
59          DUPOND           alain

Les quasi-doublons sont constitués par des tuples dont le contenu sémantique et logique est le même, avec des petites différences comme une différentiation majuscules/minuscules ou des fautes de frappe dues à des erreurs de saisie.

Exemple de quasi-doublons :

NUM         NOM              PRENOM
----------- ---------------- --------
65          Dupond           Frédéric
78          DUPOND           frédéric
81          DUPOND           fréd
99          DUPON            éric

Nous allons maintenant voir comment détecter puis éradiquer chacun de ces types de doublons. Mais avant cela, voici notre jeu d'essais :

CREATE TABLE T_DOUBLON
(NUM    INT,
NOM    VARCHAR(32),
PRENOM VARCHAR(16))

INSERT INTO T_DOUBLON VALUES (33, 'DUPONT', 'marc')
INSERT INTO T_DOUBLON VALUES (33, 'DUPONT', 'marc')
INSERT INTO T_DOUBLON VALUES (33, 'DUPONT', 'marc')
INSERT INTO T_DOUBLON VALUES (47, 'DUPOND', 'alain')
INSERT INTO T_DOUBLON VALUES (59, 'DUPOND', 'alain')
INSERT INTO T_DOUBLON VALUES (65, 'Dupond',  'Frédéric')
INSERT INTO T_DOUBLON VALUES (78, 'DUPOND', 'frédéric')
INSERT INTO T_DOUBLON VALUES (81, 'DUPOND', 'fréd')
INSERT INTO T_DOUBLON VALUES (99, 'DUPON',  'éric')

2 - Doublons absolus

Le principe de détection des doublons absolu est simple. Il s'agit de compter les lignes avec un groupage de toutes les colonnes et d'introduire un filtre sur les résultats du comptage en détectant les valeurs supérieures à 1 :

SELECT COUNT(*) AS NBR_DOUBLES, NUM, NOM, PRENOM
FROM   T_DOUBLON
GROUP  BY NUM, NOM, PRENOM
HAVING COUNT(*) > 1

NBR_DOUBLES NUM         NOM              PRENOM
----------- ----------- ---------------- --------
3           33          DUPONT           marc

Si ce type de doublon est d'une simplicité enfantine à détecter, il n'en va pas de même pour le supprimer… En effet, il convient de conserver au moins une ligne et de supprimer le surplus. Or comme toute l'information est semblable, toutes les lignes seront supprimées, à moins, et ce sera notre solution, d'introduire un discriminant…

2-1 - Suppression par ajout d'une colonne discriminante

La technique consiste à rajouter une colonne, alimenter cette colonne avec des valeurs toutes différentes, des valeurs uniques pouvant servir de clef. Pour alimenter cette colonne, on peut utiliser un curseur pour numéroter ou si votre SGBDR en dispose, en utilisant une fonction de ranking ou de génération d'identifiant.

2-1-1 - Utilisation d'un curseur

Voici un exemple pour SQL Server :

ALTER TABLE T_DOUBLON
ADD COLID INT

DECLARE @i INT
DECLARE @colid INT

SET @i = 1

DECLARE CURSEUR_DOUBLON CURSOR
FOR
SELECT COLID
FROM   T_DOUBLON
FOR UPDATE

OPEN CURSEUR_DOUBLON

FETCH CURSEUR_DOUBLON INTO @colid

WHILE @@FETCH_STATUS = 0
BEGIN

UPDATE T_DOUBLON
SET    COLID = @i
WHERE  CURRENT OF CURSEUR_DOUBLON

SET @i = @i + 1

FETCH CURSEUR_DOUBLON INTO @colid

END

CLOSE CURSEUR_DOUBLON

DEALLOCATE CURSEUR_DOUBLON

NUM         NOM              PRENOM   COLID
----------- ---------------- -------- -----------
33          DUPONT           marc     1
33          DUPONT           marc     2
33          DUPONT           marc     3
47          DUPOND           alain    4
59          DUPOND           alain    5
65          Dupond           Frédéric 6
78          DUPOND           frédéric 7
81          DUPOND           fréd     8
99          DUPON            éric     9

Dès lors, pour supprimer les doublons « 33 DUPONT marc » il suffit d'une simple requête basique :

DELETE
FROM   T_DOUBLON T
WHERE  T.COLID < ANY (SELECT COLID
FROM   T_DOUBLON T2
WHERE  T.COLID <> T2.COLID
AND  T.NUM = T2.NUM
AND  T.NOM    = T2.NOM
AND  T.PRENOM = T2.PRENOM)

NUM         NOM              PRENOM   COLID
----------- ---------------- -------- -----------
33          DUPONT           marc     3
47          DUPOND           alain    4
59          DUPOND           alain    5
65          Dupond           Frédéric 6
78          DUPOND           frédéric 7
81          DUPOND           fréd     8
99          DUPON            éric     9

Bien entendu on peut maintenant supprimer la colonne COLID introduite pour nos besoins de suppression…

2-1-2 - Utilisation d'une fonction de ranking

Une fonction de ranking, permet de donner un numéro de rang à des lignes d'une table. Certains SGBDR permettent l'utilisation d'une telle fonction comme rowid. Le principe est alors le suivant :

- ajouter la nouvelle colonne ;

- alimenter cette colonne avec la fonction de ranking ;

- supprimer les données par requête ;

- supprimer la colonne de ranking.

Voici un exemple qui utilise une fonction générant un unique identifier ou GUID, (SQL Server) :

ALTER TABLE T_DOUBLON
ADD COLUID uniqueidentifier

NUM         NOM              PRENOM   COLUID
----------- ---------------- -------- ------------------
33          DUPONT           marc     NULL
33          DUPONT           marc     NULL
33          DUPONT           marc     NULL
47          DUPOND           alain    NULL
59          DUPOND           alain    NULL
65          Dupond           Frédéric NULL
78          DUPOND           frédéric NULL
81          DUPOND           fréd     NULL
99          DUPON            éric     NULL

UPDATE T_DOUBLON
SET    COLUID = newid()

NUM         NOM              PRENOM   COLUID
----------- ---------------- -------- ------------------------------------
33          DUPONT           marc     2FEB898A-709C-4C8B-9A4D-DDE82D73CA06
33          DUPONT           marc     659DB730-B4F3-4078-A21F-9A2250CE4284
33          DUPONT           marc     DE8C63A6-3940-4246-AB6C-5BBA122A4507
47          DUPOND           alain    82A33D79-2806-4FA7-AD95-F6B209D18424
59          DUPOND           alain    EE8F99EE-4E25-47A2-8988-1D7702A61A35
65          Dupond           Frédéric 28B3CAD0-8977-46EB-81A2-409B098C4087
78          DUPOND           frédéric 12A11D89-0448-46EF-B8F5-988BCB380598
81          DUPOND           fréd     D75E6872-0026-4051-83D2-648C63BA8ED6
99          DUPON            éric     D45C8563-DF53-4800-A310-DE2869380D6B

DELETE
FROM   T_DOUBLON T
WHERE  T.COLUID > ANY
(SELECT COLUID
FROM   T_DOUBLON T2
WHERE  T.COLUID <> T2.COLUID
AND  T.NUM    = T2.NUM
AND  T.NOM    = T2.NOM
AND  T.PRENOM = T2.PRENOM)

NUM         NOM              PRENOM   COLUID
----------- ---------------- -------- ------------------------------------
33          DUPONT           marc     DE8C63A6-3940-4246-AB6C-5BBA122A4507
47          DUPOND           alain    82A33D79-2806-4FA7-AD95-F6B209D18424
59          DUPOND           alain    EE8F99EE-4E25-47A2-8988-1D7702A61A35
65          Dupond           Frédéric 28B3CAD0-8977-46EB-81A2-409B098C4087
78          DUPOND           frédéric 12A11D89-0448-46EF-B8F5-988BCB380598
81          DUPOND           fréd     D75E6872-0026-4051-83D2-648C63BA8ED6
99          DUPON            éric     D45C8563-DF53-4800-A310-DE2869380D6B

ALTER TABLE T_DOUBLON
DROP COLUMN COLUID

NUM         NOM              PRENOM
----------- ---------------- --------
33          DUPONT           marc
47          DUPOND           alain
59          DUPOND           alain
65          Dupond           Frédéric
78          DUPOND           frédéric
81          DUPOND           fréd
99          DUPON            éric

Cette élégante solution est préférable dans le cas ou votre SGBDR est doté d'une telle fonctionnalité.

2-1-3 - Suppression à l'aide d'une table temporaire

Une autre formule pour éliminer des doublons, consiste à utiliser une table temporaire de même structure que l'on alimente avec les doublons rendus uniques par le mot clef DISTINCT. On élimine alors tous les doublons de la table d'origine, puis on réinjecte le contenu de la table temporaire dans la table d'origine.

Voici un exemple en SQL Server :

SELECT DISTINCT NUM, NOM, PRENOM
INTO   T_DOUBLON_TMP
FROM   T_DOUBLON
GROUP  BY NUM, NOM, PRENOM
HAVING COUNT(*) > 1

DELETE
FROM T_DOUBLON T1
WHERE  EXISTS (SELECT *
FROM   T_DOUBLON T2
WHERE  T1.NUM = T2.NUM
AND  T1.NOM = T2.NOM
AND  T1.PRENOM = T2.PRENOM
GROUP  BY NUM, NOM, PRENOM
HAVING COUNT(*) > 1)

NUM         NOM              PRENOM
----------- ---------------- --------
47          DUPOND           alain
59          DUPOND           alain
65          Dupond           Frédéric
78          DUPOND           frédéric
81          DUPOND           fréd
99          DUPON            éric

INSERT INTO T_DOUBLON
SELECT NUM, NOM, PRENOM
FROM   T_DOUBLON_TMP

NUM         NOM              PRENOM
----------- ---------------- --------
33          DUPONT           marc
47          DUPOND           alain
59          DUPOND           alain
65          Dupond           Frédéric
78          DUPOND           frédéric
81          DUPOND           fréd
99          DUPON            éric

DROP TABLE T_DOUBLON_TMP

2-1-4 - Suppression sans modification du schéma

Il arrive que les utilisateurs n'aient pas les droits nécessaires sur la base pour modifier le schéma et en particulier ajouter ou supprimer une colonne à une table ou encore créer et détruire une table, même temporaire.

Une solution utile dans ce cas consiste à ajouter de l'information dans une des colonnes déjà constituées de la table.

Le choix de la colonne dans laquelle nous allons rajouter de l'information doit être dicté par les éléments suivants :

- colonne peu sollicitée en recherche et pas liée à une autre table (clef étrangère) ;

- colonne contenant encore assez d'espace libre pour ajouter au moins un chiffre.

Dans notre exemple, c'est à l'évidence la colonne NOM qui comporte le maximum d'espace libre. Mais il y a fort à parier que c'est aussi la plus sollicitée en recherche. En revanche, la colonne PRENOM est probablement la moins sollicitée. La taille de la colonne est de 16 caractères et elle est remplie au maximum à 8. Il nous reste donc 8 caractères, ce qui permet en théorie d'aller de 0 à 99 999 999 soit jusqu'à la numérotation de 100 millions de lignes… Largement suffisant évidemment dans notre cas.
Mais pour faciliter le « retour en arrière » et donc nettoyer plus facilement cette colonne, nous allons utiliser un caractère de marquage… Voyons comment faire, à l'aide d'un exemple pour SQL Server :

DECLARE @prenom VARCHAR(16)
DECLARE @i INT

SET @i = 0

DECLARE CURSEUR_DOUBLON CURSOR
FOR
SELECT PRENOM
FROM   T_DOUBLON
FOR UPDATE

OPEN CURSEUR_DOUBLON

FETCH CURSEUR_DOUBLON INTO @prenom

WHILE @@FETCH_STATUS = 0
BEGIN

UPDATE T_DOUBLON
SET    PRENOM = @prenom + '#' + CAST(@i AS VARCHAR(7))
WHERE  CURRENT OF CURSEUR_DOUBLON

SET @i = @i + 1

FETCH CURSEUR_DOUBLON INTO @prenom

END

CLOSE CURSEUR_DOUBLON

DEALLOCATE CURSEUR_DOUBLON

NUM         NOM         PRENOM
----------- ----------- ----------------
33          DUPONT      marc#0
33          DUPONT      marc#1
33          DUPONT      marc#2
47          DUPOND      alain#3
59          DUPOND      alain#4
65          Dupond      Frédéric#5
78          DUPOND      frédéric#6
81          DUPOND      fréd#7
99          DUPON       éric#8

DELETE
FROM T_DOUBLON T1
WHERE  T1.PRENOM > ANY (SELECT T2.PRENOM
FROM   T_DOUBLON T2
WHERE  T1.NUM = T2.NUM
AND  T1.NOM = T2.NOM
AND  T1.PRENOM <> T2.PRENOM)

NUM         NOM         PRENOM
----------- ----------- ----------------
33          DUPONT      marc#0
47          DUPOND      alain#3
59          DUPOND      alain#4
65          Dupond      Frédéric#5
78          DUPOND      frédéric#6
81          DUPOND      fréd#7
99          DUPON       éric#8

UPDATE T_DOUBLON
SET    PRENOM =
SUBSTRING(PRENOM,
1,
CHARINDEX('#', PRENOM) -1)

NUM         NOM         PRENOM
----------- ----------- ----------------
33          DUPONT      marc
47          DUPOND      alain
59          DUPOND      alain
65          Dupond      Frédéric
78          DUPOND      frédéric
81          DUPOND      fréd
99          DUPON       éric

On voit immédiatement l'intérêt d'avoir ajouté le marqueur « # » afin de nettoyer au plus vite la colonne polluée par notre discriminant…

CONSEIL : avant de choisir votre discriminant, assurez-vous qu'il n'est pas présent dans la colonne en cherchant par requête les colonnes contenant un tel caractère. Pour cela, utilisez le LIKE de SQL ou mieux, une fonction de recherche de caractère.

3 - Doublons relatifs

Le traitement et la détection des doublons relatifs sont bien plus simples puisque le discriminant, en général la clef, est déjà présent dans la table.

Voici un exemple de détection de tels doublons :

SELECT DISTINCT *
FROM   T_DOUBLON T1
WHERE  EXISTS (SELECT *
FROM   T_DOUBLON T2
WHERE  T1.NUM <> T2.NUM
AND  T1.NOM    = T2.NOM
AND  T1.PRENOM = T2.PRENOM)

NUM         NOM                              PRENOM
----------- -------------------------------- ----------------
47          DUPOND                           alain
59          DUPOND                           alain

Et voici comment les éradiquer :

DELETE
FROM   T_DOUBLON T
WHERE  T.NUM < ANY (SELECT NUM
FROM   T_DOUBLON T2
WHERE  T.NUM <> T2.NUM
AND  T.NOM    = T2.NOM
AND  T.PRENOM = T2.PRENOM)

NUM         NOM                              PRENOM
----------- -------------------------------- ----------------
33          DUPONT                           marc
33          DUPONT                           marc
33          DUPONT                           marc
59          DUPOND                           alain
65          Dupond                           Frédéric
78          DUPOND                           frédéric
81          DUPOND                           fréd
99          DUPON                            éric

4 - Quasi-doublons

Le cas des quasi-doublons est bien plus délicat. En effet il faut s'entendre sur la valeur de l'information. Néanmoins une technique classique pour en débusquer la plupart est de combiner une recherche partielle et le nivellement de la casse.

Exemple :

SELECT DISTINCT *
FROM   T_DOUBLON T1
WHERE  EXISTS
(SELECT *
FROM   T_DOUBLON T2
WHERE  T1.NUM <> T2.NUM
AND  (LOWER(T1.NOM)    LIKE '%' + LOWER(T2.NOM) + '%'    OR LOWER(T2.NOM) LIKE '%' + LOWER(T1.NOM)+'%')
AND  (LOWER(T1.PRENOM) LIKE '%' + LOWER(T2.PRENOM) + '%' OR LOWER(T2.PRENOM) LIKE '%' + LOWER(T1.PRENOM) + '%'))

NUM         NOM                              PRENOM
----------- -------------------------------- ----------------
65          Dupond                           Frédéric
78          DUPOND                           frédéric
81          DUPOND                           fréd
99          DUPON                            éric

Bien entendu leur éradication répond à la même problématique et appelle les mêmes réponses que celles vues précédemment.