Introduzione alle dipendenze funzionali

In questo articolo parleremo delle dipendenze funzionali nei database: di cosa si tratta, dove vengono utilizzate e quali algoritmi esistono per trovarle.

Considereremo le dipendenze funzionali nel contesto dei database relazionali. Grossolanamente, in questi database le informazioni sono memorizzate sotto forma di tabelle. Useremo quindi concetti approssimativi che nella rigorosa teoria relazionale non sono intercambiabili: chiameremo la tabella una relazione, le colonne attributi (il loro insieme sarà lo schema della relazione), e un insieme di valori di una riga su un sottoinsieme di attributi sarà un_tuple_.

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

Definizione 1. Una relazione R soddisfa la DF X → Y (dove X, Y ⊆ R) se e solo se per tutte le_tuple_ , ∈ R è vero che: 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_tuples_ in R e coincidono su attributi X, allora coincideranno anche su attributi Y.
E ora per ordine. Consideriamo gli attributi Paziente e Genere per i quali vogliamo sapere se esistono dipendenze 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 sia valida, ogni valore unico nella colonna Paziente deve corrispondere a un solo valore nella colonna Genere. E per la tabella di esempio questo è effettivamente vero. Tuttavia, in senso contrario, la seconda dipendenza non si sostiene, e l'attributo Genere non è determinante per Paziente.Analogamente, se prendiamo la dipendenza Dottore → Paziente, possiamo notare che essa è violata, poiché il valore Robin per questo attributo ha più valori diversi — Ellis e Graham..

Quindi, le dipendenze funzionali permettono di determinare le relazioni esistenti tra insieme di attributi della tabella. Da qui in avanti considereremo le relazioni più interessanti, ovvero quelle che sono: X → Ynon banali, cioè il lato destro della dipendenza non è un sottoinsieme del lato sinistro

• (Y ̸⊆ X) minimali, cioè non esiste una dipendenza;
• Z → Y Z ⊂ X., che Le dipendenze esaminate fino a questo momento erano rigide, cioè non prevedevano violazioni nella tabella, ma oltre a queste ce ne sono altre che ammettono una certa incoerenza tra i valori delle tuple. Tali dipendenze rientrano in una classe separata, vengono definite approssimative e si consente loro di essere violate su un determinato 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ò essere violata su 1% delle tuple presenti nel considerato insieme di attributi. Cioè, per 1000 registrazioni, al massimo 10 tuple possono violare la DF. Noi esamineremo una metrica leggermente diversa, basata su valori distinti confrontati a coppie di tuple. Per la dipendenza sulla relazione X → Y è calcolata così: r Calcoliamo l'errore per

dell'esempio sopra. Abbiamo due_tuples_ i cui valori differiscono sull'attributo Dottore → Paziente , ma coincidono su PazienteDottore Dottore, Paziente: [Robin, Ellis] = (Robin, Graham) e [Robin, Ellis] = (). Seguendo la definizione di errore, dobbiamo considerare tutte le coppie in conflitto, e quindi ce ne saranno due: () e la sua inversione (, ). Inseriamo nella formula e otteniamo:, Ora cerchiamo di rispondere alla domanda: «A cosa serve tutto questo?». In effetti, esistono diverse tipologie di DF. Il primo tipo è costituito da quelle dipendenze definite dall'amministratore nella fase di progettazione del database. Ce ne sono di solito poche, sono rigide e il loro uso principale è la normalizzazione dei dati e il design dello schema della relazione.

Il secondo tipo è costituito dalle dipendenze che rappresentano dati «nascosti» e relazioni precedentemente sconosciute tra gli attributi. Cioè, di queste dipendenze non si era pensato al momento della progettazione, e vengono trovate già per un insieme di dati esistente, affinché poi, sulla base delle numerose DF identificate, si possano trarre conclusioni sulle informazioni memorizzate. Proprio con tali dipendenze stiamo lavorando. Esse fanno parte di un intero campo del data mining con diverse tecniche di ricerca e algoritmi sviluppati sulla loro base. Scopriamo quali benefici possono portare le dipendenze funzionali trovate (esatte o approssimative) in alcuni dati.

