Introduzione alle dipendenze funzionali

In questo articolo discuteremo delle dipendenze funzionali nei database: cosa siano, dove vengano applicate e quali algoritmi esistano per la loro ricerca.

Considereremo le dipendenze funzionali nel contesto dei database relazionali. Se vogliamo semplificare, in tali database le informazioni sono memorizzate in forma di tabelle. In seguito utilizzeremo nozioni approssimative che nella rigorosa teoria relazionale non sono interscambiabili: la tabella stessa sarà chiamata relazione, le colonne saranno chiamate attributi (il loro insieme sarà lo schema della relazione), e il set di valori di una riga su un sottoinsieme di attributi sarà il tupla.

Ad esempio, nella tabella sopra, (Benson, M, M organ) è una tupla per gli attributi (Paziente, Genere, Dottore).
Più formalmente, ciò si scrive nel seguente modo: [Paziente, Genere, Dottore] = (Benson, M, M organ).
Ora possiamo introdurre il concetto di dipendenza funzionale (DF):

Definizione 1. La relazione R soddisfa la DF X → Y (dove X, Y ⊆ R) se e solo se, per ogni tupla , ∈ R vale: se [X] = [X], allora [Y] = [Y]. In tal caso si dice che X (determinante, o insieme di attributi determinante) determina funzionalmente Y (insieme dipendente).

In altre parole, la presenza della DF X → Y significa che se abbiamo due tuple in R e queste coincidono sugli attributi X, allora coincideranno anche sugli attributi Y.
E ora procediamo per ordine. Consideriamo gli attributi Paziente e Genere per i quali vogliamo sapere se ci sono dipendenze tra di essi o meno. Per tale insieme di attributi possono esistere le seguenti dipendenze:

1. Paziente → Genere
2. Genere → Paziente

Secondo la definizione sopra, affinché la prima dipendenza si mantenga, a ogni valore unico della colonna Paziente deve corrispondere solo un valore della colonna Genere. E per la tabella di esempio è davvero così. Tuttavia, al contrario non funziona, cioè la seconda dipendenza non è soddisfatta, e l'attributo Genere non è un determinante per Paziente. Analogamente, se consideriamo la dipendenza Dottore → Paziente, possiamo notare che essa viene violata, poiché il valore Robin per questo attributo ha diversi valori — Ellis e Graham.

In questo modo, le dipendenze funzionali consentono di determinare le relazioni esistenti tra insiemi di attributi della tabella. Da qui in avanti, esamineremo le relazioni più interessanti, ossia quelle X → Y, che sono:

• non banali, cioè la parte destra della dipendenza non è un sottoinsieme della sinistra (Y ̸⊆ X);
• minimali, cioè non esiste tale dipendenza Z → Y, che Z ⊂ X.

Le dipendenze esaminate fino a questo momento erano severe, ossia non prevedevano alcuna violazione nella tabella, ma oltre a esse ce ne sono altre che ammettono una certa incoerenza tra i valori delle tuple. Tali dipendenze sono assegnate a una classe separata, vengono chiamate approssimative e si consente loro di violarsi su un certo numero di tuple. Questo numero è regolato dall'indicatore di errore massimo emax. Ad esempio, una quota di errore = 0.01 può significare che la dipendenza può violarsi su l'1% delle tuple esistenti nel dato insieme di attributi. Cioè, per 1000 registrazioni al massimo 10 tuple possono violare la dipendenza. Noi considereremo una metrica leggermente diversa, basata sui valori distinti delle tuple confrontate. Per la dipendenza X → Y relativa r si considera così:

Calcoliamo l'errore per Dottore → Paziente l'esempio sopra. Abbiamo due tuple, i cui valori differiscono per l'attributo Paziente, ma coincidono su Dottore: [Dottore, Paziente] = (Robin, Ellis) e [Dottore, Paziente] = (Robin, Graham). Seguendo la definizione di errore, dobbiamo considerare tutte le coppie in conflitto, quindi ce ne saranno due: (, ) e la sua inversione (, ). Inseriamo nella formula e otteniamo:

