Departamento de Engenharia Informática 2010/2011 ... · 2.3. Considere as instruções envolvidas no primeiro escalonamento apresentado. Coloque as instruções de trinco apropriadas,

Departamento de Engenharia Informática 2010/2011

Administração e Optimização de BDs 2º semestre

Mini-Projecto 3 – A entregar a 7 de Maio de 2011

IST/DEI Pág. 1 de 12

A resolução deve ser claramente identificada com o número de grupo e entregue sob a forma de um relatório impresso, seguindo o template dado na página da cadeira.

A entrega electrónica deve incluir o código Java com a solução da pergunta 5.

1 - Uma instituição bancária nacional implementou um novo tipo de produto denominado “conta casada” que liga duas contas bancárias e permite que sejam efectuados levantamentos a descoberto desde que as soma dos saldos das contas participantes permaneça positiva. Assuma que o saldo inicial da primeira conta (conta A) é 200 euro e o da segunda (conta B) é 300 euro. Ou seja, o saldo conjunto é de 500 euro no total. Suponha que são submetidos dois pedidos de levantamento simultâneos (i.e., executados concorrentemente) de valores diferentes para as mesmas contas conjuntas, um no valor de 150 euro e outro no valor de 450. Note que em conjunto não deverá ser possível efetuar o levantamento 150 + 450 euro. Os levantamentos são representados pelas transações T1 e T2 como se segue: T1:

BEGIN TRANSACTION

SELECT Saldo, Assoc INTO SaldoA, ContaB

FROM Contas

WHERE NumConta = A

SELECT Saldo INTO SaldoB

FROM Contas

WHERE NumConta = ContaB

IF (SaldoA + SaldoB > 150) THEN

UPDATE Contas

SET Saldo = Saldo - 150

WHERE NumConta = A

END IF

COMMIT

T2:

BEGIN TRANSACTION

SELECT Saldo, Assoc INTO SaldoB, ContaA

FROM Contas

WHERE NumConta = B

SELECT Saldo INTO SaldoA

FROM Contas

WHERE NumConta = ContaA

IF (SaldoA + SaldoB > 450) THEN

UPDATE Contas

SET Saldo = Saldo - 450

WHERE NumConta = B

END IF

COMMIT

Indique como podem variar os resultados e a execução da transação T1 consoante os diferentes níveis de isolamento. Tenha o cuidado de indicar problemas diferentes em cada uma das alíneas. Sugestão: Apresente para cada alínea um escalonamento em que T1 tenha um comportamento diferente consoante o nível de isolamento.

1.1. Diferenças entre a execução no nível de isolamento READ UNCOMMITED, face ao nível de isolamento READ COMMITED;

Administração e Optimização de Bases de Dados


1.2. Diferenças entre a execução no nível de isolamento READ COMMITTED, face ao nível de isolamento READ COMMITTED SNAPSHOT.

1.3. Diferenças entre a execução no nível de isolamento READ COMMITTED SNAPSHOT, face ao nível de isolamento SERIALIZABLE

2 – Considere os seguintes dois escalonamentos para transacções concorrentes.

T1 T2 T3 T1 T2 T3

R(B) R(C)

R(C) R(B)

R(A) W(B)

W(A) R(B)

W(B) R(C)

W(C) R(A)

R(C) W(A)

R(B) W(B)

W(B) W(C)

R(B) R(A)

W(B) R(B)

R(A) W(B)

W(A) W(A)

2.1. Construa os grafos de precedências para os escalonamentos apresentados.

2.2. Os escalonamentos apresentados são conflict-serializable? Justifique a sua resposta indicando, em caso afirmativo, quais seriam os escalonamentos série correspondentes.

2.3. Considere as instruções envolvidas no primeiro escalonamento apresentado. Coloque as instruções de trinco apropriadas, obedecendo ao protocolo strict two-phase locking.

2.4. Diga o que entente por escalonamento recuperável e indique em que medida é que o protocolo de locking usado na alínea anterior garante esta propriedade.

2.5. Podem ocorrer deadlocks sob o resultado da alínea 2.4? Justifique a sua resposta.

3 – Considere o primeiro escalonamento do Exercício 2 e considere ainda que, inicialmente, o relógio do sistema está a zero e que todos os recursos da base de dados têm um read-timestamp e um write-timestamp igual a zero. Indique quais as acções que são tomadas por um protocolo de escalonamento baseado em timestamps quando o mesmo recebe a sequência de operações para as transacções concorrentes indicada (i.e., para cada operação, indicar se a mesma é executada ou não, justificar a decisão de execução ou não, e indicar as actualizações nos valores dos timestamps). 4 – Considere o segundo escalonamento do Exercício 2. Indique quais as acções que são tomadas por um protocolo de escalonamento multi-versões, baseado em timestamps, quando o mesmo recebe a sequência de operações para as transacções indicadas.



