Basi Di Dati

Introduzione alle basi di dati

Mercoledì 28 settembre 2022, 15:00

“I dati sono il nuovo petrolio” (Clive Humby, UK Mathematician, 2006). Al contrario del petrolio, i dati vengono generati ad un ritmo impressionante. Così come il petrolio è stato la risorsa naturale che ha portato alla rivoluzione industriale, i dati saranno la risorsa naturale della nuova rivoluzione industriale.

Caratteristiche dei dati

• È ormai facile produrre quantità enormi di dati, che possono essere riusati, condivisi, collegati per soddisfare nuove esigenze e per condurre nuove analisi.
• I dati devono essere organizzati e governati in modo razionale e memorizzati in forme usabili e accessibili.
• Fa parte delle risorse di un'organizzazione.
• Ha diverse funzioni:
  • Raccolta, acquisizione delle informazioni.
  • Archiviazione, conservazione delle informazioni.
  • Elaborazione delle informazioni.
  • Distribuzione, scambio di informazioni.
  • Il concetto di “sistema informativo” è indipendente da qualsiasi forma di automatizzazione.
• Collezione di dati in memoria secondaria stabile in modo che si conservino con il passare del tempo.
• Collezione di dati in memoria secondaria gestita da un apposito sistema software, chiamato DBMS (Data Base Management Systems).

Questi dati devono essere gestiti, memorizzati e organizzati in maniera corretta per diversi scopi. La memoria secondaria deve essere condivisa in modo da poter essere acceduta da tanti agenti (o utenti) in modo concorrente ed è gestita in modo centralizzato.

DBMS (Data Base Management Systems)

• Il DBMS è il sistema responsabile della gestione dei dati: i dati sono accessibili all’esterno solo tramite il DBMS.
• Sistema (prodotto software) in grado di gestire collezioni di dati che siano:
  • Grandi: di dimensioni molto maggiori della memoria centrale dei sistemi di calcolo utilizzati normalmente.
  • Persistenti: con un periodo di vita indipendente dalle singole esecuzioni dei programmi che le utilizzano.
  • Condivise: utilizzate da applicazioni diverse, garantendo:
    • Affidabilità: resistenza a malfunzionamenti hardware e software.
    • Privatezza: con una disciplina e un controllo degli accessi.
    • Efficienza: utilizzare al meglio le risorse di spazio e tempo del sistema.
    • Efficacia: rendere produttive le attività dei suoi utilizzatori.
• Ogni DBMS è basato su un modello dei dati, ovvero un insieme di costrutti utilizzati per organizzare i dati di interesse e descriverne le operazioni.
• Ci si riferisce principalmente a DBMS basati sul modello relazionale, a sua volta basato sulla nozione di relazione.

Proposto da E. F. Codd nel 1970 per favorire l’indipendenza fisica dei dati (ovvero per rendere il modo in cui si usano i dati a livello logico indipendente dalla loro memorizzazione fisica). Disponibile come modello logico in DBMS reali nel 1981. Si basa sul concetto matematico di relazione (ma con importanti varianti). Le relazioni hanno una rappresentazione naturale per mezzo di tabelle. È un formalismo che consente di organizzare, interrogare e utilizzare dati secondo certe regole e certe strategie.

Relazioni matematiche e database

• Il prodotto cartesiano D₁ × D₂ × ... × D_n è l’insieme di tutte le n-ple ordinate (d₁, d₂, ..., d_n) tali che d₁ ∈ D₁, d₂ ∈ D₂, ..., d_n ∈ D_n.
• Una relazione matematica sugli insiemi D₁, D₂, ..., D_n è un sottoinsieme del prodotto cartesiano D₁ × D₂ × ... × D_n.
• Se R è una relazione matematica sugli insiemi D₁, D₂, ..., D_n, tali insiemi sono detti i domini della relazione R.
• Una relazione su n domini si dice che ha grado (o arità) n.
• Il numero di n-ple contenute in una relazione è la cardinalità della relazione stessa.
• Una relazione matematica è quindi un insieme di ennuple ordinate (dette anche n-ple, o tuple) su D₁, D₂, ..., D_n, dove ogni tupla è una sequenza di valori della forma (d₁, ..., d_n) tale che d₁ ∈ D₁, ..., d_n ∈ D_n.
• La tupla (d₁, ..., d_n) viene anche scritta come <d₁, ..., d_n>.

