BD - Aula 5 - Transação

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

12/09/2012 
1 
Transação 
Rodrigo Spínola 
Agenda 
• Definições iniciais 
• Controle de Concorrência 
• Estados de uma Transação 
• Propriedades de uma Transação 
• Log de Transações 
• Controle de Concorrência 
 
 
 
2 
DEFINIÇÕES INICIAIS 
3 
12/09/2012 
2 
Transações – Algumas 
Definições 
• Mecanismo para se descrever unidade lógica de 
processamento em banco de dados 
 
• SGBDs são em geral multiusuários 
 
• Uma transação é totalmente executada ou nada dela 
(nenhum comando) é realizado 
 
• Baseado no conceito de Redundância – garantir que qualquer 
pedaço da informação possa ser reconstituído a partir de 
outras informações armazenadas 
4 
Transações – Algumas 
Definições 
• Para garantir o processamento de várias 
transações é necessário o controle de 
concorrência 
 
• Necessário também mecanismo de 
recuperação para problemas de falhas de 
transação. 
 
 
 
5 
Transações – Algumas 
Definições 
• Unidade lógica de processamento em um SGBD 
• Composta de uma ou mais operações 
– seus limites podem ser determinados em SQL 
• De forma abstrata e simplificada, uma transação pode ser 
encarada como um conjunto de operações de leitura e escrita 
de dados 
read(x) 
x = x – i 
read(y) 
y = y * x 
write(x) 
write(y) 
Tx lê o dado X do BD e o 
armazena na variável X 
grava no dado Y do BD o 
valor da variável Y 
6 
12/09/2012 
3 
Transações – Algumas 
Definições 
• Uma transação possui uma ou mais operações ao 
banco de dados, incluindo operações de inclusão, 
exclusão, modificação e recuperação 
• Para especificar os limites da transação podemos 
usar begin transaction e end transaction 
• Um programa pode conter várias transações 
• O tamanho do item de dado envolvido na transação 
denomina-se granularidade, que pode ser um 
registro ou um bloco de disco. 
7 
Transações - Gerenciamento 
• Read(x) 
– Encontra bloco do disco em que x está armazenado. 
– Copia bloco para buffer da memória principal. 
– Copia o item x do buffer para a variável do programa. 
• Write (x) 
– Encontra bloco do disco em que x está armazenado. 
– Copia o bloco para buffer da memória principal. 
– Copia x da variável do programa para o buffer. 
– Armazena o bloco atualizado do buffer para o disco (imediatamente ou 
depois) 
 
A B Programa 1 
M
em
ó
ri
a 
 
A 
B 
Programa 2 
M
em
ó
ri
a 
A 
B 
8 
Transações - Gerenciamento 
• Controle de concorrência 
– Coordena as ações de processos que operam em 
paralelo 
• acessam dados compartilhados 
• potencialmente interferem uns com os outros 
• Recuperação 
– Assegura que falhas de software e hardware não 
corrompem dados persistentes 
 
 
9 
12/09/2012 
4 
CONTROLE DE CONCORRÊNCIA 
10 
Transações - Controle de 
concorrência 
• Transações ocorrem de forma concorrente 
• Se duas transações acessam o mesmo item do banco 
e suas operações são entrelaçadas é necessário o 
controle da concorrência. 
• Por que o controle de concorrência é necessário? 
– Problema de perda de atualização 
– Problema da dependência de atualização não confirmada 
– Problema de função de agregação incorreta (sumário 
incorreto) 
 
 11 
Transações - Controle de 
concorrência 
Read (X)
X = X - N
Write (X)
Read (Y)
Y = Y + N
Write (Y)
Read (X)
X = X + M
Write (X)
T1 T2
tempo 
Problema da perda de atualização 
Item X tem um valor incorreto 
pois sua atualização através de T1 
foi pedida 
12 
12/09/2012 
5 
Transações - Controle de 
concorrência 
Dependência de uma atualização não confirmada 
(Leitura de sujeira – dirty read) 
Read (X)
X = X - N
Write (X)
Read (X)
X = X + M
Write (X)
T1 T2
Read (Y)tempo 
FALHA 
A transação T1 falha e deve retornar 
o valor de X para seu valor original 
 mas T2 já leu o valor incorreto 
