DBMS distribuito - Guida rapida

Per il corretto funzionamento di qualsiasi organizzazione, è necessario un database ben mantenuto. Nel recente passato, i database erano di natura centralizzata. Tuttavia, con l'aumento della globalizzazione, le organizzazioni tendono a diversificarsi in tutto il mondo. Possono scegliere di distribuire i dati su server locali invece che su un database centrale. Così, è arrivato il concetto diDistributed Databases.

Questo capitolo fornisce una panoramica dei database e dei sistemi di gestione dei database (DBMS). Un database è una raccolta ordinata di dati correlati. Un DBMS è un pacchetto software per lavorare su un database. Uno studio dettagliato del DBMS è disponibile nel nostro tutorial denominato "Learn DBMS". In questo capitolo, rivediamo i concetti principali in modo che lo studio del DDBMS possa essere svolto con facilità. I tre argomenti trattati sono schemi di database, tipi di database e operazioni sui database.

Database e Database Management System

UN databaseè una raccolta ordinata di dati correlati creata per uno scopo specifico. Un database può essere organizzato come una raccolta di più tabelle, in cui una tabella rappresenta un elemento o un'entità del mondo reale. Ogni tabella ha diversi campi diversi che rappresentano le caratteristiche dell'entità.

Ad esempio, un database aziendale può includere tabelle per progetti, dipendenti, reparti, prodotti e record finanziari. I campi nella tabella Employee possono essere Name, Company_Id, Date_of_Joining e così via.

UN database management systemè una raccolta di programmi che consente la creazione e la manutenzione di un database. DBMS è disponibile come pacchetto software che facilita la definizione, la costruzione, la manipolazione e la condivisione dei dati in un database. La definizione di un database include la descrizione della struttura di un database. La costruzione di un database implica l'archiviazione effettiva dei dati su qualsiasi supporto di memorizzazione. La manipolazione si riferisce al recupero delle informazioni dal database, all'aggiornamento del database e alla generazione di report. La condivisione dei dati facilita l'accesso ai dati da parte di diversi utenti o programmi.

Esempi di aree di applicazione DBMS

  • Macchine automatiche di cassiera
  • Sistema di prenotazione dei treni
  • Sistema di gestione dei dipendenti
  • Sistema informativo degli studenti

Esempi di pacchetti DBMS

  • MySQL
  • Oracle
  • server SQL
  • dBASE
  • FoxPro
  • PostgreSQL, ecc.

Schemi di database

Uno schema del database è una descrizione del database specificata durante la progettazione del database e soggetta a alterazioni rare. Definisce l'organizzazione dei dati, le relazioni tra di essi e i vincoli ad essi associati.

I database sono spesso rappresentati tramite three-schema architecture o ANSISPARC architecture. L'obiettivo di questa architettura è separare l'applicazione utente dal database fisico. I tre livelli sono:

  • Internal Level having Internal Schema - Descrive la struttura fisica, i dettagli della memoria interna e i percorsi di accesso per il database.

  • Conceptual Level having Conceptual Schema- Descrive la struttura dell'intero database nascondendo i dettagli della memorizzazione fisica dei dati. Questo illustra le entità, gli attributi con i relativi tipi di dati e vincoli, operazioni e relazioni dell'utente.

  • External or View Level having External Schemas or Views - Descrive la parte di un database rilevante per un particolare utente o un gruppo di utenti mentre nasconde il resto del database.

Tipi di DBMS

Esistono quattro tipi di DBMS.

DBMS gerarchico

Nel DBMS gerarchico, le relazioni tra i dati nel database vengono stabilite in modo che un elemento di dati esista come subordinato di un altro. Gli elementi di dati hanno relazioni padre-figlio e sono modellati utilizzando la struttura dati "ad albero". Questi sono molto veloci e semplici.

DBMS di rete

DBMS di rete in uno in cui le relazioni tra i dati nel database sono di tipo molti-a-molti sotto forma di una rete. La struttura è generalmente complicata a causa dell'esistenza di numerose relazioni molti-a-molti. Il DBMS di rete è modellato utilizzando una struttura dati "a grafo".

DBMS relazionale

Nei database relazionali, il database è rappresentato sotto forma di relazioni. Ogni relazione modella un'entità ed è rappresentata come una tabella di valori. Nella relazione o nella tabella, una riga è chiamata tupla e denota un singolo record. Una colonna è chiamata campo o attributo e denota una proprietà caratteristica dell'entità. RDBMS è il sistema di gestione di database più diffuso.

Ad esempio - Una relazione studentesca -

DBMS orientato agli oggetti

Il DBMS orientato agli oggetti è derivato dal modello del paradigma di programmazione orientato agli oggetti. Sono utili per rappresentare sia i dati coerenti archiviati nei database, sia i dati temporanei, come si trovano nell'esecuzione dei programmi. Usano piccoli elementi riutilizzabili chiamati oggetti. Ogni oggetto contiene una parte di dati e un insieme di operazioni che lavorano sui dati. L'oggetto e i suoi attributi sono accessibili tramite puntatori invece di essere archiviati in modelli di tabelle relazionali.

Ad esempio: un database orientato agli oggetti di un conto bancario semplificato

DBMS distribuito

Un database distribuito è un insieme di database interconnessi distribuiti sulla rete di computer o su Internet. Un DDBMS (Distributed Database Management System) gestisce il database distribuito e fornisce meccanismi in modo da rendere i database trasparenti per gli utenti. In questi sistemi, i dati vengono distribuiti intenzionalmente tra più nodi in modo che tutte le risorse di elaborazione dell'organizzazione possano essere utilizzate in modo ottimale.

Operazioni su DBMS

Le quattro operazioni di base su un database sono Crea, Recupera, Aggiorna ed Elimina.

  • CREATE struttura del database e popolarlo con i dati - La creazione di una relazione con il database implica la specifica delle strutture dei dati, dei tipi di dati e dei vincoli dei dati da memorizzare.

    Example - Comando SQL per creare una tabella studenti -

CREATE TABLE STUDENT ( 
   ROLL INTEGER PRIMARY KEY, 
   NAME VARCHAR2(25), 
   YEAR INTEGER, 
   STREAM VARCHAR2(10) 
);

  • Una volta definito il formato dei dati, i dati effettivi vengono memorizzati in base al formato in un supporto di memorizzazione.

    Example Comando SQL per inserire una singola tupla nella tabella degli studenti -

INSERT INTO STUDENT ( ROLL, NAME, YEAR, STREAM) 
VALUES ( 1, 'ANKIT JHA', 1, 'COMPUTER SCIENCE');

  • RETRIEVEinformazioni dal database - Il recupero delle informazioni generalmente implica la selezione di un sottoinsieme di una tabella o la visualizzazione dei dati dalla tabella dopo che sono stati eseguiti alcuni calcoli. È fatto interrogando sul tavolo.

    Example - Per recuperare i nomi di tutti gli studenti del flusso di informatica, è necessario eseguire la seguente query SQL:

SELECT NAME FROM STUDENT 
WHERE STREAM = 'COMPUTER SCIENCE';

  • UPDATE informazioni memorizzate e modifica della struttura del database - L'aggiornamento di una tabella implica la modifica dei vecchi valori nelle righe della tabella esistente con nuovi valori.

    Example - Comando SQL per cambiare il flusso da Elettronica a Elettronica e comunicazioni -

UPDATE STUDENT 
SET STREAM = 'ELECTRONICS AND COMMUNICATIONS' 
WHERE STREAM = 'ELECTRONICS';

  • Modificare il database significa cambiare la struttura della tabella. Tuttavia, la modifica della tabella è soggetta a una serie di restrizioni.

    Example - Per aggiungere un nuovo campo o colonna, ad esempio indirizzo alla tabella Studente, utilizziamo il seguente comando SQL:

ALTER TABLE STUDENT 
ADD ( ADDRESS VARCHAR2(50) );

  • DELETE informazioni memorizzate o eliminare una tabella nel suo insieme: l'eliminazione di informazioni specifiche comporta la rimozione di righe selezionate dalla tabella che soddisfano determinate condizioni.

    Example- Per eliminare tutti gli studenti che sono attualmente al 4 ° anno quando stanno svenendo, utilizziamo il comando SQL -

DELETE FROM STUDENT 
WHERE YEAR = 4;

  • In alternativa, l'intera tabella può essere rimossa dal database.

    Example - Per rimuovere completamente la tabella studenti, il comando SQL utilizzato è:

DROP TABLE STUDENT;

Questo capitolo introduce il concetto di DDBMS. In un database distribuito, ci sono un certo numero di database che possono essere distribuiti geograficamente in tutto il mondo. Un DBMS distribuito gestisce il database distribuito in modo che appaia come un unico database agli utenti. Nella parte successiva del capitolo, andremo a studiare i fattori che portano a database distribuiti, i suoi vantaggi e svantaggi.

UN distributed database è una raccolta di più database interconnessi, che sono distribuiti fisicamente in varie posizioni che comunicano tramite una rete di computer.

Caratteristiche

  • I database nella raccolta sono logicamente correlati tra loro. Spesso rappresentano un unico database logico.

  • I dati vengono archiviati fisicamente su più siti. I dati in ogni sito possono essere gestiti da un DBMS indipendente dagli altri siti.

  • I processori nei siti sono collegati tramite una rete. Non hanno alcuna configurazione multiprocessore.

  • Un database distribuito non è un file system poco connesso.

  • Un database distribuito incorpora l'elaborazione delle transazioni, ma non è sinonimo di un sistema di elaborazione delle transazioni.

Sistema di gestione database distribuito

Un sistema di gestione del database distribuito (DDBMS) è un sistema software centralizzato che gestisce un database distribuito come se fosse tutto archiviato in un'unica posizione.

Caratteristiche

  • Viene utilizzato per creare, recuperare, aggiornare ed eliminare database distribuiti.

  • Sincronizza periodicamente il database e fornisce meccanismi di accesso in virtù dei quali la distribuzione diventa trasparente per gli utenti.

  • Assicura che i dati modificati in qualsiasi sito siano universalmente aggiornati.

  • Viene utilizzato in aree applicative in cui vengono elaborati grandi volumi di dati e l'accesso simultaneo a numerosi utenti.

  • È progettato per piattaforme di database eterogenee.

  • Mantiene la riservatezza e l'integrità dei dati dei database.

Fattori che incoraggiano il DDBMS

I seguenti fattori incoraggiano il passaggio a DDBMS:

  • Distributed Nature of Organizational Units- La maggior parte delle organizzazioni dei tempi attuali sono suddivise in più unità distribuite fisicamente in tutto il mondo. Ogni unità richiede il proprio set di dati locali. Pertanto, il database generale dell'organizzazione viene distribuito.

  • Need for Sharing of Data- Le molteplici unità organizzative hanno spesso bisogno di comunicare tra loro e condividere i propri dati e risorse. Ciò richiede database comuni o database replicati che dovrebbero essere utilizzati in modo sincronizzato.

  • Support for Both OLTP and OLAP- Online Transaction Processing (OLTP) e Online Analytical Processing (OLAP) funzionano su sistemi diversificati che possono avere dati comuni. I sistemi di database distribuiti aiutano entrambe queste elaborazioni fornendo dati sincronizzati.

  • Database Recovery- Una delle tecniche comuni utilizzate in DDBMS è la replica dei dati su diversi siti. La replica dei dati aiuta automaticamente nel recupero dei dati se il database in qualsiasi sito è danneggiato. Gli utenti possono accedere ai dati di altri siti durante la ricostruzione del sito danneggiato. Pertanto, l'errore del database può diventare quasi invisibile per gli utenti.

  • Support for Multiple Application Software- La maggior parte delle organizzazioni utilizza una varietà di software applicativo, ciascuno con il proprio supporto database specifico. DDBMS fornisce una funzionalità uniforme per l'utilizzo degli stessi dati su piattaforme diverse.

Vantaggi dei database distribuiti

Di seguito sono riportati i vantaggi dei database distribuiti rispetto ai database centralizzati.

Modular Development- Se il sistema deve essere espanso a nuove sedi o nuove unità, in sistemi di database centralizzati, l'azione richiede sforzi sostanziali e interruzioni del funzionamento esistente. Tuttavia, nei database distribuiti, il lavoro richiede semplicemente l'aggiunta di nuovi computer e dati locali al nuovo sito e infine il loro collegamento al sistema distribuito, senza interruzioni nelle funzioni correnti.

More Reliable- In caso di malfunzionamento del database, l'intero sistema di database centralizzati si arresta. Tuttavia, nei sistemi distribuiti, quando un componente si guasta, il funzionamento del sistema continua potrebbe avere prestazioni ridotte. Quindi DDBMS è più affidabile.

Better Response- Se i dati vengono distribuiti in modo efficiente, le richieste degli utenti possono essere soddisfatte dai dati locali stessi, fornendo così una risposta più rapida. D'altra parte, nei sistemi centralizzati, tutte le query devono passare attraverso il computer centrale per l'elaborazione, il che aumenta il tempo di risposta.

Lower Communication Cost- Nei sistemi di database distribuiti, se i dati si trovano localmente dove vengono utilizzati principalmente, i costi di comunicazione per la manipolazione dei dati possono essere ridotti al minimo. Ciò non è fattibile nei sistemi centralizzati.

Avversità dei database distribuiti

Di seguito sono riportate alcune delle avversità associate ai database distribuiti.

  • Need for complex and expensive software - DDBMS richiede un software complesso e spesso costoso per fornire trasparenza e coordinamento dei dati tra i diversi siti.

  • Processing overhead - Anche operazioni semplici possono richiedere un gran numero di comunicazioni e calcoli aggiuntivi per fornire l'uniformità dei dati nei siti.

  • Data integrity - La necessità di aggiornare i dati in più siti pone problemi di integrità dei dati.

  • Overheads for improper data distribution- La reattività delle query dipende in gran parte dalla corretta distribuzione dei dati. La distribuzione impropria dei dati spesso porta a una risposta molto lenta alle richieste degli utenti.

In questa parte del tutorial, studieremo i diversi aspetti che aiutano nella progettazione di ambienti di database distribuiti. Questo capitolo inizia con i tipi di database distribuiti. I database distribuiti possono essere classificati in database omogenei ed eterogenei con ulteriori divisioni. La sezione successiva di questo capitolo discute le architetture distribuite, ovvero client-server, peer-to-peer e multi-DBMS. Infine, vengono introdotte le diverse alternative di progettazione come la replica e la frammentazione.

Tipi di database distribuiti

I database distribuiti possono essere ampiamente classificati in ambienti di database distribuiti omogenei ed eterogenei, ciascuno con ulteriori suddivisioni, come mostrato nella figura seguente.

Database distribuiti omogenei

In un database distribuito omogeneo, tutti i siti utilizzano DBMS e sistemi operativi identici. Le sue proprietà sono:

  • I siti utilizzano software molto simili.

  • I siti utilizzano DBMS o DBMS identici dello stesso fornitore.

  • Ogni sito è a conoscenza di tutti gli altri siti e collabora con altri siti per elaborare le richieste degli utenti.

  • Si accede al database tramite un'unica interfaccia come se fosse un unico database.

Tipi di database distribuiti omogenei

Esistono due tipi di database distribuito omogeneo:

  • Autonomous- Ogni database è indipendente e funziona da solo. Sono integrati da un'applicazione di controllo e utilizzano il passaggio di messaggi per condividere gli aggiornamenti dei dati.

  • Non-autonomous - I dati vengono distribuiti tra i nodi omogenei e un DBMS centrale o master coordina gli aggiornamenti dei dati tra i siti.