E ora cerchiamo di rispondere alla domanda: «A cosa serve tutto questo?». In realtà, le dipendenze possono essere diverse. Il primo tipo sono quelle dipendenze che vengono definite dall'amministratore nella fase di progettazione del database. Di solito sono poche, sono severe e il loro uso principale è nella normalizzazione dei dati e nel design dello schema relazionale.

Il secondo tipo è rappresentato dalle dipendenze che mostrano dati «nascosti» e relazioni precedentemente sconosciute tra gli attributi. Cioè, di queste dipendenze non si teneva conto al momento della progettazione e vengono scoperte solo su un insieme di dati esistente, per poi trarre conclusioni sulle informazioni memorizzate basandosi su molte funzionalità scoperte. È proprio con queste dipendenze che lavoriamo. Un'intera area del data mining si occupa di esse, con varie tecniche di ricerca e algoritmi costruiti su di esse. Analizziamo quindi in che modo le dipendenze funzionali trovate (sia esatte che approssimative) possano essere utili in alcuni dati.

Oggi tra le principali aree di applicazione delle dipendenze si evidenzia la pulizia dei dati. Essa implica lo sviluppo di processi per identificare i «dati sporchi» e correggerli successivamente. Esemplari rappresentanti dei «dati sporchi» sono i duplicati, gli errori nei dati o gli errori di battitura, i valori mancanti, i dati obsoleti, gli spazi superflui e simili.

Esempio di errore nei dati:

Esempio di duplicati nei dati:

Ad esempio, abbiamo una tabella e un insieme di regole che devono essere rispettate. In questo caso, la pulizia dei dati implica modificare i dati in modo che le regole siano corrette. Nel far ciò, il numero di modifiche deve essere minimo (per questa procedura esistono algoritmi specifici su cui non ci soffermeremo in questo articolo). Di seguito è riportato un esempio di tale trasformazione dei dati. A sinistra c'è la relazione originale, nella quale, ovviamente, non sono rispettate le regole necessarie (in rosso è evidenziato un esempio di violazione di una delle regole). A destra è presentata la relazione aggiornata, in cui le celle verdi mostrano i valori modificati. Dopo aver eseguito tale procedura, le dipendenze necessarie sono state mantenute.

Un'altra area popolare di applicazione è il design del database. Qui vale la pena ricordare le forme normali e la normalizzazione. La normalizzazione è un processo di adattamento di una relazione a un certo insieme di requisiti, ciascuno dei quali è definito a modo suo da una forma normale. Non entreremo nei dettagli dei requisiti delle diverse forme normali (questo viene trattato in qualsiasi libro sul corso di basi di dati per principianti), ma notiamo solo che ognuna di esse utilizza a modo suo il concetto di dipendenze funzionali. Infatti, le dipendenze funzionali sono essenzialmente vincoli di integrità che vengono considerati nella progettazione del database (in questo contesto, le dipendenze funzionali sono talvolta chiamate superchiavi).

Esaminiamo la loro applicazione per le quattro forme normali nell'immagine qui sotto. Ricordiamo che la forma normale di Boyce-Codd è più rigorosa della terza forma, ma meno rigorosa della quarta. Non ci occupiamo ancora della quarta, poiché la sua definizione richiede una comprensione delle dipendenze multivalore, che in questo articolo non ci interessano.

Un'altra area in cui le dipendenze hanno trovato applicazione è la riduzione della dimensionalità dello spazio delle caratteristiche in compiti come la costruzione di un classificatore bayesiano naive, l'estrazione di caratteristiche significative e la riparametrazione di un modello di regressione. Negli articoli originali, questo compito è chiamato definizione delle caratteristiche ridondanti (feature redundancy) e rilevanti (feature relevancy) [5, 6], ed è risolto attraverso un attivo utilizzo dei concetti di basi di dati. Con l'emergere di tali lavori, possiamo dire che oggi c'è una domanda per soluzioni che consentano di combinare database, analisi e implementazione dei problemi di ottimizzazione sopra menzionati in un unico strumento [7, 8, 9].

Esistono molti algoritmi (sia moderni che meno recenti) per trovare dipendenze in un insieme di dati. Questi algoritmi possono essere suddivisi in tre gruppi:

