Base di Dati V

Riassunto gerarchico delle nozioni del corso 2006-2007 di BASI DI DATI II della Prof. Nicoletta Dessì - Università degli Studi di Cagliari, Facoltà di Scienze Matematiche Fisiche Naturali, Dipartimento di Matematica ed Informatica, Corso di Laurea Specialistica in Tecnologie Informatiche

Riferimenti: Elmasri R, Navathe SB, "Sistemi di basi di dati - Complementi", IV ediz., Pearson - Addison Wesley

• TRANSAZIONI
  • sistemi di gestione delle transazioni
    • sono sistemi con grandi basi di dati e centinaia di utenti che eseguono transazioni contemporaneamente
    • richiedono alta disponibilità e tempi di risposta rapidi per centinaia di richieste simultanee
  • gestione delle transazioni
    • sistemi monoutente
      • può essere usato al massimo da un utente alla volta
      • sono generalmente limitati ad un utilizzo su PC
    • sistemi multiutente
      • può essere utilizzato contemporaneamente da più utenti
      • genera accessi concorrenti alla base di dati
      • sono resi possibili dai concetti di multiprogrammazione
        • il calcolatore esegue più programmi o processi alla volta in modalità alternata (interleaved) o parallela se sono presenti più processori
  • transazione
    • meccanismo per descrivere le unità logiche di elaborazione delle basi di dati
    • programma in esecuzione che forma un'unità logica di elaborazione sulla base di dati
    • comprende una o più operazioni di accesso alla base di dati
      • inserimenti, cancellazioni, modifiche, interrogazioni
    • può essere incapsulata in un programma applicativo o specificata iterattivamente tramite un linguaggio di interrogazione ad alto livello come SQL
    • è racchiusa tra le operazioni di begin transaction (bot) e end transaction (eot)
    • può essere a sola lettura
      • le operazioni sulla base di dati sono di sola lettura e non effettuano alcun aggiornamento
    • i concetti base sulle transazioni PRESCINDONO dalla granularità degli elementi
      • la granularità è la dimensione di un elemento campo di record, record, blocco di disco, ...
      • stato della base di dati
        • raccolta di tutti gli elementi (valori) memorizzati nella base di dati in un determinato momento
    • operazioni fondamentali
      • begin_transaction
        • indica l'inizio dell'esecuzione della transazione
      • end_transaction
        • indica la conclusione delle operazioni di read e write
      • read_item(X)
        • legge un elemento della base di dati denominato X e lo copia in una variabile del programma (anch'essa denominata X per semplicità)
      • write_item(X)
        • scrive il valore della variabile X del programma copiandolo nell'elemento della base di dati chiamato X
      • commit
        • indica la terminazione con successo
        • tutte le modifiche effettuate dalla transazione possono essere trasmesse (committed) alla base di dati
      • rollback (abort)
        • indica la terminazione senza successo (fallimento)
        • tutte le modifiche effettuate dalla transazione devono essere disfatte (undo)
    • read-set
      • insieme di tutti gli elementi letti dalla transazione
    • write-set
      • insieme di tutti gli elementi che la transazione scrive
  • transazione ben formata (WFT - Well Formed Transaction)
    • è costituita da una serie di operazioni che muovono il sistema da uno stato consistente a un altro stato consistente
      • preservano l'integrità dei dati e prevengono che gli utenti li manipolino arbitrariamente
  • proprietà ACID per le transazioni
    • ATOMICITA'
      • la transazione è un'unità indivisibile di esecuzione
      • gli aggiornamenti che essa effettua vengono eseguiti TUTTI o NESSUNO
      • in caso di errore o non completamento delle operazioni sui dati la transazione deve essere:
        • disfatta (UNDO) se non è stato eseguito il commit
        • rifatta (REDO) se è stato eseguito il commit
    • CONSISTENZA
      • le operazioni effettuate da una transazione devono rispettare i vincoli di integrità sui dati
      • e di solito ritenuta di pertinenza dei programmatori
      • i vincoli sono controllati:
        • all'atto dell'operazione
        • dopo il commit
      • il non rispetto dei vincoli comporta un UNDO
    • ISOLAMENTO
      • l'effetto di più transazioni eseguite in concorrenza deve essere uguale a quello che si otterrebbe eseguendo singolarmente ciascuna transazione
      • evita l'effetto domino: disfacimento in cascata di tutte le transazioni nel caso in cui una di esse non vada a buon fine
      • è garantito dal sottosistema di controllo della concorrenza
      • si può dividere in
        • isolamento 0
          • non sovrascrive le letture sporche di transazioni di livello più alto
        • isolamento 1
          • non ha perdita di aggiornamento
        • isolamento 2
          • non ha perdita di aggiornamento e nessuna lettura sporca
        • isolamento 3 (isolamento vero)
          • assicura gli isolamenti del livello 2 ed in più letture ripetibili
    • DURABILITA' (PERSISTENZA)
      • l'effetto di una transazione portata a termine correttamente non deve venire perso
      • è garantita dal sottosistema di gestione dell'affidabilità
  • controllo di concorrenza
    • se la proprietà di isolamento non è completamente soddisfatta, due (o più) transazioni effettuate su un database consistente possono portare il database in uno stato inconsistente
    • due azioni sullo stesso oggetto di due diverse transazioni si dicono essere in CONFLITTO se almeno una delle due è una operazione di scrittura
    • date due transazioni T1 e T2 in conflitto, si possono verificare tre tipologie di situazioni anomale:
      • conflitto Write-Read (WR):
        • T2 legge un dato precedentemente scritto da T1
      • conflitto Read-Write (RW):
        • T2 scrive un dato precedentemente letto da T1
      • conflitto Write-Write (WW):
        • T2 scrive un dato precedentemente scritto da T1
  • anomalie
    • conflitti WR: reading uncommitted data
      • si può verificare una anomalia se una transazione T2 legge un dato che è stato modificato da una transazione T1 non ancora conclusa (quindi uncommitted)
      • in particolare questa situazione può generare
        • letture sporche (dirty read)
          • una transazione ha letto uno stato intermedio ("sporco") e lo può comunicare all'esterno
    • conflitti RW: unrepeatable read
      • si possono verificare diverse anomalie se una transazione T2 cambia il valore di un dato che è stato letto da una transazione T1 mentre T1 è ancora in esecuzione
      • in particolare, questa situazione può generare:
        • letture inconsistenti
          • ad esempio due letture successive della stessa transazione sullo stesso dato possono produrre risultati diversi perchè tra di esse il dato è stato modificato da un'altra transazione
        • perdita di aggiornamento
          • una transazione legge un dato che è stato modificato ma che non è stato ancora scritto nel database
    • conflitti WW: overwriting uncommitted data
      • si possono verificare anomalie se una transazione T2 sovrascrive il valore di un dato che è già stato modificato da una transazione T1, mentre T1 è ancora in esecuzione
      • questa situazione può generare
        • aggiornamenti fantasma
          • una transazione vede uno stato non esistente (o non coerente) poichè prima di usarlo è stato modificato da un'altra transazione
        • inserimenti fantama
  • controllo di affidabilità
    • è compito del sottosistema di gestione dell'affidabilità (recovery subsystem)
    • equivale al controllo delle proprietà ACID
    • si accede al DB SOLO tramite transazioni
    • la perdita ANCHE di una sola delle proprietà ACID da parte di una o più transazioni METTE A RISCHIO l'integrità e la consistenza del DB
    • le proprietà ACID non sono valide in altri ambienti con processi concorrenti e distribuiti (es. Web Services)
    • il DBMS deve garantire una delle seguenti cose:
      • le operazioni delle transazioni siano completate con successo ed il loro effetto sia memorizzato permanentemente nella BD
      • la transazione non abbia alcun effetto sulla BD e sulle altre transazioni
    • per garantire l'affidabilità si usano:
      • astrazione della memoria stabile
      • mirroring dei dischi (ridondanza)
      • file di LOG
  • tipi di guasti
    • guasto del sistema di elaborazione (crash di sistema)
      • (errore a livello hardware, software o di rete)
    • errore di transazione o di sistema
      • (divisione per zero, parametri errati, errore logico di programmazione, interruzione da parte dell'utente)
    • errori locali o condizioni di eccezione rilevate dalla transazione
      • si verificano delle condizioni (dati mancanti o non conformi) per cui è necessario interrompere la transazione
    • attuazione del controllo di concorrenza
      • il meccanismo di controllo della concorrenza può forzare l'interruzione
    • errore di dispositivo (disco)
    • problemi fisici e catastrofici
  • stato di una transazione
    • attiva
    • parzialmente confermata
    • confermata (committed)
    • fallita (failed)
    • terminata
  • file di LOG
    • file sequenziale che registra in ordine temporale le azioni sugli items compiute dalle transazioni
    • è influenzato solo da guasti del disco catastrofici
    • generalmente se ne conserva una copia di backup su dispositivi di memorizzazione secondari
    • ogni transazione ha un identificatore T generato automaticamente dal sistema
    • tipologia dei record
      • [start_transaction, T]
        • la transazione T ha iniziato l'esecuzione
      • [write_item, T, X, vecchio_valore, nuovo_valore]
        • la transazione T ha modificato il valore dell'elemento X da vecchio_valore al nuovo_valore
      • [read_item, T, X]
        • la transazione T ha letto il valore X della base di dati
      • [commit, T]
        • la trasazione T è terminata con successo ed il suo effetto può essere registrato permanentemente nella base di dati
      • [abort, T]
        • la transazione T è stata annullata
    • record di transazione
      • Begin, Commit, Abort
        • in ordine temporale
      • Update, Insert, Delete
        • Before Image (BI): U,D
        • After Image (AI): U,I
    • checkpoint
      • punto di ripristino del file di log
      • operazione periodica di flush in memoria di transazioni con record di Commit o Abort
      • un record [checkpoint] viene periodicamente scritto all'interno del log nel momento in cui il sistema trascrive nella base di dati su disco tutti i buffer del DBMS che sono stati modificati
      • per scrivere un check point occorre:
        • sospendere temporaneamente l'esecuzione delle transazioni
        • eseguire la scrittura forzata (force) di tutti i buffer di memoria principale modificati
        • eseguire la scrittura di un record [checkpoint] e la scrittura forzata del log su disco
        • riprendere l'esecuzione delle transazioni
      • fuzzy checkpoint
        • il precedente checkpoint rimane attivo fintanto che la scrittura del nuovo non viene completata con successo
    • commit point (CP) di una transazione
      • una transazione T raggiunge il CP quando TUTTE le sue operazioni di accesso al DB sono state eseguite con successo e l'effetto delle sue operazioni è stato registrato sul file di LOG
      • una volta superato il CP si dice che la transazione è confermata e si suppone che il suo effetto sia registrato permanentemente nella base di dati
    • Force Writing del LOG
      • prima che una transazione raggiunga il suo punto di commit, la parte del log che non è ancora stata scritta deve esservi registrata
      • è necessaria perchè solo le voci del log che sono state trascritte sul disco vengono prese in considerazione per il ripristino
    • recovery tramite LOG
      • UNDO
        • le transazioni possono essere disfatte copiando nel record del file oggetto della transazione la BEFORE Image (BFIM)
        • devono essere DISFATTE le transazioni che hanno registrato [start_transaction, T] ma NON [commit, T]
      • REDO
        • le transazioni possono essere rifatte copiando nel record del file oggetto della transazione la AFTER Image (AFIM)
        • devono essere RIFATTE TUTTE le committed transactions
  • scheduler
    • modulo di sistema che gestisce le operazioni di scheduling delle transazioni
    • accetta o rifiuta transazioni concorrenti in modo da evitare anomalie (rispetto delle proprietà ACID)
  • schedule
    • ordine con cui vengono eseguite le OPERAZIONI di più transazioni CONCORRENTI
    • uno schedule S di n transazioni (T1, T2, ..., Tn) è un ordinamento delle operazioni delle transazioni tale che, per ogni transazione Ti che partecipa ad S, le operazioni di Ti all'interno di S devono apparire nel medesimo ordine con cui esse occorrono in Ti
    • esempi di schedule
      • (i pedici indicano a quale transazione appartengono le operazioni)
      • Sa: r1(X); r2(X); w1(X); r1(Y); w2(X); w1(Y);
      • Sb: r1(X); w1(X); r2(X); w2(X); r1(Y); a1;
    • conflitto
      • due operazioni di uno schedule sono in conflitto se soddisfano tutte le seguenti condizioni:
        • appartengono a differenti transazioni
        • accedono al medesimo elemento X
        • almeno una di esse è una operazione di scrittura (write_item(X))
    • schedule completo
      • uno schedule è completo quando soddisfa le seguenti condizioni:
        • le operazioni di S sono esattamente quelle di un ben determinato gruppo di transazioni ciascuna delle quali termina con commit o abort (registrati nello schedule)
          • all'interno di uno schedule completo devono apparire tutte le operazioni di una transizione
        • lo schedule rispetta l'ordine delle operazioni di ciascuna transazione
        • per ogni coppia di operazioni in CONFLITTO una di esse deve apparire prima dell'altra
          • due operazioni non in conflitto posso apparire nello schedule senza definire quale delle due avvenga prima dell'altra
    • caratterizzazione dello schedule
      • rispetto al ripristino
        • proprietà dello schedule
          • recoverable (ripristinabile)
            • non è mai necessario l'annullamento (rollback) di una transazione terminata con successo (commit)
            • è ripristinabile senza rollback sulla base del LOG qualora si verifichi un guasto
            • uno schedule è RECOVERABILE se le transazioni che hanno SCRITTO un elemento LETTO da altre transazioni dello scheduler eseguono il commit PRIMA delle transazioni che hanno effettuato tali letture
              • (nessuna transazione T in S esegue il commit prima che lo abbiano eseguito le transazioni T' che hanno scritto un elemento letto da T)
          • unrecoverable (non ripristinabile)
            • non soddisfa il criterio recoverable e pertanto non dovrebbero essere consentiti
          • cascadeless (privo dell'effetto a cascata)
            • evita il verificarsi del rollback a cascata
              • (una transazione non ancora conclusa viene annullata perché legge un elemento scritto da una transazione fallita)
            • ogni sua transazione legge esclusivamente elementi scritti da transazioni concluse con successo
            • di fatto si proibiscono le letture sporche
            • può ritardare le transazioni
            • uno schedule cascadeless e anche recoverable
          • strict (rigido)
            • le transazioni non possono ne leggere ne scrivere un elemento X fino a che l'ultima transazione che ha scritto X non si è conclusa (commit o abort)
            • di fatto proibisce letture+scritture sporche
            • semplifica il processo di ripristino: disfare un'operazione write_item(X) fallita, consiste nel copiare il valore precedente di X (before image)
            • uno schedule strict è anche cascadeless e recoverable
      • rispetto alla serializzabilità
        • tipi di schedule che vengono considerati corretti quando più transazioni vengono eseguite in modo concorrente
        • schedule seriali
          • le operazioni delle loro transazioni sono eseguite consecutivamente, senza alternanza con operazioni appartenenti ad altre transazioni
          • per ogni transazione T di dello schedule S, tutte le operazioni di T sono eseguite consecutivamente in S
          • solamente una transazione è attiva per ogni istante di tempo
          • sono generalmente considerati inaccettabili nella pratica perché sprecano il tempo di elaborazione della CPU
        • serializzabilità di uno schedule
          • indica quali schedule sono corretti quando l'esecuzione delle transazioni contempla l'alternanza di operazioni all'interno dello schedule stesso
          • uno schedule S di n transazioni si dice serializzabile se è equivalente ad almeno uno schedule seriale delle medesime n transazioni
          • per n transazioni esistono n! possibili schedule seriali e molti altri possibili schedule non seriali
        • equivalenza tra schedule
          • due schedule sono EQUIVALENTI se le operazioni che in essi compaiono sono applicate in entrambi NEL MEDESIMO ORDINE agli stessi elementi
          • equivalenza rispetto al risultato
            • si ha quando due schedule producono lo stesso stato finale, il quale però può risultare tale anche accidentalmente
            • non è una definizione valida di equivalenza
        • conflict-equivalenza
          • l'ordine di ogni coppia di operazioni in conflitto è il medesimo in entrambi gli schedule
          • uno schedule può essere derivato da un altro scambiando le operazioni commutative e rispettando l'ordine nelle operazioni in conflitto
          • due schedule conflict-equivalenti sono anche view-equivalenti, non è vero il viceversa
        • conflict-serializzabilità
          • uno schedule lo è se è conflict-equivalente a qualche schedule seriale definito sulle stesse transazioni
          • uno schedule è conflict-serializzabile se e solo se il suo grafo di serializzazione (grafo delle precedenze) non possiede cicli
          • grafo di serializzazione (grafo delle precedenze)
            • consente di verificare la conflict-serializzabilità
            • sono grafi diretti che constano di:
              • un nodo per ogni transazione
              • un link (arco orientato) per ogni operazione di conflitto
                • la direzione del link rispetta l'ordine temporale del conflitto (dalla transazione dell'operazione che precede alla transazione dell'operazione che segue)
              • regole di creazione
                • creare un nodo Ti per ogni transazione Ti di S
                • per ogni coppia (i,k), se wi(X)rk(X) oppure ri(X)wk(X) oppure wi(X)wk(X), allora creare un arco X da Ti a Tk
        • view-equivalenza
          • due schedule S e S' sono detti view-equivalenti se soddisfano le seguenti condizioni:
            • operazioni di lettura corrispondenti (stesso item) restituiscono nei due schedule uno stesso valore
              • (in entrambi gli schedule, tutte le transazioni eseguono gli stessi calcoli e scrivono sul database gli stessi valori)
            • entrambi gli schedule lasciano il DB nello stesso stato finale
            • l'ultima operazione che scrive un item deve essere la stessa in entrambi gli schedule
          • fintanto che ogni operazione di lettura di una transazione legge la medesima operazione di scrittura in entrambi gli schedule, le operazioni di scrittura di ogni transazione devono produrre lo stesso risultato
          • le operazioni di lettura osservano la medesima vista in entrambi gli schedule
        • view-serializzabilità
          • uno schedule lo è se è view-equivalente a qualche schedule seriale definito sulle stesse transazioni
          • la verifica della view-serializzabilità è un problema NP-hard, pertanto i controlli della concorrenza si basano sempre sulla conflict-equivalenza
• CONTROLLO DELLA CONCORRENZA
  • definizione
    • insieme di tecniche che assicurano la proprietà di isolamento di transazioni concorrenti
    • impiegano tecniche di locking
    • definiscono protocolli che garantiscono schedule serializzabili
    • sono influenzate dalla granularità dei dati
  • lock
    • variabile associata ad un elemento per descriverne la modalità di accesso
    • vengono usati per sincronizzare l'accesso ai dati della base di dati da parte di transazioni concorrenti
    • sono definiti da:
      • valori assunti dalla variabile di LOCK
      • struttura dati associata alla variabile (lockset)
      • operazioni
      • regole di accesso che le transazioni devono seguire
  • lock manager
    • sottosistema DBMS
    • tiene traccia SOLO dei dati bloccati in una tabella di lock che contiene i lockset
    • gestisce le operazioni
    • controlla il rispetto delle regole di accesso da parte delle transazioni
    • il locking da solo non garantisce la serializzabilità degli schedule
  • tipi di lock
    • binari
      • è molto restrittivo ed è pertanto poco usato
      • stati:
        • bloccato,locked (lock(X)=1)
          • un'operazione sulla base di dati non può accedere al dato
        • libero, unlocked (lock(X)=0)
          • un'operazione sulla base di dati può accedere al dato quando richiesto
      • lockset
        • [X, LOCK, T che possiede il lock]
      • operazioni
        • lock(X): accesso riservato alla transazione
        • unlock(X): sblocco ed accesso libero
      • regole di accesso
        • chiedere lock(X) prima di ogni R(X) e W(X)
        • finite le operazioni su X dare unlock(X)
        • nessun lock(X) se è già posseduto
        • eseguire unlock solo sui dati posseduti
      • shared/exclusive (read/write, condivisi/esclusivi, multiple-mode lock)
        • stati
          • read-locked
            • permette l'accesso concorrente in lettura
          • write-locked
            • accesso bloccato
          • unlocked
            • dato libero ed accessibile
        • lockset
          • [X, LOCK, numero_letture, T che possiede il lock]
          • nel caso di read_lock T è una coda delle transazioni concorrenti
        • regole di accesso
          • chiedere read_lock(X) oppure write_lock(X) prima di ogni read_item(X)
          • chiedere write_lock(X) prima di ogni write_item(X)
          • finite TUTTE le operazioni su X eseguire unlock(X)
            • questa regola potrebbe essere modificata per consentire ad una transazione di sbloccare temporaneamente per poi ribloccarlo successivamente quando necessario
          • nessun read_lock(X) se è già posseduto in lettura o scrittura
            • può essere modificata per permettere l'upgrade da read_lock a write_lock
          • nessun write_lock(X) se è già posseduto in lettura o scrittura
            • può essere modificata per permettere il downgrade da write_lock a read_lock
          • eseguire unlock solo sui dati posseduti
  • locking a 2 fasi (protocollo 2PL - 2 Phase Locking)
    • questo protocollo garantisce schedule serializzabili anche se non permette tutti quelli possibili
    • 2PL basic
      • una transazione segue tale protocollo se tutte le sue operazioni di lock precedono la prima operazione di unlock
      • non garantisce schedule recoverable (es. write_lock rilasciati prima di un abort)
      • può essere diviso in due fasi:
        • 1P) fase crescente o di espansione
          • possono esser acquisiti nuovi lock sui dati ma non se ne possono rilasciare
          • prevede anche l'eventuale upgrade dei lock (da read_lock a write_lock)
        • 2P) fase calante
          • possono essere rilasciati i lock esistenti ma non se ne possono acquisire di nuovi
          • prevede anche l'eventuale downgrade dei lock (da write_lock a read_lock)
    • 2PL conservative (statico)
      • richiede che T effettui il lock di TUTTI i dati a cui deve accedere (read-set e write-set), PRIMA che abbia inizio la sua esecuzione
      • garantisce l'assenza di deadlock
      • applicabilità molto difficile
      • la transazione è sempre in fase calante
    • 2PL strict
      • richiede che T non rilasci nessun lock ESCLUSIVO finchè non ha eseguito commit/abort
      • non garantisce l'assenza di deadlock
      • garantisce schedule strict rispetto al ripristino (nessuna transazione attiva legge o scrive il valore SCRITTO da un'altra transazione attiva)
      • utilizzo commerciale (è la variante 2PL più popolare)
    • 2PL rigorous
      • richiede che T non rilasci nessun lock (esclusivo o no) finché non ha eseguito commit/abort
      • è più semplice da implementare del 2PL strict
      • non garantisce l'assenza di deadlock
      • garantisce schedule strict rispetto al ripristino
      • la transazione è sempre in fase crescente
  • deadlock (blocco critico)
    • si ha quando, in un insieme di due o più transazioni, ogni transazione T è in attesa di qualche dato che risulta bloccato da un'altra transazione T' dell'insieme
  • prevenzione dei deadlock
    • si possono prevenire i deadlock utilizzando i seguenti protocolli:
      • 2PL conservative: non rappresenta un'ipotesi praticabile
      • ordinamento di tutti i dati e la garanzia che ogni tansazione acceda ai dati secondo questo ordine: il programmatore (o sistema) dovrebbe conoscere a priori l'ordine scelto relativo ai dati e questo non risulta praticabile
      • schemi basati su timestamp di transazione TS(T)
        • il timestamp di transazione TS(T) è un identificatore unico associato ad ogni transazione che ne determina un'ordinamento temporale
        • prevengono sicuramente il deadlock (anche quando non serve)
        • evitano la starvation
        • wait-die
          • se la transazione più vecchia chiede dati bloccati da una più giovane, la più vecchia può attendere (WAIT)
          • viceversa, ogni transazione che chiede il lock su dati bloccati da una transazione più vecchia viene interrotta e fatta ripartire con lo stesso timestamp (DIE)
        • wound-wait
          • se la transazione più vecchia chiede dati bloccati da una più giovane, la più vecchia prelaziona la più giovane causandone l'abort (WOUND=ferita)
          • viceversa, ogni transazione che chiede il lock su dati bloccati da una transazione più vecchia può attendere (WAIT)
      • schemi non basati su timestamp
        • no waiting
          • se una transazione non è in grado di ottenere un certo lock, essa viene bloccata e fatta ripartire successivamente
        • cautious waiting (evita ripartenze inutili)
          • T1 aspetta i dati di T2:
            • se T2 non è bloccata, T1 aspetta
            • se T2 è bloccata, T1 viene terminata
  • rilevazione dei deadlock
    • grafo delle attese
      • si ha uno stato di deadlock se esolo se il grafo delle attese possiede un ciclo
      • un arco in tale grafo tra Ti t Tj indica che Ti è in attesa di porre un lock su un dato X temporanemente bloccato da Tj
    • timeout
      • ogni transazione viene annullata (abort) se ancora attiva dopo un intervallo di tempo prefissato
      • è una delle tecniche più usate
  • problemi dei deadlock
    • quando controllare la presenza di deadlock
    • quali transazioni terminare (selezione della vittima)
      • in genere si terminano le transazioni meno attive
    • starvation
      • una transazione è impossibilitata a proseguire per un periodo di tempo indefinito
      • va prevenuta utilizzando schemi del tipo firt-come-first-served o dando delle priorità alle transazioni
  • timestamp ordering (TSO - ordinamento dei timestamp)
    • è una tecnica di controllo della concorrenza
    • utilizza un identificatore (timestamp) associato alla transazione considerata come evento temporale
    • determina un ordinamento temporale delle transazioni
    • principio base
      • ogni transazione non può leggere o scrivere un dato scritto da una transazione con timestamp superiore al suo (più giovane)
      • ogni transazione non può scrivere un dato che è già stato letto da una transazione con timestamp superiore al suo (più giovane)
    • algoritmo TSO
      • genera schedule equivalenti al particolare ordine seriale delle transazioni
      • associa ad ogni dato il TS della transazione più giovane T che ha avuto accesso al dato
      • basic
        • caratteristiche
          • assenza di deadlock
          • respinge sempre l'ultima operazione in conflitto che violi TSO uccidendo la T che l'ha lanciata
          • ogni T interrotta riparte con un nuovo TS
          • tutte le T' che hanno usato valori scritti da T devono essere disfatte
          • non evita il rollback a cascata (è richiesto un protocollo aggiuntivo)
          • schedule non ricoverabile
        • algoritmo
          • T chiede write_item(X)
            • se read_TS(X) > TS(T) oppure write_TS(X) > TS(T), allora uccidi T (T viola il TSO)
            • altrimenti write_item(X); write_TS(X)=TS(T)
          • T chiede read_item(X)
            • se write_TS(X) > TS(T), allora uccidi T (T non puo leggere un dato scritto dalla transazione più giovane T')
            • altrimenti read_item(X); read_TS(X)=max(TS(T),read_TS(X))
      • strict
        • caratteristiche
          • nessuna interruzione
          • nessun deadlock
          • garantisce schedule strict ricoverabili
          • garantisce schedule conflict-serializzabili
        • algoritmo
          • sulla richiesta di read_item(X) o write_item(X), se write_TS(X)<TS(T) allora T aspetta che si concluda la transazione T' che ha scritto X per ultima
      • Thomas write rule
        • non realizza la conflict-serializzabilità ma respinge un numero inferiore di operazioni di scrittura modificando i controlli per l'operazione write_item
        • algoritmo
          • T chiede write_item(X)
            • se read_TS(X) > TS(T), allora uccidi T
            • se write_TS(X) > TS(T), allora ignora write e continua T (write ha perso il turno)
            • altrimenti (entrambe le condizioni precedenti false) write_item(X); write_TS(X)=TS(T)
  • tecniche multi-versione
    • sono tecniche per il controllo della concorrenza
    • più versioni del dato corrispondenti ai vari aggiornamenti
    • perfetto per DB temporali che tengono traccia di tutti i cambiamenti (CVS, SVN)
    • richiedono più memoria
    • quando una transazione richiede l'accesso ad un elemento, se possibile, viene scelta una versione appropriata al fine di mantenere la serializzabilità dello schedule in esecuzione
    • alcune operazioni di lettura che potrebbero essere rifiutate con altre tecniche, possono ora essere accettate leggendo una versione più vecchia mantenendo così la serializzabilità
    • multi-versione TSO
      • per ogni elemento dati X vengono mantenute varie versioni (X1, X2, ..., Xk) ed i seguenti timestamp:
        • read_TS(Xi): max tra tutti i TS(T) delle T che hanno letto Xi
        • write_TS(Xi): TS(T) della T che ha scritto Xi
      • regole per la serializzabilità
        • T chiede write_item(X)
          • se write_TS(Xi)= MAX(write_TS(Xj))<= TS(T) e read_TS(Xi)>TS(T), allora uccidi T
          • altrimenti read_TS(Xj)=write_TS(Xj)=TS(T)
        • T chiede read_item(X)
          • se MAX(write_TS(Xi))<=TS(T), allora read_TS(Xi)=MAX(read_TS(Xi),TS(T))
          • (dato l'ordine dei timestamp, la read ha sempre successo)
    • multi-versione 2PL
      • lo stato lock(X) di un elemento può essere:
        • read_locked
        • write_locked
        • certify_locked
        • unlocked
      • permette ad altre transazioni di leggere l'elemento X, mentre una singola transazione T detiene un lock in scrittura su di esso
      • ammette due versioni per ogni elemento X:
        • versione committed: una deve sempre essere stata scritta da una transazione che ha già eseguito il commit
        • l'altra versione X' viene creata quando una transazione T acquisisce un lock in scrittura sull'elemento
      • ogni transazione T può dare il commit SOLO dopo aver ottenuto un certify_lock per tutti gli elementi su cui detiene un write_lock
      • essendo certify un lock totalmente esclusivo, T deve attendere la fine di tutte le read, il valore scritto diventa la committed version
      • evita il fenomeno delle interruzioni a cascata (cascade abort)
      • se si concede l'upgrade della read si possono verificare deadlock che vanno gestiti con altre tecniche
  • tecniche ottimistiche
    • sono tecniche per il controllo della concorrenza
    • ipotizzano un basso livello di interferenza tra le transazioni
    • eseguono i controlli a transazioni TERMINATE (non viene attuata alcuna verifica durante l'esecuzione delle transazioni)
    • effettuano gli aggiornamenti su copie locali degli elementi ed aggiornano il database solo dopo aver fatto il controllo di serializzabilità sulle transazioni completate
    • prevede tre fasi: lettura (su copie locali), validazione (si verifica la serializzabilità), scrittura (si applicano le transazioni validate al database)
    • esempio di fase di validazione
      • almeno una delle seguenti 3 condizioni deve essere soddisfatta
        • 1) Tj completa la fase di scrittura PRIMA che Ti cominci la fase di lettura
        • 2) Ti inizia la fase di scrittura dopo che Tj ha terminato la fase di scrittura e {read_set(Ti) ∩ write_set(Tj)=O}
        • 3) Tj completa lettura PRIMA che Ti concluda lettura e {read_set(Ti),write_set(Ti)} ∩ write_set(Tj)=O}
  • granularità vs locking
    • la granularità può influenzare le prestazioni delle tecniche di controllo della concorrenza e gestione dell'affidabilità
    • un elemento potrebbe essere: un record del DB, un valore di un record, un blocco di disco, un file, un intera base di dati
    • tanto maggiore è la dimensione dell'elemento, tanto minore è il grado di concorrenza permesso
    • tanto più piccola è la dimensione degli elementi, tanto più grande è il loro numero e con esso i lock da gestire
    • è necessario scegliere la giusta granularità a seconda della tipologia di transazioni coinvolte
    • locking a più livelli di granularità
      • la granularità è organizzata gerarchicamente ed è diversa per vari insiemi di transazioni
      • per rendere pratico questo tipo di locking sono necesarie ulteriori modalità di locking rispetto a quelle 2PL:
        • intention-shared (IS) (intenzione di lock condiviso)
          • indica che uno o più lock condivisi saranno richiesti su qualche nodo discendente
        • intention-exclusive (IX) (intenzione di lock esclusivo)
          • indica che uno o più lock esclusivi saranno richiesti su qualche nodo discendente
        • shared-intention-exclusive (SIX) (lock condiviso ed intenzione di lock esclusivo)
          • indica che il nodo corrente è bloccato in modalità condivisa, ma che uno o più lock esclusivi saranno richiesti su qualche nodo discendente
      • protocollo di locking a granularità multipla (MGL - Multi Granularity Locking)
        • adatto ad ambienti con transazioni brevi che accedono solo a pochi elementi di fine granularità (record o campi) o transazioni lunghe che accedono a file interi
        • regole:
          • 1) rispetto Matrice Compatibilità
          • 2) Radice sempre bloccata per prima
          • 3) T può bloccare un nodo SOLO se non ne ha sbloccato nessuno (2PL)
          • 4) T può sbloccare un nodo SOLO se nessun figlio è bloccato da T
          • 5) T può ottenere S o IS su un nodo n solo se ha IX o IS sul padre di n. Cioè:
            • ST(n) o IST(n) se e solo se IXT(Pn) o IST(Pn)
          • 6) T può ottenere X o IX su un nodo n solo se ha X o SIX sul padre di n. Cioè:
            • XT(n) o IXT(n) se e solo se XT(Pn) o SIX T(Pn)