5 – Tomando como base as classes Java disponibilizadas na página Web da cadeira, implemente o algoritmo de recuperação ARIES. As classes disponibilizadas na página da cadeira permitem-lhe simular a escrita/leitura de páginas no disco (por forma a verificar o PageLSN), as estruturas de dados onde são armazenados o registos do log de recuperação, e as estruturas de dados auxiliares necessárias à execução do algoritmo ARIES.



Abaixo encontram-se as resoluções para os problemas propostos no Mini-Projecto 3.

Resolução do Problema 1

1. Em termos abstractos, considerando as linhas das contas A e B, representadas pelo

objectos A e B respectivamente, as transações T1 e T2 pode ser descritas através das seguintes sequências de operações:

T1= R1(A); R1(B); R1(A); W1(A); C1

T2= R2(B); R2(A); R2(B); W2(B); C2

1.1. Diferenças entre a execução no nível de isolamento READ UNCOMMITED, face ao nível de isolamento READ COMMITED; Podem existir Dirty Reads, por exemplo.

T1 T2

R(A) = 200

R(B) = 300

R(A) = 200

R(A) = 300; W(B,-150)

R(B) = -150

Dirty Read => Lê o valor escrito por T2 antes do commit de T2 e já não entra no IF e não faz o levantamento (houve um Dirty Read que não poderia existir com isolamento READ COMMITED)

Commit

Commit

1.2. Diferenças entre a execução no nível de isolamento READ COMMITTED, face ao nível de isolamento READ COMMITTED SNAPSHOT. Podem existir Non-Repeatable Reads e Lost Updates. Um Non-repeatable read não é possível com estas transações pois teria de haver uma situação em que uma das transações re-lesse o valor entretanto “committed” por outra. Isto é, uma sequência com o padrão: R1(A); W2(A); C2; R1(A). No entanto, isto não é possível porque a escrita efectuada por T2 é W2(B) e não existe nenhuma escrita no objecto A. Os Lost Updates simples, na forma R1(A); R2(A); W1(A); W2(A); C1; C2; não é possível com isolamento READ COMMITED pois o commit C1 iria abortar a execução. A sequência R1(A); R2(A); W1(A); C1; W2(A); C2; causa um lost update com o nível de isolamento READ COMMITED uma vez que W2(A) re-escreve o valor de W1(A) e faz commit. A sequência R1(A)=20; R2(A)=20; W1(A,30); C1; R2(A)=30; W2(A,40); C2; é um lost update que pode ocorrer em READ COMMITED mas nunca em



READ COMMITED SNAPSHOT uma vez que, em READ COMMITED SNAPSHOT, o objecto A após lido pela transação T1 não seria re-lido com outro valor dentro da mesma transação.

1.3. Diferenças entre a execução no nível de isolamento READ COMMITTED SNAPSHOT, face ao nível de isolamento SERIALIZABLE. No nível de isolamento READ COMMITED SNAPSHOT podem ocorrer Read Skews e Write Skews que não ocorrem no nível de isolamento SERIALIZABLE.

T1 T2

R(A) = 200

R(B) = 300

R(A) = 200

R(B) = 200

R(B) = 300; W(B, -150)

Commit

R(A) = 200; W(A, 50)

Write Skew => Mesmo com READ_COMMITED_SNAPSHOT o valor escrito por T2 e o levantamento é efectuado; T1 faz commit e o valor da conta fica a -100. Qualquer escalonamento com isolamento SERIALIZABLE não efectua um dos levantamentos.

Commit


Pergunta 2.1

Para o primeiro escalonamento teriamos um grafo com três nós (T1, T2, T3) e com arestas de T3 -> T1 (por B) , T3 -> T2 (por B,C) e T1 -> T2 (por A,B).

Para o segundo escalonamento teriamos um grafo com três nós (T1, T2, T3) e com arestas de T3 -> T1 (por B), T1 -> T2 (por A), T2 -> T3 (por B,C) e T2 -> T1 (por B)

Pergunta 2.2

O primeiro escalonamento é conflict-serializable, uma vez que o grafo de precedências não apresenta ciclos. Um escalonamento série equivalente seria T3 -> T1 -> T2. O segundo



