Mini-Projecto 3
AOBD – 2007/2008
1 - Considere o esquema simplificado (i.e. não foram incluídos os
nomes de todos os atributos) das seguintes tabelas na base de dados
AdventureWorks e ainda a seguinte interrogação SQL.
Purchasing.Vendor(VendorID,Name)
Purchasing.PurchaseOrderHeader(PurchaseOrderID, VendorID)
Purchasing.PurchaseOrderDetail(PurchaseOrderDetailID,PurchaseOrde
rID,ProductID)
Production.Product(ProductID,Name,ListPrice)
SELECT V.Name, P.Name
FROM
Purchasing.Vendor V, Production.Product P,
Purchasing.PurchaseOrderHeader OH,
Purchasing.PurchaseOrderDetail OD
WHERE V.VendorID=OH.VendorID AND
OH.PurchaseOrderID=OD.PurchaseOrderID
AND
OD.ProductID=P.ProductID AND V.Name=’Norstan Bike Hut’ AND
P.ListPrice <=1000;
• Considere um optimizador semelhante ao introduzido nas aulas teóricas (i.e. Sistema R da
IBM). Indique quais as ordenações possíveis para as junções presentes na interrogação,
assumindo que o optimizador iria descartar planos de execução envolvendo produtos cartesianos.
Apenas planos left-deep seriam permitidos:
((V |x| OH ) |x| OD) |x| P
((P |x| OD ) |x| OH) |x| V
((OD |x| OH ) |x| V) |x| P
((OD |x| OH ) |x| P) |x| V
Uma vez que o optimizador do sistema-R iria tentar mover as selecções
para as folhas da árvore do plano de execução, os dois primeiros casos
seriam os mais prováveis de ser considerados, optando-se entre eles de
acordo com a selectividade das condições de selecção dadas sobre V e
P.
b) Qual a informação sobre estas relações que um optimizador iria necessitar para poder escolher
um bom plano de execução para a interrogação. Justifique a sua resposta.
Para estimar o custo, o optimizador iria necessitar de informação
tal como quais os índices existentes (e o seu tipo) sobre os atributos
envolvidos nos joins e selecções. Iria também necessitar
de estatísticas sobre as tabelas em questão, tais como os valores
mínimo e máximo dos índices e a distribuição dos valores, por forma a
calcular a selectividade das condições involvidas nas selecções.
c) Com a informação que tem, indique um possível plano de execução eficiente para a
interrogação, indicando os algoritmos escolhidos a cada passo e justificando a sua escolha.
Não é dada informação sobre o tamanho de cada relação ou sobre a selectividade
das operações de selecção envolvidas. Assumindo que a condição de igualdade
seria mais selectiva que a selecção de um intervalo, um plano eficiente poderia ser
projection((( selection(V) |x| OH ) |x| OD) |x| selection(P))
As selecções podem explorar índices, caso estes existam, e caso contrário seriam
calculadas usando um full-table scan. Os algoritmos de join iriam depender da
existência de índices sobre os atributos de join, por exemplo indices B+ tree sobre
os atributos do join podiam ser interessantes para o algoritmo de join sort-merge.
d) Que índices, e que tipo de índice, poderiam ser úteis para o processamento desta
interrogação.
Um indice clustered do tipo B+tree seria útil para a selecção
pelo intervalo. Um índice hash em V.name seria util para a condição de
igualdade. Índices sobre os atributos dos joins seriam provavelmente
úteis na selecção de um algoritmo de join mais eficiente.
e) Como iria o plano de execução da alínea anterior ser alterado, aquando da introdução de
um clausula
i) DISTINCT,
ii) ORDER BY P.Name ou
iii) GROUP BY P.Name na query.
i) Para suportar a operação DISTINCT, devemos ordenar os resultados (excepto
se estes já se encontrarem numa ordem pretendida) e pesquisar pelas
ocorrências diferentes. Num optimizador do tipo do sistema-R, a determinação do
plano de execução iria levar em conta o facto dos resultados virem um não numa
ordem interessante.
ii) A operação ORDER BY teria efeitos similares aos da pergunta anterior. O
optimizador iria considerar planos de execução que deixassem, como efeito
secundário, os resultados ordenados por P.name, ou então iria explicitamente
ordenar os resultados por P.name.
iii) A operação GROUP BY P.name requer que se ordenem os resultados dos
operadores anteriores por P.name por forma a posteriormente se calcularem os
agregados sobre os conjuntos de tuplos com o mesmo valor para P.name. Mais
uma vez, o optimizador iria considerar planos de execução que deixassem, como
efeito secundário, os resultados ordenados por P.name.
2. Considere o seguinte escalonamento para transacções concorrentes.
a) Liste todos os conflitos que podem ocorrer no escalonamento de transacções apresentado.
•Em T1, R1(a) entra em conflito com W3(a)
•Em T4, R4(a) entra em conflito com W3(a)
•Em T2, W2(b) entra em conflito com W3(b),W5(b)
•Em T5, R5(c) entra em conflito com W4(c)
•Em T3, W3(a) não apresenta conflitos
•Em T3, W3(b) entra em conflito com W5(b)
•Em T2, R2(c) entra em conflito com W4(c)
•Em T5, W5(b) não apresenta conflitos
•Em T2,W2(d) entra em conflito com R1(d)
•Em T4, W4(c) não apresenta conflitos
•Em T1, R(d) não apresenta conflitos
b) Construa o grafo de precedências para o escalonamento apresentado.
O grafo iria conter um nó para cada transacção e os seguintes arcos:
•De T1 para T3 (R1(a) e W3(a))
•De T2 para T1 (W2(d) e R1(d))
•De T2 para T3 (W2(b) e W3(b))
•De T2 para T4 (R2(c) e W4(c))
•De T2 para T5 (W2(b) e W5(b))
•De T3 para T5 (W3(b) e W5(b))
•De T4 para T3 (R4(a) e W3(a))
•De T5 para T4 (R5(c) e W4(c))
T2
T1
T5
T3
T4
c) O escalonamento apresentado é conflict-serializable? Justifique a sua resposta.
Existe um ciclo: T5 -> T4 -> T3 -> T5. O escalonamento
apresentado não é conflict-serializable.
d) Considere as instruções envolvidas no escalonamento apresentado. Coloque as
instruções de trinco apropriadas, obedecendo ao protocolo 2PL.
T1 - Lock-S(a); R1(a); Lock-S(d); R1(d); Unlock(d); Unlock(a);
T2 – Lock-X(b); W2(b); Lock-S(c); R2(c); Lock-X(d); W2(d); Unlock(d);
Unlock(c); Unlock(b)
T3 – Lock-X(a); W3(a); Lock-X(b); W3(b); Unlock(b); Unlock(a);
T4 – Lock-S(a); R4(a); Lock-X(c); W4(c); Unlock(c); Unlock(a);
T5 – Lock-S(c); R5(c); Lock-X(b); W5(b); Unlock(b); Unlock(c);
e) Diga o que entente por serializability e justifique se o protocolo de locking usado na
alínea d garante esta propriedade.
Um escalonamento (i.e. uma ordenação temporal para as operações das várias
transacções) é serializável se apresenta a propriedade serializability property,
i.e. se o seu resultado (i.e. os valores na base de dados) é igual ao resultado das
mesmas transacções executadas sequencialmente sem sobreposição. O
protocolo 2PL assegura conflict serializability, i.e. a equivalência com um
escalonamento série com as mesmas transacções, tal que os dois
escalonamentos tenham os mesmos conjuntos de operações em conflito
cronologicamente ordenados.
f) Podem ocorrer deadlocks sob o resultado da alínea d? Justifique a sua resposta.
O protocolo 2PL não oferece garantias sobre a não-ocorrência de
deadlocks. Por exemplo, um deadlock iria ocorrer no seguinte
escalonamento de operações obtido pela introdução de locks seguindo o
protocolo 2PL.
1 : Lock-X(A)
2 : Write(A)
3:
Lock-X(B)
4:
Write(B)
5 : Lock-X(B)
6:
Lock-X(A)
7 : ...
Num dado conjunto de instruções, um deadlock ocorre se as seguintes
condições forem encontradas:
a) Uma transacção está a usar um recurso e impede que outras o usem também.
b) Uma transacção guarda pelo menos um recurso e espera por outros.
c) As transacções têm um ciclo de dependências entre si, o qual causa
o deadlock.
3 - Considere que aquando de uma falha, o log de recuperação um
sistema de base de dados continha a seguinte informação:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
⟨checkpoint, {}, {} ⟩
⟨T1 , Begin⟩
⟨T1 , Insert , p, undoinfo, redoinfo, 105⟩
⟨T2 , Begin⟩
⟨T2 , Delete , p, undoinfo, redoinfo, 107⟩
⟨T1 , Insert , p, undoinfo, redoinfo, 106⟩
⟨T2 , Delete , p, undoinfo, redoinfo, 108⟩
⟨T1 , Insert , p, undoinfo, redoinfo, 109⟩
⟨T2 , Insert , p, undoinfo, redoinfo, 110⟩
⟨T2 , Abort⟩
⟨T2 , UNDO(Insert), undoinfo, redoinfo, 110⟩
Indique as acções envolvidas em cada passo do algoritmo de recuperação ARIES.
Assuma que no início da recuperação, o PageLSN na versão em disco da página p é 108.
Indique claramente:
•Quais os conteúdos da active-transaction-table e da dirty-page-table, reconstruídas
aquando da fase de análise.
•Qual o valor do RedoLSN.
1.Quais os updates realizados no passo de redo.
•Qual o valor do PageLSN na versão em buffer da página p, aquando do final do redo.
1.Quais as acções executadas durante o passo de undo e quais os registos efectuados no
log.
•Qual o valor do PageLSN na versão em buffer da página p, aquando do fim do undo.
1. Na fase de análise, as tabelas de active transactions e
updated pages são inicializadas como vazias.
Lendo do log, obtemos as
seguintes tabelas:
TT:
{(T1 , 111), (T2 , 114)}
DPT:
{(p, PageLSN= 114, RecLSN = 106)}
2. Obtemos RedoLSN = 106.
3 - Na fase de redo, examinamos o log desde o RedoLSN = 106.
104: ⟨checkpoint, {}, {} ⟩
105: ⟨T1 , Begin⟩
Skip
106: ⟨T1 , Insert , p, undoinfo, redoinfo, 105⟩
107: ⟨T2 , Begin⟩
Skip
108: ⟨T2 , Delete , p, undoinfo, redoinfo, 107⟩
Redo
109: ⟨T1 , Insert , p, undoinfo, redoinfo, 106⟩
Redo
110: ⟨T2 , Delete , p, undoinfo, redoinfo, 108⟩
Redo
111: ⟨T1 , Insert , p, undoinfo, redoinfo, 109⟩
Redo
112: ⟨T2 , Insert , p, undoinfo, redoinfo, 110⟩
113: ⟨T2 , Abort⟩
Redo
114: ⟨T2 , UNDO(Insert), undoinfo, redoinfo, 110⟩
4 - PageLSN=114
5-
(111)
115: T1, UNDO(Insert), ..., 109
(110)
116: T2, UNDO(Delete), ..., 108
(109)
117: T1, UNDO(Insert), ..., 106
(108)
118: T2, UNDO(Delete), ..., 107
(107)
119: T2, End
(106)
120: T1, UNDO(Insert), ..., 105
(105)
121: T1, End
6 – PageLSN = 120
b) Uma dirty-page-table reconstruída no passo de redo do algoritmo ARIES pode não ser
exactamente igual à existente durante na altura da falha? Explique que diferenças podem
ocorrer e indique o porquê da sua ocorrência.
Depois do checkpoint e antes da falha, a página p pode ter sido
enviada para o disco e removida da Dirty Page Table. A tabela
reconstruida pode incluir páginas que não estavam na tabela aquando da
falha, e o RecLSN de uma página p na tabela reconstruída pode assim
ser menor do que o RecLSN na tabela antes da falha.
c) No passo redo do algoritmo ARIES, pode-se dar o caso do PageLSN(p) ser maior ou
igual ao LSN do log record para uma modificação em p, embora na dirty-page-table
tenhamos que recLSN(p) ≤ LSN do log record. Explique a que se pode dever a
ocorrência desta situação.
Isto apenas significa que a página em disco é mais recente do
que o resultado da operação para a qual se está a fazer o redo. A
situação por acontecer, por exemplo, quando de uma falha durante um
processo de recovery.
d) No passo redo do algoritmo ARIES, um update é refeito numa página p apenas se o
PageLSN(p) for menor que o LSN do log record para a modificação. Durante o undo,
o PageLSN(p) não é inspeccionado, por forma a verificar que o update a ser desfeito
ocorreu realmente, isto é, que o PageLSN(p) é maior ou igual que o LSN do log
record. Explique porque é que esta verificação não é necessária.
A fase de redo coloca a base de dados no mesmo estado em que se
encontrava aquando da ocorrência da falha. As páginas com updates
executados por transacções activas (no buffer) aquando da falha estão
correctamente no buffer como resultado da fase de redo. Assim, sabemos
que os uptades a serem desfeitos se encontram no buffer, e não
precisamos de examinar o PageLSN.
e) Quais as acções que devem ser tomadas para uma nova falha que ocorra durante a
execução da recuperação, quando o algoritmo ARIES está no meio de i) a sua fase de
análise, ii) a fase de redo, iii) a fase de undo. Explique porquê.
Em todos os casos, recomeçamos o processo de recovery da mesma forma que aquando da
primeira falha.
• A fase de análise lê o log e inicializa algumas estruturas de dados em memoria (i.e. as tabelas
de transacções activas e de páginas actualizadas). Se uma nova falha ocorre, esta informação
é perdida e teremos de a executar a análise novamente.
ii. A fase de redo coloca a base de dados (no buffer) igual aquando da ocorrência da falha. As
páginas são trazidas do disco e actualizadas em memória. No entanto, é possível que o gestor
do buffer escreva algumas destas páginas em disco em algum momento, e portanto o
PageLSNde uma página em disco pode aumentar durante a fase de redo. Aquando de uma
segunda falha, podem existir menos operações de redo para ser executadas.
iii. Na fase de undo, são escritos os log records para as operações de undo que forem efectuadas.
Alguns destes log records podem estar já actualizados em disco quando a nova falha ocorre, o
que significa que a próxima recuperação pode fazer mais na fase de redo, uma vez que se
pode fazer o redo para todas as operações que estavam em disco. Depois da fase de redo da
nova recuperação, podemos continuar a fazer o undo das transacções que começamos a
desfazer durante a primeira recuperação, mas podemos ter menos operações para desfazer
caso as operações de undo da primeira recuperação tenham sido executadas durante a fase de
redo. Em suma, não é necessário fazer o undo das operações de undo feitas aquando da
primeira recuperação.
f) Durante a execução normal de transacções, muita informação é registada nos logs. Até
que localização (i.e. LSN) é possível apagar o início do ficheiro de log, por forma a
descartar registos antigos? Explique porquê.
Considere-se que TT é a transaction table que foi escrita para o disco, e PT é
a dirty page table criada no mesmo instante durante o checkpoint. Vamos
definir os seguintes LSNs:
n1 = min {O LSN da primeira log entry de T|T ∈ TT}
n2 = min {RecLSN(p) | p ∈ PT}
n3 = Begin-Checkpoint-LSN
Do log, podem ser descartadas as entradas que têm um LSN menor que n =
min {n1 , n2 , n3 }. Só a partir deste ponto temos a garantia que os registos
não serão usados numa tarefa de recuperação.
4 - No contexto do SQL Server 2005, explique em que consiste a técnica de log shipping
e indique para que finalidade pode a mesma ser utilizada. Indique ainda outras técnicas
suportadas pelo SQL Server 2005 para lidar com o mesmo problema.
Log shipping é uma técnica para automatizar o backup das transaction log
files num servidor SQL em produção (com uma dada periodicidade de
tempo) e fazer o restore num servidor standby. Executar continuamente o
backup e o restore das transaction log files faz com que os dois servidores
se encontrem praticamente sincronizados. Em caso de falha no servidor
em produção, basta redireccionar os utilizadores para o servidor que se
encontrava em standby. Uma técnica similar suportada pelo SQL Server
2005 dá pelo nome de database mirroring, envolvendo a gestão de duas
cópias imediatamente sincronizadas da base de dados, em dois servidores
diferentes.