• RECOVERY
  • tecniche impiegate nelle basi di dati per il ripristino al più recente stato consistente della base di dati, a seguito di situazioni di guasti
  • vengono progettati in modo che il rollback a cascata non sia mai necessario (schedule strict o cascadeless)
  • dump
    • è una copia periodica su dispositivo esterno dell'intera base di dati
    • si esegue a transazioni ferme
    • vengono registrati nel log
  • strategie di recovery
    • danni fisici
      • ripristino vecchia copia della base di dati (dump dei dati)
      • ripresa a freddo basata sul dump + ripresa a caldo
    • inconsistenza
      • redo/undo delle transazioni
      • ripresa a caldo basata sui file di log
  • tecniche
    • aggiornamento differito (deferred update - no-undo/redo)
      • una transazione non può modificare la base di dati su disco fino a quando non ha raggiunto il proprio punto di commit
      • una transazione non ragiunge il proprio punto di commit fino a quando tutte le sue operazioni di aggiornamento non sono state registrate nel log e quest'ultimo è stato trascritto su disco con un'operazione di scrittura force
      • non si esegue alcun undo, se necessario si esegue il redo delle transazioni che hanno eseguito il commit nel log ma che non hanno ancora scritto nel DB
    • aggiornamento immediato (immediate update - undo/redo)
      • è la più utilizzata nella pratica
      • la base di dati può essere aggiornata progressivamente da alcune operazioni prima che essa raggiunga il punto di commit
      • le operazioni vengono registrate sul log mediante scrittura forzata (primitiva force) prima di ogni update
      • vengono disfatte (rollback) le operazioni che non hanno raggiunto il commit e tutte le transazioni che hanno letto i dati aggiornati
      • vengono rifatte tutte le transazioni che hanno raggiunto il commit
      • esiste anche una variante undo/no-redo
  • caching (buffering)
    • è tipicamente gestito dal sistema operativo ma, data la sua importanza per il recovery, è gestito dal DBMS tramite chiamate a basso livello del SO
    • tipicamente una o più pagine di disco contenenti i dati da aggiornare vengono trasferite temporaneamente nei buffer della memoria principale (caching) dove sono poi aggiornate prima di essere ritrascritte sul disco
    • si utilizza una directory per la cache che può consistere in una tabella con voci della forma [indirizzo di pagina disco, posizione nel buffer]
    • il DBMS opera sempre tramite la cache trasferendo i dati da e verso il disco
    • per liberare spazio sulla cache si possono usare varie strategie come: LRU (Least Recent used) o FIFO (First In First Out)
    • dirty bit
      • bit associato ad ogni buffer della cache che può essere incluso nella voce di directory per indicare se il buffer è stato modificato o meno
      • quando è posto ad 1 indica che il buffer è stato modificato e che può essere ritrascritto sul disco
    • pin-unpin bit
      • bit che indica se la pagina della cache può essere ritrascritta sul disco (unpinned) o meno (pinned)
    • aggiornamento in-place
      • il buffer viene ritrascritto nella sua posizione originale sul disco sovrascrivendo il vecchio valore
    • shadowing
      • il buffer viene ritrascritto sul disco in una nuova posizione (AFIM - after image) così da conservare il vecchio valore (BFIM - before image) nella posizione precedente
      • consente di mantenere versioni multiple dei dati
  • write-ahead logging (scrittura anticipata del log)
    • si utilizza l'aggiornamento in-place ed un log per il ripristino
    • il meccanismo di recovery deve garantire che la BFIM dell'elemento venga memorizzata in una voce di log appropriata e che la voce di log venga trasferita su disco (flush) prima che la BFIM venga sovrascritta con la AIFM nella base di dati su disco
    • strategie
      • steal
        • una pagina della cache aggiornata da una transazione può essere scritta su disco prima che essa abbia eseguito il commit
        • viene utilizzato quando il gestore della cache del DBMS ha necessità di spazio sulla cache
        • questa politica libera i buffer
      • no-steal
        • una pagina della cache aggiornata da una transazione non può essere scritta su disco prima che essa abbia eseguito il commit
        • viene verificato il pin di pin/unpin
      • force
        • tutte le pagine aggiornate da una transazione vengono immediatamente scritte su disco quando la transazione esegue il commit
      • no-force
        • è il contrario di force
        • è l'approccio usato dall'aggiornamento differito
        • evita di riaggiornare una pagina già aggiornata
    • tipicamente si impiega un approccio steal/no-force per questioni prestazionali
    • protocollo di esempio UNDO/REDO
      • l'immagine precedente di un elemento non può essere sovrascritta dalla relativa immagine successiva nella base di dati su disco finché tutti i record di log di tipo undo della transazione che attua l'aggiornamento - fino a quel momento - non sono stati scritti (scrittura force) sul disco
      • l'operazione di commit di una transazione non può essere completata finché tutti i record di log di tipo redo e di tipo undo relativi alla transazione non sono stati scritti (scrittura force) sul disco
    • liste di supporto per le operazioni di ripristino (dall'ultimo checkpoint)
      • lista transazioni attive
      • lista transazioni committed
      • listra transazioni fallite
  • recovery con aggiornamento differito monoutente (RDU_S)
    • redo (idempotente)
      • nell'ordine del LOG di tutte le committed transactions
    • riavvio dell'ultima transazione attiva
    • REDO(Write_OP)=Rifacimento di tutte le Write tramite log impostando il nuovo valore (AI)
  • recovery con aggiornamento differito multiutente (RDU_M)
    • redo
      • nell'ordine del LOG di tutte le CT che hanno raggiunto il commit DOPO l'ultimo checkpoint (possono essere anche a cavallo)
      • tutte le transazioni attive e/o non concluse vengono annullate e riavviate
      • è ottimizzabile aggiornando per ciascun dato SOLO l'ultimo valore modificato nel Log (proveniendo da CT gli altri verrebbero sovrascritti)
    • no-undo/redo
      • perché nessuna T legge valori da transazioni non committed (NO rollback in cascata)
  • recovery con aggiornamento immediato monoutente (RIU_S)
    • undo transazione attiva
    • redo nell'ordine del LOG di tutte le committed transactions
    • riavvio dell'ultima transazione attiva
  • recovery con aggiornamento immediato multiutente (RIU_M)
    • undo in ordine INVERSO al LOG di tutte le T attive che NON hanno raggiunto il commit
    • redo nell'ordine del LOG di tutte le CT che hanno raggiunto il commit DOPO l'ultimo checkpoint (possono essere anche a cavallo)
    • tutte le transazioni attive e/o non concluse vengono annullate e riavviate
  • shadow pages
    • rappresentano un'alternativa al ripristino basato su LOG
    • durante l'esecuzione di T si conservano:
      • la tabella delle pagine correnti
      • la tabella delle shadow page
    • quando T comincia le due pagine (PG) sono uguali.
    • l'UPDATE avviene sulle pagine correnti
    • le shadow restano inalterate e servono da BI
    • al commit di T: PG correnti → PG shadow
    • pregi
      • il file di log NON esiste (non devo crearlo, aggiornarlo etc)
      • il recovery è più veloce (nessun UNDO/REDO)
    • difetti
      • frammentazione dei dati
      • garbage collection
  • ARIES
    • algoritmo di ripristino progettato per lavorare con la politica STEAL/NO-FORCE
    • basi
      • WAL (Write-Ahead Logging)
      • repeating history during REDO
        • recupero di tutte le azioni del DBMS prima del crash per riportare BD allo stato corrente al momento dello stesso
      • logging changes during UNDO
        • se accade un guasto durante il ripristino le operazioni di UNDO non vengono ripetute quando ARIES riparte
    • fasi
      • analisi
        • identifica:
          • le dirty(update) pages nel buffer (al crash)
          • le transazioni attive (al crash)
          • il punto del log da cui riparte il REDO
      • redo
        • effettua le operazioni di REDO
      • undo
        • ripercorre indietro il LOG per disfare, in ordine inverso, le transazioni attive al crash
    • tipologie di record di LOG
      • update
      • commit
      • abort
      • undo
      • eot
      • record di compensazione (UNDO)
    • Log Sequence Number (LSN)
      • associato ad ogni record di log
      • aumenta progressivamente
      • indica l'indirizzo del disco del record di LOG a cui è associato
      • corrisponde ad un'azione della transazione
      • ogni pagina di dati memorizza l'LSN dell'ultimo UPDATE presente nella pagina
      • ogni record di log registra per T:
        • LSN della transazione che precede T
        • l'ID di T
        • la tipologia del record di LOG
    • LSN (solo per write_item)
      • ID pagina dell'item
      • lunghezza item aggiornato
      • offset rispetto all'inizio pagina
      • BI e AI
    • utilizza
      • file di log
      • transaction table (TT)
        • ID di T
        • LSN ultimo record di T
        • stato di T
      • dirty page table (DP)
        • un record per ogni pagina aggiornata
          • ID page
          • ultimo LSN
    • checkpointing
      • scrive un Begin_Checkpoint nel file di LOG
      • scrive un END_Checkpoint nel file di LOG
      • appende a fine LOG TT+DP
    • analisi
      • individua il BEGIN_CHECKPOINT
      • avanza fino a fine LOG
      • accede a TT e DP ed eventualmente le modifica (es. dati mancanti)
      • compila elenco di tutti i REDO e UNDO da effettuarsi (REDO_set, UNDO_set)
    • fase di REDO
      • individua nel LOG l'ultimo punto di flushing delle dirty pages
      • avanza effettuando il REDO x ogni cambio che appare nelle DP
      • raggiunge la fine del LOG
    • fase di UNDO
      • parte dalla fine del LOG
      • procede all'indietro effettuando l'UNDO a ritroso di tutto l'UNDO_set
      • per ogni UNDO scrive un record compensativo
• SICUREZZA DELLE BASI DI DATI
  • minacce per le basi di dati
    • perdita di integrità
      • le informazioni devono essere protette da modifiche improprie
      • vengono apportate modifiche non autorizzate intenzionali o accidentali
    • perdita di disponibilità (privatezza)
      • gli oggetti della base di dati devono essere resi disponibili agli utenti o ai programmi che sono legittimamente autorizzati ad accederevi
    • perdita di riservatezza (segretezza)
      • si riferisce alla protezione dei dati dalla rivelazione (disclosure) non autorizzata
  • cause
    • attacchi fraudolenti
      • rilascio items, modifica items, negazione di servizio (DOS - Denial Of Service)
      • contromisure
        • controllo dell'accesso (CA)
          • regolamenta la riservatezza dei dati
          • stabilisce le operazioni che un utente è autorizzato a compiere sugli stessi
          • viene gestito tramite creazione di account utente con relative password
          • per accedere alla base di dati l'utente deve effettuare il login sul DB usando le proprie credenziali (user, password o dati biometrici...)
          • controlla l'identità di
            • soggetti (utenti, programmi)
            • oggetti (relazioni, viste)
            • modalità di accesso (privilegi)
              • select, modify (update, delete, insert), references
              • read, write, execute, create drop, alter, ...
          • componenti fondamentali
            • soggetti
              • entità che chiedono l'accesso
            • oggetti
              • items
            • modalità di accesso
              • read, write, ...
            • politiche
              • leggi da rispettare
            • autorizzazioni
              • permessi di accesso
            • diritti amministrativi
              • autorizzano i privilegi
          • differenze con i sistemi operativi
            • maggior numero di oggetti da proteggere
            • accesso ai vari livelli di granularità
            • protezione di strutture fisiche e logiche
            • livelli architetturali del DB con requisiti differenti
            • rispetto della rappresentazione fisica e semantica dei dati
        • controllo di inferenza
          • evita che si possano dedurre o inferire fatti riguardanti singoli individui a partire da interrogazioni che coinvolgono solamente statistiche aggregate su gruppi
          • questo problema è noto come sicurezza delle basi di dati statistiche
        • controllo di flusso
          • evita che le informazioni fluiscano in modo da raggiungere utenti non autorizzati attraverso canali nascosti (covert channel)
        • crittografia
          • è utilizzata per proteggere dati sensibili (es. numeri carte di credito)
          • i dati vengono codificati (cifrati) mediante appositi algoritmi di codifica (cifratura)
    • attacchi non fraudolenti
      • disastri inusuali, software bugs, errori umani, guasti
      • contromisure
        • protezione dalla consistenza logica del dato
          • operazionale - accesso concorrente
          • semantica - vincoli di integrità
  • account di sistema (account superuser)
    • è l'account dell'amministratore della base di dati (DBA)
    • è l'autorità centrale che gestisce l'intero sistema
    • può eseguire i seguenti comandi
      • creazione di account
        • controlla l'accesso al DBMS nel suo complesso
      • concessione di privilegi
        • controlla le autorizzazioni discrezionali
      • revoca di privilegi
        • controlla le autorizzazioni discrezionali
      • attribuzione del livello di sicurezza
        • controllo mandatorio
  • audit della base di dati
    • scansione del log per esaminare tutti gli accessi e le operazioni sul DB in un determinato periodo di tempo
    • prevede che vengano preventivamente registrati sul log gli identificativi degli utenti insieme alle operazioni applicate
  • politica di sicurezza
    • definisce le linee guida da seguire nella progettazione, implementazione e gestione del sistema di sicurezza
  • politiche di gestione della sicurezza
    • principi
      • Need to know (minimo privilegio)
        • accesso permesso solo su esplicita autorizzazione
      • Maximized sharing (max condivisione)
        • accesso permesso a meno che non sia negato
    • granularità
      • nome
        • nome dell'oggetto a cui si accede
      • contesto
        • accesso ad un gruppo di oggetti
      • soglia
        • basata sul valore del dato
      • storia accessi
        • comportamento
    • responsabilità amministrativa
      • centralizzata
        • amministratore unico
      • decentralizzata
        • gruppi diversi controllano parti diverse del DB
      • ownership
        • ogni soggetto controlla i propri dati
      • gerarchica
        • un amministratore unico delega il controllo di parti del DB
      • cooperativa
        • autorizzazioni richiedono il consenso di più soggetti
    • meccanismi di sicurezza
      • discrezionali (DAC)
        • si concedono privilegi agli utenti, compresa la capacità di accedere a specifici file di dati o a campi in una particolare modalità (letture, inserimento, cancellazione, aggiornamento)
        • possibile cessione dei privilegi
        • politiche
          • regole stabiliscono i privilegi
          • sono permessi solo gli accessi autorizzati da una regola
          • gli utenti possono concedere o revocare privilegi
        • modello base (Lampson, Graham, Denning)
          • componenti
            • soggetti s
            • oggetti o
            • matrice degli accessi M(s,o)
              • matrice sparsa che stabilisce le modalità di accesso
          • regole
            • R(s,o,m) modella lo stato autorizzativo in base al nome (ownership)
            • lo stato è modificabile tramite la matrice M
        • System R
          • concepito per DBMS relazionali (Griffiths, Wade 76, Faggin 76)
          • efficacemente implementato (Oracle)
          • componenti
            • soggetti : utenti
            • oggetti : relazioni e viste
            • privilegi : (delete, insert, select, update, modify..)
          • ownership
            • l'autore della relazione ne è il proprietario e possiede (in esclusiva) il privilegio drop
            • l'owner possiede TUTTI i privilegi di accesso sui propri dati e può definire il tipo di accesso da concedere agli altri
          • propagazione dei privilegi
            • politica:
              • discrezionale
              • a sistema chiuso
              • amministrazione decentralizzata
              • ownership
          • livelli di privilegio
            • account
              • indicano i privilegi (comandi SQL utilizzabili) definiti a livello di account
            • relazione
              • indicano per ogni utente le relazioni a cui può essere applicato ciascun comando
          • cataloghi
            • sono implementati da tabelle R
            • catalogo sysauth: (id-utente, nome-Rel,auth_R,tipo_R(Rel/Vista), privilegi, grant_option)
            • per ogni colonna di R su cui l'utente ha il privilegio di UPDATE:
              • catalogo syscolauth: (id-utente, nome-Rel,colonna, grant_option)
          • concessione privilegi
            • GRANT (lista priv.) | ALL [PRIVILEGES] ON (lista relaz) | lista viste TO (lista sogg) | PUBLIC [WITH GRANT OPTION]
            • PUBLIC = deroga a tutti gli utenti
            • esempio:
              • GRANT SELECT ON IMPIEGATI,STUDENTI TO ROSSI,VERDI
          • granularità privilegi
            • GRANT (lista priv.) ON (lista relaz) TO (lista sogg) [WITH GRANT OPTION]
            • esempio
              • GRANT UPDATE ON STUDENTI (MATRICOLA) TO ROSSI,VERDI
            • privilegi basati sul contenuto sono autorizzati su viste della relazione
            • in caso di privilegi diversi concessi su più viste si ha intersezione di privilegi
          • propagazione privilegi
            • GRANT (lista priv.) ON (lista relaz) TO (lista sogg) [WITH GRANT OPTION]
            • esempio
              • GRANT SELECT ON IMPIEGATI,STUDENTI TO ROSSI,VERDI WITH GRANT OPTION
              • (ROSSI e VERDI sono autorizzati ad estendere ad altri i propri privilegi)
            • propagazione orizzontale
              • numero di utenti a cui è stata concessa una GRANT
            • propagazione verticale
              • numero di utenti con GRANT option
            • può essere limitata superiormente
          • revoca privilegi
            • REVOKE (lista priv.) ON (lista relaz)FROM (lista sogg)
            • esempio
              • REVOKE SELECT ON IMPIEGATI,STUDENTI FROM ROSSI,VERDI
            • il privilegio è revocato ai soggetti elencati ed a tutti i soggetti a cui essi lo hanno a loro volta concesso (REVOCA RICORSIVA)
          • privilegi multipli
            • un utente può ricevere uno stesso privilegio oppure un gruppo di privilegi da diversi utenti.
            • in caso di revoca da parte di un solo utente,il privilegio viene conservato fino alla revoca da parte di TUTTI gli utenti che lo hanno concesso
          • difetti principali
            • non controlla la propagazione dei privilegi
            • la revoca ricorsiva pone problemi simili al Rollback in cascata delle transazioni
            • IL LIVELLO DI SICUREZZA NON E' DECIDIBILE (insufficiente per ambienti con forti esigenze di protezione)
      • mandatori (MAC)
        • realizzano la sicurezza multilivello mediante classificazione dei dati e degli utenti secondo varie classi (o livelli) ed implementando un'appropriata politica di sicurezza
        • rigido controllo dei privilegi associati a ben definite classi di utenti
        • è adatto per ambienti con forti esigenze di protezione (es. militari)
        • controllano i flussi
        • politiche
          • classi di sicurezza per soggetti ed oggetti
          • classi di sicurezza ordinate (tot, parz)
          • accesso controllato da assiomi di sicurezza
        • modello base (Bell-LaPadula, 1976)
          • prevede una classificazione RIGIDA e STATICA della sicurezza in quanto la classe di accesso non può essere dinamicamente modificata
          • costituisce la base per successive estensioni che permettono di trattare in modo più generale il problema
          • controlla il flusso
          • componenti
            • soggetti s
            • oggetti o
            • modi di accesso (r, w, a, execute)
          • classe di accesso
            • classifica i soggetti e gli oggetti
            • I - livello di sicurezza
              • TS - Top Secret
              • S - Secret
              • C - Confidential
              • U - Unclassified
            • SC - insieme di categorie
              • dipendono dal domino applicativo
              • esempio: esercito, marina, aviazione, ...
            • C(i) = (I(i), SC(i))
            • relazione di dominanza
              • C1(l1,SC1)≥C2(l2,SC2) se e solo se l1≥l2 AND SC1≥SC2
              • C1 domina C2 se e solo se I1 contiene I2 e SC1 contiene SC2
              • esempio
                • C1 = (TS, {carabinieri, esercito})
                • C2 = (TS, {carabinieri})
                • C3 = (C, {carabinieri, esercito})
                • C1 domina C2;
                • C1 domina strettamente C3;
                • C2 e C3 sono incomparabili
          • clearance
            • attribuzione di una classe
            • ogni utente che accede al sistema ha una CLEARANCE rigidamente rispettata
          • stato del sistema
            • è descritto da (A,M,L,G)
              • A - insieme di triple (s,o,m) degli accessi correnti
              • M - matrice degli accessi
              • L - funzione di livello che associa ad ogni elemento del sistema la sua classe di accesso L: O U S → C )
              • G - gerarchia degli oggetti accessibili
            • ogni modifica di stato avviene a seguito di una RICHIESTA
            • la risposta del sistema è chiamata DECISIONE
            • data una RICHIESTA ed uno STATO CORRENTE la decisione viene presa sulla base di ASSIOMI DI SICUREZZA
            • se accessi ed operazioni rispettano gli assiomi il sistema si dice SICURO
          • assiomi
            • proprietà di sicurezza semplice (no read-up secrecy)
              • nessun soggetto può leggere informazioni con classe di accesso maggiore o incomparabile con la propria classe di sicurezza
              • esempio
                • C1= (C, {esercito})
                • C2= (C, {marina,aviazione})
                • C3= (U, {aviazione})
                • un soggetto di classe C1 NON può leggere dati di classe C2 e C3
                • C2 legge C3
            • star (*) property (no write-down secrecy)
              • nessun soggetto può SCRIVERE informazioni in oggetti con classe di accesso INFERIORE alla propria
        • relazioni multilivello
          • appare come contenente dati diversi a soggetti (utenti) con differenti classificazioni di sicurezza
          • regole
            • integrità delle entità
              • tutti gli attributi chiave non devono assumere valore nullo e devono avere stessa CLASSIFICAZIONE
            • integrità dei valori nulli
            • integrità fra istanze
              • se una certo valore di Tupla classificato ad un certo livello può essere derivato a livello inferiore occorre memorizzarlo a tale livello
          • filtraggio
            • permette di memorizzare na singola tupla ad un livello di classificazione maggiore e produrre le tuple corrispondenti a livello di classificazione inferiore
          • polinstanziazione
            • varie tuple possono avere lo stesso valore di chiave apparente ma diversi valori di attributi per utenti a diversi livelli di classificazione
        • Role Base Access Control (RBAC)
          • controllo dell'accesso basato sui ruoli
          • un ruolo è un costrutto semantico che permette di implementare una politica di sicurezza flessibile
          • un UTENTE interagisce col sistema attivando una SESSIONE all'interno della quale può attivare diversi RUOLI dipendenti dal dominio applicativo
          • [UTENTE]-(1,N)-<SESSIONE>-(1,M)-[RUOLI]
          • i ruoli hanno un ordinamento parziale: non riflessivo, non simmetrico, transitivo
          • è una famiglia di modelli organizzati gerarchicamente per complessità crescente:
            • RBAC-0
              • UTENTI (nome_utente)
              • RUOLI (nome_ruolo)
              • PRIVILEGI (alias, relazione,nome_autorizzazione, nome_privilegio, oggetto, ...)
              • UR (nome_utente, nome_ruolo)
              • RP(nome_ruolo, alias)
            • RBAC-1
              • aggiunge a RBAC-0 la gerarchia di ruoli
              • G (Senior, Junior)
            • RBAC-2
              • aggiunge a RBAC-1 i vincoli sui ruoli
                • utenti
                  • ruoli mutualmente esclusivi x uno stesso utente
                • ruoli
                  • utente assegnato ad un certo ruolo solo se ne ricopre già un altro
                • privilegi
                  • mutualmente esclusivi per uno stesso ruolo
            • RBAC-3
              • aggiunge a RBAC -2 vincoli sui ruoli amministrativi
              • ruoli amministrativi
                • i ruoli Amministrativi sono tra loro esclusivi
                • ogni ruolo è posto in corrispondenza con i ruoli che gestisce
              • i ruoli sono inclusi nello standard SQL3
          • RBAC + XML fornisce un'adeguata politica di sicurezza per e-commerce ed il Web
      • DAC e MAC non solo mutualmente esclusive
        • DAC controlla l'accesso e MAC controlla l'autorizzazione dei soggetti
