Disciplina
Banco de Dados II
Revisão da Matéria VP2
Msc, Marcelo Bezerra de Alcântara
[email protected]
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 1
Objetivos
1. Revisar a matéria sobre as Técnicas
de controle de concorrência – Aula 05;
2. Revisar Controle de Acesso – Aula 06;
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 2
Bibliografia
1. ELMASRI, Ramez; NAVATHE,
Shamkant B, Sistemas de banco de
dados. 4. ed. Pearson Brasil, 2005.
Capítulo 17 e 18
2. KORTH, Henry F.; SILBERSCHATZ,
Abraham Sistemas de banco de
dados. 3. ed, São Paulo: Makron
Books, 1999. Capítulo 13 e 14
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 3
Questão 1
1. Proponha algoritmos de alto nível para as
operações:
a) lock-X(D, Tx)
b) unlock(D, Tx) (considere que essa operação também pode
retirar transações da fila-WAIT e solicitar novos bloqueios)
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 4
Resposta 1
lock-X(D, Tx)
início
se lock(D) = ‘U’ então
início
Tu = Tx
lock(D)  ‘X’;
fim
senão se lock(D) = ‘S’ então insere Tx na fila-WAIT(D)
senão /* lock(D) = ‘X’ */ insere (Tx, ‘S’) na fila-WAIT(D);
fim
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 5
Resposta 1
unlock-X(D, Tx)
início
se lock(D) = ‘X' então
início
se fila-WAIT(D) = vazia então
lock(D)  ‘U’;
senão
Obter o primeiro Tx da fila-WAIT(D) e realizar o
lock desejado;
fim
senão se lock(D) = ‘S’ então
início
remove Tx da fila-READ(D)
se fila-READ(D) = vazia então lock(D)=U;
fim
fim
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 6
Questão 2
1. Explique o princípio da técnica de bloqueio
de duas fases e mostre exemplo?
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 7
Resposta 2
•
Premissa
– “para toda transação Tx, todas as operações
de bloqueio de dados feitas por Tx precedem
a primeira operação de desbloqueio feita por
Tx”
•
Protocolo de duas fases
1. Fase de expansão ou crescimento
•
Tx pode obter bloqueios, mas não pode liberar
nenhum bloqueio
2. Fase de retrocesso ou encolhimento
•
Tx pode liberar bloqueios, mas não pode obter
nenhum bloqueio
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 8
Resposta 2
Gráfico de bloqueios de Tx
número
bloqueios
ponto em que os bloqueios para
todos os dados desejados por Tx
foram obtidos (Pmax(Tx))
crescimento
start
encolhimento
execução de operações de Tx
© Marcelo Bezerra de Alcântara
commit
tempo
Banco de Dados II - Revisão - 9
Resposta 2
• T1: r(Y) w(Y) w(Z)
• T2: r(X) r(Y) w(Y) r(Z) w(Z)
não é 2PL!
• Contra-Exemplo
HN-2PL = lx1(Y) r1(Y) ls2(X) r2(X) u2(X) w1(Y) u1(Y) lx2(Y)
r2(Y) w2(Y) u2(Y) lx2(Z) r2(Z) w2(Z) c2 lx1(Z) w1(Z)
u1(Z) c1
T1
• Exemplo
T2
não garantiu SR!
Pmax(T1)
H2PL = ls2(X) r2(X) lx1(Y) r1(Y) lx1(Z) w1(Y) u1(Y) lx2(Y)
r2(Y) w1(Z) u1(Z) c1 w2(Y) lx2(Z) u2(X) u2(Y) w2(Z)
u2(Z) c2
T2
Pmax(T2)
é SR! T1
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 10
Questão 3
• Explique o que é Deadlock?
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 11
Resposta 3
•
Ocorrência de deadlock
– Ty está na Fila-WAIT(D1) de um dado D1
bloqueado por Tx
– Tx está na Fila-WAIT(D2) de um dado D2
bloqueado por Ty
•
Pode ser descoberto através de um grafo
de espera de transações
– se o grafo é cíclico existe deadlock!
Tx
© Marcelo Bezerra de Alcântara
Ty
Banco de Dados II - Revisão - 12
Questão 4
• Quais são os protocolos de prevenção de
Deadlock baseado em timestamp?
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 13
Resposta 4
•
tempo de start de Tx
Timestamp
– rótulo de tempo associado à Tx (TS(Tx))
•
Técnicas
– consideram que Tx deseja um dado bloqueado
por outra transação Ty
– Técnica 1: esperar-ou-morrer (wait-die)
•
se TS(Tx) < TS(Ty) então Tx espera
senão início
abort(Tx)
start(Tx) com o mesmo TS
fim
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 14
Resposta 4
•
Técnicas (cont.)
–
Técnica 2: ferir-ou-esperar (wound-wait)
•
–
se TS(Tx) < TS(Ty) então
início
abort(Ty)
start(Ty) com o mesmo TS
fim
senão Tx espera
vantagem das técnicas
•
evitam starvation (espera indefinida) de uma Tx
–
–
quanto mais antiga for Tx, maior a sua prioridade
desvantagem das técnicas
•
muitos abortos podem ser provocados, sem nunca ocorrer
um deadlock
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 15
Questão 5
• Explique o funcionamento do protocolo de
prevenção de deadlock Cautious-Waiting?
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 16
Resposta 5
•
Princípio de Funcionamento
–
•
Vantagem
–
•
se Tx deseja D e D está bloqueado por Ty
então
se Ty não está em alguma Fila-WAIT
então Tx espera
senão início
abort(Tx)
start(Tx)
fim
se Ty já está em espera, Tx é abortada para evitar um
possível ciclo de espera
Desvantagem
–
a mesma das técnicas baseadas em timestamp
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 17
Questão 6
• Explique os outros protocolos do 2PL
(Conservador, Estrito e Rigoroso) ?
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 18
Resposta 6
•
Scheduler 2PL Conservador ou Estático
– evita deadlock, porém Tx pode esperar muito
para executar
•
Scheduler 2PL Estrito (muito usado pelos SGBDs)
– Tx só libera seus bloqueios exclusivos após
executar commit ou abort
número
bloqueios
compartilhados
Pmax(Tx)
cresci- encolhimento mento
commit tempo
start
© Marcelo Bezerra de Alcântara
número
bloqueios
exclusivos
Pmax(Tx)
crescimento
start
commit
tempo
Banco de Dados II - Revisão - 19
Resposta 6
•
Scheduler 2PL Estrito
– vantagem: garante escalonamentos estritos
– desvantagem: não está livre de deadlocks
•
Scheduler 2PL (Estrito) Rigoroso
– Tx só libera seus bloqueios após executar
commit ou abort
número
bloqueios
– vantagem
•
menos overhead para Tx
Pmax(Tx)
– Tx libera tudo apenas no final!
crescimento
– desvantagem
•
limita mais a concorrência
© Marcelo Bezerra de Alcântara
start
commit
tempo
Banco de Dados II - Revisão - 20
Questão 7
1.
Considerando a técnica TS-Básico, verifique se alguma
transação abaixo é desfeita e em que ponto
a) H1 = r1(a)
b) H2 = r1(a)
c) H3 = r1(a)
d) H4 = r1(a)
e) H5 = r2(a)
f) H6 = r2(a)
© Marcelo Bezerra de Alcântara
r2(a) r3(a) c1 c2 c3
w1(a) r2(a) c1 c2
r1(b) r2(a) r2(b) w2(a) w2(b) c1 c2
r1(b) r2(a) w2(a) w1(b) c1 c2
w2(a) w1(a) r2(a) c1 c2
w2(a) r1(b) r1(c) w1(c) w2(b) c1 c2
Banco de Dados II - Revisão - 21
Resposta 7
1.
2.
3.
4.
5.
6.
H1 = r1(a)
H2 = r1(a)
H3 = r1(a)
H4 = r1(a)
H5 = r2(a)
H6 = r2(a)
r2(a) r3(a) c1 c2 c3 - OK
w1(a) r2(a) c1 c2 - OK
r1(b) r2(a) r2(b) w2(a) w2(b) c1 c2 - ok
r1(b) r2(a) w2(a) w1(b) c1 c2 - ok
w2(a) w1(a) r2(a) c1 c2 - Errado
w2(a) r1(b) r1(c) w1(c) w2(b) c1 c2 - OK
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 22
Questão 8
1. Explique o funcionamento do Scheduler
Baseado em validação
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 23
Resposta 8
•
Técnica na qual atualizações de uma
transação Tx são feitas sobre cópias locais
dos dados
• Quando Tx solicita commit é feita a sua
validação
– Tx violou a serializabilidade?
• SIM: Tx é abortada e reiniciada
posteriormente
• NÃO: atualiza o BD a partir das cópias dos
dados e encerra Tx
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 24
Resposta 8
•
Cada transação Tx passa por 3 fases:
1. Leitura
• Tx lê dados de transações committed do BD
e atualiza dados em cópias locais
2. Validação
• análise da manutenção da serializabilidade
de conflito caso as atualizações de Tx
sejam efetivadas no BD
3. Escrita
• se fase de Validação for OK, aplica-se as
atualizações de Tx no BD e Tx encerra com
sucesso; caso contrário, Tx é abortada
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 25
Resposta 8
• Vantagens
– reduz o overhead durante a execução de Tx
– evita aborto em cascata
• Tx não grava no BD antes de suas atualizações
serem validadas em memória
– se Tx interfere em outra Ty committed ou em validação,
suas atualizações são descartadas
• Desvantagem
– se houve interferência entre Tx e outras
transações (isso não é esperado pois a técnica é
otimista), isso é descoberto somente ao final da
execução de Tx (na validação) e só após essa
validação Tx pode ser reiniciada
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 26
Pergunta 9
• Quais os tipos de bloqueios de intensão
e para que serve?
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 27
Resposta 9
• Indicam, em grânulos mais grossos, que Tx está
bloqueando algum dado em um grânulo mais fino
– vê o BD como uma árvore de grânulos
• Tipos de bloqueios de intenção
– IS (Intention-Shared)
• indica que um ou mais bloqueios compartilhados serão
solicitados em nodos descendentes
– IX (Intention-eXclusive)
• indica que um ou mais bloqueios exclusivos serão solicitados
em nodos descendentes
– SIX (Shared-Intention-eXclusive)
• bloqueia o nodo corrente no modo compartilhado, porém um ou
mais bloqueios exclusivos serão solicitados em nodos
descendentes
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 28
Questão 10
• Dada a transação abaixo, indique os
bloqueios necessários para executar a
transação considerando os níveis: Banco
– Tabela - Tupla.
read(tupla-X:TABELA-X)
read(tupla-Y:TABELA-Z)
x:=x+1
write(tupla-X:TABELA-X)
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 29
Resposta 10
IX (T1)
BD
IX (T1) Tabela X
Tupla X
Tabela Y
Tupla Bn-M
X (T1)
© Marcelo Bezerra de Alcântara
...
IS (T2)
Tupla Y
IS (T1)
...
Tupla Bm-P
...
S (T2)
Banco de Dados II - Revisão - 30
Questão 11
• Escreve o algoritmos do TS-Básico.
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 31
Pergunta 11
TS-Básico(Tx, dado, operação)
início
se operação = ‘READ’ então
se TS(Tx) < R-TS(dado).TS-Write então
início abort(Tx);
restart(Tx) com novo TS;
fim
senão início executar read(dado);
se R-TS(dado).TS-Read < TS(Tx) então
R-TS(dado).TS-Read  TS(Tx);
fim
senão início /* operação = ‘WRITE’ */
se TS(Tx) < R-TS(dado).TS-Read OU
TS(Tx) < R-TS(dado).TS-Write então
início abort(Tx);
restart(Tx) com novo TS;
fim
senão início
executar write(dado);
R-TS(dado).TS-Write  TS(Tx);
fim
fim
fim
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 32
Questão 12
• Para que server o operador grant do
SQL
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 33
Resposta 12
• O Comando grant é usado para
conferir autorização. A forma básica
deste comando é:
grant <lista de privilégios>
on <nome da relação ou visão>
to <lista de usuários>
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 34
Resposta 12
grant select on agencia to U1, U2, U3
grant update on deposito to U1
grant references (nome-agencia)
on agencia to U1
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 35
Questão 13
• Para que server a opção with grant
option?
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 36
Resposta 13
• A opção with grant option, permite ao
usuário que recebeu um privilégio
repassar para quem quiser.
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 37
Questão 14
• Para que server a operação revoke?
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 38
Resposta 14
• Para revogar a autorização, o comando
revoke é usado. Ele toma a forma
quase idêntica àquela do comando
grant:
revoke <lista de privilégios>
on <nome da relação ou visão>
from <lista de usuários>
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 39
Resposta 14
revoke select on agencia from U1, U2,
U3
revoke update on deposito from U1
revoke references (nome-agencia) on
agencia from U1
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 40
Questão 15
• Para que servem os pápeis (Role) no
contexto de segurança no SGBD e como
ela são criadas?
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 41
Resposta 15
• É um identificador ao qual pode-se
atribuir privilégios que não existem a
princípio. Então pode-se atribuir a um
usuário este papel (conjunto de
privilégios) com um único comando
GRANT.
• Pode-se inclusive ao criar um papel usar
outros papéis já cadastrados.
• Ex. PapelVendedor,
PapelVendedorSapatos,
PapelVendedoFrutas.
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 42
Resposta 15
• Sintaxe SQL:1999
CREATE ROLE nome-papel
[WITH ADMIN {CURRENT_USER |
CURRENT_ROLE}]
Para remover um papel:
DROP ROLE nome-papel;
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 43
Questão 16
• O que são visões em um SGBD?
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 44
Resposta 16
• Uma visão, na terminologia SQL, é uma
tabela única e derivada de outra tabela, que
pode ser uma tabela básica ou uma visão
previamente definida. Uma visão não existe
de forma física, ela é considerada uma
tabela virtual, em contraste com as tabelas
básicas, cujas tuplas são realmente
armazenadas no banco de dados. Isso
limita as operações de atualização possíveis
para as visões, embora não imponha
nenhuma limitação para consultas.
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 45
Questão 17
• Para que servem operador create view e
drop view respectivamente?
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 46
Resposta 17
• Create view para criar uma visão
• Drop view para remover
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 47
Questão 18
• Para que server o Audit Trail?
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 48
Resposta 18
• Audit trail: componente de todo SGBD
que armazena histórico de informações
de auditoria
© Marcelo Bezerra de Alcântara
Banco de Dados II - Revisão - 49