13 
Transações - Controle de 
concorrência 
tempo 
Read (X)
X = X - N
Write (X)
Sum = 0
Read (A)
Sum = Sum + A
T1 T2
Read (Y)
Y = Y + N
Write (Y)
Read (X)
Sum = Sum + X
Read (Y)
Sum = Sum + Y
Problema do sumário incorreto 
T2 lê X depois que ele é subtraído 
e lê Y antes que seja adicionado. 
O resultado será uma soma 
incorreta 
14 
Transações - Controle de 
concorrência 
• Begin Transaction: inicia a transação de forma 
explícita 
• Commit Transaction: encerra a transação com 
sucesso e torna a atualização permanente 
• Rollback Transaction: Término de transação 
com erro, retorna o banco para posição 
anterior à transação 
15 
12/09/2012 
6 
Transações - Recuperação 
• Se todas as operações na transação são completadas 
com sucesso  tem efeito permanente no banco de 
dados 
• Se uma operação falhar  nada terá efeito no banco 
• Tipos de falhas : 
– Erros de hardware, software ou rede; 
– Erros de sistemas ou transação; 
– Condições de exceção detectados na transação. 
 
 
 16 
ESTADOS DE UMA TRANSAÇÃO 
17 
Estados de uma Transação 
• Uma transação é sempre monitorada pelo SGBD 
quanto ao seu estado 
– que operações já fez? concluiu suas operações? deve 
abortar? 
 
• Estados de uma transação 
– Ativa, Em processo de efetivação, Efetivada, Em processo 
de aborto, Concluída 
– Respeita um Grafo de Transição de Estados 
18 
12/09/2012 
7 
Transição de Estados de uma 
Transação 
Ativa 
Em processo de efetivação 
Efetivada 
Em processo de aborto 
Concluída 
iniciar 
transação 
finalizar 
transação 
transação deve 
ser desfeita 
conclusão 
da transação 
com sucesso 
encerramento 
com sucesso 
conclusão 
da transação 
sem sucesso 
reads e writes 
encerramento 
sem sucesso 
19 
Transição de Estados de uma 
Transação 
Ativa 
Em processo de efetivação 
Efetivada 
Em processo de aborto 
Concluída 
iniciar 
transação 
finalizar 
transação 
transação deve 
ser desfeita 
conclusão 
da transação 
com sucesso 
encerramento 
com sucesso 
conclusão 
da transação 
sem sucesso 
reads e writes 
encerramento 
sem sucesso 
Estado inicial de toda 
transação selecionada 
para execução. 
 
Enquanto ativa, uma transação executa 
uma ou mais operações read e write 
 
20 
Transição de Estados de uma 
Transação 
Ativa 
Em processo de efetivação 
Efetivada 
Em processo de aborto 
Concluída 
iniciar 
transação 
finalizar 
transação 
transação deve 
ser desfeita 
conclusão 
da transação 
com sucesso 
encerramento 
com sucesso 
conclusão 
da transação 
sem sucesso 
reads e writes 
encerramento 
sem sucesso 
Entra nesse estado após 
executar sua última operação 
(solicitação de COMMIT). 
 
Neste momento, o SGBD precisa garantir 
que as suas atualizações sejam efetivadas 
com sucesso (não sofra falhas). 
 
Aplicação de técnicas de recovery. 
 
21 
12/09/2012 
8 
Transição de Estados de uma 
Transação 
Ativa 
Em processo de efetivação 
Efetivada 
Em processo de aborto 
Concluída 
iniciar 
transação 
finalizar 
transação 
transação deve 
ser desfeita 
conclusão 
da transação 
com sucesso 
encerramento 
com sucesso 
conclusão 
da transação 
sem sucesso 
reads e writes 
encerramento 
sem sucesso 
Entra nesse estado após o SGBD confirmar 
que todas as modificações da transação 
estão garantidas no BD (COMMIT OK). 
 
Exemplos: gravação em Log, descarga de 
todos os buffers em disco . 
 
22 
Transição de Estados de uma 
Transação 
Ativa 
Em processo de efetivação 
Efetivada 
Em processo de aborto 
Concluída 
iniciar
transação 
finalizar 
transação 
transação deve 
ser desfeita 
conclusão 
da transação 
com sucesso 
encerramento 
com sucesso 
conclusão 
da transação 
sem sucesso 
reads e writes 
encerramento 
sem sucesso 
Entra nesse estado se não puder 
prosseguir a sua execução. 
Pode passar para esse estado enquanto 
ativa ou em processo de efetivação: 
 exemplo (I): violação de RI 
 exemplo (II): pane no S.O. 
 
Suas ações já realizadas devem ser 
desfeitas (ROLLBACK). 
23 
Transição de Estados de uma 
Transação 
Ativa 
Em processo de efetivação 
Efetivada 
Em processo de aborto 
Concluída 
iniciar 
transação 
finalizar 
transação 
transação deve 
ser desfeita 
conclusão 
da transação 
com sucesso 
encerramento 
com sucesso 
conclusão 
da transação 
sem sucesso 
reads e writes 
encerramento 
sem sucesso 
Estado final de uma transação 
Indica uma transação que deixa o 
sistema. As informações da transação 
mantidas em catálogo podem ser 
excluídas: operações feitas, dados 
manipulados, buffers utilizados, ... 
 
Se a transação não concluiu com 
sucesso, ela pode ser reiniciada 
automaticamente 
 
24 
12/09/2012 
9 
PROPRIEDADES DE UMA 
TRANSAÇÃO 
25 
Propriedades de uma 
Transação 
• Requisitos que sempre devem ser atendidos 
por uma transação 
• Chamadas de propriedades ACID 
– Atomicidade 
– Consistência 
– Isolamento 
– Durabilidade ou Persistência 
 
26 
Atomicidade 
• Princípio do “Tudo ou Nada” 
– ou todas as operações da transação são efetivadas 
com sucesso no BD ou nenhuma delas se efetiva 
• preservar a integridade do BD 
• Responsabilidade do subsistema de 
recuperação contra falhas (subsistema de 
recovery) do SGBD 
– desfazer as ações de transações parcialmente 
executadas 
 
27 
12/09/2012 
10 
Consistência 
• Uma transação sempre conduz o BD de um 
estado consistente para outro estado 
também consistente 
• Responsabilidade conjunta do 
– DBA 
• definir todas as RIs para garantir estados e transições 
de estado válidos para os dados 
– exemplos: salário > 0; salário novo > salário antigo 
– subsistema de recovery 
• desfazer as ações da transação que violou a integridade 
28 
Isolamento 
• No contexto de um conjunto de transações 
concorrentes, a execução de uma transação Tx deve 
funcionar como se Tx executasse de forma isolada 
– Tx não deve sofrer interferências de outras transações 
executando concorrentemente 
 
• Responsabilidade do subsistema de controle de 
concorrência (scheduler) do SGBD 
– garantir escalonamentos sem interferências 
 
29 
Isolamento 
T1 T2 
read(A) 
A = A – 50 
write(A) 
read(A) 
A = A+A*0.1 
write(A) 
read(B) 
B = B + 50 
write(B) 
read(B) 
B = B - A 
write(B) 
T1 T2 
read(A) 
A = A – 50 
read(A) 
A = A+A*0.1 
write(A) 
read(B) 
write(A) 
read(B) 
B = B + 50 
write(B) 
B = B - A 
write(B) 
escalonamento válido escalonamento inválido 
T1 interfere 
em T2 
T2 interfere 
em T1 
30 
12/09/2012 
11 
Durabilidade ou Persistência 
• Deve-se garantir que as modificações 
realizadas por uma transação que concluiu 
com sucesso persistam no BD 
– nenhuma falha posterior ocorrida no BD deve 
perder essas modificações 
• Responsabilidade do subsistema de recovery 
– refazer transações que executaram com sucesso 
em caso de falha no BD 
31 
Transações - Propriedades 
(ACID) 
Atomicidade 
Consistência 
Isolamento 
Durabilidade 
Subsistema 
de 
Recuperação 
Controle de 
Concorrência 
Restrições de 
Integridade/ 
Programador 
32 
LOG DE TRANSAÇÕES 
33 
12/09/2012 
12 
Transações - Log de 
transações 
• Para ter capacidade de se recuperar de falhas 
que afetam a transação o sistema mantém um 
log 
• No log são registradas todas as operações das 
transações que afetam valores nos bancos de 
dados (alterações) 
• O log é mantido em disco 
 
34 
Transações - Registros de Log 
• Seja T a idenficação de uma transação: 
– [Start_transaction, T]: marca o início da transação T 
– [Write_item, T, X, old_value, new_value]: indica que a 
transação T alterou o valor de X no banco de dados do 
valor antigo para o novo 
– [read_item, T, X]: indica que a transação T leu o valor do 
item T no banco de dados 
– [commit, T]: indica que a transação T foi completada com 
sucesso e confirma a gravação no banco de dados 
– [abort, T]: indica que a transaçõa T foi abortada 
35 
Transações - Log de 
transações 
• Periodicamente o log é copiado para fita 
 
• Como o log contém todos os registros das operações 
que alteraram qualquer item do banco, é possível 
desfazer (undo) o efeito destas operações ou refazer 
as operações até um certo ponto 
 
• Base para o processo de recuperação – Recovery 
 
36 
12/09/2012 
13 
Transações - Modificações no 
BD 
• Modificações Adiadas: O BD não é atualizado 
até que a transação alcance o commit. 
 
• Modificações Imediata: O BD é modificado 
antes de alcançar o commit. As informações 
do log são gravadas no meio estável a fim de 
possibilitar a recuperação. 
37 
Transações - Check point 
• Ponto de checagem 
– Gravado periodicamente no log no ponto em que o SGBD 
grava no banco de dados todos os blocos que tenham sido 
modificados 
– Todas as transações commited no log não precisam mais 
ser refeitas no banco 
– O gerenciador de recuperações deve decidir em que 
intervalo realizar o checkpoint 
– O intervalo pode ser mantido em termo de tempo ou em 
termo de número de transações confirmadas desde o 
último checkpoint 
 
38 
Transações - Check point 
• Suspende todas as transações temporariamente. 
• Grava os buffers modificados do BD da memória para o disco. 
• Grava um registro de checkpoint no log 
• Retorna as transações em execução 
 
T1
T2
T3
T4
T5
Ponto de checagem
(tempo, tc)
Falha no sistem
(tempo, tc)
Tempo
tc tf
39 
12/09/2012 
14 
CONTROLE DE CONCORRÊNCIA 
40 
Controle de Concorrência 
• SGBD 
– sistema multiusuário em geral 
• diversas transações executando simultaneamente 
• Garantia de isolamento de Transações 
– 1a solução: uma transação executa por vez 
• escalonamento serial de transações 
• solução bastante ineficiente! 
– várias transações podem esperar muito tempo para serem 
executadas 
– CPU pode ficar muito tempo ociosa 
» enquanto uma transação faz I/O, por exemplo, outras 
transações poderiam ser executadas 
41 
Controle de Concorrência 
• Solução mais eficiente 
– execução concorrente de transações de modo a preservar o isolamento 
• escalonamento (schedule) não-serial e íntegro 
– responsabilidade do subsistema de controle de concorrência ou scheduler 
T1 T2 
read(X) 
X = X – 20 
write(X) 
read(Y) 
Y = Y + 20 
write(Y) 
read(X) 
X = X + 10 
write(X) 
T1 T2 
read(X) 
X = X – 20 
write(X) 
read(X) 
X = X + 10 
write(X) 
read(Y) 
Y = Y + 20 
write(Y) 
execução 
serial 
execução 
não-serial 
ou concorrente 
42 
12/09/2012 
15 
Scheduler 
• Responsável pela definição de escalonamentos não-seriais de 
transações 
• “Um escalonamento E define uma ordem de execução das 
operações de várias transações, sendo que a ordem das 
operações de uma transação Tx em E aparece na mesma 
ordem na qual elas ocorrem isoladamente em Tx” 
• Problemas de um escalonamento não-serial mal definido 
(inválido) 
– atualização perdida (lost-update) 
– leitura suja (dirty-read) 
 
