String Comparison - Damerau-Levenshtein Algorithm

When creating a set of test records for a new Identity Insight installation, one of the things you will want to identify are pairs of string values that are similar, but not exact.  This applies to names, attributes, and numbers.

One way to evaluate the difference between two strings is to identify the changes needed to change one string to the other; the fewer the changes, the more similar the strings.  The Damerau-Levenshtein Distance algorithm counts the minimum number of insertions, deletions, substitutions, and transpositions needed to change one string to another.

Here is a Javascript function that implements the Damerau-Levenshtein algorithm.  This was written to run with cscript in a Windows environment.

function fnDamerauLevenshtein(a, b ) {
   
   //Initialize distance matrix
   var d = [];
   for (i = 0; i <= a.length; i++) {
      d[i] = [];
   }
   
   //If either string is zero length, then return the length of the other string (all insertions)
   if (a.length == 0)
      return b.length;
   if (b.length == 0)
      return a.length;
   
   //Populate initial values in matrix
   for(i = 0; i <= a.length; i++)
      d[i][0] = i;
   for(j = 0; j <= b.length; j++)
      d[0][j] = j;
   
   //Populate distance matrix
   for(i = 1; i<= a.length; i++) {
      for(j = 1; j <= b.length; j++) {
         if (a.substring(i-1, i) == b.substring(j-1, j))
            cost = 0;
         else
            cost = 1;
         
         //Levenshtein portion of algorithm, determines insertions, deletions, substitutions
         min1 = d[i - 1][j] + 1;
         min2 = d[i][j - 1] + 1;
         min3 = d[i - 1][j - 1] + cost;
         d[i][j] = Math.min(min1, min2, min3);
         
         //Damerau portion of algorithm, determines transpositions
         if(i > 1 && j > 1)
            if (a.substring(i-1, i) == b.substring(j - 2, j-1) && a.substring(i - 2, i-1) == b.substring(j-1, j))
               d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost);
      }
   }
   
   //The final distance value is stored in the last corner of the matrix
   return d[a.length][b.length];
}

WScript.Echo('Distance between ' + WScript.Arguments.Item(0) + ' and ' + WScript.Arguments.Item(1));
WScript.Echo(fnDamerauLevenshtein(WScript.Arguments.Item(0),WScript.Arguments.Item(1)));

Save the code as DamerauLevenshtein.js.  To test the code, open a command prompt and type:

>cscript DamerauLevenshtein.js accept except

Distance between accept and except
2

>

Display Entity History

This rather ugly Oracle query will display the history of an entity.  This includes each identity's creation, updates, and deletions, plus any merges that occurred.

set pagesize 0
set linesize 1000
define ent = &entity_id

column create_dt format a20
column typ format a20
column subtyp format a20
column result format a200

break on create_dt skip 1 on entity_id on dsrc_acct_id;

select to_char(d.sys_create_dt, 'YYYY-MM-DD HH24:MI:SS') create_dt, 
    coalesce(( select distinct org_entity_id    
               from er_relocation e 
               where e.dsrc_acct_id = d.dsrc_acct_id 
               and action_date = (select min(action_date) 
                                  from er_relocation 
                                  where dsrc_acct_id = e.dsrc_acct_id 
                                  and action_date > d.sys_create_dt)
              )
              ,entity_id) entity_id, 
    dsrc_acct_id, 
    'Account Created' typ, 
    '' subtyp, 
    dsrc_code || ' ' || dsrc_acct result 
from dsrc_acct d 
join dsrc_code c on d.dsrc_id = c.dsrc_id 
where d.entity_id = &ent
    union
select to_char(d.sys_delete_dt, 'YYYY-MM-DD HH24:MI:SS') create_dt, 
    coalesce(( select distinct org_entity_id 
               from er_relocation e 
               where e.dsrc_acct_id = d.dsrc_acct_id 
               and action_date = (select min(action_date)                                              from er_relocation 
                                  where dsrc_acct_id = e.dsrc_acct_id 
                                  and action_date > d.sys_delete_dt)
                )
                ,entity_id) entity_id, 
    dsrc_acct_id, 
    'Account Deleted' typ, 
    '' subtyp, 
    dsrc_code || ' ' || dsrc_acct result 
