Appunti di Basi di dati

Basi di dati

Davide Pirrò - February 2023

1. Introduction

La progettazione di una base di dati avviene in diverse fasi:

• Analisi del dominio applicativo
• Progettazione concettuale
• Progettazione logica
• Progettazione fisica

2. Progettazione concettuale: modello ER

Il modello ER è un modello concettuale per la rappresentazione dei dati del dominio di interesse ad un alto livello astratto. È formato da:

• Entità
• Relazioni o associazioni

2.1 Entità

Un’entità è un insieme di oggetti omogenei definiti da una struttura data dagli attributi. Ogni oggetto di un’entità si chiama istanza. Ogni entità deve avere una chiave primaria, ovvero un attributo che identifica le istanze tra di loro (non può quindi ripetersi). Una chiave primaria può anche essere composta, ovvero può essere il risultato di più attributi. In questo caso i singoli attributi che la compongono possono essere ripetuti, ma la combinazione degli attributi non può ripetersi.

2.2 Relazioni o associazioni

Una Relazione o Associazione è una relazione matematica che associa una o più istanze di un’entità ad una o più istanze di un’altra entità nel caso binario o di n altre entità nel caso più generale. Può anche essere definita come il sottoinsieme del prodotto cartesiano delle entità che vi partecipano. Ogni entità partecipa ad una relazione con due vincoli di cardinalità:

• Vincolo di cardinalità minima: il minimo numero di volte che ogni istanza dell’entità deve comparire nella relazione
• Vincolo di cardinalità massima: il numero massimo di volte che ogni istanza dell’entità può comparire nella relazione

Sulla base dei vincoli di cardinalità massima possiamo definire diversi tipi di relazioni:

• Relazioni uno-a-uno
• Relazioni uno-a-molti
• Relazioni molti-a-molti

Tra le stesse entità si possono definire diverse relazioni. Le relazioni possono avere attributi, che a differenza delle entità non sono obbligatori.

2.3 Relazioni ricorsive

Un’entità può avere un’associazione ricorsiva, ovvero un’associazione che collega più istanze della stessa entità.

2.4 Entità deboli

Un’entità debole ha nella sua chiave primaria la chiave primaria di un’altra entità con cui ha un’associazione. Una chiave esterna può essere definita solo dal lato uno di un’entità uno a molti.

2.5 Reificazione di associazioni

Possiamo trasformare un’associazione in un’entità che ha per chiave primaria le chiavi primarie delle entità ad essa collegate o una chiave primaria propria, nel qual caso è permessa la ripetizione di istanze dell’associazione.

2.6 Generalizzazione

Due entità possono tra loro essere in rapporto di subordinazione, una rispetto all’altra. La prima delle due prende il nome di entità generale, mentre le entità ad essa subordinate si chiamano entità figlie. La generalizzazione è totale se l’unione degli insiemi delle istanze delle entità figlie è uguale all’insieme delle istanze dell’entità generale. Inoltre, se alcune istanze delle entità figlie si ripetono, la generalizzazione è sovrapposta, altrimenti è disgiunta. Gli attributi e le associazioni di entità più generali si propagano alle entità figlie. La generalizzazione è un costrutto derivato, ovvero che si può rappresentare attraverso entità e associazioni (che sono i costrutti primari). Questo implica che si possono eliminare. In particolare, per eliminarle esistono 3 modi:

• Accorpamento delle entità figlie nell’entità genitore
• Accorpamento dell’entità genitore nelle entità figlie
• Trasformazione di generalizzazioni in associazioni

2.7 Vincoli di integrità

Condizioni che devono essere verificate dai dati. Alcuni non sono rappresentabili con il modello ER.

3. Progettazione logica: modello relazionale

Il modello relazionale consente di rappresentare i dati in forma tabellare: ogni tabella è chiamata relazione. Ogni relazione ha uno schema e un’estensione, le istanze (le righe) della tabella vengono chiamate tuple; di conseguenza, non possono esistere due tuple con chiavi primarie uguali. Infatti, la chiave primaria identifica le tuple. Il concetto di associazione del modello ER viene rappresentato dalle chiavi secondarie nel modello relazionale. Una chiave secondaria è una chiave primaria di un’altra relazione che viene inserita per indicare le associazioni tra le tuple. Vincolo di integrità relazionale: ogni chiave secondaria deve apparire come chiave primaria di una tupla della relazione di appartenenza. Ogni campo di una tupla può avere valore nullo, ovvero un valore particolare che indica che l’informazione è inesistente o sconosciuta. Le chiavi primarie non possono essere valori nulli.

3.1 Progettazione logica: da schema ER a schema relazionale

Per rappresentare correttamente il dominio applicativo è utile usare la progettazione concettuale dei dati, che è ad un livello di astrazione maggiore. Il modello ER deve però essere poi trasposto in modello relazionale per poter effettivamente essere implementato. Per eseguire correttamente questo passaggio bisogna seguire delle semplici regole:

• Ogni entità diventa una relazione
• Le associazioni da molti a molti diventano relazioni
• Le associazioni ternarie (o in generale n-arie) diventano relazioni
• Le associazioni 1 a 1 vengono rappresentate con chiavi esterne, se posso omettere le chiavi secondarie
• Gli attributi delle associazioni vanno nelle relazioni che contengono le chiavi secondarie
• Nei casi di vincoli di cardinalità minima 0 e massima 1, è preferibile scegliere la relazione ad essa associata per inserire le chiavi secondarie, per evitare di avere valori nulli come chiavi secondarie.
• Per garantire che un’associazione con vincoli di cardinalità 1,1 abbia una sola istanza per ogni istanza dell’entità, si impone un vincolo di unicità nella chiave primaria che la rappresenta.

4. Algebra relazionale

L’algebra relazionale è un linguaggio di interrogazione di basi di dati relazionali costituito da operatori che hanno per operandi relazioni e che restituiscono relazioni. Gli operatori possono essere quelli insiemistici oppure operatori particolari dell’algebra relazionale.

4.1 Operatori insiemistici

Date due relazioni R(X) e S(X) con X = ...A un insieme di attributi comuni ad R e S allora possiamo definire i seguenti operatori insiemistici:

• Unione: T = R ∪ S = {t | t ∈ R or t ∈ S}
• Intersezione: T = R ∩ S = {t | t ∈ R and t ∈ S}
• Sottrazione: T = R - S = {t | t ∈ R and t ∉ S}

Date due relazioni R(X) e S(Y) con X = ...A e Y = ...B insieme di attributi comuni ad R e S allora possiamo definire l’operatore insiemistico prodotto cartesiano: T(X, Y) = R(X) × S(Y)

4.2 Operatori specifici

Gli operatori specifici possono essere unari o binari. Quelli unari sono:

• Selezione: indicata con σ restituisce solo le tuple che rispettano una condizione F definita dalla selezione stessa
• Proiezione: indicata con π restituisce la stessa relazione, ma con solo gli attributi A₁...A_n definiti dalla proiezione stessa
• Ridenominazione: indicata con ρ restituisce la stessa relazione, ma con solo gli attributi cambiati di nome, nel modo indicato dalla ridenominazione stessa

Quelli binari invece sono gli operatori di join:

• Join naturale
• Equi-join
• Tetha-join
• Join-esterno
• Semijoin

Il join naturale e l’equi-join sono i più utilizzati. Il join naturale (indicato dal simbolo ▷◁) restituisce una relazione che ha come parametri...