Database distribuiti eterogenei

In un database distribuito eterogeneo, diversi siti hanno diversi sistemi operativi, prodotti DBMS e modelli di dati. Le sue proprietà sono:

  • Siti diversi utilizzano schemi e software diversi.

  • Il sistema può essere composto da una varietà di DBMS come relazionali, di rete, gerarchici o orientati agli oggetti.

  • L'elaborazione delle query è complessa a causa di schemi dissimili.

  • L'elaborazione delle transazioni è complessa a causa di software dissimili.

  • Un sito potrebbe non essere a conoscenza di altri siti e quindi la cooperazione nell'elaborazione delle richieste degli utenti è limitata.

Tipi di database distribuiti eterogenei

  • Federated - I sistemi di database eterogenei sono di natura indipendente e integrati insieme in modo da funzionare come un unico sistema di database.

  • Un-federated - I sistemi di database utilizzano un modulo di coordinamento centrale attraverso il quale si accede ai database.

Architetture DBMS distribuite

Le architetture DDBMS sono generalmente sviluppate in base a tre parametri:

  • Distribution - Indica la distribuzione fisica dei dati tra i diversi siti.

  • Autonomy - Indica la distribuzione del controllo del sistema di database e il grado in cui ciascun DBMS costituente può operare in modo indipendente.

  • Heterogeneity - Si riferisce all'uniformità o alla diversità dei modelli di dati, componenti di sistema e database.

Modelli architettonici

Alcuni dei modelli architettonici comuni sono:

  • Client - Architettura server per DDBMS
  • Architettura peer-to-peer per DDBMS
  • Architettura multi-DBMS

Client - Architettura server per DDBMS

Questa è un'architettura a due livelli in cui la funzionalità è suddivisa in server e client. Le funzioni del server comprendono principalmente la gestione dei dati, l'elaborazione delle query, l'ottimizzazione e la gestione delle transazioni. Le funzioni client includono principalmente l'interfaccia utente. Tuttavia, hanno alcune funzioni come il controllo della coerenza e la gestione delle transazioni.

Le due diverse architetture client - server sono -

  • Single Server Multiple Client
  • Multiple Server Multiple Client (mostrato nel diagramma seguente)

Architettura peer-to-peer per DDBMS

In questi sistemi, ogni peer agisce sia come client che come server per impartire servizi di database. I pari condividono le loro risorse con altri pari e coordinano le loro attività.

Questa architettura ha generalmente quattro livelli di schemi:

  • Global Conceptual Schema - Raffigura la vista logica globale dei dati.

  • Local Conceptual Schema - Raffigura l'organizzazione logica dei dati in ogni sito.

  • Local Internal Schema - Raffigura l'organizzazione fisica dei dati in ogni sito.

  • External Schema - Raffigura la visualizzazione dei dati da parte dell'utente.

Architetture multi-DBMS

Si tratta di un sistema di database integrato formato da una raccolta di due o più sistemi di database autonomi.

Il multi-DBMS può essere espresso attraverso sei livelli di schemi:

  • Multi-database View Level - Rappresenta più viste utente che comprendono sottoinsiemi del database distribuito integrato.

  • Multi-database Conceptual Level - Raffigura multi-database integrato che comprende definizioni di strutture logiche globali multi-database.

  • Multi-database Internal Level - Raffigura la distribuzione dei dati tra diversi siti e la mappatura da più database a dati locali.

  • Local database View Level - Rappresenta la visualizzazione pubblica dei dati locali.

  • Local database Conceptual Level - Raffigura l'organizzazione locale dei dati in ogni sito.

  • Local database Internal Level - Raffigura l'organizzazione fisica dei dati in ogni sito.

Esistono due alternative di progettazione per multi-DBMS:

  • Modello con livello concettuale multi-database.
  • Modello senza livello concettuale multi-database.

Alternative di design

Le alternative di progettazione della distribuzione per le tabelle in un DDBMS sono le seguenti:

  • Non replicato e non frammentato
  • Completamente replicato
  • Parzialmente replicato
  • Fragmented
  • Mixed

Non replicato e non frammentato

In questa alternativa di progettazione, tabelle diverse vengono posizionate in siti diversi. I dati sono posizionati in modo che siano molto vicini al sito in cui vengono utilizzati maggiormente. È più adatto per i sistemi di database in cui la percentuale di query necessarie per unire le informazioni nelle tabelle collocate in siti diversi è bassa. Se viene adottata una strategia di distribuzione appropriata, questa alternativa di progettazione aiuta a ridurre i costi di comunicazione durante l'elaborazione dei dati.

Completamente replicato

In questa alternativa di progettazione, in ogni sito, viene memorizzata una copia di tutte le tabelle del database. Poiché ogni sito ha la propria copia dell'intero database, le query sono molto veloci e richiedono costi di comunicazione trascurabili. Al contrario, l'enorme ridondanza dei dati richiede costi enormi durante le operazioni di aggiornamento. Quindi, questo è adatto per i sistemi in cui è necessario gestire un numero elevato di query mentre il numero di aggiornamenti del database è basso.

Parzialmente replicato

Copie di tabelle o porzioni di tabelle vengono archiviate in siti diversi. La distribuzione delle tabelle avviene in base alla frequenza di accesso. Ciò tiene in considerazione il fatto che la frequenza di accesso alle tabelle varia notevolmente da sito a sito. Il numero di copie delle tabelle (o porzioni) dipende dalla frequenza con cui vengono eseguite le query di accesso e dal sito che genera le query di accesso.

Frammentato

In questa struttura, una tabella è divisa in due o più parti denominate frammenti o partizioni e ogni frammento può essere archiviato in siti diversi. Ciò tiene conto del fatto che raramente accade che tutti i dati memorizzati in una tabella siano richiesti in un determinato sito. Inoltre, la frammentazione aumenta il parallelismo e fornisce un migliore ripristino di emergenza. In questo caso c'è solo una copia di ogni frammento nel sistema, cioè nessun dato ridondante.

Le tre tecniche di frammentazione sono:

  • Frammentazione verticale
  • Frammentazione orizzontale
  • Frammentazione ibrida

Distribuzione mista

Questa è una combinazione di frammentazione e repliche parziali. Qui, le tabelle sono inizialmente frammentate in qualsiasi forma (orizzontale o verticale), quindi questi frammenti vengono parzialmente replicati attraverso i diversi siti in base alla frequenza di accesso ai frammenti.

Nell'ultimo capitolo, abbiamo introdotto diverse alternative di design. In questo capitolo studieremo le strategie che aiutano nell'adozione dei progetti. Le strategie possono essere sostanzialmente suddivise in replicazione e frammentazione. Tuttavia, nella maggior parte dei casi, viene utilizzata una combinazione dei due.

Replica dei dati

La replica dei dati è il processo di archiviazione di copie separate del database in due o più siti. È una tecnica popolare di tolleranza agli errori dei database distribuiti.

Vantaggi della replica dei dati

  • Reliability - In caso di guasto di un sito, il sistema di database continua a funzionare poiché una copia è disponibile in un altro sito (i).

  • Reduction in Network Load- Poiché sono disponibili copie locali dei dati, l'elaborazione delle query può essere eseguita con un utilizzo ridotto della rete, in particolare durante le prime ore. L'aggiornamento dei dati può essere effettuato in orari non ottimali.

  • Quicker Response - La disponibilità di copie locali dei dati garantisce un'elaborazione rapida delle query e, di conseguenza, tempi di risposta rapidi.

  • Simpler Transactions- Le transazioni richiedono un numero inferiore di join di tabelle ubicate in siti diversi e un coordinamento minimo sulla rete. Quindi, diventano più semplici in natura.

Svantaggi della replica dei dati

  • Increased Storage Requirements- Il mantenimento di più copie di dati è associato a maggiori costi di archiviazione. Lo spazio di archiviazione richiesto è in multipli dello spazio di archiviazione richiesto per un sistema centralizzato.

  • Increased Cost and Complexity of Data Updating- Ogni volta che un elemento di dati viene aggiornato, l'aggiornamento deve riflettersi in tutte le copie dei dati nei diversi siti. Ciò richiede tecniche e protocolli di sincronizzazione complessi.

  • Undesirable Application – Database coupling- Se non vengono utilizzati meccanismi di aggiornamento complessi, la rimozione dell'incoerenza dei dati richiede un coordinamento complesso a livello di applicazione. Ciò si traduce in un'applicazione indesiderata - accoppiamento del database.

Alcune tecniche di replica comunemente utilizzate sono:

  • Replica snapshot
  • Replica quasi in tempo reale
  • Replica pull

Frammentazione

La frammentazione è il compito di dividere una tabella in una serie di tabelle più piccole. Vengono chiamati i sottoinsiemi della tabellafragments. La frammentazione può essere di tre tipi: orizzontale, verticale e ibrida (combinazione di orizzontale e verticale). La frammentazione orizzontale può essere ulteriormente classificata in due tecniche: frammentazione orizzontale primaria e frammentazione orizzontale derivata.

La frammentazione dovrebbe essere eseguita in modo tale che la tavola originale possa essere ricostruita dai frammenti. Ciò è necessario in modo che la tavola originale possa essere ricostruita dai frammenti ogni volta che è necessario. Questo requisito è chiamato "ricostruttività".

Vantaggi della frammentazione

  • Poiché i dati sono archiviati vicino al sito di utilizzo, l'efficienza del sistema di database è aumentata.

  • Le tecniche di ottimizzazione delle query locali sono sufficienti per la maggior parte delle query poiché i dati sono disponibili localmente.

  • Poiché i dati irrilevanti non sono disponibili nei siti, è possibile mantenere la sicurezza e la privacy del sistema di database.

Svantaggi della frammentazione

  • Quando sono necessari dati da frammenti diversi, le velocità di accesso possono essere molto elevate.

  • In caso di frammentazioni ricorsive, il lavoro di ricostruzione richiederà tecniche costose.

  • La mancanza di copie di backup dei dati in siti diversi può rendere il database inefficace in caso di guasto di un sito.

Frammentazione verticale

Nella frammentazione verticale, i campi o le colonne di una tabella vengono raggruppati in frammenti. Per mantenere la ricostruttività, ogni frammento dovrebbe contenere il campo oi campi della chiave primaria della tabella. La frammentazione verticale può essere utilizzata per rafforzare la riservatezza dei dati.

Ad esempio, si consideri che un database universitario conserva i record di tutti gli studenti registrati in una tabella Studenti con lo schema seguente.

ALUNNO

Regd_No Nome Corso Indirizzo Semestre Commissioni Marks

Ora, i dettagli delle commissioni vengono mantenuti nella sezione conti. In questo caso, il designer frammenterà il database come segue:

CREATE TABLE STD_FEES AS 
   SELECT Regd_No, Fees 
   FROM STUDENT;

Frammentazione orizzontale

La frammentazione orizzontale raggruppa le tuple di una tabella in base ai valori di uno o più campi. Anche la frammentazione orizzontale dovrebbe confermare la regola della ricostruttività. Ogni frammento orizzontale deve avere tutte le colonne della tabella di base originale.

Ad esempio, nello schema dello studente, se i dettagli di tutti gli studenti del corso di informatica devono essere mantenuti presso la School of Computer Science, il progettista frammenterà orizzontalmente il database come segue:

CREATE COMP_STD AS 
   SELECT * FROM STUDENT  
   WHERE COURSE = "Computer Science";

Frammentazione ibrida

Nella frammentazione ibrida, viene utilizzata una combinazione di tecniche di frammentazione orizzontale e verticale. Questa è la tecnica di frammentazione più flessibile poiché genera frammenti con informazioni estranee minime. Tuttavia, la ricostruzione della tabella originale è spesso un'operazione costosa.

La frammentazione ibrida può essere eseguita in due modi alternativi:

  • Inizialmente, genera una serie di frammenti orizzontali; quindi generare frammenti verticali da uno o più dei frammenti orizzontali.

  • Inizialmente, genera una serie di frammenti verticali; quindi generare frammenti orizzontali da uno o più dei frammenti verticali.

La trasparenza della distribuzione è di proprietà dei database distribuiti in virtù dei quali i dettagli interni della distribuzione sono nascosti agli utenti. Il progettista DDBMS può scegliere di frammentare le tabelle, replicare i frammenti e archiviarli in siti diversi. Tuttavia, poiché gli utenti sono ignari di questi dettagli, trovano il database distribuito facile da usare come qualsiasi database centralizzato.

Le tre dimensioni della trasparenza della distribuzione sono:

  • Trasparenza della posizione
  • Trasparenza della frammentazione
  • Trasparenza della replica

Trasparenza della posizione

La trasparenza della posizione garantisce che l'utente possa eseguire query su qualsiasi tabella o frammento (i) di una tabella come se fossero archiviati localmente nel sito dell'utente. Il fatto che la tabella oi suoi frammenti siano archiviati in un sito remoto nel sistema di database distribuito dovrebbe essere completamente ignaro per l'utente finale. L'indirizzo dei siti remoti e i meccanismi di accesso sono completamente nascosti.

Al fine di incorporare la trasparenza della posizione, DDBMS dovrebbe avere accesso al dizionario dei dati aggiornato e accurato e alla directory DDBMS che contiene i dettagli delle posizioni dei dati.

Trasparenza della frammentazione

La trasparenza della frammentazione consente agli utenti di eseguire query su qualsiasi tabella come se non fosse frammentata. Pertanto, nasconde il fatto che la tabella su cui l'utente sta interrogando è in realtà un frammento o un'unione di alcuni frammenti. Nasconde anche il fatto che i frammenti si trovano in siti diversi.

Questo è in qualche modo simile agli utenti delle viste SQL, in cui l'utente potrebbe non sapere che sta utilizzando una vista di una tabella invece della tabella stessa.

Trasparenza della replica

La trasparenza della replica garantisce che la replica dei database sia nascosta agli utenti. Consente agli utenti di eseguire query su una tabella come se esistesse solo una singola copia della tabella.

La trasparenza della replica è associata alla trasparenza della concorrenza e alla trasparenza degli errori. Ogni volta che un utente aggiorna un elemento di dati, l'aggiornamento si riflette in tutte le copie della tabella. Tuttavia, questa operazione non dovrebbe essere nota all'utente. Questa è la trasparenza della concorrenza. Inoltre, in caso di guasto di un sito, l'utente può comunque procedere con le sue query utilizzando copie replicate senza alcuna conoscenza del guasto. Questa è la trasparenza del fallimento.

Combinazione di lucidi

In qualsiasi sistema di database distribuito, il progettista dovrebbe garantire che tutte le trasparenze dichiarate siano mantenute in misura considerevole. Il progettista può scegliere di frammentare le tabelle, replicarle e memorizzarle in siti diversi; tutto ignaro dell'utente finale. Tuttavia, la completa trasparenza della distribuzione è un compito arduo e richiede notevoli sforzi di progettazione.

Il controllo del database si riferisce al compito di far rispettare le normative in modo da fornire dati corretti agli utenti autentici e alle applicazioni di un database. Affinché i dati corretti siano disponibili per gli utenti, tutti i dati devono essere conformi ai vincoli di integrità definiti nel database. Inoltre, i dati dovrebbero essere schermati da utenti non autorizzati in modo da mantenere la sicurezza e la privacy del database. Il controllo del database è una delle attività principali dell'amministratore del database (DBA).

Le tre dimensioni del controllo del database sono:

  • Authentication
  • Diritti di accesso
  • Vincoli di integrità

Autenticazione

In un sistema di database distribuito, l'autenticazione è il processo attraverso il quale solo gli utenti legittimi possono accedere alle risorse di dati.