• DATA WAREHOUSING
  • i sistemi di data warehousing forniscono al top management informazioni rapide ed efficaci sulle quali basare le decisioni strategiche
  • DSS Decision Support System
    • tecnologia che supporta la dirigenza aziendale nel prendere decisioni tattico-strategiche in modo migliore e più veloce
    • evoluzione
      • anni '60: rapporti batch
        • difficile trovare ed analizzare i dati
        • costo: ogni richiesta richiede un nuovo programma
      • anni '70: DSS basato su terminale
        • non integrato con strumenti di automazione d'ufficio
      • anni '80: strumento d'automazione d'ufficio
        • strumenti di interrogazione, fogli elettronici, interfacce grafiche
        • accesso ai dati operazionali
      • anni '90: data warehousing, con strumenti integrati
        • OLAP
  • caratteristiche dei data warehouse
    • vista concettuale multidimensionale
    • dimensionalità generica
    • dimensioni e livelli di aggregazione non limitati a priori
    • operazioni cross-dimensionali non limitate
    • gestione di matrici dinamiche sparse
    • architettura client-server
    • supporto multiutente
    • accessibilità
    • trasparenza
    • manipolazione intuitiva dei dati
    • generazione di reportistica
    • struttura flessibile dei report
  • sistema informativo
    • combinazione di risorse umane, materiali e procedure per la gestione (raccolta, archiviazione, elaborazione, scambio, ...) delle informazioni necessarie per le attività aziendali
    • attività aziendali
      • attività di pianificazione strategica
        • informazioni di governo
      • attività di programmazione e controllo
        • informazioni di gestione
      • attività operative
        • informazini di servizio
  • [ sitema azienda [ sistema informativo [ sistema informatico ] ] ]
  • evoluzione dei sistemi informatici
    • inizio anni '60: applicazioni operative
      • elaborazione ripetitiva di grandi quantità di dati: fatture, paghe, stipendi etc...
    • fine anni '60: Servizi informatici di funzione
      • supporto ai responsabili delle funzioni aziendali: contabilità generale, controllo di gestione, ...
    • inizio anni '70: Servizi informatici per l'organizzazione
      • integrazione dati comuni alle diverse funzioni: DBMS (Data Base Management System)
    • inizio anni '80: Servizi informatici per pianificazione strategica
      • sintesi di informazioni dai dati della produzione: supporto alle decisioni, Datawarehouse
    • fine anni '90: Servizi informatici per la cooperazione
      • internet e Web favoriscono lo sviluppo di protocolli di interazione e cooperazione tra sistemi diversi: commercio elettronico, web services
  • dal dato alla conoscenza
    • dato → informazione → conoscenza
    • archivi → basi di dati → basi di conoscenza
    • programmi → DBMS → tecniche DM/DW
  • tipologie di dati
    • strutturati
    • non strutturati
    • semistrutturati
  • difetti dei sistemi tradizionali
    • no dati storici
    • sistemi eterogenei
    • basse prestazioni
    • DBMS non adeguati al supporto decisionale
    • problemi di sicurezza
  • OLTP - On-Line Transaction Processing
    • sono i sistemi tradizionali
    • proprietà
      • transazioni predefinite e di breve durata
      • dati dettagliati, recenti e aggiornati
      • dati residenti su un unico DB
      • read e write di pochi record
      • critiche le proprietà ACID
      • implementate su Main Frame
  • OLAP - On-Line Analytical Processing
    • sistemi di data warehousing
    • i dati usati dai sistemi OLAP sono gli stessi di quelli usati dai sistemi OLTP, quello che cambia nei due tipi di sistemi è l'elaborazione compiuta sui dati
    • proprietà
      • interrogazioni complesse e casuali
      • dati storici e aggregati
      • dati provenienti da più DB eterogenei
      • moltissime operazioni di Read (nessuna di write)
      • visualizzazione dei dati su PC
  • architettura multi-tier di riferimento
    • database OLTP
    • strumenti ETL (Estrazione Trasporto e Trasformazione)
    • data warehouse
    • data mart
    • utilizzatori finali
  • metadati
    • aggiungono delle informazioni ai dati
    • link tra i DB ed il DW
    • ad ogni passo di costruzione il DW genera metadati che possono essere utilizzati per fasi successive
    • uso bimodale
      • 16-22 ore al giorno usati per attività di interrogazione (funzionalità front room)
      • 2-8 ore al giorno usati per caricamento, indicizzazione, controllo qualità e pubblicazione (funzionalità back room)
  • progettazione concettuale di data warehouse
    • ROLAP (Relational OLAP)
      • insieme dei dati su cui navigare è registrato su una o più tabelle relazionali
      • i dati sono acceduti tramite query
      • sui dati, vengono effettuate le sintesi necessarie per la visualizzazione dei risultati
      • supporta interrogazioni tipiche (roll-up, drill-down, ...)
      • presentation server relazionale
        • Oracle 9i + Discoverer
      • vantaggio
        • i dati acceduti sono sempre gli ultimi disponibili
          • esiste una classe di strumenti che è in grado di recuperare i dati dalle tabelle e sintetizzarli
      • svantaggio
        • una volta usciti dal viewer i dati di sintesi si perdono e quindi per riaccedervi è necessario rieseguire le estrazioni e le sommarizzazioni
    • MOLAP (Multidimensional OLAP)
      • l'insieme dei dati su cui navigare è archiviato su una struttura dati a matrice dove sono registrate tutte le sintesi statistiche degli incroci multidimensionali possibili
      • il presentation server in questo caso chiede i dati direttamente al database multidimensionale
      • i dati devono essere organizzati attraverso modelli multidimensionali
      • M indica una struttura per i dati multidimensionali
      • vantaggio
        • tempi di risposta brevi
      • svantaggio
        • il Multidimensional Data Base deve essere allineato all'aggiornamento dei dati di base dal quale viene generato
      • supporta interrogazioni tipiche (roll-up, drill-down, ...)
      • presentation server multidimensionale
        • Express Server
      • FS - Fact Scheme
        • fatti - FT - Fact Table
          • è un concetto sul quale centrare l'analisi (identifica l'attività principale)
          • un fatto è un evento di interesse per l'impresa ed è descritto da un insieme di misure
          • è caratterizzato dai dati di dettaglio che si desidera analizzare
        • misura
          • una proprietà atomica di un fatto da analizzare
          • una dimensione determina la granularità di rappresentazione dei fatti
        • dimensione o gerarchia - DT - Dimension Table
          • una prospettiva lungo la quale effettuare l'analisi
          • parametri rispetto ai quali si analizzano i dati di dettaglio
          • una gerarchia determina come le istanze di fatto possono essere aggregate e selezionate in modo significativo per il processo decisionale
      • topologie
        • stella (star schema)
          • un singolo oggetto (fact table) connesso ad un numero di oggetti (dimension tables)
          • rappresenta una relazione molti a molti
          • il collegamento tra ogni tabella delle dimensioni e la tabella dei fatti rappresenta una relazione uno a molti
          • la chiave della FT è composta dalle chiavi delle varie DT
          • le sottoparti della chiave della FT sono chiavi importate delle DT
          • esiste una relazione di tipo 1-a-n tra le DT e la FT
          • l'accesso ai dati avviene tramite join tra le DT e la FT
          • vantaggi
            • permette di fare assunzioni circa i dati, da utilizzare in fase di ottimizzazione
            • simmetrico
            • facilmente estensibile
            • approcci standard alla costruzione
            • query tipiche eseguibili efficientemente
        • costellazione di fatti
        • fiocco di neve (snowflake)
          • le tabelle delle dimensioni sono suddivise a livello degli attributi di aggregazione
          • si ottiene normalizzando una o più dimensioni dello star schema
            • numero di tabelle maggiori ma di piccole dimensioni e normalizzate
            • conseguente semplicità di gestione in fase di popolazione ed aggiornamento delle tabelle
    • DOLAP (Desktop OLAP)
      • i dati vengono recuperati da un DW relazionale o multidimensionale e copiati localmente
      • Business Objects
  • progettazione dalla BD
    • introduzione di elementi dimensionali nella base di dati integrata
    • identificazione di fatti, misure e dimensioni
    • ristrutturazione dello schema concettuale
      • rappresentazione dei fatti tramite entità
      • individuazione di nuove dimensioni
      • raffinamento dei livelli per ogni dimensione
    • grafo dimensionale
    • progettazione logica e fisica
  • dal DB al DW
    • fatti e dimensioni diventano tabelle a cui si aggiunge una chiave artificiale
    • le tabelle delle dimensioni contengono tutti gli attributi per tutti i livelli della gerarchia
    • poiché le associazioni sono tutte uno-a-molti, si modellano con chiavi esterne
  • chiavi
    • le chiavi aggiunte devono essere chiavi artificiali (numeriche, progressive)
      • non sono le chiavi semantiche eventualmente utilizzate nella base di dati operazionale
    • si ottimizzano le operazioni di join
    • le chiavi semantiche possono essere comunque presenti come attributi comuni
  • interrogazioni
    • SQL standard
      • per ciascuna misura, bisogna considerare alternativamente ogni dimensione e applicare esplicitamente la formula di aggregazione desiderata (conteggio, somma, media, etc.).
      • è complicato e dispendioso in termini di tempo
      • spesso si usano tecniche proprietarie basate su opportune estensioni del linguaggio
    • nuovi tipi di query
      • dipendono dai tool di accesso
      • influenzano l'implementazione delle query
      • operazioni di base:
        • roll-up
          • i dati vengono riassunti riducendo la granularità ed aunmentando la generalità (ad esempio da settimana a trimestre ad anno)
        • drill-down o roll-down
          • i dati vengono mostrati con livelli di dettaglio crescenti (complementare a roll-up)
        • pivoting
          • viene eseguita la tabulazione incrociata (detta anche rotazione)
        • slicing
          • esegue una selezione su una dimensione dell'ipercubo
        • dicing
          • definisce un sottocubo eseguendo una selezione su due o più dimensioni
        • ordinamento
          • i dati vengono ordinati rispetto ad un valore
        • selezione
          • i dati sono resi disponibili per valore o intervallo
        • attributi derivati (calcolati)
          • gli attributi sono calcolati eseguendo operazioni sui valori memorizzati e derivati
        • top-n
          • estrai i primi n elementi da una certa selezione con un certo ordinamento
      • alcuni tipi di DBMS (es. Oracle) includono nel loro SQL dei nuovi operatori di aggregazione (ROLLUP, CUBE, RANK/TOP-N) che riducono notevolmente la complessità dell'SQL
