51
Módulo I: Processamento de Transações (Aulas 1 e 2) Clodis Boscarioli

Transacoes Aula1 [Modo de Compatibilidade]clodis/BDII/BDII_Modulo_1.pdf · Sistemas de reserva de passagens aéreas; ... Sistemas de venda para WEB. ... caso de uma falha, nenhuma

Embed Size (px)

Citation preview

Módulo I: Processamentode Transações

(Aulas 1 e 2)

Clodis Boscarioli

Agenda:

� Introdução:

� Apresentação da disciplina;

� Leitura do Plano de Ensino;

� Conceito de transação;� Conceito de transação;

� Estados de uma transação;

� Teoria de Serialização:

� Serialização de conflito;

� Serialização de visão.

Visão Geral de um SGBD

SGBD

Usuários

Interface comaplicações

Programas deaplicações

Consultas(queries)

Esquema de Banco de Dados

Usuáriosnavegantes

Programadoresde aplicações

Usuáriossofisticados

Administra-dores de BD

Processadorde consultas

InterpretadorDDL

CompiladorDML

Pré-compiladorde comandosDML

Programas deaplicações em código objeto

Componentes de execuçãode consultas

Dicionáriode dados

Gerenciadorde memória

Gerenciadorde transações

Gerenciador de buffer

Gerenciadorde arquivos

Armazenamentoem disco Índices

Arquivos dedados

Dados estatísticos BD

Justificativa� Um dos critérios de classificação para SGBDs é em relação ao

número de usuários que podem usá-los ao mesmo tempo:

� Monousuário: apenas um usuário pode utilizar o sistema em um momento;

� Sistemas de BD que são projetados para uso em um micro-computador;� Multiusuário: vários usuários podem utilizar o sistema em um momento.

� Sistemas de reserva de passagens aéreas;� Sistemas bancários/financeiros;

Sistemas de venda para WEB.� Sistemas de venda para WEB.

� Neste contexto, insere-se o conceito de multiprogramação. É permitida a existência de SGBDs multiusuários porque possibilita-se a execução de vários programas ao “mesmo tempo”.

� Na realidade, se existe apenas uma CPU, então parte dos programas são intercalados na execução e, a cada “unidade de tempo”, um programa apenas é executado;

� Comandos de um programa são executados e então o programa é suspenso para que comandos de um outro programa sejam executados.

CPU1

CPU2Uma únicaCPU

A A

B B

C

D

tempo

CPU1

t1 tn t1 tn

Em SGBDs os dados do BD são os recursos primários que podem ser lidos/recuperados e modificados.

A execução de um programa de acesso e/ou modificação ao conteúdo do BD échamado de transação.

Transações� Um conjunto de várias operação em um BD pode ser visto pelo usuário

como uma única unidade.

� Exemplo:� A transferência de fundos de uma conta corrente pra uma conta poupança é

uma operação única do ponto de vista do cliente, porém, dentro do sistemas de banco de dados, ela envolve várias operações.

� É essencial que todo o conjunto de operações seja concluído, ou que, no caso de uma falha, nenhuma delas ocorra.caso de uma falha, nenhuma delas ocorra.

� Essas operações, que formam uma única unidade lógica de trabalho são chamadas de transações.

� Um SGBD precisa:� Garantir que a execução da transação seja completa;� Administrar a execução simultânea de várias transações evitando

inconsistências;� Uma transação que calcula o total de dinheiro do cliente poderia trabalhar com o saldo

da conta corrente antes do débito feito pela transação de transferência e, também, verificar o saldo da poupança depois do crédito. Com isso, obteria um resultado incorreto.

Operações de Leitura/Escrita

� As operações de acesso ao BD que uma transação pode fazer são:

� read(x): que transfere o item de dados x do BD para um buffer local alocado à transação que executou a operação de read. O valor de x é colocado dentro de uma variável de programa.valor de x é colocado dentro de uma variável de programa.

� write(x): que transfere o item de dados x do buffer local da transação que executou o write de volta para o BD. O valor da variável de programa é passado para o item de dado no BD.

OBS.: para fins de simplificação, o item de dados e a variável de programa correspondente serão representados da mesma forma, x.

Execução das Operações

� Executar read(x):

� Encontrar o endereço do bloco de disco que contém x;� Copiar este bloco de disco para dentro do buffer/memória principal, se

ele já não estiver lá;� Copiar o item x do buffer para a variável de programa.

� Executar write(x):

� Encontrar o endereço do bloco de disco que contém x;� Copiar o bloco de disco para a memória principal se ele já não estiver