Una relazione nel modello relazionale è simile ad una relazione matematica, ma con le seguenti differenze:

• Le posizioni che determinano le varie componenti delle tuple sono dette attributi (dominio della relazione matematica).
• Ogni attributo è caratterizzato da un nome ed un insieme di valori atomici, quest’ultimo detto dominio dell’attributo.
• Si noti che un valore atomico è un valore semplice (ad esempio, un intero o una stringa), non costituito da una struttura complessa.
• Non può succedere che due attributi della stessa relazione abbiano lo stesso nome.

Rappresentazione delle relazioni

• Una relazione nel modello relazionale si può rappresentare come una tabella in cui:
  • Gli attributi corrispondono alle colonne ed i nomi degli attributi (tutti diversi l’uno dall’altro) sono usati come intestazioni delle colonne.
  • Poiché ad ogni colonna della relazione è associato il nome di un attributo, l’ordinamento delle colonne nella tabella è irrilevante; la struttura, al contrario della relazione matematica, è non posizionale.
  • Ogni riga della tabella corrisponde ad una tupla della relazione, e siccome la relazione è un insieme di tuple (cioè una collezione senza ripetizioni), non ci possono essere due righe uguali nella tabella.
• Sia X l’insieme degli attributi di una relazione R. Se t è una tupla di R, cioè una tupla su X, e se A ⊆ X, allora t[A] oppure anche t.A detta la “restrizione” di t su A, indica il valore che la tupla t ha in corrispondenza dell’attributo A.
• La stessa notazione è estesa anche ad insiemi di attributi.
• Per completezza definiamo anche t[∅] (cioè la restrizione della tupla t sull’insieme vuoto di attributi, e stabiliamo che t[∅] sia la cosiddetta “tupla vuota”, cioè una tupla senza componenti).

Schema di relazione e istanza

• La specifica del nome R di una relazione, degli attributi A₁, A₂, ..., A_n e dei domini di tali attributi D₁, D₂, ..., D_n forma lo schema di relazione, che si denota come R(A₁: D₁, A₂: D₂, ..., A_n: D_n) oppure semplicemente nel caso non interessi esplicitare i domini degli attributi come R(A₁, A₂, ..., A_n).
• Di conseguenza, una tupla di R con t[A₁] = a, t[A₂] = b, ..., t[A_n] = c si può denotare anche come <A₁: a, A₂: b, ..., A_n: c>.
• Una tupla di una relazione si può rappresentare come “tupla etichettata”, in cui le etichette sono gli attributi della relazione, ed i valori associati alle etichette sono i valori in corrispondenza dei vari attributi.
• I valori di ciascuna colonna sono fra loro omogenei, cioè appartengono allo stesso dominio.
• Le righe (cioè le tuple) sono tutte diverse fra loro (perché la relazione è un insieme di tuple, non un multiinsieme).
• Le intestazioni delle colonne (attributi) sono tutte diverse tra loro.
• Nella rappresentazione tabellare della relazione:
  • L’ordinamento tra le righe è irrilevante.
  • L’ordinamento tra le colonne è irrilevante.
• Il modello relazionale è basato sui valori, quindi utilizza i valori per creare legami (relazioni) -> eventuali riferimenti fra due relazioni diverse sono espressi per mezzo di valori che compaiono nelle tuple di entrambe le relazioni.
• Schema di relazione := un nome di relazione R con un insieme non vuoto di attributi A₁, ..., A_n ed eventualmente anche i corrispondenti domini R(A₁, ..., A_n) oppure R(A₁: D₁, A₂: D₂, ..., A_n: D_n).
• Istanza di relazione su uno schema R(X) := insieme r delle tuple sull’insieme di attributi X.
• Relazione := schema Z di relazione + istanza di relazione su Z.
• Schema di base di dati := insieme non vuoto di schemi di relazione (con nomi diversi) R = {R₁(A₁ A₂ ... A_n), ..., R_m(B₁ B₂ ... B_n)}.
• Istanza di base di dati su uno schema R = {R₁(X₁), ..., R_m(X_m)} := insieme di relazioni r = {r₁, ..., r_m}, dove per ogni i = 1, ..., m, r_i è una istanza relazione sullo schema R_i(X_i).
• Base di dati := schema S di basi di dati + istanza di basi di dati su S.

