Teoria delle dipendenze

Fondamenti di Teoria delle

Basi di Dati

Parte 8: Teoria delle dipendenze

Vincoli di integrità

„ Esistono istanze di basi di dati che, pur

sintatticamente corrette, non rappresentano informazioni possibili per l’applicazione di interesse

Una base di dati "scorretta"

Studente Voto Lode Corso

32 01 276545 276545 30 e lode 02 787643 27 e lode 03 739430 24 04 Esami Matricola 276545 787643 787643 Cognome Rossi Neri Bianchi Nome Mario Piero Luca Studenti 787643 787643 27 e lode

Vincolo di integrità

„ Proprietà che deve essere soddisfatta dalle

istanze che rappresentano informazioni corrette per l’applicazione

„ Un vincolo è una funzione booleana (un

predicato)

Tipi di vincoli

„ vincoli intrarelazionali

„ vincoli su valori (o di dominio) „ vincoli di tupla

Vincoli di tupla

„ Esprimono condizioni sui valori di ciascuna tupla,

indipendentemente dalle altre tuple

„ Caso particolare:

Sintassi ed esempi

„ Una possibile sintassi:

„ espressione booleana di atomi che confrontano valori di

attributo o espressioni aritmetiche su di essi

(Voto ≥ 18) AND (Voto ≤ 30)

Vincoli di tupla, altro esempio

Impiegato Rossi Neri Bruni Stipendi Lordo 55.000 45.000 47.000 Netto 42.500 35.000 36.000 Ritenute 12.500 10.000 11.000

Identificazione delle tuple

„ non ci sono due tuple con lo stesso valore sull’attributo

Matricola

„ non ci sono due tuple uguali su tutti e tre gli attributi

Cognome, Nome e Data di Nascita

Matricola 27655 78763 65432 Nome Mario Piero Mario 87654 67653 Mario Cognome Rossi Neri Neri Rossi Rossi Piero Corso Ing Inf Ing Mecc Ing Inf Ing Inf Ing Mecc Nascita 5/12/78 10/7/79 3/11/76 3/11/76 5/12/78

Chiave

„ Insieme di attributi che identificano le tuple di

una relazione

„ Formalmente:

„ un insieme K di attributi è superchiave per r se r

non contiene due tuple distinte t₁ e t₂ con t₁[K] = t₂[K]

„ K è chiave per r se è una superchiave minimale

Una chiave

„ Matricola, Cognome è una superchiave

„ Matricola è una chiave:

„ è superchiave

„ contiene un solo attributo e quindi è minimale

Matricola 27655 78763 65432 Nome Mario Piero Mario 87654 67653 Mario Cognome Rossi Neri Neri Rossi Rossi Piero Corso Ing Inf Ing Mecc Ing Inf Ing Inf Ing Mecc Nascita 5/12/78 10/7/79 3/11/76 3/11/76 5/12/78

Vincoli, schemi e istanze

„ i vincoli corrispondono a proprietà del mondo reale

modellato dalla base di dati

„ interessano a livello di schema (con riferimento cioè a

tutte le istanze)

„ ad uno schema associamo un insieme di vincoli e

consideriamo corrette (valide, ammissibili) le istanze che soddisfano tutti i vincoli

Dipendenza funzionale

„ relazione r su R(X)

„ due sottoinsiemi non vuoti Y e Z di X

„ esiste in r una dipendenza funzionale (FD) da Y a

Z (in simboli Y→Z) se, per ogni coppia di ennuple

t₁ e t₂ di r con gli stessi valori su Y, risulta che t₁ e

Esempio

→ Stipendio

Impiegato Stipendio Progetto Bilancio Funzione

Rossi 20 Marte 2 tecnico

Verdi 35 Giove 15 progettista Verdi 35 Venere 15 progettista

Neri 55 Venere 15 direttore Neri 55 Giove 15 consulente

Neri 55 Marte 2 consulente

Mori 48 Marte 2 direttore

Mori 48 Venere 15 progettista Bianchi 48 Venere 15 progettista Bianchi 48 Giove 15 direttore

Integrità referenziale

„ informazioni in relazioni diverse sono correlate

attraverso valori comuni in particolare, valori delle chiavi (primarie)

„ le correlazioni debbono essere "coerenti“

„ Un vincolo di integrità referenziale (“foreign key”)

fra gli attributi X di una relazione R₁ e un’altra

relazione R₂ impone ai valori su X in R₁ di

Matricola 3987 3295

Vigili

Cognome Rossi Neri Nome Luca Piero

Infrazioni

Codice 34321 73321 64521 53524 Data 1/2/95 4/3/95 5/4/96 5/2/98 Vigile 3987 3295 3295 9345 Prov Numero MI TO PR PR 39548K E39548 839548 839548 3295 3295 3987 3987 9345 3987 9345 3295 3295 3295

Auto

_{Prov Numero} MI TO 39548K E39548 Cognome Rossi Rossi Nome Mario Mario

Infrazioni

Codice 34321 73321 64521 53524 Data 1/2/95 4/3/95 5/4/96 5/2/98 Vigile 3987 3295 3295 9345 Prov Numero MI TO PR PR 39548K E39548 839548 839548 MI TO PR PR 39548K E39548 839548 839548 MI TO 39548K E39548

Infrazioni

Codice 34321 73321 64521 53524 Data 1/2/95 4/3/95 5/4/96 5/2/98 Vigile 3987 3295 3295 9345 Prov Numero MI TO PR PR 39548K E39548 839548 839548