lá;� Copiar o item x da variável de programa x para a localização correta no

buffer;� Copiar o bloco alterado do buffer de volta para o disco (imediatamente

ou mais tarde).

Exemplo de Transação

A) read(x);x := x – N;write(x);

B) read(x);x := x + M;write(x);write(x);

read(y);y := y + N;write(y);

write(x);

T1 T2

Acesso concorrente ao dado x.

Seja T1 uma transação que transfere 50 reais da conta A para a conta B. Essa transação pode ser definida como:

T1: read(A);A := A - 50;

Outro Exemplo

A := A - 50;write(A);read(B);B := B + 50;write(B);

Propriedades das Transações (ACID)

� A – Atomicidade: ou todas as operações da transação são refletidas corretamente no banco de dados ou nenhuma o será.

� Suponha que, durante a execução da transação Ti, uma falha aconteça impedindo Ti de se completar com sucesso (uma queda de energia). Suponha ainda que a falha tenha ocorrido depois da execução da operação write(A), mas antes da operação write(B). O que acontece?

� O estado do sistema não reflete mais um estado real do mundo que sesupõe representado no BD. É um estado inconsistente.

� Estes estados não podem ser perceptíveis. Ou seja, estadosinconsistente só são permitidos no momento de execução datransação, onde o usuário não terá qualquer tipo de acesso aos dados.

� Assegurar a atomicidade de uma transação é responsabilidade do SGBD, mais especificamente, do Componente de Gerenciamento de Transações e Recuperador de Falhas.

Propriedades das transações (ACID)

� C - Consistência: a execução de uma transação isolada (ou seja, sem a execução concorrente de outra transação) preserva a consistência do banco de dados.

� A exigência da consistência aqui significa que a soma � A exigência da consistência aqui significa que a soma de A com B deve permanecer inalterada após a execução da transação.

� Se o banco de dados está consistente antes de umaexecução de transação, o banco de dadospermanece consistente após a execução datransação.

� Responsabilidade do programador.

Propriedades das transações (ACID)

� I – Isolamento: embora diversas transações possam ser executadas de forma concorrente, o sistema garante que, para todo par de transações Ti e Tj, Ti tem a sensação de que Tj terminou sua execução antes de Ti começar, ou vice-versa. Cada transação não toma conhecimento de outras transações concorrentes a ela no sistema.

� A execução concorrente de várias transações implica no intercalamentode suas operações. Se este intercalamento é feito de forma

� A execução concorrente de várias transações implica no intercalamentode suas operações. Se este intercalamento é feito de formainconveniente, inconsistências serão geradas.

� No exemplo dado, se uma transação concorrente ler o valor de A antes dele ser escrito mais depois do processamento A-50 ter sido feito, ela estará lendo um valor inconsistente.

� Execuções em série resolvem este problema mas a concorrência é benéfica por causa do tempo de execução (melhora do desempenho).

� Assegurar o isolamento é de responsabilidade do Controlador de Concorrência.

Propriedades das transações (ACID)

� D – Durabilidade: depois da transaçãocompletar-se com sucesso, as mudanças queela faz no banco de dados persistem, atémesmo se houver falhas no sistema.

� No exemplo dado, se a transação se completar com � No exemplo dado, se a transação se completar com sucesso e o usuário que a disparou for notificado da transferência de fundos, isso significa que não houve nenhuma falha de sistema que tenha resultado em perda de dados relativa a essa transferência.

� Assegurar a durabilidade é responsabilidade do componente do SGBD chamado de Recuperador de Falhas.

Operações Adicionais

� Uma transação é uma unidade de trabalho atômica que é completada em sua totalidade ou nada dela deve ter efeito. Para tornar isso possível, as seguintes operações são necessárias:

� Begin-transaction: Denota o início da execução da transação;

� End-transaction: Especifica que as operações da transação terminaram e marca o limite final da execução da transação. Neste ponto é necessário verificar se o COMMIT ou o ABORT são necessários, caso e marca o limite final da execução da transação. Neste ponto é necessário verificar se o COMMIT ou o ABORT são necessários, caso já não tenham sido explicitados;

� Commit-transaction: Sinal de término com sucesso e que as alterações podem ser “permanentemente” gravadas no BD;

� Rollback (abort-transaction): Assinala que a transação não terminou com sucesso e que seus efeitos devem ser desfeitos;

� Undo: Desfaz uma operação;

� Redo: Refaz uma operação.

Procedure Transfer;begin

