TUNIM - L'algoritmo di fusione

La creazione delle classi globali

1. Dato un cluster si individua un possibile insieme di attributi globali eseguendo l'unione di tutti gli attributi locali. Per esempio:

   Cluster 1 = {University. Research_Staff, University.School_Member, Computer_Science.Student, Computer_Science.Professor, Computer_Science.CS_Person, Tax_Position.University_Person}

   unione_attributi = {first_name, last_name, relation, e_mail, dept_code, section_code, faculty, year, name, title, belongs_to, rank, takes, student_code, faculty_name, tax_fee}

   Per eliminare le ridondanze si esegue una fusione degli attributi simili considerando le relazioni del Common Thesaurus.

2. Tutti gli attributi legati da relazioni validate di sinonimia SYN, appartenenti tutti a classi locali diverse, vengono collassati automaticamente in uno solo il cui nome è quello di uno degli attributi fusi e il dominio pure, poichè le relazioni sono validate. Ad esempio: dalla relazione section_name SYN faculty_name si ottiene un unico attributo globale faculty_name (o section_name).

   Note:

   • Se ci sono attributi legati da relazioni SYN che appartenentgono tutti alla medesima classe locale non è possibile eseguire la fusione perchè con le attuali mapping rule non si riesce a rappresentare una tale corrispondenza: ci vorrebbe una specie di union che indicasse al Query Manager di unire le informazioni di un attributo locale alle informazioni di un altro.
   • Se qualcuno degli attributi legati da relazioni SYN è coinvolto anche in relazioni NT allora si pone il problema di quale fusione effettuare per quegli attributi: la fusione con le NT o con le SYN ? Esempio: nel grafo sottostante di riferimento, è meglio fondere N1_B con G oppure G con H assieme a (N1_B, N1_A) in N1 ? Solo il progettista può dirlo.
3. Ogni gerarchia di termini legati da relazioni validate di specializzazione (BT e NT) viene sostituita da un unico attributo, in cui nome e dominio coincidono con quelli del termine più generale della gerarchia stessa, quello cioè che ne sta a capo e che quindi la rappresenta. Per esempio, dalle relazioni name BT first_name e name BT last_name si ricava l'unico attributo name che sostituisce entrambi gli attributi first_name, last_name presenti nell'unione.

   Note: le stesse del caso precedente.

4. Nel caso di relazioni non validate il problema è più complesso. Infatti, da un lato abbiamo un'informazione fornita dal progettista o da un dizionario lessicale (la relazione terminologica), secondo cui i concetti espressi dai nomi degli attributi sono tra loro correlati, mentre dall'altro l'analisi sui domini mostra che gli attributi in questione sono incompatibili.

   E' possibile individuare un attributo globale con relazioni non validate solo nel caso in cui gli attributi delle relazioni verificano le seguenti condizioni:

   1. rappresentano gerarchie di aggregazione (sono attributi complessi o foreign key)
   2. le classi locali puntate dalle foreign key o da un attributo complesso appartengono ad uno stesso cluster
   3. hanno lo stesso significato semantico, cioè devono essere legati da relazioni di sinonimia (SYN) o di specializzaizone (BT, NT)

5. Individuati gli attributi globali si procede con la compilazione della mapping-table. La mapping-table è costituita da un numero di colonne pari al numero di atributi globali e da un numero di righe pari alle classi locali appartenenti al cluster. Ogni elemento della tabella assume un valore diverso a seconda del tipo di corrispondenza che sussiste tra l'attributo di una classe locale e l'attributo globale. Considerata una classe locale, i tipi di corrispondenza e i valori corrispondenti che si possono avere nella mapping-table sono i seguenti:

   • corrispondenza semplice: indicata col nome dell'attributo locale, es. name;
     
   • corrispondenza in AND: usata per indicare che il valore assunto dall'attributo globale in questione è il concatenamento dei valori assunti da più attributi locali (es. first_name AND last_name);
     
   • corrispondenza in UNION: è il caso in cui l'attributo globale può assumere il valore di uno solo tra un insieme di attributi locali, in funzione del valore di un altro attributo ("tag"). In questo caso nella cella della mapping-table comparirà un costrutto come quello di esempio:

     case of rank:
     'student': email
     'phd': phd_email
     

     con il quale si vuole indicare che l'attributo globale può assumere il valore dell'attributo locale email se rank='student' oppure phd_email se rank='phd';
     

   • corrispondenza a valore costante: si indica nella mapping-table specificando la costante che l'attributo globale assume ogni volta che si accede alla classe locale;
     
   • corrispondenza nulla: nella mapping-table si indica specificando la stringa null e significa che un attributo globale non assume valori di attributi locali appartenenti alla classe locale.
     

Esempio di mapping-table

Funzionamento di TUNIM