Il secondo tipo è rappresentato da dipendenze che mostrano dati "nascosti" e relazioni precedentemente sconosciute tra gli attributi. In altre parole, si tratta di dipendenze a cui non si pensava al momento della progettazione e che vengono scoperte successivamente su un insieme di dati esistente, per poi trarre delle conclusioni sulle informazioni conservate basandosi su un gran numero di dipendenze identificate. È proprio su queste dipendenze che lavoriamo. Esse appartengono a un intero settore del data mining, con diverse tecniche di ricerca e algoritmi costruiti su di esse. Approfondiamo come le dipendenze funzionali trovate (siano esse esatte o approssimate) possano essere utili per dei dati.

Oggi tra i principali ambiti di applicazione delle dipendenze si distingue la pulizia dei dati. Questa implica lo sviluppo di processi per identificare i "dati sporchi" con successiva correzione. Esempi di "dati sporchi" includono duplicati, errori nei dati o refusi, valori mancanti, dati obsoleti, spazi superflui e simili.

Esempio di errore nei dati:

Esempio di duplicati nei dati:

Ad esempio, abbiamo una tabella e un insieme di vincoli che devono essere rispettati. In questo caso, la pulizia dei dati implica modificare i dati in modo tale che i vincoli diventino corretti. Inoltre, il numero di modifiche deve essere minimo (per questa procedura esistono algoritmi specifici, sui quali non ci soffermeremo in questo articolo). Di seguito è riportato un esempio di tale trasformazione dei dati. A sinistra c'è la relazione originale, in cui non sono rispettati i vincoli necessari (in rosso è evidenziato un esempio di violazione di uno dei vincoli). A destra è mostrata la relazione aggiornata, in cui le celle verdi indicano i valori modificati. Dopo aver effettuato questa procedura, i vincoli necessari sono stati mantenuti.

Un altro ambito popolare di applicazione è il design del database. Qui è importante ricordare le forme normali e la normalizzazione. La normalizzazione è il processo di portare una relazione in conformità a un determinato insieme di requisiti, ognuno dei quali è definito in modo diverso dalla forma normale. Non entreremo nei dettagli dei requisiti delle diverse forme normali (questo è trattato in qualsiasi libro di database per principianti), ma noteremo solo che ognuna di esse utilizza in modo specifico il concetto di dipendenze funzionali. Infatti, le dipendenze funzionali sono essenzialmente vincoli di integrità che vengono considerati durante la progettazione di un database (in questo contesto, le dipendenze funzionali vengono talvolta denominate superchiavi).

Consideriamo la loro applicazione per quattro forme normali nell'immagine sottostante. Ricordiamo che la forma normale di Boyce-Codd è più rigorosa della terza forma, ma meno rigorosa della quarta. Quest'ultima non viene ancora considerata, poiché per la sua definizione è necessaria la comprensione delle dipendenze multivalore, che non ci interessano in questo articolo.

Un'altra area in cui le dipendenze sono state applicate è la riduzione dimensionale 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 è denominato determinazione delle caratteristiche ridondanti e rilevanti, e viene affrontato mediante l'uso attivo dei concetti di database. Con la comparsa di tali lavori, possiamo dire che oggi c'è una domanda per soluzioni che combinano i database, l'analisi e l'implementazione dei suddetti problemi di ottimizzazione in un unico strumento.

Per trovare le dipendenze funzionali in un insieme di dati esistono molti algoritmi (sia moderni che meno recenti). Tali algoritmi possono essere suddivisi in tre gruppi:

• Algoritmi che utilizzano la traversata delle reticoli algebrici (Lattice traversal algorithms)
• Algoritmi basati sulla ricerca di valori concordi (Difference- and agree-set algorithms)
• Algoritmi basati su confronti a coppie (Dependency induction algorithms)

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


Maggiori dettagli su questa classificazione possono essere letti. Di seguito sono riportati esempi di algoritmi per ciascun tipo:

Attualmente, stanno emergendo nuovi algoritmi che combinano diversi approcci per la ricerca di dipendenze funzionali. Esempi di tali algoritmi includono Pyro e HyFD. Analizzeremo il loro funzionamento nei prossimi articoli di questa serie. In questo articolo, ci limiteremo ad analizzare i concetti fondamentali e il lemma necessari per comprendere le tecniche di identificazione delle dipendenze.

Iniziamo con un concetto semplice: difference- e agree-set, utilizzati nel secondo tipo di algoritmi. Il difference-set rappresenta un insieme di tuple che non coincidono nei valori, mentre l'agree-set è l'opposto: tuple che coincidono nei valori. Vale la pena notare che in questo caso stiamo considerando solo la parte sinistra della dipendenza.

Un altro concetto importante, che è stato menzionato sopra, è la reticolo algebrico. Poiché molti algoritmi moderni operano con questo concetto, dobbiamo avere un'idea di cosa sia.

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

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

1. Reflexività, cioè a ⩽ a
2. Antisimmetria, cioè se a ⩽ b e b ⩽ a, allora a = b
3. Transitività, cioè se a ⩽ b e b ⩽ c, allora a ⩽ c

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

Come esempio più semplice di un 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 sono soddisfatti.

Esempio più significativo. Consideriamo l'insieme di tutti i sottoinsiemi {1, 2, 3}, ordinato dalla relazione di inclusione ⊆. Infatti, questa relazione soddisfa tutte le condizioni di un ordine parziale, quindi ⟨P({1, 2, 3}), ⊆⟩ è un insieme parzialmente ordinato. Nella figura qui sotto è mostrata la struttura di questo insieme: se si può raggiungere un elemento da un altro tramite le frecce, allora sono in relazione d'ordine.

Avremo bisogno di altre due semplici definizioni nell'area della matematica: supremum (supremum) e infimum (infimum).

Definizione 3. Siano ⟨S, ⩽⟩ un insieme parzialmente ordinato e A ⊆ S. Il limite superiore di A è un elemento u ∈ S tale che ∀x ∈ S: x ⩽ u. Sia U l'insieme di tutti i limiti superiori di S. Se in U esiste un elemento minimo, allora esso è chiamato supremum e indicato come sup A.

Analogamente si introduce il concetto di limite inferiore.

Definizione 4. Siano ⟨S, ⩽⟩ un insieme parzialmente ordinato e A ⊆ S. Il limite inferiore di A è un elemento l ∈ S tale che ∀x ∈ S: l ⩽ x. Sia L l'insieme di tutti i limiti inferiori di S. Se in L esiste un elemento massimo, allora esso è chiamato infimum e indicato come inf A.

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

Ora possiamo formulare la definizione della rete algebrica.

Definizione 5. Sia ⟨P, ⩽⟩ un insieme parzialmente ordinato tale che ogni sottoinsieme di due elementi ha limiti superiori e inferiori precisi. Allora P è chiamata rete algebrica. In questo caso, sup{x, y} è scritto come x ∨ y, e inf{x, y} come x ∧ y.

Verifichiamo che il nostro esempio di lavoro ⟨P({1, 2, 3}), ⊆⟩ sia una rete. 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 intersechiamo, otteniamo l'insieme {1}, che sarà il limite inferiore. Il supremum lo otterremo dalla loro unione — {1, 2, 3}.

Nell'algoritmi di individuazione delle dipendenze funzionali, lo spazio di ricerca è spesso rappresentato in forma di rete, dove insiemi di un elemento (leggi: primo livello della rete di ricerca, dove la parte sinistra delle dipendenze consiste di un solo attributo) rappresentano ogni attributo della relazione originale.
All'inizio vengono considerate dipendenze del tipo ∅ → Attributo singolo. Questo passaggio consente di determinare quali attributi sono chiavi primarie (per tali attributi non esistono determinanti e quindi la parte sinistra è vuota). Successivamente, tali algoritmi si muovono verso l'alto nella rete. È importante notare che la rete può essere attraversata non completamente, ossia se si fornisce un massimo desiderato per la dimensione della parte sinistra, allora oltre quel livello, con tale dimensione, l'algoritmo non proseguirà.