• OBJECT ORIENTED DBMS
  • applicazioni avanzate di BD
    • CAD
    • CAM
    • CASE
    • OIS
    • GIS
    • Network Management systems
    • Editoria Digitale
    • Siti Web
  • limiti attuali DBMS
    • rappresentazione "povera" delle entità del mondo reale (universo tabellare)
    • semantic overloading
      • impossibile distinguere le differenti tipologie di relazione espresse in E/R
    • limitato supporto x rappresentare i vincoli di integrità
    • struttura dati omogenea (in verticale ed orizzontale)
    • set limitato di operazioni (SQL)
    • difficoltà di gestire query ricorsive
    • impedence mismatch
  • evoluzione DBMS
    • modello gerarchico (60/70)
    • modello reticolare
    • modello relazionale (70/80)
    • modello ER
    • modelli semantici (81)
      • object relational data models
      • object oriented data models
  • Object-Oriented DB manifesto (89)
    • introduce 13 caratteristiche che si ritengono indispensabili per un OODBMS:
      • oggetti complessi
      • OID
      • incapsulazione
      • types e classi
      • ereditarietà
      • binding dinamico
      • DML computazionalmente completo
      • set dei dati estensibile
  • Object-Data Management Group (90)
    • associazione di venditori, sciolta nel 2001, che mirava a definire degli standards
    • ODMG 1.0
    • ODMG 2.0 (1997)
    • ODMG 3.0 (1999)
  • The Thirth Manifesto (Darwin, 1995-2000)
    • alcune caratteristiche degli oggetti sono necessarie, ma devono essere ortogonali al modello relazionale
      • no extension
      • no correction
      • no subsumption
      • no perversion
    • SQL è rigettato come "perversion" del modello relazionale