start; (begin transaction) input (FROMaccount, TOaccount, amount); temp := read(Accounts[FROMaccount]);if temp < amount then

beginoutput(“insufficient funds”);

Exemplo com Operadores (1)

output(“insufficient funds”);Abort;

endelsebegin

write(Accounts[FROMaccount],temp - amount);temp = read(Accounts[TOaccount]);write(Accounts[TOaccount], temp + amount);commit;output(“transfer complete”);

end;return; (end transaction)

end.

begin transaction

update TABELA1 set CAMPO1 = ‘NOVO VALOR’where CAMPO2 = 35if @@ERROR <> 0rollback elsecommit

Exemplo com Operadores (2)

commit

end transaction

Suponha uma tabela que possua 6000 tuplas que satisfaçam a condição e quena tupla 4666 houve uma falha no sistema. Neste caso, a variável chamada@@ERROR guardará o código do erro, o comando ROLLBACK será executadoe as 4666 tuplas já atualizadas serão automaticamente voltadas a seu estadoanterior.

Ao contrário, se tudo correr bem, o comando COMMIT será executado e todasas 6000 tuplas serão atualizadas com êxito.

Estados de uma Transação

AtivaEm efetivação

parcial Efetivada

BeginTransaction

EndTransaction

Read/Write

Em falha

Completa

Com sucessoou com falha.

AbortAbort

Diagrama de transição de estadospara a execução da transação.

Considerações� Uma transação entra no estado de falha quando o

sistema determina que ela já não pode prosseguir sua execução normal. Essa transação deve ser desfeita e entra no estado de abortada. Nesse momento o sistema tem duas opções:

Reiniciar a transação: somente se ela foi abortada como� Reiniciar a transação: somente se ela foi abortada comoresultado de algum erro de hardware ou de software não criadopela lógica interna da transação. Uma transação reiniciada éconsiderada uma transação nova.

� Matar a transação: normalmente, isto é feito em decorrência dealgum erro lógico interno e só pode ser corrigido refazendo oprograma de aplicação. Esse erro dá-se ou porque a entrada dedados não era adequada ou porque os dados desejados nãoforam encontrados no banco de dados.

Considerações

� Escritas externas observáveis (escrever em um terminal ou em uma impressora):

� Uma escrita desse tipo não pode ser apagada já que � Uma escrita desse tipo não pode ser apagada já que é vista externamente ao sistema de banco de dados.

� Geralmente somente são permitidas após a transação ser efetivada.

Execução Concorrente

� Permitir que múltiplas transações concorram na atualização de dados traz diversas complicações em relação à consistência desses dados.

� Razões para permitir a concorrência:

� Uma transação consiste em diversos passos. Alguns envolvem atividadesde I/O, outros atividades de CPU. A CPU e os discos podem operar emparalelo. Logo, a atividade de I/O pode ser feita em paralelo com oparalelo. Logo, a atividade de I/O pode ser feita em paralelo com oprocessamento na CPU, por meio das execuções paralelas das transações.Enquanto uma leitura ou escrita solicitada por uma transação está emdesenvolvimento em um disco, outra transação pode ser processada naCPU, e outro disco pode estar executando uma leitura ou escrita solicitadapor uma terceira transação. Assim aumenta-se o rendimento do sistema, ouseja, o número de transações que podem ser executadas em umdeterminado tempo.

� Pode haver uma mistura de transações em execução simultânea nosistema, algumas curtas e outras longas. Se a execução das transações forseqüencial, uma transação curta pode ser obrigada a esperar até que umatransação longa precedente se complete. Com a concorrência reduz-se otempo médio de resposta, ou seja, o tempo médio para uma transação serconcluída após sua submissão.

Execução Concorrente

� Sejam T1 e T2 duas transações que transferem fundos de uma conta para outra.

� A transação T1 transfere 50 dólares da conta A para a conta B.

1para a conta B.

� A transação T2 transfere 10 por cento do saldo da conta A para a conta B.

Execução Concorrente

T1:

read(A);A := A – 50;

T2:

read(A);temp := A * 0,1;A := A – 50;

write(A);read(B);B := B + 50;write(B);

temp := A * 0,1;A := A – temp;write(A);read(B);B := B + temp;write(B);

Execução Seqüencial

T1 T2 T1 T2

read(A);A := A – 50;write(A);read(B);

read(A);temp := A * 0,1;A := A – temp;write(A);

Escalas de execução em seqüência: Observe que o estado do BD é sempre consistente.

read(B);B := B + 50;write(B);

