Les doublons : détection et éradication...

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

Article lu   fois.

L'auteur

Site personnelSite personnel

Liens sociaux

Viadeo Twitter Google Bookmarks ! Facebook Digg del.icio.us Yahoo MyWeb Blinklist Netvouz Reddit Simpy StumbleUpon Bookmarks Share on Google+ 

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 :

 
Sélectionnez

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. A 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 :

 
Sélectionnez

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

Les quasis 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 :

 
Sélectionnez

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 :

 
Sélectionnez

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

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ésultat du comptage en détectant les valeurs supérieures à 1 :

 
Sélectionnez

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

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 colonnes 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 :

 
Sélectionnez

ALTER TABLE T_DOUBLON
      ADD COLID INT
 
 
Sélectionnez

 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
 
Sélectionnez

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 :

 
Sélectionnez

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)
 
Sélectionnez

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

 
Sélectionnez

ALTER TABLE T_DOUBLON
      ADD COLUID uniqueidentifier
 
Sélectionnez

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
 
Sélectionnez

UPDATE T_DOUBLON
SET    COLUID = newid()
 
Sélectionnez

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
 
Sélectionnez

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)
 
Sélectionnez

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
 
Sélectionnez

ALTER TABLE T_DOUBLON
      DROP COLUMN COLUID
 
Sélectionnez

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 rendu unique 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 :

 
Sélectionnez

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

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)
 
Sélectionnez

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
 
Sélectionnez

INSERT INTO T_DOUBLON
SELECT NUM, NOM, PRENOM
FROM   T_DOUBLON_TMP
 
Sélectionnez

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
 
Sélectionnez

DROP TABLE T_DOUBLON_TMP
 

2.1.4. Suppression sans modification du schema

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é 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é en recherche. En revanche, la colonne PRENOM est probablement la moins sollicité. 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 :

 
Sélectionnez

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 
 
Sélectionnez

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
 
Sélectionnez

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)
 
Sélectionnez

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
 
Sélectionnez

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

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 utiliser le LIKE de SQL ou mieux, une fonction de recherche de caractère.

3. Doublons relatifs

Le traitement et la détection des doublons relatif est bien plus simple 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 :

 
Sélectionnez

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)
 
Sélectionnez

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

Et voici comment les éradiquer :

 
Sélectionnez

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)
 
Sélectionnez

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 :

 
Sélectionnez

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) + '%'))
 
Sélectionnez

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 apelle les mêmes réponses que celles vues précédemment.

Livres
SQL - développement
SQL - le cours de référence sur le langage SQL
Avant d'aborder le SQL
Définitions
SGBDR fichier ou client/serveur ?
La base de données exemple (gestion d'un hôtel)
Modélisation MERISE
Mots réservés du SQL
Le SQL de A à Z
Les fondements
Le simple (?) SELECT
Les jointures, ou comment interroger plusieurs tables
Groupages, ensembles et sous-ensembles
Les sous-requêtes
Insérer, modifier, supprimer
Création des bases
Gérer les privilèges ("droits")
Toutes les fonctions de SQL
Les techniques des SGBDR
Les erreur les plus fréquentes en SQL
Les petits papiers de SQLPro
Conférence Borland 2003
L'héritage des données
Données et normes
Modélisation par méta données
Optimisez votre SGBDR et vos requêtes SQL
Le temps, sa mesure, ses calculs
QBE, le langage de ZLOOF
Des images dans ma base
La jointure manquante
Clefs auto incrémentées
L'indexation textuelle
L'art des "Soundex"
Une seule colonne, plusieurs données
La division relationnelle, mythe ou réalité ?
Gestion d'arborescence en SQL
L'avenir de SQL
Méthodes et standards
Les doublons
SQL Server
Eviter les curseurs
Un aperçu de TRANSACT SQL V 2000
SQL Server 2000 et les collations
Sécurisation des accès aux bases de données SQL Server
Des UDF pour SQL Server
SQL Server et le fichier de log...
Paradox
De vieux articles publiés entre 1995 et 1999 dans la défunte revue Point DBF

  

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.