• BASI DI DATI MULTIMEDIALI (MMDBMS)
  • richiedono la rappresentazione e la gestione di dati non tradizionali:
    • testi arbitrari
    • immagini
    • audio
    • video
    • dati tradizionali (relazionali, orientati ad oggetti)
  • un sistema di gestione dati multimediali (MMDBMS) permette la rappresentazione e la gestione di diversi tipi di dati, potenzialmente rappresentati secondo diversi formati:
    • rappresentare dati corrispondenti a diverse tipologie di media
    • interrogare dati rappresentati in formati diversi in modo uniforme
    • interrogare dati in formati diversi simultaneamente nel contesto della stessa query
    • recuperare gli oggetti dal supporto su cui risiedono, compatibilmente con il tipo di media che rappresentano
  • query
    • un linguaggio di query per MMDBMS deve avere caratteristiche particolari
    • query processing deve analizzare il contenuto degli oggetti
  • rappresentazione
    • i dati sono tipicamente non strutturati
    • si vuole analizzare il contenuto
    • un oggetto multimediale in genere può essere composto da diversi sotto-oggetti, ciascuno relativo ad un particolare media
    • le relazioni tra oggetti e sotto-oggetti possono essere modellate utilizzando un approccio orientato ad oggetti o relazionale ad oggetti
    • per ciascun oggetto multimediale si usano due tipi di attributi che si possono interpretare come una sorta di metadati e dipendono dal tipo di media considerato:
      • descrittivi
        • associano informazioni descrittive (relazionali) a ciascun oggetto
        • vengono associati manualmente all'oggetto
      • content-based (anche chiamati features)
        • associano informazioni relative al contenuto
        • vengono estratti direttamente dal sistema
    • i documenti multimediali potranno essere confrontati solo rispetto agli attributi e alle feature
    • feature uguali non sempre si riferiscono ad oggetti uguali
    • i sistemi mettono a disposizione funzionalità per estrarre feature e per utilizzare tali feature nel contesto delle interrogazioni
  • modalità di memorizzazione
    • internamente al sistema come valori non strutturati in campi LOB (Large Object)
      • facilitano la memorizzazione di dati multimediali (documenti, immagini, audio, ecc.)
      • possono contenere fino a 4GB di dati (di solito i RDBMS non vanno oltre 2-32KB)
      • il DBMS non associa alcuna interpretazione a questi dati
      • si distinguono in:
        • BLOB (Binary LargeObject)
        • CLOB (Character Large Object)
      • supportati da SQL-99
      • sono fisicamente memorizzati esternamente alle tabelle ma internamente al DB (comportamento transazionale)
    • esternamente al sistema, mantendo all'interno del DBMS solo il riferimento alla posizione del file
  • ORDBMS (Object Relational Data Base Management System)
    • gli ORDBMS forniscono inoltre nuovi tipi di dato complessi che supportano:
      • la rappresentazione del dato multimediale
      • nuovi metodi e operatori
      • metodi per l'ottimizzazione di interrogazioni
    • esempi
      • Illustra/Informix → DataBlade
      • IBM → Database Extender
      • Oracle → Oracle Intermedia
      • Librerie fornite da terze parti
  • query
    • query processing
      • la query viene eseguita sui metadati (attributi + features)
      • dai metadati si risale ai documenti originali
      • i documenti originali vengono restituiti all'utente
    • aspetti da supportare
      • le query devono potere essere eseguite su diversi tipi di media contemporaneamente
      • devono considerare attributi e features
      • devono supportare query per similitudine
      • devono associare un valore di rilevanza ad ogni oggetto restituito
      • devono poter essere pesate
      • devono supportare query spazio-temporali
    • attributi e feature
      • le query interrogano gli oggetti multimediali considerando gli attributi e le feature ad essi associati
      • esempio: ritrova tutte le immagini di abitazioni di tipo villa a Cagliari
        • assumo di avere estratto le forme dalle immagini
        • assumo di avere associato informazione descrittiva (luogo, tipo abitazione)
    • query per similitudine
      • il contenuto degli oggetti viene espresso attraverso features
      • le feature non rappresentano pienamente il contenuto semantico di un oggetto
      • le condizioni di selezione sugli oggetti multimediali non sempre sono certe
      • le condizioni non sono in generale condizioni di uguaglianza ma di similitudine
        • le condizioni in genere sono verificate in una certa misura data dalla similitudine tra ciò che stiamo cercando e ciò che abbiamo trovato
    • ranking
      • il ranking è un ordinamento degli oggetti restituiti da una interrogazione che riflette il grado di rilevanza dei documenti rispetto all'interrogazione
      • i criteri per effettuare il ranking dipendono dal media considerato
    • query pesate
      • in alcuni casi può essere utile pesare le varie condizioni nel contesto di una query associando un livello di importanza alla condizione nel determinare la similarità degli oggetti
      • esempio: determinare le immagini che contengono una persona (0.7)
    • query spazio-temporali
      • necessità di interrogare relazioni spazio-temporali esistenti tra gli oggetti
      • relazioni spaziali
        • associano le feature associate ad un oggetto da un punto di vista spaziale
        • importante per immagini/testo
        • in un'immagine, relaziono le forme che compaiono rispetto alla loro posizione (vicino, lontano, a destra, a sinistra)
        • in un testo, relaziono il contenuto (prima, dopo)
      • relazioni temporali
        • associano le feature associate ad un oggetto da un punto di vista temporale
        • importante per audio/video
        • sequenze audio/video: prima, dopo, subito prima, subito dopo, contemporaneamente
    • specifica delle query
      • si estende SQL con condizioni specifiche da applicare ad oggetti multimediali
      • query by example
        • si fornisce un oggetto di esempio e si vogliono determinare tutti gli oggetti simili
  • BASI DI DATI TESTUALI
    • è un database in grado di memorizzare, gestire ed interrogare documenti testuali non strutturati
    • l'obiettivo è di minimizzare il tempo necessario per localizzare le informazioni
    • i risultati di una interrogazione sono ordinati in ordine decrescente di rilevanza
    • un documento è rilevante se l'utente che formula l'interrogazione giudica che il documento e l'interrogazione si riferiscono entrambi allo stesso argomento
    • sfruttano tecniche sviluppate per i sistemi di Information Retrieval (IR)
    • l'ambito dell'IR ha prodotto negli ultimi 20 anni:
      • modelli per la rappresentazione di documenti
      • architetture e linguaggi
      • interfacce e metodi di visualizzazione
    • nonostante questo l'area dell'IR è sempre stata di interesse limitato
    • l'avvento del Web ha cambiato le cose:
      • il Web ha però introdotto nuove problematiche (ad es. bassa qualità di definizione e struttura delle informazioni): le tecniche di IR sono viste come una chiave per trovare le soluzioni
    • lo scopo è di reperire tutti e soli quei documenti che interessano l'utente
      • un sistema con tali caratteristiche non può però essere realizzato in pratica
      • si valuta un sistema tanto più efficiente quanto più è in grado di avvicinarsi a tale requisito
    • criteri di valutazione
      • richiamo (recall)
        • richiamo = rilevanti_restituiti / totale_rilevanti
        • il potere di richiamo è la percentuale di documenti rilevanti restituiti rispetto al totale di documenti rilevanti presenti nel sistema
        • il potere di richiamo ideale è uguale ad 1 (o al 100%)
        • in generale il potere di richiamo sarà un valore inferiore ad uno perché il numero di documenti pertinenti restituiti sarà inferiore al numero di documenti pertinenti presenti nel sistema
      • precisione (precision)
        • precisione = rilevanti_restituiti / totale_restituiti
        • è la percentuale di documenti rilevanti sul totale dei documenti restituiti
        • la precisione ideale è uguae ad 1 (o al 100%)
      • aumentando il numero di documenti restituiti si aumenta il potere di richiamo a spese della precisione
    • feature
      • in generale sono i termini utilizzati come indici
    • indici
      • possono essere: una parola chiave o un insieme di parole
      • determinazione degli indici
        • structure: struttura interna del documento (capitoli, sezioni, sottosezioni)
        • stopwords: articoli e congiunzioni
        • noun groups: si eliminano (o si raggruppano insieme ai sostantivi) aggettivi, avverbi, verbi
        • stemming: ci si riduce a radice comune (es. plurale, singolare)
    • chiave
      • un insieme di concetti che caratterizzano il contenuto informativo del documento
    • sia i documenti che le interrogazioni vengono rappresentati in termini di feature
    • problemi
      • vedere il testo come un insieme di parole chiave è limitativo ed è causa spesso insoddisfazione da parte dell'utente
      • spesso gli utenti non sono in grado di formulare interrogazioni che riflettono i loro requisiti informativi
    • modelli classici
      • ranking
        • uno dei problemi più critici è quello di decidere i criteri di rilevanza di un documento rispetto ad una interrogazione
        • il ranking è un ordinamento dei documenti restituiti da una interrogazione che riflette il grado di rilevanza dei documenti rispetto all'interrogazione
        • i criteri per effettuare il ranking dipendono dal modello adottato per rappresentare i documenti (e di conseguenza anche le query)
      • concetti base
        • ogni documento è rappresentato da un insieme di termini indice rappresentativi
        • un indice è una parola utile per ricordare l'argomento del documento
        • solitamente gli indici sono dei nomi
        • i motori di ricerca assumono che tutte le parole nel testo siano indici (rappresentazione full text)
        • non tutti i termini che compaiono in un documento sono egualmente rappresentativi del suo contenuto informativo:
          • di solito i termini troppo frequenti non sono buoni candidati per diventare indici
          • l'importanza di un indice è rappresentata da un peso ad esso associato
      • modello vettoriale
        • vec(dj) = (w1j, w2j, ..., wtj) è il vettore di pesi associati al documento dj, dove t è il numero totale di indici
        • gi(vec(dj)) = wij è una funzione che restituisce il peso dell'indice ki nel documento dj
        • si assume che i pesi degli indici siano indipendenti
          • questa assunzione è una semplificazione perché esistono delle correlazioni tra termini che compaiono in un documento
          • questo facilita la definizione dei pesi ma rende meno precisa la ricerca: es: computer → network
      • modello booleano
        • è un modello semplice basato sulla teoria degli insiemi
        • le interrogazioni sono espressioni booleane
          • semantica precisa
          • formalismo consolidato
          • q = ka AND (kb OR NOT kc)
        • i pesi assumono valori binari (wij ∈ {0,1})
          • un peso uguale a uno indica che il termine compare nel documento
          • un peso uguale a zero indica che il termine non compare nel documento
        • svantaggi
          • nessuna nozione di matching parziale
          • nessun meccanismo di ranking
          • i bisogni informativi di un utente devono essere tradotti in una espressione booleana
          • le interrogazioni formulate dagli utenti sono spesso troppo approssimate
          • il modello Booleano è il meno potente in quanto non consente il matching parziale
          • risultati sperimentali indicano che il modello vettoriale ha prestazioni migliori del modello probabilistico
    • gestione di testi in Oracle 9i
      • indicizzazione di documenti
        • CONTEXT, per ricerche su documenti arbitrari
        • CTXCAT, per ricerche combinate su documenti brevi e dati strutturati
        • MATCHES, per classificazione documenti
      • tipologie di interrogazione
        • ricerca di documenti che contengono parole o frasi
          • per default case insensitive
          • operatori di espansione, di prossimità
        • ricerca all'interno di sezioni di documenti (WITHIN)
        • ricerca di documenti che trattano un certo argomento (ABOUT)
        • operatori logici, operatori di score
  • BASI DI DATI PER IMMAGINI
    • problematiche
      • rappresentazione delle immagini
      • misura della similarità
      • metodi di accesso e ritrovamento
    • features
      • shape (forma)
        • l'idea è quella di estrarre delle forme dall'immagine
        • possono rappresentare contorni o approssimazione di contorni
      • texture (tessitura)
        • rappresentano informazioni relative alle "regolarità" o "irregolarità" dell'immagine
        • dipendono dalla percezione visiva di un'immagine
        • si basano sulle cosiddette Tamura features
          • coarseness (rugosità)
          • contrasto
          • direzionalità
      • color (colore)
        • proprietà globale che non richiede conoscenza degli oggetti contenuti nelle immagini
        • può essere determinato in modo automatico quindi è molto utilizzato
        • spesso si usano istogrammi che rappresentano la composizione di colori in un'immagine
        • ogni componente dell'istogramma corrisponde ad un colore (256 o 64 componenti)
        • per rappresentare un'immagine, si associa ad ogni componente il numero di pixel dell'immagine più simili al colore considerato
        • il colore di ogni pixel in genere viene rappresentato come una tripla (Red,Green,Blue)
    • proprietà globali
      • un descrittore di forma, shape dell'oggetto e/o la zona dell'immagine nella quale l'oggetto è collocato (approssimazione)
    • proprietà locali
      • un descrittore di proprietà, che descrive le proprietà di un insieme di pixel nell'immagine (RGB, livelli di grigio per immagini in bianco e nero, texture)
    • query per similitudine
      • le query possono coinvolgere sia proprietà locali che proprietà globali
      • approccio metrico
        • si assume che esista una distanza metrica d con la quale confrontare ogni coppia di oggetti
        • più bassa è la distanza, più simili sono gli oggetti
    • rappresentazione immagini nel DBMS
      • dipende dal sistema prescelto
        • riferimento esterno
          • il DB contiene riferimento ai file che contengono le immagini
        • rappresentazione interna
          • le immagini vengono memorizzate nel DBMS tipo blob (binary large object)
      • è rappresentabile come una tripla IDB=(GI, Prop, Rec)
        • GI è un insieme di immagini a cui è stata associata una griglia
        • Prop è un insieme di proprietà di celle
        • Rec è una funzione che associa ad ogni immagine un insieme di shape, in base ad una qualche rappresentazione
    • gestione immagini in Oracle
      • package ORDSYS (gestione oggetti multimediali)
      • per le immagini ORDImage: un'istanza è costituita da:
        • attributi, che rappresentano il dato sorgente, cioè l'immagine
        • proprietà globali come lunghezza, larghezza, dimensione, tipo file (es. TIFF), tipo di compressione (es. JPEG), tipo di contenuto (es. Monocromatico)
        • metodi, che permettono di gestire le immagini
      • ORDImageSignature: un'istanza rappresenta le feature (signature) associate ad un'immagine