• Algoritmi che utilizzano il percorso attraverso reticoli algebrici (Lattice traversal algorithms)
• Algoritmi basati sulla ricerca di valori coerenti (Difference- and agree-set algorithms)
• Algoritmi basati su confronti a coppie (Dependency induction algorithms)

Una breve descrizione di ciascun tipo di algoritmo è presentata nella tabella sottostante:


Maggiori informazioni su questa classificazione sono disponibili in [4]. Di seguito sono presentati esempi di algoritmi per ciascun tipo:

Attualmente stanno emergendo nuovi algoritmi che combinano diversi approcci alla ricerca delle dipendenze funzionali. Esempi di tali algoritmi sono Pyro [2] e HyFD [3]. L'analisi del loro funzionamento è prevista nei prossimi articoli di questo ciclo. In questo articolo ci limiteremo a esaminare i concetti di base e il lemma necessari per comprendere le tecniche di identificazione delle dipendenze.

Iniziamo con i semplici — difference- e agree-set, utilizzati nel secondo tipo di algoritmi. Il difference-set rappresenta un insieme di tuple che non corrispondono nei valori, mentre l'agree-set è l'opposto: tuple che corrispondono nei valori. È importante notare che in questo caso consideriamo solo la parte sinistra della dipendenza.

Un concetto altrettanto importante, già menzionato precedentemente, è la reticolo algebrico. Poiché molti algoritmi moderni operano su questo concetto, è fondamentale avere un'idea chiara di cosa sia.

Per introdurre il concetto di reticolo, è necessaria la definizione di un insieme parzialmente ordinato (o partially ordered set, abbreviato — poset).

Definizione 2. Si dice che un insieme S sia parzialmente ordinato da una relazione binaria ⩽, se per ogni a, b, c ∈ S si verificano le seguenti proprietà:

1. Riflessività, cioè a ⩽ a
2. Antisimmetria, ovvero, se a ⩽ b e b ⩽ a, allora a = b
3. Transitività, cioè per a ⩽ b e b ⩽ c segue che a ⩽ c

Tale relazione è chiamata (non stretta) relazione di ordine parziale, e l'insieme stesso è un insieme parzialmente ordinato. Notazione formale: ⟨S, ⩽⟩.

Come esempio più semplice di insieme parzialmente ordinato, possiamo considerare l'insieme di tutti i numeri naturali N con la consueta relazione d'ordine ⩽. Non è difficile verificare che tutte le necessarie assiomi siano soddisfatti.

Un esempio più sostanzioso. Consideriamo l'insieme di tutte le sottoinsiemi {1, 2, 3}, ordinato dalla relazione di inclusione ⊆. Infatti, questa relazione soddisfa tutte le condizioni dell'ordine parziale, quindi ⟨P ({1, 2, 3}), ⊆⟩ è un insieme parzialmente ordinato. Nella figura sotto è rappresentata la struttura di questo insieme: se da un elemento si può arrivare a un altro tramite le frecce, allora essi sono in relazione d'ordine.

Avremo bisogno di altre due definizioni semplici nel campo della matematica: supremum e infimum.

Definizione 3. Sia ⟨S, ⩽⟩ un insieme parzialmente ordinato, A ⊆ S. Un upper bound di A è un elemento u ∈ S tale che ∀x ∈ S: x ⩽ u. Sia U l'insieme di tutti gli upper bounds di S. Se in U esiste un elemento minimo, allora si chiama supremum e si denota come sup A.

Analogamente si introduce il concetto di lower bound esatto.

Definizione 4. Sia ⟨S, ⩽⟩ un insieme parzialmente ordinato, A ⊆ S. Un lower bound di A è un elemento l ∈ S tale che ∀x ∈ S: l ⩽ x. Sia L l'insieme di tutti i lower bounds di S. Se in L esiste un elemento massimo, allora si chiama infimum e si denota come inf A.

Consideriamo come esempio l'insieme parzialmente ordinato ⟨P ({1, 2, 3}), ⊆⟩ e troviamo in esso supremum e infimum:

Ora possiamo formulare la definizione di reticolo algebrico.