Algebra relazionale

Giovedì 29 settembre 2022, 13:00

Formati da due componenti:

• Operazioni sullo schema -> DDL: data definition language
• Operazioni sui dati -> DML: data manipulation language interrogazioni ("query language") aggiornamenti.

Tipologia

• Dichiarativi: specificano le proprietà del risultato ("che cosa").
• Procedurali: specificano le modalità di generazione del risultato ("come").

Rappresentanti più significativi

• Algebra relazionale: procedurale.
• Calcolo relazionale: dichiarativo.
• SQL (Structured Query Language): parzialmente dichiarativo.
• QBE (Query by Example): dichiarativo.
• Fornisce una base teorica e matematica ai linguaggi di query.
• Formata da un insieme di relazioni + insieme di operatori che operano sulle relazioni.
• Costituita da un insieme di operatori:
  • Definiti su relazioni.
  • Che producono relazioni.
  • E possono essere composti.

Operatori dell’algebra relazionale

• Unione, intersezione, differenza.
• Ridenominazione.
• Selezione.
• Proiezione.
• Join in diverse versioni: join naturale, prodotto cartesiano, theta-join.

Ogni operatore è formato da sintassi (forma di frase) + semantica (significato della frase) + pragmatica (uso pratico della frase). A livello estensionale (cioè delle istanze), le relazioni sono insiemi di tuple, e quindi è sensato definire per essi gli operatori insiemistici. Sono operatori binari (due operandi) e i risultati dell’applicazione di tali operatori sono a loro volta relazioni (vista la proprietà di chiusura delle algebre). È possibile applicare unione (in RA \union), intersezione (in RA \intersect), differenza (in RA \diff) solo a relazioni che hanno uguali definizioni intensionali (ovvero stessi identici attributi). La semantica degli operatori insiemistici è quella classica.

L’algebra relazionale è un impianto matematico formato da operatori che lavorano su relazioni. Le relazioni sono quindi i “valori” su cui gli operatori agiscono. Il risultato di una interrogazione espressa in algebra relazionale è esso stesso una relazione e di tale relazione è rilevante sia l’insieme degli attributi sia, ovviamente, le tuple che lo compongono, ma non è, invece, significativo il nome. Potremmo scegliere l’espressione sintattica che ha generato il risultato come nome, ma poiché la relazione risultato non fa parte della base di dati (è semplicemente un valore calcolato nel sistema algebrico), tale nome è irrilevante. Quando passeremo ad analizzare i sistemi di basi di dati (che, al contrario dell’algebra, non sono solo formalismi matematici, ma sono veri e propri sistemi software), ci occuperemo del modo in cui vengono gestiti i risultati di interrogazioni.

L'algebra relazionale è un linguaggio funzionale (non esiste il concetto di side-effect). Operatore monadico (con un argomento) "modifica lo schema" (cambiando il nome di uno o più attributi) lasciando inalterata l'istanza dell'operando. Sintassi: in RA \rename_{A₁, B₁, ..., B_n}(Operando). Semantica: Lo schema della relazione rappresentata da “Operando” viene modificato sostituendo al nome di attributo B_n il nome A_n. Non ci devono essere duplicati negli attributi risultanti dalla ridenominazione (cioè A₁, ..., A_n devono essere tutti diversi tra loro).

Operatori di selezione e proiezione

Supponiamo di volere l'unione dei genitori e dei loro figli. Operatore monadico (cioè con un argomento) che prevede la formulazione di una condizione (un’espressione booleana). Produce un risultato che:

• Ha lo stesso schema dell'operando.
• Contiene un sottoinsieme delle tuple dell'operando, quelle che soddisfano la condizione espressamente indicata nell’operatore. Sintassi: in RA \select_{condizione}(Operando). Condizione: espressione booleana applicata agli attributi della relazione utilizzando gli operatori classici di confronto.
• Semantica: la relazione risultato ha gli stessi attributi dell’operando e contiene le tuple dell'operando che soddisfano la condizione specificata. Esempi: impiegati che guadagnano più di 50 e lavorano a Milano, impiegati che guadagnano più di 50, impiegati che hanno lo stesso nome della filiale presso cui lavorano.

Operatore monadico che produce un risultato che:

• Ha parte degli attributi dell'operando.
• Contiene tuple cui contribuiscono tutte le tuple dell'operando: sono le tuple ottenute dall’operando eliminando gli attributi che non compaiono nella lista espressamente indicata nell’operatore. Sintassi: in RA \project_{ListaAttributi}(Operando). Semantica: la relazione risultato ha i soli attributi contenuti in ListaAttributi, e contiene le tuple ottenute da tutte le tuple dell'operando ristrette agli attributi nella Lista.
• Una proiezione contiene al più tante tuple quante l'operando, e può contenerne di meno, a causa di eliminazione di duplicati. Se X contiene un insieme di attributi “chiave” per R (quando nella stessa relazione non possono esistere due tuple che hanno lo stesso valore per quell'attributo), allora PROJ_X(R) contiene esattamente tante tuple quante R. Gli attributi sono un insieme quindi non hanno ordinamento. Infatti anche se una relazione matematica è formata da tuple ordinate, quando nel modello relazionale si è introdotto il concetto di tupla "etichettata" si è eliminata la componente di ordinamento, dando un nome all'attributo.

Esempi: matricola e cognome di tutti gli impiegati, cognome e filiale di tutti gli impiegati. Sono due operatori "ortogonali": selezione (decomposizione orizzontale) e proiezione (decomposizione verticale). Combinando selezione e proiezione, possiamo estrarre interessanti informazioni da una relazione. Restituire matricola e cognome degli impiegati che guadagnano più di 50. Proiezione e selezione non sono commutative. Due espressioni relazionali sono equivalenti se sono diverse, ma applicate alla base di dati restituiscono lo stesso risultato.

Esercizi

1. Trovare id del concerto (idconc) e id dell’artista (idart) dei concerti tenuti a Roma.
2. Trovare id degli artisti (idart) che non hanno mai tenuto concerti a Napoli, assumendo che non esistano valori di idart nella relazione Concerto che non siano presenti nella relazione Artisti, e assumendo che esistano valori di idart nella relazione Concerto che non siano presenti nella relazione Artisti.

L’unico modo per esprimere condizioni di negazione (che non si riducano a semplici selezioni) è utilizzare l’operatore di differenza. Da questo segue che un principio importante da tenere presente per scrivere query corrette è: L’insieme degli elementi di A che non soddisfano la proprietà B è uguale all’insieme che otteniamo da A togliendo gli elementi che soddisfano la proprietà B.

Operatore JOIN

Mercoledì 5 ottobre 2022, 15:00

• Permette di correlare dati in relazioni diverse.
• Esistono diverse versioni del join: join naturale, theta-join, equijoin, join esterno, ecc.
• Combinando selezione e proiezione, possiamo estrarre informazioni da una relazione, ma non possiamo però correlare informazioni presenti in relazioni diverse.
• Operatore binario che produce un risultato il cui schema ha l'unione (quindi con un risultato che non ha duplicati) degli attributi degli operandi e le cui tuple sono costruite ciascuna a partire da due tuple che si "combinano", una di un operando ed una di un altro operando.

Se X₁ e X₂ sono due insiemi, l’espressione X₁ ∪ X₂ denota la loro unione. Siano R (X₁), R (X₂) due schemi di relazioni. R JOIN R è una relazione su X₁ ∪ X₂ il cui insieme di tuple è: { t su X₁ ∪ X₂ | esistono due tuple t₁ ∈ R e t₂ ∈ R tali che t₁[X₁] = t₁ e t₂[X₂] = t₂ }.

Diciamo che t₁ ∈ R e t₂ ∈ R sono combinabili dal join naturale se t₁[X₁ ∩ X₂] = t₂[X₁ ∩ X₂] => ogni tupla nel join tra R ed R proviene da due tuple combinabili dal join -> t₁ ∈ R e t₂ ∈ R tali che t₁[X₁ ∩ X₂] = t₂[X₁ ∩ X₂] si combinano per ottenere la tupla t tale che t[X₁] = t₁ e t[X₂] = t₂. In altre parole si combinano se coincidono negli attributi in comune. Il risultato di JOIN avrà l'unione degli attributi delle relazione R e R join in cui ogni tupla contribuisce al risultato. Join in cui c'è almeno una tupla che non contribuisce al risultato -> ci sono tuple che non si combinano con nessun'altra e verranno perse. Join in cui nessuna delle tuple delle due relazioni si combina. Join che restituisce come risultato il prodotto cartesiano delle due relazioni.