• XML (eXtensible Markup Language)
  • è un meta-linguaggio di markup progettato per lo scambio e l'interusabilità di documenti strutturati su Internet
  • è una versione semplificata dell'SGML, un complesso meta-linguaggio che permette di definire linguaggi dichiarativi per la realizzazione di documenti
  • è estensibile ed offre la possibilità di definire i propri "tag"
  • i tag non servono per formattare ma per descrivere e dare significato ai dati
  • diversamente da HTML pone l'accento sulla struttura anziché sulla presentazione
    • l'HTML è non strutturato, statico e non consente tag personalizzati
  • definizioni
    • XML 1.0: un meta-linguaggio di markup
    • XHTML: riformulazione dello standard HTML 4.0 tale che i documenti conformi a questa specifica risultino anche documenti XML ben formati
    • DTD: specifica di vincoli di correttezza su documenti XML
    • XML-Schema: specifica di vincoli sofisticati di correttezza su documenti XML
    • XPath: modello le cui espressioni permettono la navigazione lungo i nodi di un albero XML
    • XPointer (XML Pointer Language): fornisce meccanismi di indirizzamento all'interno dei documenti XML
    • XLink (XML Linking Language): specifica come definire legami, di tipo bidirezionale, tra documenti XML
    • XSLT: trasformazione di documenti XML
    • XSL:FO: formattazione di documenti XML
    • DOM, SAX: interfacce programmatiche (API) per l'analisi (parsing) dei documenti XML
    • SOAP (Simple Object Access Protocol): protocollo basato su XML e pensato per lo scambio di dati in ambito decentralizzato e distribuito
  • meta-linguaggio
    • è un linguaggio utilizzabile per sviluppare altri linguaggi
    • possiamo anche considerarlo come una famiglia di linguaggi che condividono la stessa architettura
    • in pochi anni si sono moltiplicati "vocabolari XML" specifici, ovvero linguaggi di markup costruiti con le regole di XML e pensati per ambiti di applicazione ben definiti
      • linguaggi di strutturazione dei contenuti: XHTML, RSS, XLink
      • linguaggi di trasporto dei dati: SOAP, WSDL, UDDI
      • linguaggi di programmazione: XSL, Voice-XML
      • linguaggi di modellazione: RDF, OWL
    • i linguaggi e i protocolli basati su XML stanno sostituendo la tecnologia EDI (Electronic Data Interchange)
      • EDI era il precedente standard di condivisione dell'informazione in ambito commerciale e industriale
  • vantaggi
    • semplicità
    • riuso
    • separazione struttura-contenuto-presentazione
    • bilanciamento carico client-server in rete
    • supporto per integrare dati da sorgenti differenti
    • capacità di descrivere dati a beneficio di altre applicazioni
    • abilitazione di motori di ricerca avanzati
    • meta-linguaggio
      • XML non è una grammatica (cioè un vocabolario di termini riservati e regole di utilizzo), ma una grammatica di grammatiche, ovvero un modo per generare linguaggi personalizzati in base alle esigenze del progettista
    • documenti auto-descrittivi
      • la scelta dei nomi degli elementi può essere fatta per facilitare la comprensione del ruolo strutturale/semantico dell'elemento
      • l'uso di un DTD/XML Schema può esplicitare le regole di composizione ed i rapporti possibili tra le varie parti dei documenti
    • platform-independence
      • XML è uno standard aperto
      • chiunque può realizzare strumenti che lo usino come formato dei dati
    • strutturazione gerarchica dei documenti
      • permette strutture ad albero
  • svantaggi/limiti
    • troppe e troppo differenti grammatiche possono esprimere gli stessi concetti
    • la flessibilità, che è una delle ragioni del successo di XML, complica notevolmente l'estrazione automatica di informazione e conoscenza dai dati
    • linguaggi di validazione come DTD e XML Schema specificano solo la sintassi e la struttura dei documenti
    • la semantica dei documenti XML, invece, non è specificata formalmente, ma è "incorporata" nei nomi dei tag e, pertanto, può risultare comprensibile all'uomo ma non alla macchina
  • XML descrive la struttura dei dati
    • può descrivere la struttura comune a due DB eterogenei o altre sorgenti di dati (interscambio)
  • XML permette di separare
    • struttura
      • file DTD (Document Type Definition) o XML Schema
    • contenuto
      • documento XML
      • documenti XML di contenuto differente possono condividere lo stesso schema strutturale/sintattico
    • presentazione
      • foglio di stile
      • uno stesso documento XML può essere presentato con modalità differenti
  • un documento XML è costituito da
    • un insieme di tag aperti e chiusi (elementi)
    • gli elementi possono avere un numero arbitrario di coppie attributo-valore
  • anatomia di un documento XML
    • prologo
      • indicazione della versione
        • <?xml version="1.0" encoding="UTF-8" standalone="no"?>
      • informazioni sullo stile di presentazione
        • <?xml:stylesheet type="text/xsl href="staff_list.xsl"?>
      • indicazione di uno schema sintattico di riferimento
        • <!DOCTYPE STAFFLIST SYSTEM "staff_list.dtd">
    • corpo del documento
      • marcatori (tag)
      • dati (istanze)
  • documento ben formato
    • esiste un elemento radice che contiene tutti gli altri
    • gli elementi hanno un tag di apertura e un tag di chiusura (o sono self-closing)
    • i tag sono correttamente annidati
    • i valori degli attributi sono racchiusi tra virgolette
    • i nomi di tag e attributi sono costituiti da una sola parola
    • gli attributi hanno sempre un valore
  • documento valido
    • lo è se è ben formato ed è conforme ad un apposito schema strutturale/sintattico (DTD o XML Schema)
  • parser
    • programma software che legge il documento XML e ne crea una rappresentazione interna utile per successive elaborazioni (come la visualizzazione)
    • parser validante
      • in presenza di un DTD, è in grado di verificare se un documento XML è valido, e di segnalare gli errori di markup presenti
    • parser non validante
      • anche in presenza di un DTD, è solo in grado di verificare se un documento XML è ben formato
      • è più semplice del parser validante
      • spesso è sufficiente
  • API (Application Programming Interface) XML
    • tree-based: DOM - Document Object Model
      • crea in memoria una rappresentazione ad albero del documento
      • fornisce classi e metodi che permettono ad un'applicazione di navigare l'albero e modificarlo
      • utilizzato per effettuare manipolazioni strutturali dell'albero (es. aggiungere/cancellare nodi, riordinare elementi)
      • necessita di un parsing iniziale del documento
    • event-based: SAX - Simple API for XML
      • consente di personalizzare la gestione degli elementi sulla base di eventi
      • esempio, un elemento che comincia o finisce a seconda di un certo evento gestito dall'applicazione
      • non costruisce rappresentazioni dell'albero in memoria
      • si basa su inizio-fine tag per la gestione di un elemento
  • strutura dei documenti XML
    • DTD (Document Type Definition)
      • un XML conforme a DTD si dice VALIDO
      • si specificano
        • quali elementi e quali attributi saranno accettati nei documenti XML che si dichiareranno conformi ad esso
        • possibili combinazioni/annidamenti degli elementi
      • le specifiche DTD possono essere inserite direttamente nel prologo del documento XML (DTD interno)
    • limiti del DTD
      • fornisce solo una parte delle informazioni necessarie a descrivere in modo esauriente la grammatica completa di un linguaggio
        • ad esempio, posso richiedere che un certo attributo abbia come valore una generica stringa di caratteri, ma non ho alcun modo di specificare il formato esatto della stringa
        • oppure, posso richiedere che un certo elemento possa comparire solo all'interno di un altro, ma non posso specificare quante volte l'elemento debba comparire
      • tipi di dato molto generali con una loro sintassi
      • gli elementi del DTD descrivono uno schema dipendente dal particolare ordine del documento
      • necessità di estendere la potenzialità dei parser: dalla capacità di interpretare i documenti alla capacità di interpretare gli schemi dei documenti
    • XML Schema
      • un XML conforme a XML Schema si dice SCHEMA VALIDO
      • è lo strumento ideale per esprimere documenti di testo, ma è anche uno strumento per trasferire DATI STRUTTURATI
      • è stato pensato per fornire quel supporto di validazione che i DTD permettono solo parzialmente (in particolare sul contenuto degli elementi e sui valori degli attributi dei documenti XML)
      • tramite XML Schema, si può realizzare una "interfaccia" tra applicazione ed applicazione, esprimendo un "contratto" dettagliato sul formato e l'organizzazione dei dati
        • il rispetto di questo contratto permette l'interoperabilità tra applicazioni differenti
      • usa XML come sintassi, mentre i DTD usano una sintassi propria e particolare, che richiede parser e strumenti di verifica appositi
      • è estremamente verboso, tre o quattro volte più lungo del corrispondente DTD
      • formato
        • è racchiuso in un elemento <schema>, e può contenere, in varia forma ed ordine, i seguenti elementi: <import> ed <include> per inserire altri frammenti di schema da altri documenti
      • prevede più di quaranta tipi semplici predefiniti (string, float, double, decimal, boolean, date, ...)
        • ogni tipo semplice è caratterizzato da alcune proprietà, dette facets, che ne descrivono vincoli e formati (es: minLength, maxLength)
        • è possibile derivare nuovi tipi, sia semplici che complessi (strutturati)
      • vocabolario
        • insieme di comandi o nomi che possono essere utilizzati nello schema (es. element, sequence, group, ...)
        • è possibile utilizzare diversi vocabolari in uno stesso documento
      • namespace
        • identifica esattamente l'ambito di ciascun elemento, conciliando la presenza di più vocabolari, e soprattutto conciliando la presenza di elementi aventi lo stesso nome ma differente significato
        • evita i conflitti di elementi che hanno lo stesso nome o sono definiti da più di un vocabolario
        • L'URI che identifica il namespace non punta necessariamente a un DTD o a uno schema o a qualunque definizione
        • sono mal supportati dai DTD: occorre creare dei DTD che contengano la dichiarazione completa dei nomi con i prefissi
        • un documento può essere validato in relazione ad uno o più schemi: alle componenti di ciascuno schema è associato uno specifico namespace, detto targetnamespace
        • è possibile specificare regole di validazione solo su alcuni e non tutti i namespace che compaiono in un documento
        • è possibile dare indicazioni al parser per controllare la coesistenza con elementi di altri namespace
    • foglio di stile (stylesheet)
      • specifica come devono essere rappresentati i singoli elementi del documento XML
      • CSS - Cascade StyleSheet (fogli di stile a cascata)
        • offrono funzionalità limitate: a ciascun elemento è assegnata una caratterizzazione puramente "tipografica"
      • XSL (Extensible Stylesheet Language)
        • funzionalità più avanzate per la presentazione dei documenti XML
        • è definito tramite lo stesso XML ed è suddiviso in due parti:
          • XSLT (XSL Transform)
            • linguaggio di trasformazione
            • insieme di regole per selezionare ed elaborare il contenuto dei documenti
            • grazie all'XSLT è possibile interpretare un file XML e trasformarlo in qualcos'altro, ad esempio in HTML
          • XSL:FO
            • un linguaggio di formattazione
  • query
    • XML Query Working Group
      • formato dal W3 nel 1999 per definire:
        • un modello dei dati per documenti XML
        • un insieme di OPERATORI per query su questo modello
        • un LINGUAGGIO di Query su questi operatori
    • XPATH - (XML Path Language)
      • linguaggio di Query di tipo dichiarativo
      • fornisce una semplice sintassi per interrogare porzioni di documenti XML
      • ricerca collezioni di documenti specificando un path (percorso) simile ad una directory
      • permette condizioni di qualifica sul path per semplificare la ricerca
      • ogni documento è visto come un albero
      • la ricerca parte da un context node e prosegue secondo un location path che specifica come passare da un documento ad un altro
      • location path
        • è composto da una serie di step separati da / come nelle usuali directory
        • ogni step consente, rispetto allo step precedente, uno spostamento in profondità nell'albero che descrive il documento
    • XQuery
      • specifica interrogazioni in XML
      • FLWOR expressions (leggi flower)
        • FOR [variabili legate ai nodi individuali (elementi)]
        • LET [variabili legate a collezioni di nodi (elementi)]
        • WHERE [condizioni di qualificazione]
        • ORDER BY [tipo di ordinamento]
        • RETURN [specificazione del risultato dell'operazione]
  • XML e DataBase
    • modelli per l'archiviazione di documenti
      • orientati ai dati (data-centric models)
        • molto strutturati, pochi dati (es. modulo internet)
        • XML è utilizzato per archiviare e rendere interscambiabili i dati che sono fortemente strutturati in modo da essere facilmente gestiti da una macchina
        • in questi modelli l'utilizzo di XML per la precedente finalità è accidentale in quanto potrebbero essere utilizzati altri supporti come un DBMS relazionale
        • XML è stato completamente integrato in Oracle9i e Oracle 10g
      • orientati al documento (document-centric models)
        • struttura leggera, molti dati (es. libro)
        • i documenti sono progettati per essere utilizzati dagli uomini (libri, giornali, e-mail)
        • molti dati sono irregolari o incompleti e la loro struttura può cambiare rapidamente (dati semistrutturati)
        • utilizzo difficile di DBMS, si usano CMS (Content Management Systems)
      • ibridi
        • un misto tra i due modelli precedenti
    • memorizzazione di XML in DB
      • possibili approcci generali:
        • utilizzando i valori d'attributo di una tupla
          • alcuni SQL prevedono un type XML, ma non prevedono una struttura di memorizzazione specifica
          • l'UPDATE del documento richiede di memorizzarlo di nuovo completamente per soddisfare i requisiti strutturali di XML
        • "a brandelli" (shredded form) utilizzando più attributi distribuiti in più relazioni
          • il documento è decomposto secondo gli elementi che lo costituiscono e distribuito in relazioni esistenti
          • regole generali
            • si associa ad ogni elemento una relazione
            • per ogni figlio si decide se:
              • includerlo come attributo della relazione
              • farne una nuova relazione (maxOccurs>1)
              • includerlo come attributo in una relazione esistente
        • in modalità indipendente dallo schema
          • i nodi di un documento sono rappresentati singolarmente in una relazione
          • struttura difficile da navigare, è preferibile una sua espressione denormalizzata
        • in parsed form, cioè si memorizza il formato convertito da un parser.
• SEMANTIC WEB
  • obiettivi
    • estendere l'attuale Web attribuendo ad ogni informazione un significato ben preciso
    • sviluppare un linguaggio per esprimere le informazioni in una forma comprensibile e processabile dalla macchina
  • elaborazione automatica
    • l'elaborazione automatica dei contenuti da parte della macchina presuppone l'esistenza di "meta-informazioni" o "meta-dati" sui contenuti stessi
    • attraverso i meta-dati gli autori possono specificare informazioni che permettano alle applicazioni (es. i motori di ricerca) di interpretare in modo intelligente i documenti
  • scenari
    • applicazione che gestisce dati che conosce
    • applicazioni che si scambiano metadati concordati
    • applicazioni che si scambiano metadati senza accordo preventivo (modello internet)
      • servono standard per
        • rappresentare i metadati
        • scambiare i metadati
        • estrarre significati dai metadati attraverso motori inferenziali
  • il Web si deve dotare di una sovrastruttura per "l'interoperabilità semantica" tra le applicazioni, in modo da poter svolgere quelle funzioni che oggi debbono essere fatte a mano o codificate dentro ai programmi
  • il consorzio W3C si sta adoperando per definire un insieme di standard che, nel loro insieme, costituiranno l'architettura del Semantic Web
    • tale architettura prevede più livelli per la trattazione dei dati:
      • logico
        • ragionamento automatico
        • si esplicano meccanismi di inferenza e di ragionamento automatico sui dati, sulla base delle definizioni precedentemente specificate al livello ontologico
      • ontologico
        • definizione di concetti, relazioni tra concetti, assiomi
        • deve essere garantita l'interoperabilità semantica, attraverso la definizione formale dei concetti relativi ad un certo dominio e delle relazioni che sussistono tra di essi
        • standard di riferimento (sperimentali):
          • DAML + OIL
          • OWL (Ontology Web Language)
      • schema
        • definizione del vocabolario per l'etichettatura semantica delle risorse
        • vengono specificate meta-informazioni sui dati, aggiungendo semantica al livello precedente
        • standard di riferimento:
          • RDF (Resource Description Framework)
          • RDF Schema
      • dati
        • modello dei dati e sintassi per i metadati
        • deve essere garantita l'interoperabilità sintattica
        • standard di riferimento:
          • XML (eXtensible Markup Language)
          • XML Schema