from dsrc_acct d 
join dsrc_code c on d.dsrc_id = c.dsrc_id 
where d.entity_id = &ent 
and d.sys_delete_dt is not null
    union
select to_char(sys_create_dt, 'YYYY-MM-DD HH24:MI:SS') create_dt, 
    coalesce(( select distinct org_entity_id 
               from er_relocation e 
               where e.dsrc_acct_id = n.dsrc_acct_id 
               and action_date = (select min(action_date) 
                                  from er_relocation 
                                  where dsrc_acct_id = e.dsrc_acct_id 
                                  and action_date > n.sys_create_dt)
               )
               ,entity_id) entity_id, 
    dsrc_acct_id, 
    'Name' typ, 
    '' subtyp, 
    rtrim(coalesce(name_pfx||' ','') || coalesce(first_name||' ','') || coalesce(mid_name||' ','') || coalesce(last_name||' ','') || coalesce(name_gen||' ','') || coalesce(name_sfx,'')) result 
from name n 
where entity_id = &ent
    union
select to_char(sys_create_dt, 'YYYY-MM-DD HH24:MI:SS') create_dt, 
    coalesce(( select distinct org_entity_id 
               from er_relocation e    
               where e.dsrc_acct_id = a.dsrc_acct_id 
               and action_date = (select min(action_date)                                           from er_relocation 
                                  where dsrc_acct_id = e.dsrc_acct_id 
                                  and action_date > a.sys_create_dt)
               )
               ,entity_id) entity_id, 
    dsrc_acct_id, 
    'Address' typ, 
    '' subtyp, 
    rtrim(coalesce(addr1||' ','') || coalesce(addr2||' ','') || coalesce(addr3||' ','') || coalesce(city||' ','') || coalesce(state||',','') || coalesce(postal_code||' ','') || coalesce(country||' ','') || coalesce(country_code,'')) result 
from address a 
where entity_id = &ent
    union
select to_char(sys_create_dt, 'YYYY-MM-DD HH24:MI:SS') create_dt, 
    coalesce(( select distinct org_entity_id 
               from er_relocation e 
               where e.dsrc_acct_id = a.dsrc_acct_id 
               and action_date = (select min(action_date) 
                                  from er_relocation 
                                  where dsrc_acct_id = e.dsrc_acct_id 
                                  and action_date > a.sys_create_dt)
               )
               ,entity_id) entity_id, 
    dsrc_acct_id, 
    'Email' typ, 
    '' subtyp, 
    rtrim(email_addr) result 
from email_addr a 
where entity_id = &ent
    union
select to_char(a.sys_create_dt, 'YYYY-MM-DD HH24:MI:SS') create_dt, 
    coalesce(( select distinct org_entity_id 
               from er_relocation e 
               where e.dsrc_acct_id = a.dsrc_acct_id 
               and action_date = (select min(action_date) 
                                  from er_relocation 
                                  where dsrc_acct_id = e.dsrc_acct_id 
                                  and action_date > a.sys_create_dt)
               )
               ,entity_id) entity_id, 
    dsrc_acct_id, 
    'Attribute' typ, 
    t.attr_type subtyp, 
    t.attr_type || ': ' || a.attr_value result 
from attribute a 
join attr_type t on a.attr_type_id = t.attr_type_id --and a.attr_type_id not in (16,102) 
where entity_id = &ent
    union
select to_char(n.sys_create_dt, 'YYYY-MM-DD HH24:MI:SS') create_dt, 
    coalesce(( select distinct org_entity_id 
               from er_relocation e 
               where e.dsrc_acct_id = n.dsrc_acct_id 
               and action_date = (select min(action_date) 
                                  from er_relocation 
                                  where dsrc_acct_id = e.dsrc_acct_id 
                                  and action_date > n.sys_create_dt)
               )
               ,entity_id) entity_id, 
    dsrc_acct_id, 
    'Number' typ, 
    t.num_type subtyp, 
    t.num_type || ': ' || n.num_value || ' ' || n.num_location result 
