Skip to content

SQL è disuguaglianza triangolare

22 settembre 2015

In questo articolo intendo, con un esempio tratto dalla mia realtà lavorativa, mostrare un legame inaspettato tra un’applicazione informatica e una teoria matematica. Legami di questo tipo sono talvolta difficili da individuare, perché se da un lato la pratica è travolgente e “sporca”, dall’altro la teoria è complicata e distaccata. Ricondursi ad una teoria comporta solitamente l’astrazione di una situazione concreta, esercizio a volte difficoltoso ma potenzialmente utile perché può dare fondamento a quella che altrimenti è solo un’intuizione.

Parlo di SQL, che è un linguaggio informatico per interrogare (query) database. Per semplicità, consideriamo un database composto da una singola tabella, con un certo numero di righe (record) e un certo numero di colonne (campi). Con l’SQL è possibile effettuare operazioni su tutti i valori presenti in determinati campi, come ad esempio totalizzare il contenuto di un campo numerico o estrarre tutti i valori univoci di un campo alfanumerico.

Supponiamo di avere un database con due campi, uno che presenta n valori distinti e uno che contiene valori numerici sia positivi che negativi. Siano i record del database partizionati sulla base del primo campo, quindi il generico record x appartiene necessariamente ad uno degli insieme A_1, \ldots, A_n, la cui unione determina l’insieme complessivo A.

Un esempio è una tabella contenente tutti i movimenti di cassa di un conto corrente nel corso di un anno. In questo caso n=12, e A_3 rappresenta l’insieme delle righe riferite al mese di marzo. Chiamiamo f(x) il valore numerico del flusso di cassa situato nel record x. Il saldo finale a fine anno è

\sum_{x\in A} f(x),

che è uno dei classici risultati che si possono calcolare agevolmente in SQL.

Poniamo ora di essere interessati al totale delle entrate, vale a dire di ignorare le righe con f(x) negativo. Matematicamente stiamo usando la funzione ()_+, chiamata parte positiva. Si definisce (z)_+ = z se z \geq 0, ed è (z)_+ = 0 se z < 0. Siamo però di fronte ad un ostacolo, perché SQL non calcola la funzione ()_+ sui dati di una singola riga, così come non calcola la funzione \max tra due valori. Al più può trovare il \max tra tutti i valori di un campo, ma la funzione non può essere usata per determinare il massimo tra due numeri, anche perché in caso contrario avremmo potuto scrivere \max(x, 0) invece di ()_+.

E’ anche vero che in SQL si possono fare filtri per escludere i valori negativi, ma nel mio esempio questi valori dovevano essere invece posti a 0. Come fare senza la funzione che calcola la parte positiva? Si dà il caso che in SQL ci sia la funzione \mbox{abs} che calcola il valore assoluto dell’input. Per chi vuole distrarsi, propongo di interrompere la lettura e di provare invece a definire la funzione ()_+ avendo a disposizione solo \mbox{abs} e le quattro operazioni. La soluzione sarà data a tradimento più sotto.

La funzione ()_+ non è lineare, quindi l’applicarla in varie fasi di raggruppamento porta a risultati diversi. Ad esempio la si può applicare a monte, su ogni riga del database, per trasformare in 0 tutte le transazioni negative. La comparazione che mi sono ritrovato a fare prevedeva invece di applicarle in fasi successive di raggruppamento. In un primo caso consideravo solo i saldi mensili positivi, sommandoli poi insieme:

\sum_{i = 1}^n \left( \sum_{x \in A_i} f(x) \right)_+;

un secondo caso considerava il saldo totale solo se positivo:

\left( \sum_{x \in A} f(x)\right)_+ = \left( \sum_{i = 1}^n \sum_{x \in A_i} f(x) \right)_+.

Dalle mie estrazioni sembrava che il primo risultato fosse sempre maggiore o uguale al secondo. E’ sempre vero? Perché? lo si può dimostrare?

Così come descritto, il problema potrebbe sembrare fin troppo semplice, ma è appena il caso di dire che capire cosa stesse succedendo nella situazione reale non era altrettanto palese: molti campi e molte tabelle aggiunte in tempi diversi, una partizione meno visibile rispetto ai mesi di calendario e un significato più articolato di semplici transazioni monetarie contribuivano a confondere le acque. Quindi già la formulazione in termini matematici è stata di grande aiuto.

Per proseguire nell’astrazione, chiamo y_i = \sum_{x\in A_i} f(x), quindi quello che succedeva empiricamente era che

(y_1 + \ldots + y_n)_+ \leq (y_1)_+ + \ldots + (y_n)_+.

Per tornare al problema della mancanza della funzione ()_+ in SQL, una soluzione è scrivere

(x)_+ = \frac{x + |x|}{2}.

Chi si fosse perso l’occasione di trovare autonomamente questa formuletta rimedi ora verificando che sia corretta. Usando questa formula, dobbiamo allora dimostrare che

\frac{y_1 + \ldots + y_n + |y_1 + \ldots + y_n|}{2} \leq \frac{y_1 + \ldots + y_n}{2} + \frac{|y_1| + \ldots + |y_n|}{2},

che equivale a

|y_1 + \ldots + y_n| \leq |y_1| + \ldots + |y_n|,

che è sempre vera!

Quest’ultima equazione è infatti una generalizzazione della disuguaglianza triangolare. Se immaginiamo di avere un poligono di n+1 lati, e di individuare un lato principale, il suo vettore è determinato dalla somma dei vettori di tutti gli altri lati, quindi la sua lunghezza è |y_1 + \ldots + y_n|. Tutti gli altri lati, insieme, determinano una spezzata che connette i due vertici toccati dal lato principale, e che ha lunghezza |y_1| + \ldots + |y_n|. Per definizione il primo segmento, essendo rettilineo, deve connettere i due vertici percorrendo la strada più breve, il che giustifica l’equazione.

Nel nostro caso abbiamo scalari invece di vettori, ma il ragionamento sta in piedi comunque immaginando che siano proiezioni di vettori sulla retta reale. Una dimostrazione rigorosa può ad esempio partire dalla disuguaglianza triangolare base,

|y_1 + y_2| \leq |y_1| + |y_2|,

ed estendere poi il numero di dimensioni tramite ricorrenza. Poiché questa disuguaglianza è vera, diciamo che la funzione valore assoluto è sub-additiva.

In conclusione, il processo di astrazione mi è stato utile sia per apprendere maggiori informazioni sul lavoro che stavo facendo grazie alla sua matematizzazione, sia per validare teoricamente l’intuizione costruita per via empirica che il totale diminuiva con l’aumentare del grado di raggruppamento. Come effetto collaterale, che personalmente non riesco a considerare meno importante, la possibilità di essere coinvolto in un’attività delle più umane: usare il cervello.

Advertisements
No comments yet

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: