© Marcelo Bezerra de AlcântaraBanco de Dados II - Revisão - 1 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

Disciplina Disciplina Banco de Dados IIBanco de Dados II

Revisão da Matéria VP2Revisão da Matéria VP2

Msc, Marcelo Bezerra de Alcântara

[email protected]


ObjetivosObjetivos

1. Revisar a matéria sobre as Técnicas de controle de concorrência – Aula 05;

2. Revisar Controle de Acesso – Aula 06;


BibliografiaBibliografia

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


Questão 1Questã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)


Resposta 1Resposta 1

lock-X(D, Tx)início

se lock(D) = ‘U’ então início

Tu = Tx lock(D) ‘X’;

fimsenã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



unlock-X(D, Tx)início

se lock(D) = ‘X' então início

se fila-WAIT(D) = vazia entãolock(D) ‘U’;

senão Obter o primeiro Tx da fila-WAIT(D) e realizar o lock desejado;

fimsenã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;

fimfim



1. Explique o princípio da técnica de bloqueio de duas fases e mostre exemplo?



• 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 fases1. 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



númerobloqueios

Gráfico de bloqueios de Tx

tempostart commit

crescimento encolhimento

ponto em que os bloqueios para todos os dados desejados por Tx

foram obtidos (Pmax(Tx))

execução de operações de Tx



• T1: r(Y) w(Y) w(Z)

• T2: r(X) r(Y) w(Y) r(Z) w(Z) • 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

• Exemplo

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

T1 T2 não garantiu SR!

T1 T2é SR! Pmax(T2)

Pmax(T1)

não é 2PL!



• Explique o que é Deadlock?



• 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 Ty



• Quais são os protocolos de prevenção de Deadlock baseado em timestamp?



• 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

tempo de start de Tx



• 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



• Explique o funcionamento do protocolo de prevenção de deadlock Cautious-Waiting?



• Princípio de Funcionamento– 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• Vantagem

– 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



• Explique os outros protocolos do 2PL (Conservador, Estrito e Rigoroso) ?


Resposta 6Resposta 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úmerobloqueiosexclusivos

tempostart commit

Pmax(Tx)

númerobloqueioscomparti-

lhados

tempostart commit

Pmax(Tx)

crescimentocresci-mento

encolhi-mento


Resposta 6Resposta 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– vantagem

• menos overhead para Tx– Tx libera tudo apenas no final!

– desvantagem• limita mais a concorrência

númerobloqueios

tempostart commit

Pmax(Tx)

crescimento


Questão 7Questão 71. Considerando a técnica TS-Básico, verifique se alguma

transação abaixo é desfeita e em que ponto a) H1 = r1(a) r2(a) r3(a) c1 c2 c3 b) H2 = r1(a) w1(a) r2(a) c1 c2c) H3 = r1(a) r1(b) r2(a) r2(b) w2(a) w2(b) c1 c2d) H4 = r1(a) r1(b) r2(a) w2(a) w1(b) c1 c2e) H5 = r2(a) w2(a) w1(a) r2(a) c1 c2f) H6 = r2(a) w2(a) r1(b) r1(c) w1(c) w2(b) c1 c2


Resposta 7Resposta 71. H1 = r1(a) r2(a) r3(a) c1 c2 c3 - OK2. H2 = r1(a) w1(a) r2(a) c1 c2 - OK3. H3 = r1(a) r1(b) r2(a) r2(b) w2(a) w2(b) c1 c2 - ok4. H4 = r1(a) r1(b) r2(a) w2(a) w1(b) c1 c2 - ok5. H5 = r2(a) w2(a) w1(a) r2(a) c1 c2 - Errado6. H6 = r2(a) w2(a) r1(b) r1(c) w1(c) w2(b) c1 c2 - OK



1. Explique o funcionamento do Scheduler Baseado em validação


Resposta 8Resposta 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


Resposta 8Resposta 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


Resposta 8Resposta 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


Pergunta 9Pergunta 9

• Quais os tipos de bloqueios de intensão e para que serve?



• 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


Questão Questão 1010

• 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+1write(tupla-X:TABELA-X)



BD

Tabela X Tabela Y

Tupla X Tupla Bn-M Tupla Y Tupla Bm-P... ...

...IS (T2)

X (T1)

IX (T1)

IX (T1) IS (T1)

S (T2)


Questão Questão 1111

• Escreve o algoritmos do TS-Básico.


Pergunta 11Pergunta 11TS-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



• Para que server o operador grant do SQL



• 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>



grant select on agencia to U1, U2, U3

grant update on deposito to U1

grant references (nome-agencia)

on agencia to U1



• Para que server a opção with grant option?



• A opção with grant option, permite ao usuário que recebeu um privilégio repassar para quem quiser.



• Para que server a operação revoke?



• 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>



revoke select on agencia from U1, U2, U3

revoke update on deposito from U1

revoke references (nome-agencia) on agencia from U1



• Para que servem os pápeis (Role) no contexto de segurança no SGBD e como ela são criadas?



• É 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.



• Sintaxe SQL:1999

CREATE ROLE nome-papel

[WITH ADMIN {CURRENT_USER | CURRENT_ROLE}]

Para remover um papel:

DROP ROLE nome-papel;



• O que são visões em um SGBD?



• 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.



• Para que servem operador create view e drop view respectivamente?



• Create view para criar uma visão• Drop view para remover



• Para que server o Audit Trail?



• Audit trail: componente de todo SGBD que armazena histórico de informações de auditoria

Documents

© Marcelo Bezerra de AlcântaraBanco de Dados II - Revisão - 1 Disciplina Banco de Dados II Revisão da Matéria VP2 Msc, Marcelo Bezerra de Alcântara [email protected]