L'autenticazione può essere applicata a due livelli:

  • Controlling Access to Client Computer- A questo livello, l'accesso dell'utente è limitato durante l'accesso al computer client che fornisce l'interfaccia utente al server del database. Il metodo più comune è una combinazione nome utente / password. Tuttavia, metodi più sofisticati come l'autenticazione biometrica possono essere utilizzati per dati ad alta sicurezza.

  • Controlling Access to the Database Software- A questo livello, il software / amministratore del database assegna alcune credenziali all'utente. L'utente accede al database utilizzando queste credenziali. Uno dei metodi consiste nel creare un account di accesso all'interno del server database.

Diritti di accesso

I diritti di accesso di un utente si riferiscono ai privilegi concessi all'utente riguardo alle operazioni DBMS come i diritti per creare una tabella, rilasciare una tabella, aggiungere / eliminare / aggiornare le tuple in una tabella o eseguire una query sulla tabella.

In ambienti distribuiti, poiché esiste un numero elevato di tabelle e un numero ancora maggiore di utenti, non è possibile assegnare diritti di accesso individuali agli utenti. Quindi, DDBMS definisce determinati ruoli. Un ruolo è un costrutto con determinati privilegi all'interno di un sistema di database. Una volta definiti i diversi ruoli, ai singoli utenti viene assegnato uno di questi ruoli. Spesso una gerarchia di ruoli viene definita in base alla gerarchia di autorità e responsabilità dell'organizzazione.

Ad esempio, le seguenti istruzioni SQL creano un ruolo "Accountant" e quindi assegnano questo ruolo all'utente "ABC".

CREATE ROLE ACCOUNTANT; 
GRANT SELECT, INSERT, UPDATE ON EMP_SAL TO ACCOUNTANT; 
GRANT INSERT, UPDATE, DELETE ON TENDER TO ACCOUNTANT; 
GRANT INSERT, SELECT ON EXPENSE TO ACCOUNTANT; 
COMMIT; 
GRANT ACCOUNTANT TO ABC; 
COMMIT;

Controllo dell'integrità semantica

Il controllo dell'integrità semantica definisce e applica i vincoli di integrità del sistema di database.

I vincoli di integrità sono i seguenti:

  • Vincolo di integrità del tipo di dati
  • Vincolo di integrità dell'entità
  • Vincolo di integrità referenziale

Vincolo di integrità del tipo di dati

Un vincolo del tipo di dati limita l'intervallo di valori e il tipo di operazioni che possono essere applicate al campo con il tipo di dati specificato.

Ad esempio, si consideri che una tabella "OSTELLO" ha tre campi: il numero dell'ostello, il nome dell'ostello e la capacità. Il numero dell'ostello deve iniziare con la lettera maiuscola "H" e non può essere NULL e la capacità non deve essere superiore a 150. Il seguente comando SQL può essere utilizzato per la definizione dei dati:

CREATE TABLE HOSTEL ( 
   H_NO VARCHAR2(5) NOT NULL, 
   H_NAME VARCHAR2(15), 
   CAPACITY INTEGER, 
   CHECK ( H_NO LIKE 'H%'), 
   CHECK ( CAPACITY <= 150) 
);

Controllo dell'integrità delle entità

Il controllo dell'integrità dell'entità applica le regole in modo che ogni tupla possa essere identificata in modo univoco da altre tuple. Per questo viene definita una chiave primaria. Una chiave primaria è un insieme di campi minimi che possono identificare in modo univoco una tupla. Il vincolo di integrità dell'entità afferma che due tuple in una tabella non possono avere valori identici per le chiavi primarie e che nessun campo che fa parte della chiave primaria può avere un valore NULL.

Ad esempio, nella tabella dell'ostello sopra, il numero dell'ostello può essere assegnato come chiave primaria tramite la seguente istruzione SQL (ignorando i controlli):

CREATE TABLE HOSTEL ( 
   H_NO VARCHAR2(5) PRIMARY KEY, 
   H_NAME VARCHAR2(15), 
   CAPACITY INTEGER 
);

Vincolo di integrità referenziale

Il vincolo di integrità referenziale stabilisce le regole delle chiavi esterne. Una chiave esterna è un campo in una tabella dati che è la chiave primaria di una tabella correlata. Il vincolo di integrità referenziale stabilisce la regola che il valore del campo della chiave esterna deve essere tra i valori della chiave primaria della tabella di riferimento o essere completamente NULL.

Ad esempio, consideriamo un tavolo per studenti in cui uno studente può scegliere di vivere in un ostello. Per includerlo, la chiave primaria della tabella dell'ostello dovrebbe essere inclusa come chiave esterna nella tabella degli studenti. La seguente istruzione SQL incorpora questo:

CREATE TABLE STUDENT (  
   S_ROLL INTEGER PRIMARY KEY, 
   S_NAME VARCHAR2(25) NOT NULL, 
   S_COURSE VARCHAR2(10), 
   S_HOSTEL VARCHAR2(5) REFERENCES HOSTEL 
);

Quando viene inserita una query, viene inizialmente scansionata, analizzata e convalidata. Viene quindi creata una rappresentazione interna della query, ad esempio un albero della query o un grafico della query. Quindi vengono ideate strategie di esecuzione alternative per recuperare i risultati dalle tabelle del database. Il processo di scelta della strategia di esecuzione più appropriata per l'elaborazione delle query è chiamato ottimizzazione delle query.

Problemi di ottimizzazione delle query in DDBMS

In DDBMS, l'ottimizzazione delle query è un'attività cruciale. La complessità è elevata poiché il numero di strategie alternative può aumentare in modo esponenziale a causa dei seguenti fattori:

  • La presenza di una serie di frammenti.
  • Distribuzione dei frammenti o delle tabelle su vari siti.
  • La velocità dei collegamenti di comunicazione.
  • Disparità nelle capacità di elaborazione locale.

Quindi, in un sistema distribuito, l'obiettivo è spesso trovare una buona strategia di esecuzione per l'elaborazione delle query piuttosto che la migliore. Il tempo per eseguire una query è la somma di quanto segue:

  • È ora di comunicare le query ai database.
  • È ora di eseguire frammenti di query locali.
  • È ora di raccogliere dati da diversi siti.
  • È ora di visualizzare i risultati nell'applicazione.

Elaborazione query

L'elaborazione della query è un insieme di tutte le attività a partire dal posizionamento della query fino alla visualizzazione dei risultati della query. I passaggi sono come mostrato nel diagramma seguente:

Algebra relazionale

L'algebra relazionale definisce l'insieme di base delle operazioni del modello di database relazionale. Una sequenza di operazioni di algebra relazionale forma un'espressione di algebra relazionale. Il risultato di questa espressione rappresenta il risultato di una query sul database.

Le operazioni di base sono:

  • Projection
  • Selection
  • Union
  • Intersection
  • Minus
  • Join

Proiezione

L'operazione di proiezione visualizza un sottoinsieme di campi di una tabella. Questo dà una partizione verticale della tabella.

Syntax in Relational Algebra

$$ \ pi _ {<{AttributeList}>} {(<{Nome tabella}>)} $$

Ad esempio, consideriamo il seguente database degli studenti:

STUDENT
Roll_No Name Course Semester Gender
2 Amit Prasad BCA 1 Maschio
4 Varsha Tiwari BCA 1 Femmina
5 Asif Ali MCA 2 Maschio
6 Joe Wallace MCA 1 Maschio
8 Shivani Iyengar BCA 1 Femmina

Se vogliamo visualizzare i nomi e i corsi di tutti gli studenti, useremo la seguente espressione di algebra relazionale:

$$\pi_{Name,Course}{(STUDENT)}$$

Selezione

L'operazione di selezione mostra un sottoinsieme di tuple di una tabella che soddisfa determinate condizioni. Questo dà una partizione orizzontale della tabella.

Syntax in Relational Algebra

$$ \ sigma _ {<{Condizioni}>} {(<{Nome tabella}>)} $$

Ad esempio, nella tabella Studenti, se vogliamo visualizzare i dettagli di tutti gli studenti che hanno optato per il corso MCA, useremo la seguente espressione di algebra relazionale:

$$\sigma_{Course} = {\small "BCA"}^{(STUDENT)}$$

Combinazione di operazioni di proiezione e selezione

Per la maggior parte delle query, abbiamo bisogno di una combinazione di operazioni di proiezione e selezione. Ci sono due modi per scrivere queste espressioni:

  • Utilizzo della sequenza di operazioni di proiezione e selezione.
  • Utilizzo dell'operazione di rinomina per generare risultati intermedi.

Ad esempio, per visualizzare i nomi di tutte le studentesse del corso BCA -

  • Espressione di algebra relazionale mediante sequenze di operazioni di proiezione e selezione

$$\pi_{Name}(\sigma_{Gender = \small "Female" AND \: Course = \small "BCA"}{(STUDENT)})$$

  • Espressione di algebra relazionale che utilizza l'operazione di rinomina per generare risultati intermedi

$$FemaleBCAStudent \leftarrow \sigma_{Gender = \small "Female" AND \: Course = \small "BCA"} {(STUDENT)}$$

$$Result \leftarrow \pi_{Name}{(FemaleBCAStudent)}$$

Unione

Se P è il risultato di un'operazione e Q è il risultato di un'altra operazione, l'unione di P e Q ($p \cup Q$) è l'insieme di tutte le tuple che è in P o in Q o in entrambe senza duplicati.

Ad esempio, per visualizzare tutti gli studenti che sono nel semestre 1 o nel corso BCA -

$$Sem1Student \leftarrow \sigma_{Semester = 1}{(STUDENT)}$$

$$BCAStudent \leftarrow \sigma_{Course = \small "BCA"}{(STUDENT)}$$

$$Result \leftarrow Sem1Student \cup BCAStudent$$

Intersezione

Se P è il risultato di un'operazione e Q è il risultato di un'altra operazione, l'intersezione di P e Q ( $p \cap Q$ ) è l'insieme di tutte le tuple che sono sia in P che in Q.

Ad esempio, dati i seguenti due schemi:

EMPLOYEE

EmpID Nome Città Dipartimento Stipendio

PROJECT

PId Città Dipartimento Stato

Per visualizzare i nomi di tutte le città in cui si trova un progetto e anche un dipendente risiede:

$$CityEmp \leftarrow \pi_{City}{(EMPLOYEE)}$$

$$CityProject \leftarrow \pi_{City}{(PROJECT)}$$

$$Result \leftarrow CityEmp \cap CityProject$$

Meno

Se P è il risultato di un'operazione e Q è il risultato di un'altra operazione, P - Q è l'insieme di tutte le tuple che sono in P e non in Q.

Ad esempio, per elencare tutti i reparti che non hanno un progetto in corso (progetti con stato = in corso) -

$$AllDept \leftarrow \pi_{Department}{(EMPLOYEE)}$$

$$ProjectDept \leftarrow \pi_{Department} (\sigma_{Status = \small "ongoing"}{(PROJECT)})$$

$$Result \leftarrow AllDept - ProjectDept$$

Aderire

L'operazione di join combina le tuple correlate di due diverse tabelle (risultati di query) in una singola tabella.

Ad esempio, considera due schemi, Cliente e Filiale in un database bancario come segue:

CUSTOMER

CustID AccNo TypeOfAc BranchID DateOfOpening

BRANCH

BranchID BranchName IFSCcode Indirizzo

Per elencare i dettagli del dipendente insieme ai dettagli della filiale:

$$Result \leftarrow CUSTOMER \bowtie_{Customer.BranchID=Branch.BranchID}{BRANCH}$$

Traduzione di query SQL in algebra relazionale

Le query SQL vengono tradotte in espressioni di algebra relazionale equivalenti prima dell'ottimizzazione. Una query viene inizialmente scomposta in blocchi di query più piccoli. Questi blocchi vengono tradotti in espressioni di algebra relazionale equivalenti. L'ottimizzazione include l'ottimizzazione di ogni blocco e quindi l'ottimizzazione dell'intera query.

Esempi

Consideriamo i seguenti schemi:

DIPENDENTE

EmpID Nome Città Dipartimento Stipendio

PROGETTO

PId Città Dipartimento Stato

LAVORI

EmpID PID Ore

Esempio 1

Per visualizzare i dettagli di tutti i dipendenti che guadagnano uno stipendio INFERIORE allo stipendio medio, scriviamo la query SQL:

SELECT * FROM EMPLOYEE 
WHERE SALARY < ( SELECT AVERAGE(SALARY) FROM EMPLOYEE ) ;

Questa query contiene una sottoquery nidificata. Quindi, questo può essere suddiviso in due blocchi.

Il blocco interno è -

SELECT AVERAGE(SALARY)FROM EMPLOYEE ;

Se il risultato di questa query è AvgSal, il blocco esterno è -

SELECT * FROM EMPLOYEE WHERE SALARY < AvgSal;

Espressione di algebra relazionale per blocco interno -

$$AvgSal \leftarrow \Im_{AVERAGE(Salary)}{EMPLOYEE}$$

Espressione di algebra relazionale per blocco esterno -

$$ \ sigma_ {Salary <{AvgSal}>} {EMPLOYEE} $$

Esempio 2

Per visualizzare l'ID del progetto e lo stato di tutti i progetti del dipendente 'Arun Kumar', scriviamo la query SQL:

SELECT PID, STATUS FROM PROJECT 
WHERE PID = ( SELECT FROM WORKS  WHERE EMPID = ( SELECT EMPID FROM EMPLOYEE 
            WHERE NAME = 'ARUN KUMAR'));

Questa query contiene due sottoquery nidificate. Pertanto, può essere suddiviso in tre blocchi, come segue:

SELECT EMPID FROM EMPLOYEE WHERE NAME = 'ARUN KUMAR'; 
SELECT PID FROM WORKS WHERE EMPID = ArunEmpID; 
SELECT PID, STATUS FROM PROJECT WHERE PID = ArunPID;

(Qui ArunEmpID e ArunPID sono i risultati di query interne)

Le espressioni di algebra relazionale per i tre blocchi sono:

$$ArunEmpID \leftarrow \pi_{EmpID}(\sigma_{Name = \small "Arun Kumar"} {(EMPLOYEE)})$$

$$ArunPID \leftarrow \pi_{PID}(\sigma_{EmpID = \small "ArunEmpID"} {(WORKS)})$$

$$Result \leftarrow \pi_{PID, Status}(\sigma_{PID = \small "ArunPID"} {(PROJECT)})$$

Calcolo degli operatori di algebra relazionale

Il calcolo degli operatori di algebra relazionale può essere eseguito in molti modi diversi e ogni alternativa è chiamata file access path.

L'alternativa di calcolo dipende da tre fattori principali:

  • Tipo di operatore
  • Memoria disponibile
  • Strutture del disco

Il tempo per eseguire un'operazione di algebra relazionale è la somma di:

  • È ora di elaborare le tuple.
  • È ora di recuperare le tuple della tabella dal disco alla memoria.

Poiché il tempo per elaborare una tupla è molto inferiore al tempo per recuperare la tupla dalla memoria, in particolare in un sistema distribuito, l'accesso al disco è molto spesso considerato come la metrica per il calcolo del costo dell'espressione relazionale.

Calcolo della selezione

Il calcolo dell'operazione di selezione dipende dalla complessità della condizione di selezione e dalla disponibilità di indici sugli attributi della tabella.

