Introduzione alle dipendenze funzionali

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

Considereremo le dipendenze funzionali nel contesto dei database relazionali. Per dirla in modo molto approssimativo, in tali database le informazioni vengono archiviate sotto forma di tabelle. Successivamente, utilizziamo concetti approssimativi che non sono intercambiabili nella teoria relazionale rigorosa: chiameremo la tabella stessa una relazione, le colonne - attributi (il loro insieme - uno schema di relazione) e l'insieme di valori di riga su un sottoinsieme di attributi - una tupla.

Ad esempio, nella tabella sopra, (Benson, M, organo M) è una tupla di attributi (Paziente, Paul, Dottore).
Più formalmente, questo è scritto come segue: [Paziente, genere, medico🇧🇷 (organo Benson, M, M).
Ora possiamo introdurre il concetto di dipendenza funzionale (FD):

Definizione 1. La relazione R soddisfa la legge federale X → Y (dove X, Y ⊆ R) se e solo se per qualsiasi tupla , ∈ R vale: se [X] = [X], quindi [Y] = [Y]. In questo caso, diciamo che X (il determinante, o insieme di attributi che definisce) determina funzionalmente Y (l'insieme dipendente).

In altre parole, la presenza di una legge federale X → Y significa che se abbiamo due tuple in R e corrispondono negli attributi X, allora coincideranno negli attributi Y.
E ora, in ordine. Diamo un'occhiata agli attributi Il paziente и Genere per il quale vogliamo scoprire se ci sono dipendenze tra loro o meno. Per tale insieme di attributi possono esistere le seguenti dipendenze:

1. Paziente → Sesso
2. Sesso → Paziente

Come definito sopra, affinché la prima dipendenza possa essere mantenuta, ogni valore di colonna univoco Il paziente solo un valore di colonna deve corrispondere Genere. E per la tabella di esempio è proprio così. Tuttavia, ciò non funziona nella direzione opposta, ovvero la seconda dipendenza non è soddisfatta e l'attributo Genere non è un determinante per Paziente. Allo stesso modo, se prendiamo la dipendenza Dottore → Paziente, puoi vedere che è violato, poiché il valore pettirosso questo attributo ha diversi significati - Ellis e Graham.

Pertanto, le dipendenze funzionali consentono di determinare le relazioni esistenti tra insiemi di attributi di tabella. Da qui in poi prenderemo in considerazione i collegamenti più interessanti, anzi tali X → Ycosa sono:

• non banale, cioè il lato destro della dipendenza non è un sottoinsieme del sinistro (Y̸⊆ X);
• minimo, cioè non esiste tale dipendenza Z → YChe Z ⊂ X.

Le dipendenze considerate fino a questo punto erano rigide, ovvero non prevedevano alcuna violazione della tabella, ma oltre ad esse ci sono anche quelle che consentono qualche incoerenza tra i valori delle tuple. Tali dipendenze vengono poste in una classe separata, chiamata approssimata, e possono essere violate per un certo numero di tuple. Questo importo è regolato dall'indicatore di errore massimo emax. Ad esempio, il tasso di errore = 0.01 può significare che la dipendenza può essere violata dall'1% delle tuple disponibili sull'insieme di attributi considerato. Cioè, per 1000 record, un massimo di 10 tuple possono violare la legge federale. Considereremo una metrica leggermente diversa, basata su valori diversi a coppie delle tuple confrontate. Per dipendenza X → Y sull'atteggiamento r è considerato così:

Calcoliamo l'errore per Dottore → Paziente dall'esempio sopra. Abbiamo due tuple i cui valori differiscono nell'attributo Il paziente, ma coincidono Medico: [Dottore, paziente] = (Robin, Ellis) E [Dottore, paziente] = (Robin, Graham). Dopo la definizione di errore, dobbiamo tenere conto di tutte le coppie in conflitto, il che significa che ce ne saranno due: (, ) e il suo inverso (, ). Sostituiamolo nella formula e otteniamo:

Ora proviamo a rispondere alla domanda: “Perché tutto questo?” In realtà, le leggi federali sono diverse. Il primo tipo sono quelle dipendenze determinate dall'amministratore nella fase di progettazione del database. Di solito sono pochi, rigorosi e l'applicazione principale è la normalizzazione dei dati e la progettazione di schemi relazionali.

Il secondo tipo sono le dipendenze, che rappresentano dati “nascosti” e relazioni tra attributi precedentemente sconosciute. Cioè, tali dipendenze non sono state pensate al momento della progettazione e vengono trovate per il set di dati esistente, in modo che in seguito, sulla base delle numerose leggi federali identificate, si possa trarre qualsiasi conclusione sulle informazioni memorizzate. Sono proprio queste dipendenze con cui lavoriamo. Sono gestiti da un intero campo di data mining con varie tecniche di ricerca e algoritmi costruiti sulla base. Scopriamo come possono essere utili le dipendenze funzionali trovate (esatte o approssimative) in qualsiasi dato.

Oggi, una delle principali applicazioni delle dipendenze è la pulizia dei dati. Implica lo sviluppo di processi per identificare i “dati sporchi” e quindi correggerli. Esempi importanti di "dati sporchi" sono duplicati, errori di dati o errori di battitura, valori mancanti, dati obsoleti, spazi aggiuntivi e simili.

Esempio di errore nei dati:

Esempio di duplicati nei dati:

Ad esempio, abbiamo una tabella e una serie di leggi federali che devono essere eseguite. La pulizia dei dati in questo caso comporta la modifica dei dati in modo che le leggi federali diventino corrette. In questo caso, il numero di modifiche dovrebbe essere minimo (questa procedura ha i propri algoritmi, sui quali non ci concentreremo in questo articolo). Di seguito è riportato un esempio di tale trasformazione dei dati. A sinistra è riportata la relazione originaria, in cui, ovviamente, i LS necessari non sono soddisfatti (in rosso è evidenziato un esempio di violazione di uno dei LS). Sulla destra c'è la relazione aggiornata, con le celle verdi che mostrano i valori modificati. Dopo questa procedura, le dipendenze necessarie hanno iniziato a essere mantenute.

Un'altra applicazione popolare è la progettazione di database. Qui vale la pena ricordare le forme normali e la normalizzazione. La normalizzazione è il processo che rende una relazione conforme a un determinato insieme di requisiti, ciascuno dei quali è definito dalla forma normale a suo modo. Non descriveremo i requisiti delle varie forme normali (questo viene fatto in qualsiasi libro sul corso sui database per principianti), ma noteremo solo che ognuna di esse utilizza il concetto di dipendenze funzionali a modo suo. Dopotutto, i FL sono intrinsecamente vincoli di integrità che vengono presi in considerazione durante la progettazione di un database (nel contesto di questa attività, i FL sono talvolta chiamati superchiavi).

Consideriamo la loro applicazione per le quattro forme normali nell'immagine qui sotto. Ricordiamo che la forma normale di Boyce-Codd è più restrittiva della terza forma, ma meno restrittiva della quarta. Per ora non consideriamo quest'ultimo, poiché la sua formulazione richiede la comprensione delle dipendenze multivalore, che non ci interessano in questo articolo.

Un'altra area in cui le dipendenze hanno trovato la loro applicazione è la riduzione della dimensionalità dello spazio delle funzionalità in attività quali la creazione di un classificatore Bayes ingenuo, l'identificazione di funzionalità significative e la riparametrizzazione di un modello di regressione. Negli articoli originali, questo compito è chiamato determinazione della ridondanza e della rilevanza delle funzionalità [5, 6], ed è risolto con l'uso attivo dei concetti di database. Con l'avvento di tali lavori, possiamo dire che oggi c'è una richiesta di soluzioni che ci consentano di combinare database, analisi e implementazione dei problemi di ottimizzazione di cui sopra in un unico strumento [7, 8, 9].

Esistono molti algoritmi (moderni e meno moderni) per la ricerca di leggi federali in un set di dati e possono essere suddivisi in tre gruppi:

• Algoritmi che utilizzano l'attraversamento di reticoli algebrici (algoritmi di attraversamento del reticolo)
• Algoritmi basati sulla ricerca di valori concordati (Algoritmi Difference- e agreement-set)
• Algoritmi basati su confronti a coppie (Algoritmi di induzione delle dipendenze)

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


Puoi leggere di più su questa classificazione [4]. Di seguito sono riportati esempi di algoritmi per ciascun tipo:

Attualmente stanno emergendo nuovi algoritmi che combinano diversi approcci per trovare dipendenze funzionali. Esempi di tali algoritmi sono Pyro [2] e HyFD [3]. Un'analisi del loro lavoro è prevista nei seguenti articoli di questa serie. In questo articolo esamineremo solo i concetti e i lemmi di base necessari per comprendere le tecniche di rilevamento delle dipendenze.

Cominciamo con uno semplice, l'insieme delle differenze e dell'accordo, utilizzato nel secondo tipo di algoritmi. Difference-set è un insieme di tuple che non hanno gli stessi valori, mentre agreement-set, al contrario, è tuple che hanno gli stessi valori. Vale la pena notare che in questo caso stiamo considerando solo il lato sinistro della dipendenza.

Un altro concetto importante che abbiamo incontrato sopra è il reticolo algebrico. Poiché molti algoritmi moderni operano su questo concetto, dobbiamo avere un'idea di cosa si tratti.

Per introdurre il concetto di reticolo è necessario definire un insieme parzialmente ordinato (o insieme parzialmente ordinato, abbreviato in poset).

Definizione 2. Un insieme S si dice parzialmente ordinato dalla relazione binaria ⩽ se per ogni a, b, c ∈ S sono soddisfatte le seguenti proprietà:

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

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

Come esempio più semplice di insieme parzialmente ordinato, possiamo prendere l'insieme di tutti i numeri naturali N con la consueta relazione d'ordine ⩽. È facile verificare che tutti gli assiomi necessari sono soddisfatti.

Un esempio più significativo. Considera l'insieme di tutti i sottoinsiemi {1, 2, 3}, ordinati dalla relazione di inclusione ⊆. Infatti, questa relazione soddisfa tutte le condizioni di ordine parziale, quindi ⟨P ({1, 2, 3}), ⊆⟩ è un insieme parzialmente ordinato. La figura seguente mostra la struttura di questo insieme: se un elemento può essere raggiunto tramite frecce verso un altro elemento, allora sono in una relazione d'ordine.

Avremo bisogno di due definizioni più semplici dal campo della matematica: superiore e inferiore.

Definizione 3. Sia ⟨S, ⩽⟩ un insieme parzialmente ordinato, A ⊆ S. L'estremo 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 c'è un elemento più piccolo in U, allora è chiamato supremo ed è indicato sup A.

Il concetto di limite inferiore esatto viene introdotto in modo simile.

Definizione 4. Sia ⟨S, ⩽⟩ un insieme parzialmente ordinato, A ⊆ S. L'estremo 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 c'è un elemento più grande in L, allora è chiamato minimo ed è indicato come inf A.

Considera come esempio l'insieme parzialmente ordinato sopra ⟨P ({1, 2, 3}), ⊆⟩ e trova in esso il massimo e il minimo:

Ora possiamo formulare la definizione di reticolo algebrico.

Definizione 5. Sia ⟨P,⩽⟩ un insieme parzialmente ordinato tale che ogni sottoinsieme di due elementi abbia un limite superiore e uno inferiore. Allora P è detto reticolo algebrico. In questo caso, sup{x, y} si scrive come x ∨ y, e inf {x, y} come x ∧ y.

Verifichiamo che il nostro esempio di lavoro ⟨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, considera gli insiemi {1, 2} e {1, 3} e trova il loro minimo e massimo. Se li intersechiamo, otterremo l'insieme {1}, che sarà quello inferiore. Otteniamo il massimo combinandoli: {1, 2, 3}.

Negli algoritmi per identificare problemi fisici, lo spazio di ricerca è spesso rappresentato sotto forma di un reticolo, dove insiemi di un elemento (leggi il primo livello del reticolo di ricerca, dove il lato sinistro delle dipendenze è costituito da un attributo) rappresentano ciascun attributo della relazione originaria.
Innanzitutto consideriamo le dipendenze della forma ∅ → Attributo singolo. Questo passaggio consente di determinare quali attributi sono chiavi primarie (per tali attributi non esistono determinanti e quindi la parte sinistra è vuota). Inoltre, tali algoritmi si muovono verso l'alto lungo il reticolo. Vale la pena notare che non è possibile attraversare l'intero reticolo, ovvero se all'input viene passata la dimensione massima desiderata del lato sinistro, l'algoritmo non andrà oltre un livello con quella dimensione.

La figura seguente mostra come è possibile utilizzare un reticolo algebrico nel problema di trovare una FZ. Qui ogni bordo (X,XY) rappresenta una dipendenza X → Y. Ad esempio, abbiamo superato il primo livello e sappiamo che la dipendenza è mantenuta A→B (lo visualizzeremo come una connessione verde tra i vertici A и B). Ciò significa che inoltre, quando ci spostiamo lungo il reticolo, potremmo non controllare la dipendenza A, C → B, perché non sarà più minimo. Allo stesso modo, non lo controlleremo se la dipendenza venisse mantenuta C→B.

Inoltre, di norma, tutti gli algoritmi moderni per la ricerca delle leggi federali utilizzano una struttura di dati come una partizione (nella fonte originale - partizione rimossa [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 in r che hanno lo stesso valore per X, cioè c(t) = {i|ti[X] = t[X]}. Una partizione è un insieme di cluster, esclusi i cluster di lunghezza unitaria:

In parole semplici, una partizione per un attributo X è un insieme di elenchi, in cui ciascun elenco contiene numeri di riga con gli stessi valori per X. Nella letteratura moderna, la struttura che rappresenta le partizioni è chiamata indice dell'elenco di posizioni (PLI). I cluster di lunghezza unitaria sono esclusi ai fini della compressione PLI perché sono cluster che contengono solo un numero di record con un valore univoco che sarà sempre facile da identificare.

Diamo un'occhiata a un esempio. Torniamo alla stessa tabella con i pazienti e creiamo partizioni per le colonne Il paziente и Genere (è apparsa una nuova colonna a sinistra, in cui sono contrassegnati i numeri delle righe della tabella):

Inoltre, secondo la definizione, la partizione per la colonna Il paziente sarà effettivamente vuoto, poiché i singoli cluster sono esclusi dalla partizione.

Le partizioni possono essere ottenute con diversi attributi. E ci sono due modi per farlo: esaminando la tabella, costruire una partizione utilizzando tutti gli attributi necessari contemporaneamente, oppure costruirla utilizzando l'operazione di intersezione delle partizioni utilizzando un sottoinsieme di attributi. Gli algoritmi di ricerca delle leggi federali utilizzano la seconda opzione.

In parole semplici, ad esempio, ottenere una partizione per colonne ABC, puoi prendere partizioni per AC и B (o qualsiasi altro insieme di sottoinsiemi disgiunti) e intersecarli tra loro. L'operazione di intersezione di due partizioni seleziona i cluster di maggiore lunghezza comuni ad entrambe le partizioni.

Diamo un'occhiata ad un esempio:

Nel primo caso, abbiamo ricevuto una partizione vuota. Se osservi attentamente la tabella, in effetti non ci sono valori identici per i due attributi. Se modifichiamo leggermente la tabella (il caso a destra), otterremo già un'intersezione non vuota. Inoltre, le righe 1 e 2 contengono effettivamente gli stessi valori per gli attributi Genere и Medico.

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

In poche parole, la dimensione della partizione è il numero di cluster inclusi nella partizione (ricorda che i singoli cluster non sono inclusi nella partizione!):

Ora possiamo definire uno dei lemmi chiave, che per determinate partizioni ci consente di determinare se viene mantenuta o meno una dipendenza:

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

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

1. Calcola 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. Confronta le dimensioni delle partizioni ottenute nel primo e nel terzo passaggio

Di seguito è riportato un esempio per verificare se la dipendenza vale secondo questo lemma:

In questo articolo, abbiamo esaminato concetti come dipendenza funzionale, dipendenza funzionale approssimativa, abbiamo visto dove vengono utilizzati e quali algoritmi esistono per la ricerca di funzioni fisiche. Abbiamo anche esaminato in dettaglio i concetti basilari ma importanti che vengono utilizzati attivamente nei moderni algoritmi per la ricerca delle leggi federali.

Riferimenti:

1. Huhtala Y. et al. TANE: Un algoritmo efficiente per scoprire dipendenze funzionali e approssimative //Il diario del computer. – 1999. – T. 42. – N. 2. – pp. 100-111.
2. Kruse S., Naumann F. Scoperta efficiente di dipendenze approssimative // ​​Atti della dotazione VLDB. – 2018. – T. 11. – N. 7. – pp. 759-772.
3. Papenbrock T., Naumann F. Un approccio ibrido alla scoperta delle dipendenze funzionali // Atti della conferenza internazionale sulla gestione dei dati del 2016. – ACM, 2016. – pp. 821-833.
4. Papenbrock T. et al. Scoperta delle dipendenze funzionali: una valutazione sperimentale di sette algoritmi // Atti del VLDB Endowment. – 2015. – T. 8. – N. 10. – pp. 1082-1093.
5. Kumar A. et al. Partecipare o non partecipare?: Pensare due volte alle unioni prima di selezionare le funzionalità // Atti della Conferenza internazionale sulla gestione dei dati del 2016. – 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. – pp. 325-340.
7. Hellerstein JM et al. La libreria di analisi MADlib: o competenze MAD, gli //Atti SQL del VLDB Endowment. – 2012. – T. 5. – N. 12. – pp. 1700-1711.
8. Qin C., Rusu F. Approssimazioni speculative per l'ottimizzazione della discesa del gradiente distribuita su scala terascala // Atti del quarto workshop sull'analisi dei dati nel cloud. – ACM, 2015. – Pag. 1.
9. Meng X. et al. Mllib: apprendimento automatico in Apache Spark //The Journal of Machine Learning Research. – 2016. – T. 17. – N. 1. – pp. 1235-1241.

Autori dell'articolo: Anastasia Birillo, ricercatore presso Ricerca JetBrains, Studente del centro CS и Nikita Bobrov, ricercatore presso Ricerca JetBrains

Fonte: habr.com