Definizione 5. Sia ⟨P, ⩽⟩ un insieme parzialmente ordinato tale che ogni sottoinsieme di due elementi ha esatti upper e lower bounds. Allora P è chiamato reticolo algebrico. In questo caso, sup{x, y} si scrive come x ∨ y, e inf {x, y} come x ∧ y.

Verifichiamo se il nostro esempio lavorativo ⟨P ({1, 2, 3}), ⊆⟩ è un reticolo. Infatti, per ogni a, b ∈ P ({1, 2, 3}), a∨b = a∪b, e a∧b = a∩b. Ad esempio, consideriamo gli insiemi {1, 2} e {1, 3} e troviamo il loro infimum e supremum. Se li intersecamo, otteniamo l'insieme {1}, che sarà l'infimum. Lo supremum invece si ottiene dalla loro unione: {1, 2, 3}.

Negli algoritmi di discoveri FZ, lo spazio di ricerca è spesso rappresentato in forma di reticolo, dove gli insiemi di un singolo elemento (leggi primo livello del reticolo di ricerca, dove la parte sinistra delle dipendenze è costituita da un solo attributo) rappresentano ciascun attributo della relazione originale.
All'inizio si considerano le dipendenze del tipo ∅ → Singolo attributo. Questo passaggio permette di determinare quali attributi siano le chiavi primarie (per tali attributi non ci sono determinanti, e quindi la parte sinistra è vuota). Successivamente, tali algoritmi procedono verso l'alto nel reticolo. È importante notare che non è necessario attraversare tutto il reticolo, ossia se si fornisce in input la dimensione massima desiderata della parte sinistra, l'algoritmo non procederà oltre quel livello.

Nell'immagine sottostante è mostrato come utilizzare una rete algebrica nel problema della ricerca di FZ. Qui ogni arco (X, XY) rappresenta una dipendenza X → Y. Ad esempio, abbiamo superato il primo livello e sappiamo che la dipendenza è mantenuta A → B )(mostriamola con un legame verde tra i vertici A e B). Pertanto, quando ci muoviamo verso l'alto nella rete, non dobbiamo controllare la dipendenza A, C → B, perché non sarà già minima. Analogamente, non la controlliamo nemmeno se è mantenuta la dipendenza C → B.

Inoltre, in generale, tutti gli algoritmi moderni per la ricerca di FZ utilizzano una struttura dati come la partizione (nel testo originale - stripped partition [1]). La definizione formale di partizione è la seguente:

Definizione 6. Sia X ⊆ R un insieme di attributi per la relazione r. Un cluster è un insieme di indici delle tuple di r che hanno lo stesso valore per X, cioè c(t) = {i|ti[X] = t[X]}. La partizione è un insieme di cluster che esclude i cluster di lunghezza unitaria:

In parole semplici, la partizione per l'attributo X è un insieme di elenchi, dove ogni elenco contiene i numeri di riga con valori identici per X. Nella letteratura moderna, la struttura che rappresenta le partizioni è chiamata position list index (PLI). I cluster di lunghezza unitaria sono esclusi per la compressione della PLI, poiché sono cluster che contengono solo il numero di record con un valore unico, che sarà sempre facile da identificare.

Prendiamo un esempio. Torniamo alla stessa tabella con i pazienti e costruiamo partizioni per le colonne Paziente e Genere (è stata aggiunta una nuova colonna a sinistra, in cui sono contrassegnati i numeri di riga della tabella):

In questo caso, secondo la definizione, la partizione per la colonna Paziente sarà in realtà vuota, poiché i cluster singoli sono esclusi dalla partizione.

Le partizioni possono essere ottenute su più attributi. E per questo ci sono due modi: percorrere la tabella e costruire una partizione immediatamente su tutti gli attributi necessari, oppure costruirla usando l'operazione di intersezione delle partizioni su un sottoinsieme di attributi. Gli algoritmi di ricerca di FZ utilizzano la seconda opzione.