Di seguito sono riportate le alternative di calcolo a seconda degli indici:

  • No Index- Se la tabella non è ordinata e non ha indici, il processo di selezione prevede la scansione di tutti i blocchi del disco della tabella. Ogni blocco viene portato in memoria e ogni tupla nel blocco viene esaminata per vedere se soddisfa la condizione di selezione. Se la condizione è soddisfatta, viene visualizzata come output. Questo è l'approccio più costoso poiché ogni tupla viene portata in memoria e ogni tupla viene elaborata.

  • B+ Tree Index- La maggior parte dei sistemi di database si basa sull'indice B + Tree. Se la condizione di selezione è basata sul campo, che è la chiave di questo indice B + Tree, questo indice viene utilizzato per recuperare i risultati. Tuttavia, l'elaborazione delle istruzioni di selezione con condizioni complesse può comportare un numero maggiore di accessi al blocco del disco e in alcuni casi la scansione completa della tabella.

  • Hash Index- Se vengono utilizzati indici hash e il relativo campo chiave viene utilizzato nella condizione di selezione, il recupero delle tuple utilizzando l'indice hash diventa un processo semplice. Un indice hash utilizza una funzione hash per trovare l'indirizzo di un bucket in cui è memorizzato il valore della chiave corrispondente al valore hash. Per trovare un valore chiave nell'indice, viene eseguita la funzione hash e viene trovato l'indirizzo del bucket. Vengono cercati i valori chiave nel bucket. Se viene trovata una corrispondenza, la tupla effettiva viene recuperata dal blocco del disco nella memoria.

Calcolo dei join

Quando vogliamo unire due tabelle, diciamo P e Q, ogni tupla in P deve essere confrontata con ogni tupla in Q per verificare se la condizione di join è soddisfatta. Se la condizione è soddisfatta, le tuple corrispondenti vengono concatenate, eliminando i campi duplicati e aggiunte alla relazione del risultato. Di conseguenza, questa è l'operazione più costosa.

Gli approcci comuni per l'elaborazione dei join sono:

Approccio ad anello annidato

Questo è l'approccio di join convenzionale. Può essere illustrato attraverso il seguente pseudocodice (Tabelle P e Q, con tuple_p e tuple_q e attributo di unione a) -

For each tuple_p in P 
For each tuple_q in Q
If tuple_p.a = tuple_q.a Then 
   Concatenate tuple_p and tuple_q and append to Result 
End If 
Next tuple_q 
Next tuple-p

Approccio sort-merge

In questo approccio, le due tabelle vengono ordinate individualmente in base all'attributo di unione e quindi le tabelle ordinate vengono unite. Vengono adottate tecniche di ordinamento esterno poiché il numero di record è molto elevato e non può essere contenuto nella memoria. Una volta ordinate le singole tabelle, una pagina ciascuna delle tabelle ordinate viene portata in memoria, unita in base all'attributo di unione e le tuple unite vengono scritte.

Approccio hash join

Questo approccio comprende due fasi: fase di partizionamento e fase di sondaggio. Nella fase di partizionamento, le tabelle P e Q sono suddivise in due serie di partizioni disgiunte. Viene decisa una funzione hash comune. Questa funzione hash viene utilizzata per assegnare tuple alle partizioni. Nella fase di sondaggio, le tuple in una partizione di P vengono confrontate con le tuple della corrispondente partizione di Q. Se corrispondono, vengono scritte.

Una volta derivati ​​i percorsi di accesso alternativi per il calcolo di un'espressione di algebra relazionale, viene determinato il percorso di accesso ottimale. In questo capitolo esamineremo l'ottimizzazione delle query in un sistema centralizzato, mentre nel prossimo capitolo studieremo l'ottimizzazione delle query in un sistema distribuito.