escalonamento não é conflict-serializable, uma vez que o grafo de precedências apresenta ciclos.

Pergunta 2.3

Para o primeiro caso:

T1 : L-S(A), R(A), L-X(A), W(A), L-S(B), R(B), L-X(B), W(B), U(A), U(B)

T2 : L-S(C), R(C), L-S(B), R(B), L-X(B), W(B), L-S(A), R(A), L-X(A), W(A), U(A), U(B), U(C)

T3 : L-S(B), R(B), L-S(C), R(C), L-X(B), W(B), L-X(C), W(C), U(B), U(C)

Para o segundo caso:

T1 : L-S(A), R(A), L-X(A), W(A), L-S(B), R(B), L-X(B), W(B), U(A), U(B)

T2 : L-S(C), R(C), L-S(B), R(B), L-X(B), W(B), L-S(A), R(A), L-X(A), W(A), U(A), U(B), U(C)

T2 : L-S(B), R(B), L-S(C), R(C), L-X(B), W(B), L-X(C), W(C), U(B), U(C)

Pergunta 2.4

Um escalonamento é recuperável se tivermos que as transacções apenas fazem commit depois das transacções de cujas actualizações elas dependem já tiverem feito commit. O protocolo strict-2PL (onde os locks de escrita apenas são libertados depois da transacção ter sido confirmada) garante a geração de escalonamentos recuperáveis. Com um protocolo strict-2PL, apenas conseguimos obter locks de leitura sobre objectos se os locks de escrita tiverem sido libertados, i.e. se as actualizações concorrentes já tiverem sido confirmadas.

Pergunta 2.5

Podem ocorrer deadlocks, pois o protocolo strict-2PL não oferece garantias sobre a não ocorrência de bloqueios mútuos entre duas ou mais transacções.


Vamos assumir que cada operação no escalonamento apresentado corresponde a uma unidade de tempo e vamos assumir um relógio linear com pontos 0, 1, 2, 3, ... Vamos ainda assumir que cada transacção tem um timestamp correspondendo ao tempo de execução da sua primeira operação, i.e. TS(T1) = 3, TS(T2)=7, TS(T3) = 1



Os timestamps de leitura e escrita originais, para os items, terão também o valor zero: read_TS(A) = read_TS(B) = read_TS(C) = 0 write_TS(A) = write_TS(B) = write_TS(C) = 0 Aplicando o protocol ao escalonamento apresentado, temos que o escalonamento se iria executar com sucesso: read_TS(A)=0, read_TS(B)=0, read_TS(C)=0, write_TS(A)=0, write_TS(B)=0, write_TS(C)=0 T3: read_item(B) TS(T3) > write_TS(B) Executar read_item(B) Colocar read_TS(B) <- max(read_TS(B), TS(T3)) = 1

read_TS(A)=0, read_TS(B)=1, read_TS(C)=0, write_TS(A)=0, write_TS(B)=0, write_TS(C)=0 T3: read_item(C) TS(T3) > write_TS(C) Executar read_item(C) Colocar read_TS(C) <- max(read_TS(C), TS(T3)) = 1

read_TS(A)=0, read_TS(B)=1, read_TS(C)=1, write_TS(A)=0, write_TS(B)=0, write_TS(C)=0 T1: read_item(A) TS(T1) > write_TS(A) Executar read_item(A) Colocar read_TS(A) <- max(read_TS(A), TS(T1)) = 3

read_TS(A)=3, read_TS(B)=1, read_TS(C)=1, write_TS(A)=0, write_TS(B)=0, write_TS(C)=0 T1: write_item(A) TS(T1) = read_TS(A) and TS(T1) > write_TS(A) Executar write_item(A) Colocar write_TS(A) <- max(write_TS(A), TS(T1)) = 3

read_TS(A)=3, read_TS(B)=1, read_TS(C)=1, write_TS(A)=3, write_TS(B)=0, write_TS(C)=0 T3: write_item(B) TS(T3) = read_TS(B) and TS(T3) > write_TS(B) Executar write_item(B) Colocar write_TS(B) <- max(write_TS(B), TS(T3)) = 1



read_TS(A)=3, read_TS(B)=1, read_TS(C)=1, write_TS(A)=3, write_TS(B)=1, write_TS(C)=0 T3: write_item(C) TS(T3) = read_TS(C) and TS(T3) > write_TS(C) Executar write_item(C) Colocar write_TS(C) <- max(write_TS(C), TS(T3)) = 1

read_TS(A)=3, read_TS(B)=1, read_TS(C)=1, write_TS(A)=3, write_TS(B)=1, write_TS(C)=1 T2: read_item(C) TS(T2) > write_TS(C) Executar read_item(C) Colocar read_TS(C) <- max(read_TS(C), TS(T2)) = 7

read_TS(A)=3, read_TS(B)=1, read_TS(C)=7, write_TS(A)=3, write_TS(B)=1, write_TS(C)=1 T1: read_item(B) TS(T1) > write_TS(B) Executar read_item(B) Colocar read_TS(B) <- max(read_TS(B), TS(T1)) = 3

read_TS(A)=3, read_TS(B)=3, read_TS(C)=7, write_TS(A)=3, write_TS(B)=1, write_TS(C)=1 T1: write_item(B) TS(T1) = read_TS(B) and TS(T1) > write_TS(B) Executar write_item(B) Colocar write_TS(B) <- max(read_TS(B), TS(T1)) = 3

read_TS(A)=3, read_TS(B)=3, read_TS(C)=7, write_TS(A)=3, write_TS(B)=3, write_TS(C)=1 T1: write_item(B) TS(T1) = read_TS(B) and TS(T1) > write_TS(B) Executar write_item(B) Colocar write_TS(B) <- max(read_TS(B), TS(T1)) = 3

read_TS(A)=3, read_TS(B)=3, read_TS(C)=7, write_TS(A)=3, write_TS(B)=3, write_TS(C)=1 T2: read_item(B) TS(T2) > write_TS(B) Executar read_item(B) Colocar read_TS(B) <- max(read_TS(B), TS(T2)) = 7



read_TS(A)=3, read_TS(B)=7, read_TS(C)=7, write_TS(A)=3, write_TS(B)=3, write_TS(C)=1 T2: write_item(B) TS(T2) = read_TS(B) and TS(T2) > write_TS(B) Executar write_item(B) Colocar write_TS(B) <- max(write_TS(B), TS(T2)) = 7

read_TS(A)=3, read_TS(B)=7, read_TS(C)=7, write_TS(A)=3, write_TS(B)=7, write_TS(C)=1 T2: read_item(A) TS(T2) > write_TS(A) Executar read_item(A) Colocar read_TS(A) <- max(read_TS(A), TS(T2)) = 7

read_TS(A)=7, read_TS(B)=7, read_TS(C)=7, write_TS(A)=3, write_TS(B)=7, write_TS(C)=1 T2: write_item(A) TS(T2) = read_TS(A) and TS(T2) > write_TS(A) Executar write_item(A) Colocar write_TS(A) <- max(write_TS(A), TS(T2)) = 7

read_TS(A)=7, read_TS(B)=7, read_TS(C)=7, write_TS(A)=7, write_TS(B)=7, write_TS(C)=1


Para nos referirmos a versões, usamos A, B, C para referênciar a versão original (valor) de cada item, e depois usamos índices (1, 2, ...) para nos referirmos a uma nova versão (e.g., A1, A2, ...) read_TS(A)=0,read_TS(B)=0,read_TS(C)=0, write_TS(A)=0,write_TS(B)=0,write_TS(C)=0 TS(T1)=6, TS(T2)=1, TS(T3)=4 (Estes valores não se alteram) T2: ler_item(C) Executar ler_item(C) Colocar read_TS(C) <- max(read_TS(C),TS(T2)) = 1 read_TS(A)=0,read_TS(B)=0,read_TS(C)=1, write_TS(A)=0,write_TS(B)=0,write_TS(C)=0 T2: ler_item(B)