43 
Atualização Perdida 
• Uma transação Ty grava em um dado atualizado por 
uma transação
Tx 
T1 T2 
read(X) 
X = X – 20 
read(Z) 
X = Z + 10 
write(X) 
read(Y) 
write(X) 
Y = X + 30 
write(Y) 
a atualização de X 
por T1 foi perdida! 
44 
Leitura Suja 
• Tx atualiza um dado X, outras transações 
posteriormente lêem X, e depois Tx falha 
T1 T2 
read(X) 
X = X – 20 
write(X) 
read(X) 
X = X + 10 
write(X) 
read(Y) 
abort( ) 
T2 leu um valor de X que 
não será mais válido! 
45 
12/09/2012 
16 
Scheduler 
• Deve evitar escalonamentos inválidos 
– exige análise de operações em conflito 
• operações que pertencem a transações diferentes 
• transações acessam o mesmo dado 
• pelo menos uma das operações é write 
– tabela de situações de conflito de transações 
• podem gerar um estado inconsistente no BD 
Ty 
Tx 
read(X) write(X) 
read(X)  
write(X)   
46 
Scheduler X Recovery 
• Scheduler deve cooperar com o Recovery! 
• Categorias de escalonamentos considerando 
o grau de cooperação com o Recovery 
– recuperáveis X não-recuperáveis 
– permitem aborto em cascata X evitam aborto em 
cascata 
– estritos X não-estritos 
 
 
 
47 
Escalonamento Recuperável 
• Garante que, se Tx realizou commit, Tx não irá sofrer UNDO 
– o recovery espera sempre esse tipo de escalonamento! 
• Um escalonamento E é recuperável se nenhuma Tx em E for 
concluída até que todas as transações que gravaram dados 
lidos por Tx tenham sido concluídas 
T1 T2 
read(X) 
X = X – 20 
write(X) 
read(X) 
X = X + 10 
write(X) 
commit( ) 
abort( ) 
escalonamento 
não-recuperável 
T1 T2 
read(X) 
X = X – 20 
write(X) 
read(X) 
X = X + 10 
write(X) 
commit( ) 
commit( ) 
escalonamento 
recuperável 
48 
12/09/2012 
17 
Escalonamento sem Aborto 
em Cascata 
• Um escalonamento recuperável pode gerar abortos de transações em 
cascata 
– consome muito tempo de recovery! 
• Um escalonamento E é recuperável e evita aborto em cascata se uma Tx 
em E só puder ler dados que tenham sido atualizados por transações que 
já concluíram 
T1 T2 
read(X) 
X = X – 20 
write(X) 
read(X) 
X = X + 10 
write(X) 
abort( ) . . . 
escalonamento 
recuperável 
com aborto em 
cascata 
T1 T2 
read(X) 
X = X – 20 
write(X) 
commit( ) 
read(X) 
X = X + 10 
write(X) 
. . . 
escalonamento 
recuperável 
sem aborto em 
cascata 
49 
Escalonamento Estrito 
• Garante que, se Tx deve sofrer UNDO, basta gravar a before image dos 
dados atualizados por ela 
• Um escalonamento E é recuperável, evita aborto em cascata e é estrito se 
uma Tx em E só puder ler ou atualizar um dado X depois que todas as 
transações que atualizaram X tenham sido concluídas 
T1 T2 
read(X) 
X = X – 20 
write(X) 
read(Y) 
X = Y + 10 
write(X) 
commit( ) 
abort( ) 
escalonamento 
recuperável 
sem aborto em 
cascata e 
não-estrito 
T1 T2 
read(X) 
X = X – 20 
write(X) 
commit( ) 
read(Y) 
X = Y + 10 
write(X) 
commit( ) 
escalonamento 
recuperável 
sem aborto em 
cascata e 
estrito 
50 
Teoria da Serializabilidade 
• Garantia de escalonamentos não-seriais válidos 
• Premissa 
– “um escalonamento não-serial de um conjunto de transações deve produzir 
resultado equivalente a alguma execução serial destas transações” 
T1 T2 
read(X) 
X = X – 20 
write(X) 
read(Y) 
Y = Y + 20 
write(Y) 
read(X) 
X = X + 10 
write(X) 
T1 T2 
read(X) 
X = X – 20 
write(X) 
read(X) 
X = X + 10 
write(X) 
read(Y) 
Y = Y + 20 
write(Y) 
execução 
serial 
execução 
não-serial 
serializável 
entrada: 
X = 50 
Y = 40 
entrada: 
X = 50 
Y = 40 
saída: 
X = 40 
Y = 60 
saída: 
X = 40 
Y = 60 
51 
12/09/2012 
18 
Verificação de 
Serializabilidade 
• Duas principais técnicas 
– equivalência de conflito 
– equivalência de visão 
 