read(A);temp := A * 0,1;A := A – temp;write(A);read(B);B := B + temp;write(B);

read(A);A := A – 50;write(A);read(B);B := B + 50;write(B);

write(A);read(B);B := B + temp;write(B);

Execução Concorrente

T1 T2

read(A);A := A – 50;write(A);

Correta

T1 T2

read(A);A := A – 50;

Incorreta

read(B);B := B + temp;write(B);

read(B);B := B + 50;write(B);

read(A);temp := A * 0,1;A := A – temp;write(A);

write(A);read(B);B := B + 50;write(B);

read(A);temp := A * 0,1;A := A – temp;write(A);

read(B);B := B + temp;write(B);

Problemas na Concorrência

� Problema de alterações perdidas;

� Problema de alteração temporária;

� Problema do resumo incorreto.

Problema de Alterações Perdidas

� Ocorre quando duas transações que acessam o mesmo item de BD possuem suas operações intercaladas de uma maneira que o valor de algum item de dado fique incorreto.

T TT1 T2

read(x);x := x - N;

write(x);read(y);

y := y + N;write(y)

read(x) x := x + M;

write(x)

Problema de Alteração Temporária

� Ocorre quando uma transação altera um item de dados e depois ela falha por alguma razão. O item de dado é acessado por outra transação antes que o valor original seja estabelecido.

T1 T2

read(x);x := x - N;write(x);

read(y);

read(x) x := x + M;write(x)

falha

Problema de Resumo Incorreto� Se uma transação está calculando uma função agregada com um

conjunto de tuplas e outras transações estão alterando algumasdestas tuplas, a função agregada pode calcular alguns valoresantes deles serem alterados e outros depois de serem alterados.

T1 T3

sum := 0;

read(x);x := x - N;write(x);

read(x) sum := sum + x;read(y);sum := sum + y;

sum := 0;read(a);sum : sum + a;

read(y);y := y + N;write(y)

Serialização (Seriação)

� O sistema de banco de dados deve controlar a execução concorrente de transações para assegurar que o estado do BD permaneça consistente.

� A consistência do banco de dados, sob execução concorrente, pode ser assegurada por meio da garantia de que qualquer escala executada tenha o mesmo efeito de outra que tivesse sido executada sem qualquer concorrência.executada sem qualquer concorrência.

� Isto é, uma escala de execução deve, de alguma forma, ser equivalente a uma escala seqüencial.

� Formas de equivalência entre escalas de execução podem ser verificadas sob dois prismas:� Por conflito; � Por visão.

Serialização de Conflito

� Considere uma escala de execução S com duas intruções sucessivas, Ii e Ij, das transações Ti e Tj (i <> j), respectivamente.

� Se Ii e Ij referem-se a itens de dados diferentes, � Se Ii e Ij referem-se a itens de dados diferentes, então é permitido alternar Ii e Ij sem afetar os resultados de qualquer instrução da escala.

� Se Ii e Ij referem-se ao mesmo item de dado Q, então a ordem dos dois passos pode importar.

Serialização de Conflito

1. Ii = read(Q) e Ij = read(Q)

A seqüência de execução de Ii e Ij não importa, já que o mesmo valor de Qé lido por Ti e Tj, independentemente da ordem destas operações.

2. Ii = read(Q) e Ij = write(Q) 2. Ii = read(Q) e Ij = write(Q)

Se Ii vier antes de Ij, então Ti não lê o valor de Q que é escrito por Tj na instrução Ij.

Se Ij vier antes de Ii, então Ti lê o valor de Q que é escrito por Tj.

Assim, a ordem de Ii e Ij importa.

Serialização de Conflito3. Ii = write(Q) e Ij = read(Q)

A ordem de Ii e Ij importa por razões semelhantes às do caso anterior.

4. Ii = write(Q) e Ij = write(Q)

Como ambas as instruções são operações de escrita, a ordem Como ambas as instruções são operações de escrita, a ordem dessas instruções não afeta Ti ou Tj.

Entretanto, o valor obtido pela próxima instrução read(Q) em S é afetado, já que somente o resultado da última das duas instruções write(Q) é preservado no banco de dados.

Se não houver nenhuma outra instrução de write(Q) depois de Iie Ij em S, então a ordem de Ii e Ij afeta diretamente o valor final de Q no que se refere ao estado do banco de dados após a execução da escala S.

Serialização de Conflito

� Diz-se que duas instruções entram em conflito se elas são operações pertencentes a transações diferentes, agindo no mesmo item de dado, e pelo menos uma dessas instruções é uma operação de escrita.