Il procedimento di generazione delle classi globali implemenetato nel modulo avviene in due fasi:

1. Generazione automatica di una prima versione delle classi globali.
2. Interazione con il progettista per l'affinamento delle classi.

1. Generazione automatica di una prima versione delle classi globali

In questa fase, il modulo esegue contemporaneamente le fasi di:

• unione degli attributi locali;
• fusione automatica degli attributi simili legati da relazioni validate e non;
• compilazione della mapping-table.

Considerato un cluster, il modulo individua un attributo globale per ciascuno degli attributi locali appartenenti alle classi locali del cluster. Per ogni attributo globale individuato viene aggiunta una colonna alla mapping-table e ne vengono compilate le caselle utilizzando solamente corrispondenze semplici e corrispondenze nulle.

Fusione di attributi legati da relazioni validate

Dato un attributo locale, viene generato un grafo costituito da relazioni validate SYN, BT o NT appartenenti al Common Thesaurus che relazionano solamente attributi locali di classi locali appartenenti al cluster.

Esempio di grafo: in arancione sono evidenziati gli attributi locali root del grafo mentre in verde sono rappresentati tutti gli altri attributi.

Da una analisi delle relazioni appartenenti al grafo, il modulo individua delle possibili fusioni: alcune possono essere eseguite in modo automatico, altre richiedono l'intervento del progettista. Nei casi in cui si presenta una ambiguita' nella scelta tra piu' tipi di fusione, il modulo richiede l'intervento del progettista.

Algoritmo. Considerato un attributo A mappato su un attributo globale con una corrispondenza semplice, da una analisi del grafo sono individuati tutti gli attributi "padri" e "fratelli" di A dopodiche' in modo completamente automatico sono fusi gli attributi "gemelli" di A, ovvero quelli coinvolti in relazioni di sinonimia (esempio: N1, Q): in caso di piu' fusioni possibili per A quelle date dalle relazioni di sinonimia hanno la precedenza sulle altre. Se ci sono piu' attributi legati ad A da relazioni di sinonimia, viene scelto l'attributo globale AG', che mappa uno degli attributi sinonimi, che ha piu' mapping rule: questo contribuisce ad ottenere una mapping-table con meno attributi globali.
Gli attributi "fratelli" di A invece possono essere fusi con esso in due modi diffrenti: attraverso una fusione in AND oppure in UNION. In questo caso il progettista indica il tipo di fusione da attuare. In particolare, se la scelta e' ricaduta sulla fusione in UNION, il progettista dovra' indicare anche l'attributo "tag" e i valori in base ai quali il Query Manager di MOMIS dovra' scegliere da quale attributo reperire i dati. In caso di piu' fusioni possibili per A quelle relative agli attributi fratelli sono seconde in ordine di priorita'.
Se A ha piu' attributi padri, allora viene scelta la fusione con l'attributo che sta' in cima alla gerarchia.

La fusione di un attributo A, mappato sull'attributo globale AG, con uno o piu' attributi B,C,..., mappati nell'attributo globale AG', avviene in questo modo:

1. viene eliminata la mapping rule (che e' una corrispondenza semplice) che mappa A nell'attributo globale AG
2. se AG non contiene altre mapping rule allora viene eliminato
3. A viene mappato in AG':
   • se la classe locale di A non ha mapping rule in AG' allora A viene mappato in AG' con una mapping rule costituita da una corrispondenza semplice
   • se la classe locale di A e' mappata in AG' con una corrispondenza semplice (un solo attributo) allora tale mapping rule dovra' diventare una corrispondenza in AND oppure in UNION: il progettista deve indica quale corrispondenza attuare
   • se la classe locale di A e' mappata in AG' con una corrispondenza in AND allora A verra' aggiunto agli attributi mappati in AND
   • se la classe locale di A e' mappata in AG' con una corrispondenza in UNION allora A verra' aggiunto agli attributi mappati in UNION e il progettista indichera' a quale valore dell'attributo "tag" corrispodenra' A

Fusione degli attributi legati da relazioni non validate

In questo caso, il modulo considera ogni relazione non validata del Common Thesaurus che sia di sinonimia o di specializzazione e verifica le condizioni di fusione per questo tipo di attributi. In caso affermativo aggiunge un attributo globale (una colonna) alla classe globale (mapping-table), mappando ciascuno degli attributi locali con quello globale.

2. Interazione con il progettista per l'affinamento delle classi

Una volta creata in automatico la prima versione di ogni classe globale, il progettista, interagendo con il modulo, puo' ottimizzare lo schema globale apportando le modifiche che ritiene oppotune (qualsiasi tipo di modifica). TUNIM guida il progettista nelle modifiche proponendo nomi alternativi per gli attributi globali e per le classi globali, controllando inoltre che non vi siano conflitti di domini nella mapping-table.

The MOMIS Home Page