Auto

Prov Numero MI E39548 Cognome Rossi Nome Mario TO E39548 E39548

Azioni compensative

„ Esempio:

„ Viene eliminata una tupla causando una violazione

„ Comportamento “standard”:

„ Rifiuto dell'operazione

„ Azioni compensative:

„ Eliminazione in cascata „ Introduzione di valori nulli

Eliminazione in cascata

Impiegati

Matricola 34321 64521 53524 Cognome Rossi Neri Verdi Progetto IDEA XYZ NULL 73032 Bianchi IDEA

Progetti

Codice IDEA XYZ Inizio 01/2000 07/2001 Durata 36 24 Costo 200 120 XYZ 07/2001 24 120 XYZ 07/2001 24 120 XYZ 07/2001 24 120 53524 Neri XYZ

Introduzione di valori nulli

Impiegati

Matricola 34321 64521 53524 Cognome Rossi Neri Verdi Progetto IDEA XYZ NULL 73032 Bianchi IDEA

Progetti

Codice IDEA BOH XYZ Inizio 01/2000 07/2001 09/2001 Durata 36 24 24 Costo 200 120 150 XYZ 07/2001 24 120 XYZ 07/2001 24 120 XYZ 07/2001 24 120 NULL

Implicazione di vincoli

„ Un insieme di vincoli Γ implica un vincolo γ se

ogni istanza che soddisfa Γ soddisfa anche γ

„ L’insieme { Impiegato → Livello, Livello → Stipendio }

implica il vincolo Impiegato → Stipendio

„ La chiusura Γ+ di un insieme di vincoli Γ è

l’insieme di tutti i vincoli implicati da Γ.

„ Γ+ = { γ | Γ implica γ }

„ Proprietà:

„ Γ ⊆ Γ+

Equivalenza e ridondanza di insiemi di vincoli

„ Γ₁ è equivalente a Γ₂ se Γ₁+ = Γ₂+ (si dice anche

che Γ₁ è una copertura di Γ₂)

„ Lemma Γ₁ + = Γ₂ + sse Γ₁ implica ogni vincolo di Γ₂

e Γ₂ implica ogni vincolo di Γ₁

„ Un vincolo γ è ridondante in Γ se Γ+ = (Γ - {γ})+ „ Un insieme di vincoli Γ è ridondante se esiste γ

ridondante in Γ

„ Lemma γ è ridondante in Γ sse Γ - {γ} implica γ

Esempi con riferimento alle dip. funzionali

„ F₁ = {A → B, AB → C, A → C} „ F₂ = {A → B, AB → C} „ F₃ = {A → B, A → C} „ F₁ è ridondante „ perché { A → B, AB → C } implica A → C „ F₁ è equivalente a F₂ „ F₂ è equivalente a F₃

Approccio assiomatico

„ Si definisce un insieme di regole di inferenza

(proof system) che consentono di generare tutte (completezza) e solo (correttezza) le dipendenze implicate da un insieme dato.

„ Per le FD si può dimostrare che le tre regole:

„ Y ⊆ X ⇒ X → Y (trivial)

„ X → Y ⇒ XZ → YZ (augmentation) „ X → Y e Y → Z ⇒ X → Z (transitivity)

„ forniscono un insieme corretto e completo

Armstrong (1974)

Chiusura di un insieme di attributi

„ Approccio alternativo al problema dell’implicaz.

„ Siano dati uno schema di relazione R(U) e un

insieme di dipendenze funzionali F definite sugli attributi in U. Sia X un insieme di attributi

contenuti in U (cioè X ⊆ U);

„ La chiusura di X rispetto a F, indicata con X+_F , è

l’insieme degli attributi che dipendono funzionalmente da X (esplicitamente o implicitamente):

„ X+_F = { A | A ⊆ U e F implica X → A }

Algoritmo di chiusura

„ Input: un insieme X di attributi e un insieme F di

dipendenze

„ Output: un insieme X_P di attributi

1) Inizializziamo X_P con l’insieme di input X

2) Esaminiamo le dipendenze in F; se esiste una

dipendenza Y → Z con Y ⊆ X_P e Z non

contenuto in X_P allora aggiungiamo gli attributi di

Z a X_P.

3) Ripetiamo il passo 2 fino al momento in cui non

Esempi

R(Impiegato,Stipendio,Progetto,Bilancio,Funzione)

Impiegato → Stipendio

Progetto → Bilancio

Impiegato Progetto → Funzione

„ IP+ = ISPBF

„ I+ = IS

Dimostrazione di correttezza

Teorema Sia X un insieme di attributi ed F un insieme di

dipendenze su attributi in X. Al termine della esecuzione dell’algoritmo risulta X_P = X+

Applicazione dell’algoritmo di chiusura

„ L’algoritmo può essere utilizzato per verificare se

un insieme di attributi è chiave

„ Lemma Siano dati uno schema di relazione R(U)

e un insieme di dipendenze funzionali F definite sugli attributi in U. Sia K un insieme di attributi contenuti in U (cioè K ⊆ U):

„ K è superchiave per R sse K+ = U

„ K è chiave per R sse per ogni attributo A ∈ K risulta

Esempio

R(Impiegato,Stipendio,Progetto,Bilancio,Funzione)

Impiegato → Stipendio

Progetto → Bilancio

Impiegato Progetto → Funzione

„ IPB+ = ISPBF

„ quindi IPB è superchiave per R

„ IP+ = ISPBF

„ anche IP è superchiave per R