In un sistema centralizzato, l'elaborazione delle query viene eseguita con il seguente obiettivo:

  • Minimizzazione del tempo di risposta della query (tempo impiegato per produrre i risultati alla query dell'utente).

  • Massimizza la velocità effettiva del sistema (il numero di richieste elaborate in un determinato periodo di tempo).

  • Riduci la quantità di memoria e spazio di archiviazione necessaria per l'elaborazione.

  • Aumenta il parallelismo.

Analisi e traduzione delle query

Inizialmente, viene eseguita la scansione della query SQL. Quindi viene analizzato per cercare errori sintattici e correttezza dei tipi di dati. Se la query supera questo passaggio, la query viene scomposta in blocchi di query più piccoli. Ogni blocco viene quindi tradotto in un'espressione di algebra relazionale equivalente.

Passaggi per l'ottimizzazione delle query

L'ottimizzazione delle query prevede tre passaggi, ovvero la generazione dell'albero di query, la generazione del piano e la generazione del codice del piano di query.

Step 1 − Query Tree Generation

Un albero di query è una struttura di dati ad albero che rappresenta un'espressione di algebra relazionale. Le tabelle della query sono rappresentate come nodi foglia. Le operazioni di algebra relazionale sono rappresentate come nodi interni. La radice rappresenta la query nel suo insieme.

Durante l'esecuzione, un nodo interno viene eseguito ogni volta che le sue tabelle di operandi sono disponibili. Il nodo viene quindi sostituito dalla tabella dei risultati. Questo processo continua per tutti i nodi interni fino a quando il nodo radice non viene eseguito e sostituito dalla tabella dei risultati.

Ad esempio, consideriamo i seguenti schemi:

DIPENDENTE

EmpID EName Stipendio DeptNo DateOfJoining

DIPARTIMENTO

DNo DName Posizione

Esempio 1

Consideriamo la query come la seguente.

$$\pi_{EmpID} (\sigma_{EName = \small "ArunKumar"} {(EMPLOYEE)})$$

L'albero della query corrispondente sarà:

Esempio 2

Consideriamo un'altra query che coinvolge un join.

$\pi_{EName, Salary} (\sigma_{DName = \small "Marketing"} {(DEPARTMENT)}) \bowtie_{DNo=DeptNo}{(EMPLOYEE)}$

Di seguito è riportato l'albero delle query per la query precedente.

Step 2 − Query Plan Generation

Dopo la generazione della struttura ad albero della query, viene creato un piano di query. Un piano di query è un albero di query esteso che include i percorsi di accesso per tutte le operazioni nell'albero di query. I percorsi di accesso specificano come devono essere eseguite le operazioni relazionali nell'albero. Ad esempio, un'operazione di selezione può avere un percorso di accesso che fornisce dettagli sull'uso dell'indice dell'albero B + per la selezione.

Inoltre, un piano di query stabilisce anche come le tabelle intermedie dovrebbero essere passate da un operatore al successivo, come dovrebbero essere usate le tabelle temporanee e come le operazioni dovrebbero essere pipeline / combinate.

Step 3− Code Generation

La generazione del codice è il passaggio finale dell'ottimizzazione delle query. È la forma eseguibile della query, la cui forma dipende dal tipo di sistema operativo sottostante. Una volta generato il codice della query, Execution Manager lo esegue e produce i risultati.

Approcci all'ottimizzazione delle query

Tra gli approcci per l'ottimizzazione delle query, vengono utilizzati principalmente la ricerca esaustiva e gli algoritmi basati sull'euristica.

Ottimizzazione della ricerca esaustiva

In queste tecniche, per una query, vengono inizialmente generati tutti i possibili piani di query e quindi viene selezionato il piano migliore. Sebbene queste tecniche forniscano la soluzione migliore, hanno una complessità temporale e spaziale esponenziale a causa dell'ampio spazio della soluzione. Ad esempio, tecnica di programmazione dinamica.

Ottimizzazione basata su euristica

L'ottimizzazione basata su euristica utilizza approcci di ottimizzazione basati su regole per l'ottimizzazione delle query. Questi algoritmi hanno una complessità temporale e spaziale polinomiale, inferiore alla complessità esponenziale degli algoritmi basati sulla ricerca esaustiva. Tuttavia, questi algoritmi non producono necessariamente il miglior piano di query.

Alcune delle regole euristiche comuni sono:

  • Eseguire le operazioni di selezione e progetto prima delle operazioni di unione. Questo viene fatto spostando le operazioni di selezione e progetto in basso nella struttura della query. Ciò riduce il numero di tuple disponibili per l'unione.

  • Eseguire le operazioni di selezione / progetto più restrittive prima delle altre operazioni.

  • Evitare il funzionamento su più prodotti poiché si traducono in tabelle intermedie di dimensioni molto grandi.

Questo capitolo discute l'ottimizzazione delle query nel sistema di database distribuito.

Architettura di elaborazione delle query distribuite

In un sistema di database distribuito, l'elaborazione di una query comprende l'ottimizzazione sia a livello globale che a livello locale. La query entra nel sistema di database sul client o sul sito di controllo. Qui l'utente viene convalidato, la query viene controllata, tradotta e ottimizzata a livello globale.

L'architettura può essere rappresentata come:

Mappatura di query globali in query locali

Il processo di mappatura delle query globali a quelle locali può essere realizzato come segue:

  • Le tabelle richieste in una query globale hanno frammenti distribuiti su più siti. I database locali contengono informazioni solo sui dati locali. Il sito di controllo utilizza il dizionario dati globale per raccogliere informazioni sulla distribuzione e ricostruisce la vista globale dai frammenti.

  • Se non è presente alcuna replica, l'ottimizzatore globale esegue query locali nei siti in cui sono archiviati i frammenti. In caso di replica, l'ottimizzatore globale seleziona il sito in base al costo di comunicazione, al carico di lavoro e alla velocità del server.

  • L'ottimizzatore globale genera un piano di esecuzione distribuito in modo che la quantità minima di trasferimento di dati si verifichi tra i siti. Il piano indica la posizione dei frammenti, l'ordine in cui devono essere eseguiti i passaggi dell'interrogazione e i processi coinvolti nel trasferimento dei risultati intermedi.

  • Le query locali sono ottimizzate dai server di database locali. Infine, i risultati della query locale vengono uniti tramite un'operazione di unione in caso di frammenti orizzontali e un'operazione di unione per frammenti verticali.

Ad esempio, si consideri che il seguente schema del progetto è frammentato orizzontalmente in base a City, le città sono New Delhi, Kolkata e Hyderabad.

PROGETTO

PId Città Dipartimento Stato

Supponiamo che ci sia una query per recuperare i dettagli di tutti i progetti il ​​cui stato è "In corso".

La query globale sarà & inus;

$$\sigma_{status} = {\small "ongoing"}^{(PROJECT)}$$

La query nel server di Nuova Delhi sarà:

$$\sigma_{status} = {\small "ongoing"}^{({NewD}_-{PROJECT})}$$

La query nel server di Calcutta sarà:

$$\sigma_{status} = {\small "ongoing"}^{({Kol}_-{PROJECT})}$$

La query nel server di Hyderabad sarà:

$$\sigma_{status} = {\small "ongoing"}^{({Hyd}_-{PROJECT})}$$

Per ottenere il risultato complessivo, dobbiamo unire i risultati delle tre query come segue:

$\sigma_{status} = {\small "ongoing"}^{({NewD}_-{PROJECT})} \cup \sigma_{status} = {\small "ongoing"}^{({kol}_-{PROJECT})} \cup \sigma_{status} = {\small "ongoing"}^{({Hyd}_-{PROJECT})}$

Ottimizzazione delle query distribuite

L'ottimizzazione delle query distribuite richiede la valutazione di un numero elevato di alberi di query, ciascuno dei quali produce i risultati richiesti di una query. Ciò è dovuto principalmente alla presenza di una grande quantità di dati replicati e frammentati. Quindi, l'obiettivo è trovare una soluzione ottimale invece della soluzione migliore.

I problemi principali per l'ottimizzazione delle query distribuite sono:

  • Utilizzo ottimale delle risorse nel sistema distribuito.
  • Trading di query.
  • Riduzione dello spazio di soluzione della query.

Utilizzo ottimale delle risorse nel sistema distribuito

Un sistema distribuito ha un numero di server di database nei vari siti per eseguire le operazioni relative a una query. Di seguito sono riportati gli approcci per l'utilizzo ottimale delle risorse:

Operation Shipping- Nell'operazione di spedizione, l'operazione viene eseguita presso il sito in cui sono archiviati i dati e non presso il sito del cliente. I risultati vengono quindi trasferiti al sito del cliente. Ciò è appropriato per le operazioni in cui gli operandi sono disponibili nello stesso sito. Esempio: operazioni di selezione e progetto.

Data Shipping- Nella spedizione dei dati, i frammenti di dati vengono trasferiti al server del database, dove vengono eseguite le operazioni. Viene utilizzato nelle operazioni in cui gli operandi vengono distribuiti in siti diversi. Ciò è appropriato anche nei sistemi in cui i costi di comunicazione sono bassi e i processori locali sono molto più lenti del server client.

Hybrid Shipping- Questa è una combinazione di dati e spedizione operativa. Qui, i frammenti di dati vengono trasferiti ai processori ad alta velocità, dove viene eseguita l'operazione. I risultati vengono quindi inviati al sito client.

Query Trading

Nell'algoritmo di scambio di query per sistemi di database distribuiti, il sito di controllo / client per una query distribuita è chiamato acquirente ei siti in cui vengono eseguite le query locali sono chiamati venditori. L'acquirente formula una serie di alternative per la scelta dei venditori e per la ricostruzione dei risultati globali. L'obiettivo dell'acquirente è raggiungere il costo ottimale.

L'algoritmo inizia con l'acquirente che assegna sottoquery ai siti del venditore. Il piano ottimale viene creato dai piani di query ottimizzati locali proposti dai venditori combinati con il costo di comunicazione per la ricostruzione del risultato finale. Una volta formulato il piano ottimale globale, la query viene eseguita.

Riduzione dello spazio della soluzione della query

La soluzione ottimale generalmente comporta la riduzione dello spazio della soluzione in modo da ridurre il costo delle query e del trasferimento dei dati. Ciò può essere ottenuto tramite una serie di regole euristiche, proprio come l'euristica nei sistemi centralizzati.

Di seguito sono riportate alcune delle regole:

  • Eseguire le operazioni di selezione e proiezione il prima possibile. Ciò riduce il flusso di dati sulla rete di comunicazione.

  • Semplifica le operazioni sui frammenti orizzontali eliminando le condizioni di selezione che non sono rilevanti per un particolare sito.

  • In caso di operazioni di join e unione comprendenti frammenti situati in più siti, trasferire i dati frammentati al sito in cui è presente la maggior parte dei dati ed eseguire l'operazione lì.

  • Utilizzare l'operazione di semi join per qualificare le tuple che devono essere unite. Ciò riduce la quantità di trasferimento dati che a sua volta riduce i costi di comunicazione.

  • Unisci le foglie e gli alberi secondari comuni in un albero di query distribuito.

Questo capitolo discute i vari aspetti dell'elaborazione delle transazioni. Studieremo anche le attività di basso livello incluse in una transazione, gli stati della transazione e le proprietà di una transazione. Nell'ultima parte, esamineremo le pianificazioni e la serializzabilità delle pianificazioni.

Transazioni

Una transazione è un programma che include una raccolta di operazioni di database, eseguite come unità logica di elaborazione dei dati. Le operazioni eseguite in una transazione includono una o più operazioni di database come inserire, eliminare, aggiornare o recuperare dati. È un processo atomico che viene eseguito completamente o non viene eseguito affatto. Una transazione che coinvolge solo il recupero dei dati senza alcun aggiornamento dei dati è chiamata transazione di sola lettura.

Ogni operazione di alto livello può essere suddivisa in una serie di attività o operazioni di basso livello. Ad esempio, un'operazione di aggiornamento dei dati può essere suddivisa in tre attività:

  • read_item() - legge l'elemento di dati dalla memoria alla memoria principale.

  • modify_item() - modificare il valore dell'articolo nella memoria principale.

  • write_item() - scrive il valore modificato dalla memoria principale alla memoria.

L'accesso al database è limitato alle operazioni read_item () e write_item (). Allo stesso modo, per tutte le transazioni, leggere e scrivere costituisce le operazioni di base del database.

Operazioni di transazione

Le operazioni di basso livello eseguite in una transazione sono:

  • begin_transaction - Un indicatore che specifica l'inizio dell'esecuzione della transazione.

  • read_item or write_item - Operazioni del database che possono essere interfogliate con le operazioni della memoria principale come parte della transazione.

  • end_transaction - Un indicatore che specifica la fine della transazione.

  • commit - Un segnale per specificare che la transazione è stata completata con successo nella sua interezza e non verrà annullata.

  • rollback- Un segnale per specificare che la transazione non è andata a buon fine e quindi tutte le modifiche temporanee nel database vengono annullate. Una transazione confermata non può essere annullata.

Stati di transazione

Una transazione può passare attraverso un sottoinsieme di cinque stati, attiva, parzialmente confermata, confermata, fallita e interrotta.

  • Active- Lo stato iniziale in cui entra la transazione è lo stato attivo. La transazione rimane in questo stato durante l'esecuzione di operazioni di lettura, scrittura o altre operazioni.

  • Partially Committed - La transazione entra in questo stato dopo che è stata eseguita l'ultima istruzione della transazione.

  • Committed - La transazione entra in questo stato dopo il completamento con successo della transazione e i controlli di sistema hanno emesso il segnale di commit.

  • Failed - La transazione passa dallo stato parzialmente confermato o attivo allo stato non riuscito quando si scopre che la normale esecuzione non può più procedere o che i controlli di sistema falliscono.

  • Aborted - Questo è lo stato dopo che è stato eseguito il rollback della transazione dopo un errore e il database è stato ripristinato allo stato precedente all'inizio della transazione.

Il seguente diagramma di transizione di stato descrive gli stati nella transazione e le operazioni di transazione di basso livello che provocano il cambiamento negli stati.

Proprietà desiderabili delle transazioni

Qualsiasi transazione deve mantenere le proprietà ACID, vale a dire. Atomicità, coerenza, isolamento e durata.

  • Atomicity- Questa proprietà afferma che una transazione è un'unità atomica di elaborazione, ovvero viene eseguita nella sua interezza o non viene eseguita affatto. Non dovrebbe esistere alcun aggiornamento parziale.

  • Consistency- Una transazione dovrebbe portare il database da uno stato coerente a un altro stato coerente. Non dovrebbe influire negativamente su alcun elemento di dati nel database.

  • Isolation- Una transazione dovrebbe essere eseguita come se fosse l'unica nel sistema. Non dovrebbe esserci alcuna interferenza dalle altre transazioni simultanee in esecuzione simultaneamente.

  • Durability - Se una transazione confermata determina una modifica, tale modifica deve essere durevole nel database e non deve essere persa in caso di errore.

Orari e conflitti

In un sistema con un numero di transazioni simultanee, a scheduleè l'ordine totale di esecuzione delle operazioni. Data una schedulazione S composta da n transazioni, diciamo T1, T2, T3 ……… ..Tn; per qualsiasi operazione Ti, le operazioni in Ti devono essere eseguite come previsto dallo schema S.

Tipi di orari

Esistono due tipi di pianificazioni:

  • Serial Schedules- In una pianificazione seriale, in qualsiasi momento, solo una transazione è attiva, ovvero non vi è alcuna sovrapposizione di transazioni. Questo è illustrato nel grafico seguente:

  • Parallel Schedules- Nelle pianificazioni parallele, più di una transazione è attiva contemporaneamente, ovvero le transazioni contengono operazioni che si sovrappongono nel tempo. Questo è illustrato nel grafico seguente:

Conflitti negli orari

In una pianificazione che comprende più transazioni, a conflictsi verifica quando due transazioni attive eseguono operazioni non compatibili. Si dice che due operazioni siano in conflitto, quando tutte le seguenti tre condizioni esistono simultaneamente:

  • Le due operazioni fanno parte di transazioni diverse.

  • Entrambe le operazioni accedono allo stesso elemento di dati.

  • Almeno una delle operazioni è un'operazione write_item (), cioè cerca di modificare l'elemento di dati.

Serializzabilità

UN serializable scheduledi "n" transazioni è una pianificazione parallela che è equivalente a una pianificazione seriale che comprende le stesse "n" transazioni. Una pianificazione serializzabile contiene la correttezza della pianificazione seriale mentre si accerta un migliore utilizzo della CPU della pianificazione parallela.

Equivalenza degli orari

L'equivalenza di due programmi può essere dei seguenti tipi:

  • Result equivalence - Si dice che due programmi che producono risultati identici siano equivalenti.

  • View equivalence - Due pianificazioni che eseguono un'azione simile in modo simile sono considerate equivalenti alla visualizzazione.

  • Conflict equivalence - Due pianificazioni sono considerate equivalenti al conflitto se contengono lo stesso insieme di transazioni e hanno lo stesso ordine di coppie di operazioni in conflitto.

Le tecniche di controllo della concorrenza assicurano che più transazioni vengano eseguite simultaneamente mantenendo le proprietà ACID delle transazioni e la serializzabilità nelle pianificazioni.

In questo capitolo studieremo i vari approcci per il controllo della concorrenza.

Protocolli di controllo della concorrenza basati sul blocco

I protocolli di controllo della concorrenza basati sul blocco utilizzano il concetto di blocco degli elementi di dati. UNlockè una variabile associata a un elemento di dati che determina se le operazioni di lettura / scrittura possono essere eseguite su quell'elemento di dati. In genere, viene utilizzata una matrice di compatibilità del blocco che indica se un elemento di dati può essere bloccato da due transazioni contemporaneamente.

I sistemi di controllo della concorrenza basati sul blocco possono utilizzare protocolli di blocco monofase o bifase.

Protocollo di blocco monofase

In questo metodo, ogni transazione blocca un elemento prima dell'uso e rilascia il blocco non appena ha finito di usarlo. Questo metodo di blocco fornisce la massima concorrenza ma non sempre impone la serializzabilità.

Protocollo di blocco a due fasi

In questo metodo, tutte le operazioni di blocco precedono la prima operazione di sblocco o sblocco. La transazione si compone di due fasi. Nella prima fase, una transazione acquisisce solo tutti i blocchi di cui ha bisogno e non rilascia alcun blocco. Questo è chiamato espansione ogrowing phase. Nella seconda fase, la transazione rilascia i blocchi e non può richiedere nuovi blocchi. Questo è chiamatoshrinking phase.

Ogni transazione che segue il protocollo di blocco a due fasi è garantita come serializzabile. Tuttavia, questo approccio fornisce un basso parallelismo tra due transazioni in conflitto.

Algoritmi di controllo della concorrenza timestamp

Gli algoritmi di controllo della concorrenza basati sul timestamp utilizzano il timestamp di una transazione per coordinare l'accesso simultaneo a un elemento di dati per garantire la serializzabilità. Un timestamp è un identificatore univoco fornito da DBMS a una transazione che rappresenta l'ora di inizio della transazione.

Questi algoritmi assicurano che le transazioni si impegnino nell'ordine dettato dai loro timestamp. Una transazione più vecchia dovrebbe eseguire il commit prima di una transazione più recente, poiché la transazione più vecchia entra nel sistema prima di quella più giovane.

Le tecniche di controllo della concorrenza basate sul timestamp generano pianificazioni serializzabili in modo tale che la pianificazione seriale equivalente sia organizzata in base all'età delle transazioni partecipanti.

Alcuni degli algoritmi di controllo della concorrenza basati su timestamp sono:

  • Algoritmo di ordinamento del timestamp di base.
  • Algoritmo di ordinamento timestamp conservativo.
  • Algoritmo multiversione basato sull'ordinamento del timestamp.

L'ordinamento basato sul timestamp segue tre regole per imporre la serializzabilità:

  • Access Rule- Quando due transazioni tentano di accedere allo stesso elemento di dati contemporaneamente, per operazioni in conflitto, la priorità viene data alla transazione precedente. Ciò fa sì che la transazione più recente attenda prima il commit della transazione più vecchia.

  • Late Transaction Rule- Se una transazione più recente ha scritto un elemento di dati, una transazione più vecchia non è autorizzata a leggere o scrivere quell'elemento di dati. Questa regola impedisce il commit della transazione precedente dopo che è già stato eseguito il commit della transazione più recente.

  • Younger Transaction Rule - Una transazione più recente può leggere o scrivere un elemento dati che è già stato scritto da una transazione precedente.

Algoritmo di controllo della concorrenza ottimistico

Nei sistemi con bassi tassi di conflitto, il compito di convalidare ogni transazione per la serializzabilità può ridurre le prestazioni. In questi casi, il test per la serializzabilità viene posticipato appena prima del commit. Poiché il tasso di conflitto è basso, è bassa anche la probabilità di interrompere le transazioni non serializzabili. Questo approccio è chiamato tecnica di controllo della concorrenza ottimistica.

In questo approccio, il ciclo di vita di una transazione è suddiviso nelle seguenti tre fasi:

  • Execution Phase - Una transazione recupera gli elementi di dati in memoria ed esegue operazioni su di essi.

  • Validation Phase - Una transazione esegue controlli per garantire che il commit delle modifiche al database superi il test di serializzabilità.

  • Commit Phase - Una transazione riscrive su disco l'elemento di dati modificato in memoria.

Questo algoritmo utilizza tre regole per imporre la serializzabilità nella fase di convalida:

Rule 1- Dati due operazioni T i e T j , se T i sta leggendo il dato che T j scrive, allora T i ‘s fase esecutiva può non sovrapposizione con T j ‘s commetto fase. T j può eseguire il commit solo dopo che Ti ha terminato l'esecuzione.

Rule 2- Date due transazioni Ti e T j , se Ti sta scrivendo l'elemento di dati che T j sta leggendo, la fase di commit di T i non può sovrapporsi alla fase di esecuzione di T j . T j può iniziare l'esecuzione solo dopo che Ti ha già eseguito il commit.

Rule 3- Date due transazioni Ti e T j , se Ti sta scrivendo l'elemento di dati che T j sta anche scrivendo, la fase di commit di T i non può sovrapporsi alla fase di commit di T j . T j può iniziare a eseguire il commit solo dopo che Ti ha già eseguito il commit.

Controllo della concorrenza nei sistemi distribuiti

In questa sezione vedremo come le tecniche di cui sopra sono implementate in un sistema di database distribuito.

Algoritmo di bloccaggio a due fasi distribuito

Il principio di base del blocco a due fasi distribuito è lo stesso del protocollo di blocco a due fasi di base. Tuttavia, in un sistema distribuito ci sono siti designati come gestori di blocchi. Un gestore dei blocchi controlla le richieste di acquisizione dei blocchi dai monitor delle transazioni. Al fine di rafforzare il coordinamento tra i gestori dei blocchi in vari siti, almeno un sito ha l'autorità di vedere tutte le transazioni e rilevare i conflitti di blocco.

A seconda del numero di siti in grado di rilevare conflitti di blocco, gli approcci di blocco a due fasi distribuiti possono essere di tre tipi:

  • Centralized two-phase locking- In questo approccio, un sito è designato come gestore della serratura centrale. Tutti i siti nell'ambiente conoscono la posizione del gestore della serratura centrale e ottengono il blocco da esso durante le transazioni.

  • Primary copy two-phase locking- In questo approccio, diversi siti sono designati come centri di controllo delle chiuse. Ciascuno di questi siti ha la responsabilità di gestire un insieme definito di blocchi. Tutti i siti sanno quale centro di controllo della serratura è responsabile della gestione del blocco di quale elemento di tabella / frammento di dati.

  • Distributed two-phase locking- In questo approccio, esistono diversi gestori di serrature, in cui ogni gestore di serrature controlla i blocchi degli elementi di dati archiviati nel proprio sito locale. La posizione del gestore blocchi è basata sulla distribuzione e replica dei dati.

Controllo della concorrenza con timestamp distribuito

In un sistema centralizzato, il timestamp di qualsiasi transazione è determinato dalla lettura dell'orologio fisico. Tuttavia, in un sistema distribuito, le letture dell'orologio fisico / logico locale di qualsiasi sito non possono essere utilizzate come timestamp globali, poiché non sono univoche a livello globale. Quindi, un timestamp comprende una combinazione dell'ID del sito e della lettura dell'orologio di quel sito.

Per l'implementazione degli algoritmi di ordinamento del timestamp, ogni sito ha uno scheduler che mantiene una coda separata per ogni gestore delle transazioni. Durante la transazione, un gestore delle transazioni invia una richiesta di blocco allo scheduler del sito. Lo scheduler inserisce la richiesta nella coda corrispondente in ordine temporale crescente. Le richieste vengono elaborate dalla parte anteriore delle code nell'ordine dei loro timestamp, ovvero dalla più vecchia per prima.

Grafici dei conflitti

Un altro metodo è creare grafici di conflitto. Per questa transazione sono definite classi. Una classe di transazione contiene due set di elementi di dati denominati set di lettura e set di scrittura. Una transazione appartiene a una particolare classe se il set di lettura della transazione è un sottoinsieme del set di lettura della classe e il set di scrittura della transazione è un sottoinsieme del set di scrittura della classe. Nella fase di lettura, ogni transazione emette le sue richieste di lettura per gli elementi di dati nel suo set di lettura. Nella fase di scrittura, ogni transazione emette le sue richieste di scrittura.

Viene creato un grafico dei conflitti per le classi a cui appartengono le transazioni attive. Questo contiene una serie di bordi verticali, orizzontali e diagonali. Un bordo verticale collega due nodi all'interno di una classe e denota conflitti all'interno della classe. Un bordo orizzontale collega due nodi attraverso due classi e denota un conflitto di scrittura-scrittura tra classi diverse. Un bordo diagonale collega due nodi attraverso due classi e denota un conflitto di scrittura-lettura o lettura-scrittura tra due classi.

I grafici di conflitto vengono analizzati per accertare se due transazioni all'interno della stessa classe o tra due classi differenti possono essere eseguite in parallelo.

Algoritmo di controllo della concorrenza ottimistico distribuito

L'algoritmo di controllo della concorrenza ottimistica distribuita estende l'algoritmo di controllo della concorrenza ottimistica. Per questa estensione vengono applicate due regole:

Rule 1- Secondo questa regola, una transazione deve essere convalidata localmente in tutti i siti quando viene eseguita. Se una transazione è ritenuta non valida in qualsiasi sito, viene interrotta. La convalida locale garantisce che la transazione mantenga la serializzabilità nei siti in cui è stata eseguita. Dopo che una transazione supera il test di convalida locale, viene convalidata a livello globale.

Rule 2- Secondo questa regola, dopo che una transazione supera il test di convalida locale, dovrebbe essere convalidata a livello globale. La convalida globale garantisce che se due transazioni in conflitto vengono eseguite insieme in più di un sito, devono eseguire il commit nello stesso ordine relativo in tutti i siti che vengono eseguiti insieme. Ciò potrebbe richiedere che una transazione attenda l'altra transazione in conflitto, dopo la convalida prima del commit. Questo requisito rende l'algoritmo meno ottimista poiché una transazione potrebbe non essere in grado di eseguire il commit non appena viene convalidata in un sito.

Questo capitolo illustra i meccanismi di gestione dei deadlock nei sistemi di database. Studieremo i meccanismi di gestione dei deadlock nel sistema di database centralizzato e distribuito.

Cosa sono i deadlock?

Deadlock è uno stato di un sistema di database con due o più transazioni, quando ogni transazione è in attesa di un elemento di dati bloccato da un'altra transazione. Un deadlock può essere indicato da un ciclo nel grafico di attesa. Questo è un grafo diretto in cui i vertici denotano transazioni e i bordi denotano attese per elementi di dati.

Ad esempio, nel seguente grafico di attesa, la transazione T1 è in attesa dell'elemento dati X che è bloccato da T3. T3 sta aspettando Y che è bloccato da T2 e T2 sta aspettando Z che è bloccato da T1. Quindi, si forma un ciclo di attesa e nessuna delle transazioni può procedere con l'esecuzione.

Gestione dei deadlock nei sistemi centralizzati

Esistono tre approcci classici per la gestione del deadlock, ovvero:

  • Prevenzione del deadlock.
  • Evitamento del deadlock.
  • Rilevamento e rimozione di deadlock.

Tutti e tre gli approcci possono essere incorporati sia in un sistema di database centralizzato che distribuito.

Prevenzione deadlock

L'approccio di prevenzione dei deadlock non consente a nessuna transazione di acquisire blocchi che porteranno a deadlock. La convenzione è che quando più di una transazione richiede il blocco dello stesso elemento di dati, solo a una di esse viene concesso il blocco.

Uno dei metodi di prevenzione dei deadlock più popolari è la pre-acquisizione di tutti i blocchi. In questo metodo, una transazione acquisisce tutti i blocchi prima di iniziare l'esecuzione e mantiene i blocchi per l'intera durata della transazione. Se un'altra transazione necessita di uno qualsiasi dei blocchi già acquisiti, deve attendere fino a quando tutti i blocchi necessari sono disponibili. Utilizzando questo approccio, il sistema non può essere bloccato poiché nessuna delle transazioni in attesa contiene alcun blocco.

Prevenzione della situazione di stallo

L'approccio per evitare i deadlock gestisce i deadlock prima che si verifichino. Analizza le transazioni e i blocchi per determinare se l'attesa porta o meno a un deadlock.

Il metodo può essere brevemente affermato come segue. Le transazioni iniziano a essere eseguite e richiedono elementi di dati che devono essere bloccati. Il gestore della serratura controlla se la serratura è disponibile. Se è disponibile, il gestore del blocco alloca l'elemento dati e la transazione acquisisce il blocco. Tuttavia, se l'elemento è bloccato da qualche altra transazione in modalità incompatibile, il gestore dei blocchi esegue un algoritmo per verificare se mantenere la transazione in stato di attesa provocherà o meno un deadlock. Di conseguenza, l'algoritmo decide se la transazione può attendere o se una delle transazioni deve essere interrotta.

Esistono due algoritmi per questo scopo, vale a dire wait-die e wound-wait. Supponiamo che ci siano due transazioni, T1 e T2, in cui T1 cerca di bloccare un elemento di dati che è già bloccato da T2. Gli algoritmi sono i seguenti:

  • Wait-Die- Se T1 è più vecchio di T2, T1 può attendere. In caso contrario, se T1 è più giovane di T2, T1 viene interrotto e successivamente riavviato.

  • Wound-Wait- Se T1 è più vecchio di T2, T2 viene interrotto e successivamente riavviato. Altrimenti, se T1 è più giovane di T2, T1 può aspettare.

Rilevamento e rimozione di deadlock

L'approccio di rilevamento e rimozione dei deadlock esegue periodicamente un algoritmo di rilevamento dei deadlock e rimuove i deadlock nel caso in cui ve ne sia uno. Non controlla il deadlock quando una transazione invia una richiesta di blocco. Quando una transazione richiede un blocco, il gestore dei blocchi controlla se è disponibile. Se è disponibile, la transazione può bloccare l'elemento di dati; altrimenti la transazione può attendere.

Poiché non ci sono precauzioni durante la concessione delle richieste di blocco, alcune delle transazioni potrebbero essere bloccate. Per rilevare i deadlock, il gestore dei blocchi controlla periodicamente se il wait-forgraph dispone di cicli. Se il sistema è in deadlock, il gestore della serratura sceglie una transazione della vittima da ogni ciclo. La vittima viene interrotta e rotolata indietro; e quindi riavviato in seguito. Alcuni dei metodi utilizzati per la selezione delle vittime sono:

  • Scegli la transazione più giovane.
  • Scegli la transazione con il minor numero di elementi di dati.
  • Scegli la transazione che ha eseguito il minor numero di aggiornamenti.
  • Scegli la transazione con il minor sovraccarico di riavvio.
  • Scegli la transazione che è comune a due o più cicli.

Questo approccio è adatto principalmente per i sistemi con transazioni basse e dove è necessaria una risposta rapida alle richieste di blocco.

Gestione dei deadlock nei sistemi distribuiti

Viene distribuita anche l'elaborazione delle transazioni in un sistema di database distribuito, ovvero la stessa transazione può essere elaborata in più di un sito. I due principali problemi di gestione dei deadlock in un sistema di database distribuito che non sono presenti in un sistema centralizzato sonotransaction location e transaction control. Una volta risolti questi problemi, i deadlock vengono gestiti attraverso la prevenzione dei deadlock, l'evitamento dei deadlock o il rilevamento e la rimozione dei deadlock.

Posizione della transazione

Le transazioni in un sistema di database distribuito vengono elaborate in più siti e utilizzano elementi di dati in più siti. La quantità di elaborazione dei dati non è distribuita uniformemente tra questi siti. Anche il periodo di tempo per l'elaborazione varia. Pertanto la stessa transazione potrebbe essere attiva su alcuni siti e inattiva su altri. Quando due transazioni in conflitto si trovano in un sito, può accadere che una di esse sia inattivo. Questa condizione non si verifica in un sistema centralizzato. Questa preoccupazione è chiamata problema di posizione della transazione.

Questa preoccupazione può essere risolta dal modello Daisy Chain. In questo modello, una transazione trasporta determinati dettagli quando si sposta da un sito a un altro. Alcuni dettagli sono l'elenco delle tabelle richieste, l'elenco dei siti richiesti, l'elenco delle tabelle e dei siti visitati, l'elenco delle tabelle e dei siti ancora da visitare e l'elenco dei blocchi acquisiti con i tipi. Dopo che una transazione termina per commit o interruzione, le informazioni dovrebbero essere inviate a tutti i siti interessati.

Controllo delle transazioni

Il controllo delle transazioni riguarda la designazione e il controllo dei siti richiesti per l'elaborazione di una transazione in un sistema di database distribuito. Ci sono molte opzioni per quanto riguarda la scelta di dove elaborare la transazione e come designare il centro di controllo, come:

  • Un server può essere selezionato come centro di controllo.
  • Il centro di controllo può viaggiare da un server all'altro.
  • La responsabilità del controllo può essere condivisa da più server.

Prevenzione dei deadlock distribuiti

Proprio come nella prevenzione centralizzata dei deadlock, nell'approccio di prevenzione dei deadlock distribuiti, una transazione dovrebbe acquisire tutti i blocchi prima di iniziare l'esecuzione. Ciò impedisce deadlock.

Il sito in cui entra la transazione è designato come sito di controllo. Il sito di controllo invia messaggi ai siti in cui si trovano gli elementi di dati per bloccare gli elementi. Quindi attende la conferma. Quando tutti i siti hanno confermato di aver bloccato gli elementi di dati, la transazione inizia. Se un sito o un collegamento di comunicazione non riesce, la transazione deve attendere fino a quando non sono stati riparati.

Sebbene l'implementazione sia semplice, questo approccio presenta alcuni inconvenienti:

  • La pre-acquisizione dei blocchi richiede molto tempo per i ritardi di comunicazione. Ciò aumenta il tempo necessario per la transazione.

  • In caso di errore del sito o del collegamento, una transazione deve attendere molto tempo affinché i siti vengano ripristinati. Nel frattempo, nei siti in esecuzione, gli elementi sono bloccati. Ciò potrebbe impedire l'esecuzione di altre transazioni.

  • Se il sito di controllo non riesce, non può comunicare con gli altri siti. Questi siti continuano a mantenere gli elementi di dati bloccati nel loro stato bloccato, con conseguente blocco.

Evitamento dei deadlock distribuiti

Come nel sistema centralizzato, l'eliminazione del deadlock distribuito gestisce il deadlock prima che si verifichi. Inoltre, nei sistemi distribuiti, è necessario affrontare i problemi di ubicazione e controllo delle transazioni. A causa della natura distribuita della transazione, potrebbero verificarsi i seguenti conflitti:

  • Conflitto tra due transazioni nello stesso sito.
  • Conflitto tra due transazioni in siti diversi.

In caso di conflitto, una delle transazioni può essere interrotta o lasciata in attesa secondo gli algoritmi distribuiti wait-die o distribuiti ferita-attesa.

Supponiamo che ci siano due transazioni, T1 e T2. T1 arriva al sito P e tenta di bloccare un elemento di dati che è già bloccato da T2 in quel sito. Quindi, c'è un conflitto nel sito P. Gli algoritmi sono i seguenti:

  • Distributed Wound-Die

    • Se T1 è più vecchio di T2, T1 può attendere. T1 può riprendere l'esecuzione dopo che il sito P riceve un messaggio che T2 ha eseguito il commit o interrotto correttamente in tutti i siti.

    • Se T1 è più giovane di T2, T1 viene interrotto. Il controllo della concorrenza nel sito P invia un messaggio a tutti i siti in cui è stato visitato T1 per interrompere T1. Il sito di controllo notifica all'utente quando T1 è stato interrotto correttamente in tutti i siti.

  • Distributed Wait-Wait

    • Se T1 è più vecchio di T2, T2 deve essere interrotto. Se T2 è attivo nel sito P, il sito P interrompe e ripristina T2, quindi trasmette questo messaggio ad altri siti pertinenti. Se T2 ha lasciato il sito P ma è attivo nel sito Q, il sito P trasmette che T2 è stato interrotto; Il sito L quindi interrompe e ripristina T2 e invia questo messaggio a tutti i siti.

    • Se T1 è più giovane di T1, T1 può aspettare. T1 può riprendere l'esecuzione dopo che il sito P riceve un messaggio che T2 ha completato l'elaborazione.

Rilevamento deadlock distribuito

Proprio come l'approccio centralizzato di rilevamento dei deadlock, i deadlock possono verificarsi e vengono rimossi se rilevati. Il sistema non esegue alcun controllo quando una transazione pone una richiesta di blocco. Per l'implementazione, vengono creati grafici di attesa globali. L'esistenza di un ciclo nel grafico di attesa globale indica deadlock. Tuttavia, è difficile individuare i deadlock poiché la transazione attende le risorse attraverso la rete.

In alternativa, gli algoritmi di rilevamento deadlock possono utilizzare timer. Ogni transazione è associata a un timer che è impostato su un periodo di tempo in cui si prevede che una transazione termini. Se una transazione non termina entro questo periodo di tempo, il timer si spegne, indicando un possibile deadlock.

Un altro strumento utilizzato per la gestione dei deadlock è un rilevatore di deadlock. In un sistema centralizzato, è presente un rilevatore di deadlock. In un sistema distribuito, possono essere presenti più rilevatori di deadlock. Un rilevatore di deadlock può trovare deadlock per i siti sotto il suo controllo. Esistono tre alternative per il rilevamento dei deadlock in un sistema distribuito, vale a dire.

  • Centralized Deadlock Detector - Un sito è designato come rilevatore di deadlock centrale.

  • Hierarchical Deadlock Detector - Diversi rilevatori di deadlock sono disposti in gerarchia.

  • Distributed Deadlock Detector - Tutti i siti partecipano alla rilevazione dei deadlock e alla loro rimozione.

Questo capitolo esamina il controllo della replica, necessario per mantenere dati coerenti in tutti i siti. Studieremo le tecniche di controllo della replicazione e gli algoritmi necessari per il controllo della replicazione.

Come discusso prima, replicationè una tecnica utilizzata nei database distribuiti per archiviare più copie di una tabella di dati in siti diversi. Il problema di avere più copie in più siti è il sovraccarico di mantenere la coerenza dei dati, in particolare durante le operazioni di aggiornamento.

Per mantenere dati reciprocamente coerenti in tutti i siti, è necessario adottare tecniche di controllo della replica. Esistono due approcci per il controllo della replica, vale a dire:

  • Controllo della replica sincrona
  • Controllo della replica asincrona

Controllo della replica sincrona

Nell'approccio della replica sincrona, il database viene sincronizzato in modo che tutte le repliche abbiano sempre lo stesso valore. Una transazione che richiede un elemento di dati avrà accesso allo stesso valore in tutti i siti. Per garantire questa uniformità, una transazione che aggiorna un elemento di dati viene espansa in modo che effettui l'aggiornamento in tutte le copie dell'elemento di dati. In genere, allo scopo viene utilizzato il protocollo di commit a due fasi.

Si consideri ad esempio una tabella dati PROJECT (PId, PName, PLocation). Dobbiamo eseguire una transazione T1 che aggiorni PLocation a "Mumbai", se PLocation è "Bombay". Se non ci sono repliche, le operazioni nella transazione T1 saranno:

Begin T1: 
   Update PROJECT Set PLocation = 'Mumbai' 
   Where PLocation = 'Bombay'; 
End T1;

Se la tabella di dati ha due repliche nel sito A e nel sito B, T1 deve generare due figli T1A e T1B corrispondenti ai due siti. La transazione ampliata T1 sarà:

Begin T1: 
   Begin T1A : 
      Update PROJECT Set PLocation = 'Mumbai' 
      Where PLocation = 'Bombay'; 
   End T1A;  
	
   Begin T2A : 
      Update PROJECT Set PLocation = 'Mumbai'
      Where PLocation = 'Bombay'; 
   End T2A; 
	
End T1;

Controllo della replica asincrona

Nell'approccio della replica asincrona, le repliche non mantengono sempre lo stesso valore. Una o più repliche possono memorizzare un valore obsoleto e una transazione può visualizzare i diversi valori. Viene chiamato il processo per portare tutte le repliche al valore correntesynchronization.

Un metodo popolare di sincronizzazione è il metodo store and forward. In questo metodo, un sito è designato come sito primario e gli altri siti sono siti secondari. Il sito principale contiene sempre valori aggiornati. Tutte le transazioni entrano prima nel sito principale. Queste transazioni vengono quindi accodate per l'applicazione nei siti secondari. I siti secondari vengono aggiornati utilizzando il metodo di rollout solo quando è pianificata l'esecuzione di una transazione su di essi.

Algoritmi di controllo della replica

Alcuni degli algoritmi di controllo della replica sono:

  • Algoritmo di controllo della replica master-slave.
  • Algoritmo di voto distribuito.
  • Algoritmo di consenso della maggioranza.
  • Algoritmo del token circolante.

Algoritmo di controllo della replica master-slave

C'è un sito master e siti "N" slave. Un algoritmo principale viene eseguito nel sito principale per rilevare i conflitti. Una copia dell'algoritmo slave viene eseguita su ogni sito slave. L'algoritmo generale viene eseguito nelle due fasi seguenti:

  • Transaction acceptance/rejection phase- Quando una transazione entra nel monitor delle transazioni di un sito slave, il sito slave invia una richiesta al sito master. Il sito master verifica la presenza di conflitti. Se non ci sono conflitti, il master invia un messaggio "ACK +" al sito slave che quindi avvia la fase di applicazione della transazione. In caso contrario, il master invia un messaggio "ACK-" allo slave che poi rifiuta la transazione.

  • Transaction application phase- Entrando in questa fase, il sito slave in cui è entrata la transazione trasmette una richiesta a tutti gli slave per l'esecuzione della transazione. Alla ricezione delle richieste, gli slave peer eseguono la transazione e al completamento inviano un "ACK" allo slave richiedente. Dopo che lo slave richiedente ha ricevuto i messaggi "ACK" da tutti i suoi peer, invia un messaggio "FATTO" al sito master. Il master comprende che la transazione è stata completata e la rimuove dalla coda in sospeso.

Algoritmo di voto distribuito

Si tratta di "N" siti peer, che devono tutti "OK" una transazione prima che inizi l'esecuzione. Di seguito sono riportate le due fasi di questo algoritmo:

  • Distributed transaction acceptance phase- Quando una transazione entra nel gestore delle transazioni di un sito, invia una richiesta di transazione a tutti gli altri siti. Alla ricezione di una richiesta, un sito peer risolve i conflitti utilizzando regole di voto basate sulla priorità. Se tutti i siti peer sono "OK" con la transazione, il sito richiedente avvia la fase di applicazione. Se uno dei siti peer non "OK" una transazione, il sito richiedente rifiuta la transazione.

  • Distributed transaction application phase- Entrando in questa fase, il sito in cui è inserita la transazione, trasmette a tutti gli slave una richiesta per l'esecuzione della transazione. Alla ricezione delle richieste, gli slave peer eseguono la transazione e al completamento inviano un messaggio "ACK" allo slave richiedente. Dopo che lo slave richiedente ha ricevuto i messaggi "ACK" da tutti i suoi peer, comunica al gestore delle transazioni che la transazione è stata completata.

Algoritmo di consenso della maggioranza

Questa è una variazione dell'algoritmo di voto distribuito, in cui una transazione può essere eseguita quando la maggioranza dei peer "OK" una transazione. Questo è diviso in tre fasi:

  • Voting phase- Quando una transazione entra nel gestore delle transazioni di un sito, invia una richiesta di transazione a tutti gli altri siti. Alla ricezione di una richiesta, un sito peer verifica la presenza di conflitti utilizzando le regole di voto e mantiene le transazioni in conflitto, se presenti, in coda in sospeso. Quindi invia un messaggio "OK" o "NON OK".

  • Transaction acceptance/rejection phase- Se il sito richiedente riceve la maggioranza "OK" sulla transazione, accetta la transazione e trasmette "ACCETTO" a tutti i siti. In caso contrario, trasmette "REJECT" a tutti i siti e rifiuta la transazione.

  • Transaction application phase- Quando un sito peer riceve un messaggio "REJECT", rimuove questa transazione dal suo elenco in sospeso e riconsidera tutte le transazioni differite. Quando un sito peer riceve un messaggio "ACCEPT", applica la transazione e rifiuta tutte le transazioni differite nella coda in sospeso che sono in conflitto con questa transazione. Al termine, invia un "ACK" allo slave richiedente.

Algoritmo del token circolante

In questo approccio le transazioni nel sistema vengono serializzate utilizzando un token circolante ed eseguite di conseguenza su ogni replica del database. Pertanto, tutte le transazioni vengono accettate, ovvero nessuna viene rifiutata. Questo ha due fasi:

  • Transaction serialization phase- In questa fase, tutte le transazioni sono pianificate per essere eseguite in un ordine di serializzazione. Ad ogni transazione in ogni sito viene assegnato un ticket univoco da una serie sequenziale, indicante l'ordine di transazione. Una volta che a una transazione è stato assegnato un ticket, viene trasmesso a tutti i siti.

  • Transaction application phase- Quando un sito riceve una transazione insieme al suo ticket, pone la transazione per l'esecuzione in base al suo ticket. Al termine dell'esecuzione della transazione, questo sito trasmette un messaggio appropriato. Una transazione termina quando ha completato l'esecuzione in tutti i siti.

Un sistema di gestione di database è suscettibile a una serie di errori. In questo capitolo studieremo i tipi di errore e i protocolli di commit. In un sistema di database distribuito, i guasti possono essere ampiamente classificati in errori soft, errori hard e guasti di rete.

Soft fallimento

Il soft failure è il tipo di errore che causa la perdita nella memoria volatile del computer e non nella memoria persistente. Qui, le informazioni memorizzate nella memoria non persistente come memoria principale, buffer, cache o registri vengono perse. Sono anche conosciuti come crash di sistema. I vari tipi di guasti soft sono i seguenti:

  • Errore del sistema operativo.
  • Crash della memoria principale.
  • Fallimento della transazione o aborto.
  • Errore generato dal sistema come un intero overflow o un errore di divisione per zero.
  • Fallimento del software di supporto.
  • Mancanza di corrente.

Difficile fallimento

Un errore grave è il tipo di errore che causa la perdita di dati nella memoria persistente o non volatile come il disco. Il guasto del disco può causare il danneggiamento dei dati in alcuni blocchi del disco o il guasto dell'intero disco. Le cause di un grave fallimento sono:

  • Mancanza di corrente.
  • Difetti nei media.
  • Malfunzionamento lettura-scrittura.
  • Danneggiamento delle informazioni sul disco.
  • Arresto anomalo della testina di lettura / scrittura del disco.

Il ripristino da errori del disco può essere breve se è disponibile un disco nuovo, formattato e pronto per l'uso. In caso contrario, la durata include il tempo necessario per ottenere un ordine di acquisto, acquistare il disco e prepararlo.

Errore di rete

Gli errori di rete sono prevalenti nei database distribuiti o di rete. Questi comprendono gli errori indotti nel sistema di database a causa della natura distribuita dei dati e del trasferimento dei dati sulla rete. Le cause dell'errore di rete sono le seguenti:

  • Errore nel collegamento di comunicazione.
  • La congestione della rete.
  • Danneggiamento delle informazioni durante il trasferimento.
  • Errori del sito.
  • Partizionamento di rete.

Protocolli di commit

Qualsiasi sistema di database dovrebbe garantire che le proprietà desiderabili di una transazione vengano mantenute anche dopo gli errori. Se durante l'esecuzione di una transazione si verifica un errore, può accadere che tutte le modifiche apportate dalla transazione non vengano salvate. Ciò rende il database incoerente. I protocolli di commit impediscono questo scenario utilizzando l'annullamento della transazione (rollback) o il ripristino della transazione (roll forward).

Punto di impegno

Il momento in cui viene presa la decisione se eseguire il commit o l'interruzione di una transazione è noto come punto di commit. Di seguito sono riportate le proprietà di un punto di commit.

  • È un momento in cui il database è coerente.

  • A questo punto le modifiche apportate dal database possono essere viste dalle altre transazioni. Tutte le transazioni possono avere una visualizzazione coerente del database.

  • A questo punto, tutte le operazioni di transazione sono state eseguite con successo ed i loro effetti sono stati registrati nel log delle transazioni.

  • A questo punto, una transazione può essere annullata in sicurezza, se necessario.

  • A questo punto, una transazione rilascia tutti i blocchi da essa detenuti.

Annulla transazione

Il processo di annullamento di tutte le modifiche apportate a un database da una transazione è denominato annullamento della transazione o rollback della transazione. Questo viene applicato principalmente in caso di guasto soft.

Ripeti transazione

Il processo di riapplicazione delle modifiche apportate a un database da una transazione è denominato ripristino della transazione o roll forward della transazione. Questo viene applicato principalmente per il ripristino da un errore grave.

Registro delle transazioni

Un registro delle transazioni è un file sequenziale che tiene traccia delle operazioni di transazione sugli elementi del database. Poiché il registro è di natura sequenziale, viene elaborato in sequenza dall'inizio o dalla fine.

Finalità di un registro delle transazioni -

  • Per supportare i protocolli di commit per eseguire il commit o supportare le transazioni.
  • Per aiutare il ripristino del database dopo un errore.

Un registro delle transazioni viene solitamente conservato sul disco, in modo che non sia influenzato da errori soft. Inoltre, il registro viene periodicamente sottoposto a backup su un archivio di archiviazione come un nastro magnetico per proteggerlo anche da guasti del disco.

Elenchi nei registri delle transazioni

Il registro delle transazioni mantiene cinque tipi di elenchi a seconda dello stato della transazione. Questo elenco aiuta il gestore del recupero a verificare lo stato di una transazione. Lo stato e gli elenchi corrispondenti sono i seguenti:

  • Una transazione che ha un record di inizio transazione e un record di commit della transazione, è una transazione confermata - mantenuta nell'elenco di commit.

  • Una transazione che ha un record di inizio transazione e un record di transazione non riuscita ma non un record di interruzione della transazione, è una transazione fallita - mantenuta nell'elenco fallito.

  • Una transazione che ha un record di inizio transazione e un record di interruzione della transazione è una transazione interrotta - mantenuta nell'elenco di interruzione.

  • Una transazione che ha un record di inizio transazione e un record di transazione prima del commit è una transazione prima del commit, cioè una transazione in cui tutte le operazioni sono state eseguite ma non confermate - mantenute nell'elenco prima del commit.

  • Una transazione che ha un record di inizio transazione ma nessun record di before-commit, commit, interruzione o fallimento, è una transazione attiva - mantenuta nell'elenco attivo.

Aggiornamento immediato e aggiornamento differito

L'aggiornamento immediato e l'aggiornamento differito sono due metodi per mantenere i registri delle transazioni.

In immediate updatemode, quando viene eseguita una transazione, gli aggiornamenti effettuati dalla transazione vengono scritti direttamente sul disco. I vecchi valori e i valori degli aggiornamenti vengono scritti nel registro prima di scrivere nel database su disco. Al momento del commit, le modifiche apportate al disco vengono rese permanenti. In caso di rollback, le modifiche apportate dalla transazione nel database vengono eliminate e i vecchi valori vengono ripristinati nel database dai vecchi valori memorizzati nel registro.

In deferred updatemodalità, quando viene eseguita una transazione, gli aggiornamenti effettuati al database dalla transazione vengono registrati nel file di registro. Al momento del commit, le modifiche nel registro vengono scritte sul disco. In caso di rollback, le modifiche nel registro vengono eliminate e nessuna modifica viene applicata al database.

Per recuperare dall'errore del database, i sistemi di gestione del database ricorrono a una serie di tecniche di gestione del ripristino. In questo capitolo studieremo i diversi approcci per il ripristino del database.

Le strategie tipiche per il ripristino del database sono:

  • In caso di errori soft che provocano incoerenza del database, la strategia di ripristino include l'annullamento o il rollback della transazione. Tuttavia, a volte, la ripetizione della transazione può anche essere adottata per ripristinare uno stato coerente della transazione.

  • In caso di malfunzionamenti con conseguenti danni estesi al database, le strategie di ripristino comprendono il ripristino di una copia precedente del database dal backup di archiviazione. Uno stato più attuale del database si ottiene ripetendo le operazioni di cui è stato eseguito il commit dal log delle transazioni.

Ripristino da un'interruzione di corrente

L'interruzione di corrente causa la perdita di informazioni nella memoria non persistente. Quando l'alimentazione viene ripristinata, il sistema operativo e il sistema di gestione del database vengono riavviati. Recovery Manager avvia il ripristino dai log delle transazioni.

In caso di modalità di aggiornamento immediato, Recovery Manager esegue le seguenti azioni:

  • Le transazioni che si trovano nell'elenco attivo e nell'elenco non riuscito vengono annullate e scritte nell'elenco interrotto.

  • Le transazioni che si trovano nell'elenco prima del commit vengono ripristinate.

  • Non viene eseguita alcuna azione per le transazioni negli elenchi di commit o interruzione.

In caso di modalità di aggiornamento differito, Recovery Manager esegue le seguenti azioni:

  • Le transazioni che si trovano nell'elenco attivo e nell'elenco non riuscito vengono scritte nell'elenco interrotto. Non sono necessarie operazioni di annullamento poiché le modifiche non sono state ancora scritte sul disco.

  • Le transazioni che si trovano nell'elenco prima del commit vengono ripristinate.

  • Non viene eseguita alcuna azione per le transazioni negli elenchi di commit o interruzione.

Ripristino dal guasto del disco

Un guasto del disco o un arresto anomalo del disco provoca una perdita totale del database. Per recuperare da questo arresto anomalo, viene preparato un nuovo disco, quindi il sistema operativo viene ripristinato e infine il database viene ripristinato utilizzando il backup del database e il registro delle transazioni. Il metodo di ripristino è lo stesso per le modalità di aggiornamento sia immediato che differito.

Il Recovery Manager esegue le seguenti azioni:

  • Le transazioni nell'elenco di commit e nell'elenco prima del commit vengono ripristinate e scritte nell'elenco di commit nel log delle transazioni.

  • Le transazioni nell'elenco attivo e nell'elenco non riuscito vengono annullate e scritte nell'elenco interrotto nel registro delle transazioni.

Checkpoint

Checkpointè un momento in cui un record viene scritto nel database dai buffer. Di conseguenza, in caso di crash del sistema, il Recovery Manager non deve ripetere le transazioni che sono state salvate prima del checkpoint. Il checkpoint periodico accorcia il processo di ripristino.

I due tipi di tecniche di checkpoint sono:

  • Checkpoint coerente
  • Checkpoint sfocato

Checkpointing coerente

Il checkpoint coerente crea un'immagine coerente del database al checkpoint. Durante il ripristino, vengono annullate o ripristinate solo le transazioni che si trovano sul lato destro dell'ultimo checkpoint. Le transazioni a sinistra dell'ultimo checkpoint coerente sono già state salvate e non devono essere elaborate di nuovo. Le azioni intraprese per il checkpoint sono:

  • Le transazioni attive vengono sospese temporaneamente.
  • Tutte le modifiche nei buffer della memoria principale vengono scritte sul disco.
  • Un record "checkpoint" viene scritto nel registro delle transazioni.
  • Il log delle transazioni viene scritto sul disco.
  • Le transazioni sospese vengono riprese.

Se nel passaggio 4 viene archiviato anche il registro delle transazioni, questo checkpoint aiuta il ripristino da errori del disco e interruzioni di alimentazione, altrimenti aiuta il ripristino solo da interruzioni di corrente.

Checkpoint fuzzy

Nel checkpoint fuzzy, al momento del checkpoint, tutte le transazioni attive vengono scritte nel log. In caso di interruzione di corrente, Recovery Manager elabora solo le transazioni che erano attive durante il checkpoint e in seguito. Le transazioni di cui è stato eseguito il commit prima del checkpoint vengono scritte sul disco e quindi non devono essere ripetute.

Esempio di checkpoint

Si consideri che nel sistema l'ora del checkpoint è tcheck e l'ora del crash del sistema è tfail. Siano quattro transazioni T a , T b , T c e T d tali che -

  • T a si impegna prima del checkpoint.

  • T b inizia prima del checkpoint ed esegue il commit prima del crash del sistema.

  • T c inizia dopo il checkpoint e si impegna prima del crash del sistema.

  • T d inizia dopo il checkpoint ed era attivo al momento del crash del sistema.

La situazione è rappresentata nel diagramma seguente:

Le azioni intraprese dal Recovery Manager sono:

  • Non si fa nulla con T a .
  • La ripetizione della transazione viene eseguita per T b e T c .
  • L'annullamento della transazione viene eseguito per T d .

Recupero della transazione utilizzando UNDO / REDO

Il ripristino delle transazioni viene eseguito per eliminare gli effetti negativi delle transazioni errate piuttosto che per recuperare da un errore. Le transazioni difettose includono tutte le transazioni che hanno modificato il database in uno stato indesiderato e le transazioni che hanno utilizzato valori scritti dalle transazioni difettose.

Il recupero della transazione in questi casi è un processo in due fasi:

  • ANNULLA tutte le transazioni e le transazioni difettose che potrebbero essere influenzate dalle transazioni difettose.

  • RIPETI tutte le transazioni che non sono difettose ma sono state annullate a causa delle transazioni difettose.

I passaggi per l'operazione UNDO sono:

  • Se la transazione difettosa ha eseguito INSERT, il Recovery Manager elimina gli elementi di dati inseriti.

  • Se la transazione difettosa ha eseguito ELIMINA, il gestore recupero inserisce gli elementi di dati eliminati dal registro.

  • Se la transazione difettosa ha eseguito l'AGGIORNAMENTO, il gestore ripristino elimina il valore scrivendo il valore prima dell'aggiornamento dal registro.

I passaggi per l'operazione REDO sono:

  • Se la transazione ha eseguito INSERT, il gestore recupero genera un inserimento dal registro.

  • Se la transazione ha eseguito DELETE, il gestore recupero genera un'eliminazione dal registro.

  • Se la transazione ha eseguito l'AGGIORNAMENTO, il gestore recupero genera un aggiornamento dal registro.

In un sistema di database locale, per eseguire il commit di una transazione, il gestore delle transazioni deve trasmettere solo la decisione di eseguire il commit al gestore del recupero. Tuttavia, in un sistema distribuito, il gestore delle transazioni dovrebbe trasmettere la decisione di impegnarsi a tutti i server nei vari siti in cui viene eseguita la transazione e applicare la decisione in modo uniforme. Quando l'elaborazione è completa in ogni sito, raggiunge lo stato della transazione parzialmente confermata e attende che tutte le altre transazioni raggiungano lo stato parzialmente confermato. Quando riceve il messaggio che tutti i siti sono pronti per il commit, inizia a eseguire il commit. In un sistema distribuito, tutti i siti eseguono il commit o nessuno di essi lo fa.

I diversi protocolli di commit distribuiti sono:

  • Impegno in una fase
  • Commit in due fasi
  • Impegno in tre fasi

Commit distribuito in una fase

Il commit distribuito in una fase è il protocollo di commit più semplice. Si consideri che esiste un sito di controllo e una serie di siti slave in cui viene eseguita la transazione. I passaggi nel commit distribuito sono:

  • Dopo che ogni slave ha completato localmente la propria transazione, invia un messaggio "FATTO" al sito di controllo.

  • Gli slave attendono il messaggio "Commit" o "Abort" dal sito di controllo. Questo tempo di attesa è chiamatowindow of vulnerability.

  • Quando il sito di controllo riceve il messaggio "FATTO" da ogni slave, decide se eseguire il commit o l'interruzione. Questo è chiamato il punto di commit. Quindi, invia questo messaggio a tutti gli schiavi.

  • Alla ricezione di questo messaggio, uno slave esegue il commit o interrompe e quindi invia un messaggio di riconoscimento al sito di controllo.

Commit distribuito in due fasi

Il commit a due fasi distribuito riduce la vulnerabilità dei protocolli di commit a una fase. I passaggi eseguiti nelle due fasi sono i seguenti:

Phase 1: Prepare Phase

  • Dopo che ogni slave ha completato localmente la propria transazione, invia un messaggio "FATTO" al sito di controllo. Quando il sito di controllo ha ricevuto il messaggio "DONE" da tutti gli slave, invia un messaggio "Prepare" agli slave.

  • Gli schiavi votano se vogliono ancora impegnarsi o meno. Se uno slave desidera eseguire il commit, invia un messaggio "Pronto".

  • Uno slave che non desidera eseguire il commit invia un messaggio "Non pronto". Ciò può accadere quando lo slave ha transazioni concorrenti in conflitto o si verifica un timeout.

Phase 2: Commit/Abort Phase

  • Dopo che il sito di controllo ha ricevuto il messaggio "Pronto" da tutti gli slave:

    • Il sito di controllo invia un messaggio "Global Commit" agli slave.

    • Gli slave applicano la transazione e inviano un messaggio "Conferma ACK" al sito di controllo.

    • Quando il sito di controllo riceve il messaggio "Commit ACK" da tutti gli slave, considera la transazione come confermata.

  • Dopo che il sito di controllo ha ricevuto il primo messaggio "Non pronto" da qualsiasi slave -

    • Il sito di controllo invia un messaggio "Global Abort" agli slave.

    • Gli schiavi interrompono la transazione e inviano un messaggio "Abort ACK" al sito di controllo.

    • Quando il sito di controllo riceve il messaggio "Abort ACK" da tutti gli slave, considera la transazione come interrotta.

Commit trifase distribuito

I passaggi nel commit trifase distribuito sono i seguenti:

Phase 1: Prepare Phase

I passaggi sono gli stessi del commit distribuito in due fasi.

Phase 2: Prepare to Commit Phase

  • Il sito di controllo emette un messaggio di trasmissione "Enter Prepared State".
  • I siti schiavi votano "OK" in risposta.

Phase 3: Commit / Abort Phase

I passaggi sono gli stessi del commit a due fasi tranne per il fatto che il messaggio "Conferma ACK" / "Interrompi ACK" non è richiesto.

In questo capitolo esamineremo le minacce che un sistema di database deve affrontare e le misure di controllo. Studieremo anche la crittografia come strumento di sicurezza.

Protezione del database e minacce

La sicurezza dei dati è un aspetto fondamentale di qualsiasi sistema di database. È di particolare importanza nei sistemi distribuiti a causa dell'elevato numero di utenti, dati frammentati e replicati, più siti e controllo distribuito.

Minacce in un database

  • Availability loss - La perdita di disponibilità si riferisce alla non disponibilità di oggetti di database da parte di utenti legittimi.

  • Integrity loss- La perdita di integrità si verifica quando sul database vengono eseguite accidentalmente o intenzionalmente operazioni inaccettabili. Ciò può accadere durante la creazione, l'inserimento, l'aggiornamento o l'eliminazione dei dati. Risulta in dati danneggiati che portano a decisioni errate.

  • Confidentiality loss- La perdita di riservatezza si verifica a causa della divulgazione non autorizzata o non intenzionale di informazioni riservate. Può provocare azioni illegali, minacce alla sicurezza e perdita della fiducia del pubblico.

Misure di controllo

Le misure di controllo possono essere sostanzialmente suddivise nelle seguenti categorie:

  • Access Control- Il controllo degli accessi include meccanismi di sicurezza in un sistema di gestione del database per proteggere dall'accesso non autorizzato. Un utente può accedere al database dopo aver cancellato il processo di accesso solo tramite account utente validi. Ogni account utente è protetto da password.

  • Flow Control- I sistemi distribuiti comprendono molti flussi di dati da un sito all'altro e anche all'interno di un sito. Il controllo del flusso impedisce il trasferimento dei dati in modo tale che possano essere acceduti da agenti non autorizzati. Una politica di flusso elenca i canali attraverso i quali le informazioni possono fluire. Definisce inoltre le classi di sicurezza per i dati e le transazioni.

  • Data Encryption- La crittografia dei dati si riferisce alla codifica dei dati quando i dati sensibili devono essere comunicati su canali pubblici. Anche se un agente non autorizzato ottiene l'accesso ai dati, non può comprenderli poiché sono in un formato incomprensibile.

Cos'è la crittografia?

Cryptography è la scienza della codifica delle informazioni prima dell'invio tramite percorsi di comunicazione inaffidabili in modo che solo un destinatario autorizzato possa decodificarle e utilizzarle.

Il messaggio in codice viene chiamato cipher text e viene chiamato il messaggio originale plain text. Il processo di conversione del testo normale in testo cifrato da parte del mittente è chiamato codifica oencryption. Il processo di conversione del testo cifrato in testo normale da parte del destinatario è chiamato decodifica odecryption.

L'intera procedura di comunicazione tramite crittografia può essere illustrata attraverso il diagramma seguente:

Metodi di crittografia convenzionali

Nella crittografia convenzionale, la crittografia e la decrittografia vengono eseguite utilizzando la stessa chiave segreta. Qui, il mittente crittografa il messaggio con un algoritmo di crittografia utilizzando una copia della chiave segreta. Il messaggio crittografato viene quindi inviato tramite canali di comunicazione pubblici. Alla ricezione del messaggio crittografato, il destinatario lo decrittografa con un algoritmo di decrittografia corrispondente utilizzando la stessa chiave segreta.

La sicurezza nella crittografia convenzionale dipende da due fattori:

  • Un algoritmo sonoro noto a tutti.

  • Una chiave segreta generata in modo casuale, preferibilmente lunga, conosciuta solo dal mittente e dal destinatario.

L'algoritmo di crittografia convenzionale più famoso è Data Encryption Standard o DES.

Il vantaggio di questo metodo è la sua facile applicabilità. Tuttavia, il problema più grande della crittografia convenzionale è condividere la chiave segreta tra le parti in comunicazione. I modi per inviare la chiave sono macchinosi e altamente suscettibili alle intercettazioni.

Crittografia a chiave pubblica

A differenza della crittografia convenzionale, la crittografia a chiave pubblica utilizza due chiavi diverse, denominate chiave pubblica e chiave privata. Ogni utente genera la coppia di chiave pubblica e chiave privata. L'utente mette quindi la chiave pubblica in un luogo accessibile. Quando un mittente desidera inviare un messaggio, lo crittografa utilizzando la chiave pubblica del destinatario. Alla ricezione del messaggio crittografato, il destinatario lo decrittografa utilizzando la sua chiave privata. Poiché la chiave privata non è nota a nessuno tranne che al destinatario, nessun'altra persona che riceve il messaggio può decrittografarla.

Gli algoritmi di crittografia a chiave pubblica più popolari sono RSA algoritmo e Diffie– Hellmanalgoritmo. Questo metodo è molto sicuro per inviare messaggi privati. Tuttavia, il problema è che comporta molti calcoli e quindi si rivela inefficiente per messaggi lunghi.

La soluzione è utilizzare una combinazione di crittografia a chiave pubblica e convenzionale. La chiave segreta viene crittografata utilizzando la crittografia a chiave pubblica prima della condivisione tra le parti in comunicazione. Quindi, il messaggio viene inviato utilizzando la crittografia convenzionale con l'aiuto della chiave segreta condivisa.

Firme digitali

Una firma digitale (DS) è una tecnica di autenticazione basata sulla crittografia a chiave pubblica utilizzata nelle applicazioni di e-commerce. Associa un segno unico a un individuo all'interno del corpo del suo messaggio. Ciò aiuta gli altri ad autenticare mittenti di messaggi validi.

In genere, la firma digitale di un utente varia da messaggio a messaggio per fornire protezione contro la contraffazione. Il metodo è il seguente:

  • Il mittente prende un messaggio, calcola il digest del messaggio del messaggio e lo firma con una chiave privata.

  • Il mittente aggiunge quindi il digest firmato insieme al messaggio di testo normale.

  • Il messaggio viene inviato tramite il canale di comunicazione.

  • Il destinatario rimuove il digest firmato aggiunto e verifica il digest utilizzando la chiave pubblica corrispondente.

  • Il destinatario quindi prende il messaggio di testo normale e lo esegue attraverso lo stesso algoritmo di digest del messaggio.

  • Se i risultati del passaggio 4 e del passaggio 5 corrispondono, il destinatario sa che il messaggio è integro e autentico.

Un sistema distribuito necessita di misure di sicurezza aggiuntive rispetto al sistema centralizzato, poiché ci sono molti utenti, dati diversificati, più siti e controllo distribuito. In questo capitolo esamineremo i vari aspetti della sicurezza del database distribuito.

Nei sistemi di comunicazione distribuita, ci sono due tipi di intrusi:

  • Passive eavesdroppers - Monitorano i messaggi e acquisiscono informazioni private.

  • Active attackers - Non solo monitorano i messaggi ma danneggiano anche i dati inserendo nuovi dati o modificando i dati esistenti.

Le misure di sicurezza comprendono la sicurezza nelle comunicazioni, la sicurezza nei dati e il controllo dei dati.

Sicurezza delle comunicazioni

In un database distribuito, avviene una grande quantità di comunicazioni di dati a causa della posizione diversificata di dati, utenti e transazioni. Quindi, richiede una comunicazione sicura tra utenti e database e tra i diversi ambienti di database.

La sicurezza nella comunicazione comprende quanto segue:

  • I dati non dovrebbero essere danneggiati durante il trasferimento.

  • Il canale di comunicazione dovrebbe essere protetto sia da intercettatori passivi che da aggressori attivi.

  • Al fine di soddisfare i requisiti sopra indicati, è necessario adottare algoritmi e protocolli di sicurezza ben definiti.

Due tecnologie popolari e coerenti per ottenere comunicazioni sicure end-to-end sono:

  • Secure Socket Layer Protocol o Transport Layer Security Protocol.
  • Reti private virtuali (VPN).

La sicurezza dei dati

Nei sistemi distribuiti, è imperativo adottare misure per proteggere i dati oltre alle comunicazioni. Le misure di sicurezza dei dati sono:

  • Authentication and authorization- Queste sono le misure di controllo degli accessi adottate per garantire che solo gli utenti autentici possano utilizzare il database. Per fornire l'autenticazione vengono utilizzati certificati digitali. Inoltre, l'accesso è limitato tramite la combinazione nome utente / password.

  • Data encryption - I due approcci per la crittografia dei dati nei sistemi distribuiti sono:

    • Approccio al database da interno a distribuito: le applicazioni utente crittografano i dati e quindi memorizzano i dati crittografati nel database. Per utilizzare i dati memorizzati, le applicazioni recuperano i dati crittografati dal database e quindi li decrittano.

    • Esterno al database distribuito: il sistema di database distribuito ha le proprie capacità di crittografia. Le applicazioni utente memorizzano i dati e li recuperano senza rendersi conto che i dati sono archiviati in forma crittografata nel database.

  • Validated input- In questa misura di sicurezza, l'applicazione utente verifica ogni input prima che possa essere utilizzato per l'aggiornamento del database. Un input non convalidato può causare un'ampia gamma di exploit come il sovraccarico del buffer, l'iniezione di comandi, lo scripting intersito e il danneggiamento dei dati.

Controllo dei dati

Un sistema di sicurezza del database deve rilevare e monitorare le violazioni della sicurezza, al fine di accertare le misure di sicurezza che dovrebbe adottare. Spesso è molto difficile rilevare una violazione della sicurezza nel momento in cui si verificano. Un metodo per identificare le violazioni della sicurezza consiste nell'esaminare i log di controllo. I registri di controllo contengono informazioni come:

  • Data, ora e luogo dei tentativi di accesso non riusciti.
  • Dettagli dei tentativi di accesso riusciti.
  • Modifiche vitali nel sistema di database.
  • Accesso a enormi quantità di dati, in particolare da database in più siti.

Tutte le informazioni di cui sopra forniscono una panoramica delle attività nel database. Un'analisi periodica del registro aiuta a identificare qualsiasi attività innaturale insieme al suo sito e al momento in cui si è verificata. Questo registro è idealmente archiviato in un server separato in modo che sia inaccessibile agli aggressori.

ja/tutorial
es/tutorial
de/tutorial
fr/tutorial
th/tutorial
pt/tutorial
ru/tutorial
vi/tutorial
it/tutorial
ko/tutorial
tr/tutorial
id/tutorial
pl/tutorial
hi/tutorial
japost
espost
depost
frpost
thpost
ptpost
rupost
vipost
itpost
kopost
trpost
idpost
plpost
hipost

© Copyright 2021 - 2024 | All Rights Reserved