from nums n 
join num_type t on n.num_type_id = t.num_type_id 
where entity_id = &ent
    union
select to_char(action_date, 'YYYY-MM-DD HH24:MI:SS') create_dt, 
    dest_entity_id entity_id, 
    dsrc_acct_id, 
    'Entity Merge' typ, 
    '' subtyp, 
    org_entity_id || ' merged into ' || dest_entity_id result 
from er_relocation 
where er_id in (select er_id 
                from er_relocation 
                where (org_entity_id = &ent or dest_entity_id = &ent)
                ) 
order by create_dt, dsrc_acct_id, typ, subtyp, result;

Regenerating UMF from Identity Insight Data

This Oracle query will generate UMF messages from the data already in Identity Insight.  This could be used to archive the data in an ingestable format, or to move the data to a different instance.

SELECT '<UMF_ENTITY><DSRC_ACTION>A</DSRC_ACTION><DSRC_CODE>' || DSRC_CODE || '</DSRC_CODE><DSRC_ACCT>' || DSRC_ACCT || '</DSRC_ACCT><DSRC_REF>' || DSRC_REF || '</DSRC_REF>' || NVL2(NAME_SEG,NAME_SEG,'') || NVL2(ADDR_SEG,ADDR_SEG,'') || NVL2(EMAIL_SEG,EMAIL_SEG,'') || NVL2(NUM_SEG,NUM_SEG,'') || NVL2(ATTR_SEG,ATTR_SEG,'') || '</UMF_ENTITY>' ADD_UMF
FROM DSRC_ACCT D
JOIN DSRC_CODE C ON D.DSRC_ID = C.DSRC_ID
LEFT JOIN (SELECT DSRC_ACCT_ID, LISTAGG('<NAME><NAME_TYPE>' || NAME_TYPE || '</NAME_TYPE>' || NVL2(NAME_PFX,'<NAME_PFX>' || NAME_PFX || '</NAME_PFX>','') || NVL2(FIRST_NAME,'<FIRST_NAME>' || FIRST_NAME || '</FIRST_NAME>','') || NVL2(MID_NAME,'<MID_NAME>' || MID_NAME || '</MID_NAME>','') || NVL2(LAST_NAME,'<LAST_NAME>' || LAST_NAME || '</LAST_NAME>','') || NVL2(NAME_GEN,'<NAME_GEN>' || NAME_GEN || '</NAME_GEN>','') || NVL2(NAME_SFX,'<NAME_SFX>' || NAME_SFX || '</NAME_SFX>','') || '</NAME>','') WITHIN GROUP (ORDER BY NAME_ID) NAME_SEG
           FROM NAME
           GROUP BY DSRC_ACCT_ID) N ON D.DSRC_ACCT_ID = N.DSRC_ACCT_ID
LEFT JOIN (SELECT DSRC_ACCT_ID, LISTAGG('<ADDRESS>' || NVL2(ADDR_TYPE,'<ADDR_TYPE>' || ADDR_TYPE || '</ADDR_TYPE>','') || NVL2(ADDR1,'<ADDR1>' || ADDR1 || '</ADDR1>','') || NVL2(ADDR2,'<ADDR2>' || ADDR2 || '</ADDR2>','') || NVL2(ADDR3,'<ADDR3>' || ADDR3 || '</ADDR3>','') || NVL2(CITY,'<CITY>' || CITY || '</CITY>','') || NVL2(STATE,'<STATE>' || STATE || '</STATE>','') || NVL2(POSTAL_CODE,'<POSTAL_CODE>' || POSTAL_CODE || '</POSTAL_CODE>','') || NVL2(COUNTRY,'<COUNTRY>' || COUNTRY || '</COUNTRY>','') || '</ADDRESS>','') WITHIN GROUP (ORDER BY ADDR_ID) ADDR_SEG
           FROM ADDRESS
           GROUP BY DSRC_ACCT_ID) R ON D.DSRC_ACCT_ID = R.DSRC_ACCT_ID