In parole semplici, per ottenere una partizione per le colonne ABC, possiamo prendere le partizioni per AC e B (o qualsiasi altro insieme di sottoinsiemi disgiunti) e intersecarli tra loro. L'operazione di intersezione di due partizioni evidenzia i cluster di lunghezza massima, comuni a entrambe le partizioni.

Consideriamo un esempio:

Nel primo caso abbiamo ottenuto una partizione vuota. Se guardiamo la tabella, effettivamente non ci sono valori identici per due attributi. Se invece modifichiamo un po' la tabella (caso a destra), otteniamo un'intersezione non vuota. In questo caso, le righe 1 e 2 contengono effettivamente valori identici per gli attributi Genere e Dottore.

Poi avremo bisogno di un concetto come la dimensione della partizione. Formalmente:

In poche parole, la dimensione della partizione rappresenta il numero di cluster che compongono la partizione (ricordiamo che i cluster singoli non fanno parte della partizione!):

Ora possiamo definire uno dei lemmi chiave, che per le partizioni date consente di stabilire se la dipendenza è mantenuta o meno:

Lemma 1. La dipendenza A, B → C è mantenuta se e solo se

Secondo il lemma, per determinare se una dipendenza è mantenuta, è necessario eseguire quattro passaggi:

1. Calcolare la partizione per il lato sinistro della dipendenza
2. Calcolare la partizione per il lato destro della dipendenza
3. Calcolare il prodotto del primo e del secondo passaggio
4. Confrontare le dimensioni delle partizioni ottenute nel primo e nel terzo passaggio

Di seguito è riportato un esempio di verifica se la dipendenza è mantenuta secondo questo lemma:

In questo articolo abbiamo trattato concetti come la dipendenza funzionale, la dipendenza funzionale approssimata, visto dove vengono applicati e quali algoritmi di ricerca delle dipendenze esistono. Abbiamo anche esaminato in dettaglio i concetti di base, ma importanti, ampiamente utilizzati negli algoritmi moderni per la ricerca delle dipendenze funzionali.

Riferimenti bibliografici:

1. Huhtala Y. et al. TANE: Un algoritmo efficiente per scoprire dipendenze funzionali e approssimate //The computer journal. - 1999. - Vol. 42. - No. 2. - Pp. 100-111.
2. Kruse S., Naumann F. Scoperta efficiente di dipendenze approssimate //Atti del VLDB Endowment. - 2018. - Vol. 11. - No. 7. - Pp. 759-772.
3. Papenbrock T., Naumann F. Un approccio ibrido per la scoperta di dipendenze funzionali //Atti della Conferenza Internazionale 2016 sulla gestione dei dati. - ACM, 2016. - Pp. 821-833.
4. Papenbrock T. et al. Scoperta di dipendenze funzionali: una valutazione sperimentale di sette algoritmi //Atti del VLDB Endowment. - 2015. - Vol. 8. - No. 10. - Pp. 1082-1093.
5. Kumar A. et al. Unirsi o meno?: Pensare due volte sulle unioni prima della selezione delle caratteristiche //Atti della Conferenza Internazionale 2016 sulla gestione dei dati. - ACM, 2016. - Pp. 19-34.
6. Abo Khamis M. et al. Apprendimento in-database con tensori sparsi // Atti del 37° Simposio ACM SIGMOD-SIGACT-SIGAI sui Principi dei Sistemi di Database. – ACM, 2018. – P. 325-340.
7. Hellerstein J. M. et al. La libreria analitica MADlib: o abilità MAD, il SQL // Atti del VLDB Endowment. – 2012. – Vol. 5. – N. 12. – P. 1700-1711.
8. Qin C., Rusu F. Approssimazioni speculative per l'ottimizzazione del gradiente distribuito terascale // Atti del Quarto Workshop sull'Analisi dei Dati nel Cloud. – ACM, 2015. – P. 1.
9. Meng X. et al. Mllib: Apprendimento automatico in Apache Spark // The Journal of Machine Learning Research. – 2016. – Vol. 17. – N. 1. – P. 1235-1241.

Autori dell'articolo: Anastasia Birillo, ricercatrice presso JetBrains Research, studentessa del centro CS e Nikita Bobrov, ricercatrice presso JetBrains Research

Fonte: habr.com