Nella figura qui sotto è mostrato come utilizzare una rete algebrica nel problema delle dipendenze funzionali. Qui ogni arco (X, XY) rappresenta una dipendenza X → Y. Ad esempio, abbiamo attraversato il primo livello e sappiamo che la dipendenza è mantenuta A → B (rappresentiamolo con una connessione verde tra i vertici A e B). Pertanto, quando ci muoviamo verso l'alto nella rete, non dobbiamo controllare la dipendenza A, C → B, poiché essa non sarà più minima. Analogamente, non la verificheremmo se fosse mantenuta la dipendenza C → B.

Inoltre, di norma, tutti gli algoritmi moderni per la ricerca delle dipendenze funzionali utilizzano una struttura dati chiamata partizione (nella fonte 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 di tuple di r, che hanno lo stesso valore per X, cioè c(t) = {i|ti[X] = t[X]}. Una partizione è un insieme di cluster, escludendo i cluster di lunghezza unità:

In parole semplici, una partizione per un attributo X rappresenta un insieme di elenchi, dove ogni elenco contiene i numeri di riga con valori identici per X. Nella letteratura contemporanea, la struttura che rappresenta le partizioni è chiamata position list index (PLI). I cluster di lunghezza unitaria vengono esclusi per comprimere il PLI, poiché si tratta di cluster che contengono solo il numero di registrazione 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 (a sinistra è comparsa una nuova colonna, con i numeri di riga della tabella):

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

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

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

Consideriamo un esempio:

Nel primo caso abbiamo ottenuto una partizione vuota. Se guardiamo attentamente la tabella, in effetti non ci sono valori identici su due attributi. Se ora modifichiamo un po' la tabella (caso a destra), otteniamo già un'intersezione non vuota. In questo caso, le righe 1 e 2 hanno davvero valori identici per gli attributi Genere e Dottore.

Ora ci sarà utile il concetto di dimensione della partizione. Formalmente:

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

Ora possiamo definire uno dei lemmi chiave, che per le partizioni date consente di determinare se una 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, sono necessari 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 passo
4. Confrontare le dimensioni delle partizioni ottenute al primo e al terzo passo

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

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

Riferimenti bibliografici:

1. Huhtala Y. et al. TANE: Un algoritmo efficiente per la scoperta di dipendenze funzionali e approssimate //The computer journal. – 1999. – Vol. 42. – N. 2. – P. 100-111.
2. Kruse S., Naumann F. Scoperta efficiente di dipendenze approssimate //Proceedings of the VLDB Endowment. – 2018. – Vol. 11. – N. 7. – P. 759-772.
3. Papenbrock T., Naumann F. Un approccio ibrido alla scoperta di dipendenze funzionali //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – P. 821-833.
4. Papenbrock T. et al. Scoperta di dipendenze funzionali: una valutazione sperimentale di sette algoritmi //Proceedings of the VLDB Endowment. – 2015. – Vol. 8. – N. 10. – P. 1082-1093.
5. Kumar A. et al. Unirsi o non unirsi?: Pensare due volte agli join prima della selezione delle caratteristiche //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – P. 19-34.
6. Abo Khamis M. et al. In-database learning with sparse tensors //Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. – ACM, 2018. – P. 325-340.
7. Hellerstein J. M. et al. La libreria di analisi MADlib: o MAD skills, l'SQL //Proceedings of the VLDB Endowment. – 2012. – Vol. 5. – N. 12. – P. 1700-1711.
8. Qin C., Rusu F. Approssimazioni speculative per l'ottimizzazione del gradiente distribuito terascale //Proceedings of the Fourth Workshop on Data analytics in the Cloud. – ACM, 2015. – P. 1.
9. Meng X. et al. Mllib: Machine learning 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