• Equivalência de Conflito 
– “dado um escalonamento não-serial E’ para um conjunto 
de Transações T, E’ é serializável em conflito se E’ for 
equivalente em conflito a algum escalonamento serial E 
para T, ou seja, a ordem de quaisquer 2 operações em 
conflito é a mesma em E’ e E.” 
52 
Equivalência de Conflito - 
Exemplo 
T1 T2 
read(X) 
X = X – 20 
write(X) 
read(Y) 
Y = Y + 20 
write(Y) 
read(X) 
X = X + 10 
write(X) 
T1 T2 
read(X) 
X = X – 20 
write(X) 
read(X) 
X = X + 10 
write(X) 
read(Y) 
Y = Y + 20 
write(Y) 
escalonamento serial E escalonamento não-serial E1 
T1 T2 
read(X) 
X = X – 20 
read(X) 
X = X + 10 
write(X) 
read(Y) 
write(X) 
Y = Y + 20 
write(Y) 
escalonamento não-serial E2 
 E1 equivale em conflito a E 
 E2 não equivale em conflito a nenhum escalonamento serial 
 para T1 e T2 
 E1 é serializável e E2 não é serializável 53 
Verificação de Equivalência 
em Conflito 
• Construção de um grafo direcionado de 
precedência 
– nós são IDs de transações 
– arestas rotuladas são definidas entre 2 transações 
T1 e T2 se existirem operações em conflito entre 
elas 
• direção indica a ordem de precedência da operação 
– origem indica onde ocorre primeiro a operação 
• Um grafo com ciclos indica um escalonamento 
não-serializável em conflito! 
54 
12/09/2012 
19 
Verificação de Equivalência 
em Conflito 
• Algoritmo para teste de serialidade de um plano S 
1. Para cada transação Ti participante do Plano S, criar um nó rotulado 
Ti no grafo de precedência. 
2. Para cada caso em S em que Tj executar um ler_item(X) depois que 
uma Ti executar um escrever_item(X), criar uma seta (Ti → Tj ) no 
grafo de precedência. 
3. Para cada caso em S em que Tj executar um escrever_item(X) depois 
que Ti executar um ler_item(X), criar uma seta (Ti → Tj ) no grafo de 
precedência. 
4. Para cada caso em S em que Tj executar um escrever_item(X) depois 
que Ti executar um escrever_item(X), criar uma seta (Ti → Tj ) no 
grafo de precedência. 
5. O plano S será serializável se, e apenas se, o grafo de precedência 
não contiver ciclos. 
 
 
55 
Grafo de Precedência 
T1 T2 
read(X) 
X = X – 20 
write(X) 
read(X) 
X = X + 10 
write(X) 
read(Y) 
Y = Y + 20 
write(Y) 
escalonamento serializável E1 
T1 T2 
read(X) 
X = X – 20 
read(X) 
X = X + 10 
write(X) 
read(Y) 
write(X) 
Y = Y + 20 
write(Y) 
escalonamento não-serializável E2 
T1 T2 T1 T2 
56 
Plano de Execução (histórico) 
de Transações 
• Representação sequencial da execução entrelaçada de um conjunto de 
transações concorrentes 
– operações consideradas 
• read (r), write (w), 
• commit (c), abort (a) 
 
• Exemplo 
• HE2 = r1(x) r2(x) w1(x) r1(y)w2(x) w1(y) c1 c2 
escalonamento não-serializável E2 
T1 T2 
read(X) 
X = X – 20 
read(X) 
X = X + 10 
write(X) 
read(Y) 
write(X) 
Y = Y + 20 
write(Y) 
commit( ) 
commit( ) 
57 
12/09/2012 
20 
Referências 
• Elmasri, R. e Navathe, S. Fundamentals of Database Systems,6 
Edição, Addison-Wesley, 2011. 
– Capítulo 21 
 
• Abraham Silberschatz, Henry F. Korth, S. Sudarshan., Sistema 
de Banco de Dados, Editora: CAMPUS 5 º Edição - 2006 808 
pág. ISBN 13: 9788535211078 
58 
Transação 
Rodrigo Spínola