T TT1 T2

read(A) write(A)

read(A) write(A)

read(B) write(B)

read(B) write(B)

A instrução write(A) de T1 entra em conflito com a instrução read(A) de T2.

Porém, a instrução write(A) e T2 não está em conflito com a instrução read(B) de T1.

Serialização de Conflito

� Seja Ii e Ij instruções consecutivas de uma escala de execução S.

� Se Ii e Ij são instruções de transações diferentes e não entram em conflito, então podemos trocar a ordem de I e I para produzir uma nova escala a ordem de Ii e Ij para produzir uma nova escala de execução S’.

� Diz-se que S e S’ são equivalentes já que todas as instruções aparecem na mesma ordem em ambas as escalas de execução com exceção de Ii e Ij, cuja ordem não importa.

Serialização de Conflito

� Ainda segundo a escala S, a instrução write(A) de T2não entra em conflito com a instrução read(B) de T1. Então, é permitido mudar a ordem dessas instruções para gerar uma escala de execução equivalente.

T1 T2

read(A) write(A)

read(A)

write(A) read(B)

write(B)

read(B) write(B)

Em relação a um mesmo estado inicial do sistema, ambas as escalas (S e esta) produzem o mesmo estado final no sistema.

Serialização de Conflito

� Se as seguintes trocas de instruções não-conflitantes forem feitas:

� read(B) de T1 por read(A) de T2;� write(B) de T1 por write(A) de T2;� write(B) de T1 por read(A) de T2.1 2

... uma escala com execuções seriais será obtida.

� Assim mostrou-se que a escala S é equivalente, por conflito, a uma escala seqüencial.

� Essa equivalência garante que para um mesmo estado inicial do sistema, a escala S produzirá o mesmo estado final produzido por essa escala seqüencial.

Serialização de Conflito

� Se uma escala de execução S puder ser transformada em outra, S’, por uma série de trocas de instruções não-conflitantes, dizemos que S e S’ são equivalentes por conflito.

� O conceito de equivalência por conflito leva ao conceito de serialização por conflito.

� Uma escala de execução S é serializável por conflito se ela é equivalente por conflito a uma escala de execução seqüencial.

Serialização de Conflito

� A escala abaixo não é serializável por conflito pois não é equivalente em conflito nem à escala seqüencial <T3,T4> nem <T4,T3>.

T3 T4

read(A)

write(A)

write(A)

Serialização de Conflito

� A escala abaixo não é serializável por conflito, mas produz o mesmo resultado que uma escala seqüencial. Confira.

T1 T2

read(A);A := A – 50;write(A);write(A);

read(A);A := A + 10;write(A);

read(B);B := B + 50;write(B);

read(B);B := B – 10;write(B);

Teste de Serialização de Conflito

� Seja S uma escala. Para saber se ela é serializável em relação às operações conflitantes é necessário criar um grafo de precedência para S.

� G = (V,E) em que V é um conjunto de vértices e E é um conjunto de arestas. conjunto de arestas.

� O conjunto de vértices é composto por todas as transações que participam da escala.

� O conjunto de arestas consiste em todas as arestas Ti � Tj para as quais uma das seguintes condições é verdadeira:

� Ti executa write(Q) antes de Tj executar read(Q);� Ti executa read(Q) antes de Tj executar write(Q);� Ti executa write(Q) antes de Tj executar write(Q);

Teste de Serialização de Conflito

� Se existir uma aresta Ti � Tj no grafo de precedência, então, em qualquer escala seqüencial S’ equivalente a S, Ti deve aparecer antes de Tj.

� Exemplo:

T1 T2T1 T2

read(A);A := A – 50;write(A);read(B);B := B + 50;write(B);

read(A);temp := A * 0,1;A := A – temp;write(A);read(B);B := B + temp;write(B);

T1 T2

Teste de Serialização de Conflito

� Exemplo:

T1 T2

read(A) A := A - 50

T1 T2

read(A) temp := A * 0,1A := A – tempwrite(A) read(B)

write(A) read(B) B := B + 50write(B)

B := B + temp;write(B)

Ciclo no grafo: Se o grafo de precedência possui ciclo, então a escala S não é serializável por conflito.

A ordem de serialização pode ser obtida por meio da classificação topológica, que estabelece uma ordem linear para a escala consistente com a ordem parcial do grafo de precedência.

Serialização de Visão

� Trata-se de uma forma de equivalência menos restritiva que a equivalência de conflito.