Executar ler_item(B) Colocar read_TS(B) <- max(read_TS(B),TS(T2)) = 1 read_TS(A)=0,read_TS(B)=1,read_TS(C)=1, write_TS(A)=0,write_TS(B)=0,write_TS(C)=0 T2: write_item(B) TS(T2) = read_TS(B) Executar write_item(B) (criando uma nova versão B1 de B) write_TS(B1) <- TS(T2) = 1, read_TS(B1) <- TS(T2) = 1 read_TS(A)=0,read_TS(B)=1,read_TS(B1)=1,read_TS(C)=1, write_TS(A)=0,write_TS(B)=0,write_TS(B1)=1,write_TS(C)=0 T3: ler_item(B) Executar ler_item(B) lendo o valor da versão B1 read_TS(B1) <- max(read_TS(B1),TS(T3)) = 4 read_TS(A)=0,read_TS(B)=1,read_TS(B1)=4,read_TS(C)=1, write_TS(A)=0,write_TS(B)=0,write_TS(B1)=1,write_TS(C)=0 T3: ler_item(C) Executar ler_item(C) read_TS(C) <- max(read_TS(C),TS(T3)) = 4 read_TS(A)=0,read_TS(B)=1,read_TS(B1)=4,read_TS(C)=4, write_TS(A)=0,write_TS(B)=0,write_TS(B1)=1,write_TS(C)=0 T1: ler_item(A) Executar ler_item(A) read_TS(A) <- max(read_TS(A),TS(T1)) = 6 read_TS(A)=6,read_TS(B)=1,read_TS(B1)=4,read_TS(C)=4, write_TS(A)=0,write_TS(B)=0,write_TS(B1)=1,write_TS(C)=0 T1: write_item(A) Executar write_item(A) (criando uma nova versão A1 de A) write_TS(A) <- TS(T1) = 6, read_TS(A) <- TS(T1) = 6 read_TS(A)=6,read_TS(A1)=6,read_TS(B)=1,read_TS(B1)=4,read_TS(C)=4, write_TS(A)=0,write_TS(A1)=6,write_TS(B)=0,write_TS(B1)=1,write_TS(C)=0 T3: write_item(B) Executar write_item(B) (criando uma nova versão B2 de B) write_TS(B2) <- TS(T3) = 4,



read_TS(B2) <- TS(T3) = 4 read_TS(A)=6,read_TS(A1)=6,read_TS(B)=1,read_TS(B1)=4,read_TS(B2)=4, read_TS(C)=4, write_TS(A)=0,write_TS(A1)=6,write_TS(B)=0,write_TS(B1)=1,write_TS(B2)=4, write_TS(C)=0 T3: write_item(C) Executar write_item(C) (criando uma nova versão C1 de C) write_TS(C1) <- TS(T3) = 4, read_TS(C1) <- TS(T3) = 4 read_TS(A)=6,read_TS(A1)=6,read_TS(B)=1,read_TS(B1)=4,read_TS(B2)=4, read_TS(C)=4,read_TS(C1)=4, write_TS(A)=0,write_TS(A1)=6,write_TS(B)=0,write_TS(B1)=1,write_TS(B2)=4, write_TS(C)=0,write_TS(C1)=4 T2: ler_item(A) Executar ler_item(A) lendo o valor da versão inicial de A read_TS(A) <- max(read_TS(A),TS(T3)) = 6 read_TS(A)=6,read_TS(A1)=6,read_TS(B)=1,read_TS(B1)=4,read_TS(B2)=4, read_TS(C)=4,read_TS(C1)=4, write_TS(A)=0,write_TS(A1)=6,write_TS(B)=0,write_TS(B1)=1,write_TS(B2)=4, write_TS(C)=0,write_TS(C1)=4 T1: ler_item(B) Executar ler_item(B) lendo o valor da versão B2 read_TS(B2) <- max(read_TS(B2),TS(T3)) = 6 read_TS(A)=6,read_TS(A1)=6,read_TS(B)=1,read_TS(B1)=4,read_TS(B2)=6, read_TS(C)=4,read_TS(C1)=4, write_TS(A)=0,write_TS(A1)=6,write_TS(B)=0,write_TS(B1)=1,write_TS(B2)=4, write_TS(C)=0,write_TS(C1)=4 T1: write_item(B) Executar write_item(B) (criando uma nova versão B3 of B) write_TS(B3) <- TS(T3) = 4, read_TS(B2) <- TS(T3) = 4 read_TS(A)=6,read_TS(A1)=6,read_TS(B)=1,read_TS(B1)=4,read_TS(B2)=6, read_TS(B3)=6,read_TS(C)=4,read_TS(C1)=4, write_TS(A)=0,write_TS(A1)=6,write_TS(B)=0,write_TS(B1)=1,write_TS(B2)=4, write_TS(B2)=6,write_TS(C)=0,write_TS(C1)=4 T2: write_item(A) Abort and Rollback T2 since read_TS(A) >TS(T2)



Uma vez que T3 tinha lido o valor de B que havia sido escrito por T2, a transacção T3 deve também ser abortada e desfeita pela técnica de recuperação (cascading rollback). Como tal, todos os efeitos de T2 e T3 têm de ser desfeitos, e apenas a transacção T1 iria terminar a sua execução.


O código Java com a resolução da Pergunta 5 encontra-se online na página da disciplina.

Documents

Departamento de Engenharia Informática 2010/2011 ... · 2.3. Considere as instruções envolvidas no primeiro escalonamento apresentado. Coloque as instruções de trinco apropriadas,