LEFT JOIN (SELECT DSRC_ACCT_ID, LISTAGG('<EMAIL>' || NVL2(ADDR_TYPE,'<ADDR_TYPE>' || ADDR_TYPE || '</ADDR_TYPE>','') || NVL2(EMAIL_ADDR,'<EMAIL_ADDR>' || EMAIL_ADDR || '</EMAIL_ADDR>','') || '</EMAIL>','') WITHIN GROUP (ORDER BY EMAIL_ADDR_ID) EMAIL_SEG
           FROM EMAIL_ADDR
           GROUP BY DSRC_ACCT_ID) E ON D.DSRC_ACCT_ID = E.DSRC_ACCT_ID
LEFT JOIN (SELECT DSRC_ACCT_ID, LISTAGG('<NUMBER><NUM_TYPE>' || NUM_TYPE || '</NUM_TYPE><NUM_VALUE>' || NUM_VALUE || '</NUM_VALUE>' || NVL2(NUM_LOCATION,'<NUM_LOCATION>' || NUM_LOCATION || '</NUM_LOCATION>','') || '</NUMBER>','') WITHIN GROUP (ORDER BY NUM_ID) NUM_SEG
           FROM NUMS N
           JOIN NUM_TYPE T ON N.NUM_TYPE_ID = T.NUM_TYPE_ID
           GROUP BY DSRC_ACCT_ID) U ON D.DSRC_ACCT_ID = U.DSRC_ACCT_ID
LEFT JOIN (SELECT DSRC_ACCT_ID, LISTAGG('<ATTRIBUTE><ATTR_TYPE>' || ATTR_TYPE || '</ATTR_TYPE><ATTR_VALUE>' || ATTR_VALUE || '</ATTR_VALUE>' || '</ATTRIBUTE>','') WITHIN GROUP (ORDER BY ATTR_ID) ATTR_SEG
           FROM ATTRIBUTE A
           JOIN ATTR_TYPE T ON A.ATTR_TYPE_ID = T.ATTR_TYPE_ID
           GROUP BY DSRC_ACCT_ID) A ON D.DSRC_ACCT_ID = A.DSRC_ACCT_ID
WHERE D.DSRC_ACCT_ID = <dsrc_acct_id>

This query, as written, will generate the UMF message for the selected identity.  You can change the final where clause to generate for an entity (WHERE D.ENTITY_ID = <entity_id>), a full data source (WHERE D.DSRC_ID = <dsrc_id>), or for all the data by leaving off the WHERE clause.

Get Performance Stats from Identity Insight

If you want to see how many UMF messages are being processed per minute, execute one of the following SQL queries:

Oracle
SELECT DT, C
FROM (SELECT TO_CHAR(RCV_DT, 'YYYY-MM-DD HH24:MI') DT, COUNT(*) C
      FROM UMF_LOG
      WHERE RCV_DT >= DATE '2014-12-15'
      GROUP BY TO_CHAR(RCV_DT, 'YYYY-MM-DD HH24:MI')
      ORDER BY TO_CHAR(RCV_DT, 'YYYY-MM-DD HH24:MI') DESC)
WHERE ROWNUM <= 100;

SQL Server
SELECT TOP 100 CONVERT(SMALLDATETIME, RCV_DT) DT, COUNT(*) C
FROM UMF_LOG WITH (NOLOCK)
WHERE RCV_DT >= '2014-12-15'
GROUP BY CONVERT(SMALLDATETIME, RCV_DT)
ORDER BY CONVERT(SMALLDATETIME, RCV_DT) DESC

This will return a count of records processed for the last 100 minutes.  Substitute in the current date for 2014-12-15 to limit the number of rows processed.

In the SQL Server query, the conversion to smalldatetime will round the RCV_DT to the nearest minute.  I use the NOLOCK hint so as to minimally impact any ongoing UMF load.