� Considere duas escalas de execução S e S’, com o mesmo conjunto de transações participando de ambas. As escalas S e S’ são ditas equivalentes por visão se as três condições seguintes forem satisfeitas:forem satisfeitas:

� Para cada item de dado Q, se a transação Ti fizer uma leitura no valor inicial de Q na escala S, então a transação Ti também deve, na escala S’, ler o valor inicial de Q;

� Para cada item de dado Q, se a transação Ti executar um read(Q) na escala S, e aquele valor foi produzido por meio da transação Tj (se houver), então a transação Ti também deverá, na escala S’, ler o valor de Q que foi produzido por meio da transação Tj;

� Para cada item de dado Q, a transação (se houver) que executa a operação final de write(Q) na escala S tem de executar a operação de write(Q) final na escala S’;

Serialização de Visão

T1 T2

read(A);A := A – 50;write(A);read(B);B := B + 50;

T1 T2

read(A);temp := A * 0,1;A := A – temp;write(A);read(B);B := B + temp;

T1 T2

read(A);temp := A * 0,1;

read(A);A := A – 50;write(A);

B := B + 50;write(B);

read(A);temp := A * 0,1;A := A – temp;write(A);read(B);B := B + temp;write(B);

read(A);A := A – 50;write(A);read(B);B := B + 50;write(B);

B := B + temp;write(B);

Não são equivalentes por visão

read(B);B := B + 50;write(B);

temp := A * 0,1;A := A – temp;write(A);

read(B);B := B + temp;write(B);

São equivalentes por visão

Serialização de Visão

� O conceito de equivalência por visão leva ao conceito de serialização por visão.

� Uma escala é serializável por visão se ela for equivalente em visão a uma escala de execução seqüencial.seqüencial.

T1 T2 T3

read(Q)

write(Q)

write(Q)

write(Q)

É equivalente em visão à escalaseqüencial <T1,T2,T3> já que uma instrução read(Q) lê o valorinicial de Q em ambas as escalase T3 executa a escrita final de Qem ambas as escalas.

Serialização de Visão

� Modifica-se o grafo de precedência para serialização por conflito para testar se o escalonamento é serializável por visão.

� Verificando se o escalonamento abaixo é serializável por conflito:Verificando se o escalonamento abaixo é serializável por conflito:

T1 T2 T3

read(Q)

write(Q)

write(Q)

write(Q)

T1T2

T3

Gravações inúteis

Serialização de Visão

� Vejamos a seguinte situação:

� Seja S uma escala.

� Suponha que a transação Tj leia o valor do item de dado Q escrito por Ti. Se S é serializável por visão, então Q escrito por Ti. Se S é serializável por visão, então qualquer em escala seqüencial S’, à qual S é equivalente, Ti deve preceder Tj.

� Suponha agora que, na escala S, a transação Tkexecutou um write(Q). Então, na escala S’, Tk deve preceder Ti ou deve seguir Tj. Ela não poderá aparecer entre Ti e Tj, porque dessa forma Tj não leria o valor de Q escrito por Ti e, S e S’ não seriam equivalentes por visão.

Serialização por Visão

� Se o grafo não contiver ciclos então o escalonamento é serializável por visão.

� Se o grafo contiver ciclos não significa, necessariamente, que o escalonamento não é serializável.

� Haverá então 2n grafos diferentes, sendo que cada um contém � Haverá então 2 grafos diferentes, sendo que cada um contém apenas uma aresta de cada par.

� Se alguns desses grafos for acíclico, sabe-se que a escala correspondente é serializável por visão.

� O escalonamento serial equivalente é obtido seguindo a ordenação topológica do grafo acíclico.

Exemplo de Ordenação Topológica

Ti

Ti

Tj

Ti

Tk

Tj Tk

Tm

Tj

Tk

Tm

Tk

Tj

Tm

� ou

Fontes Bibliográficas:

� Sistemas de Banco de Dados (Cap. 15). Abraham Silberchatz, Henry F. Korth, S Sudarshan. 5ª Ed. Elsevier, 2006.

� Sistemas de Banco de Dados (Cap. 17). Ramez Elmasri e Sham Navathe. 4ª Ed. Pearson, 2005.Elmasri e Sham Navathe. 4ª Ed. Pearson, 2005.

� Controle de Concorrência e Distribuição de Dados: A teoria clássica, suas limitações e extensões modernas. João Eduardo Ferreira e Marcelo Finger. São Paulo: Escola Brasileira de Computação, 2001.