micalevisk/lista2.md

Last active December 26, 2021 17:36

Star (0) You must be signed in to star a gist
Fork (1) You must be signed in to fork a gist

Learn more about clone URLs
Clone this repository at <script src="https://gist.github.com/micalevisk/931dd32990413303b4f59d3dc0aa9a81.js"></script>
Save micalevisk/931dd32990413303b4f59d3dc0aa9a81 to your computer and use it in GitHub Desktop.

Download ZIP

coisas de Banco de Dados 1 2017/02

Raw

lista2.md

Lista de Exercícios - Álgebra Relacional

Enunciados

Respostas

Lista de Exercícios - Álgebra Relacional - (minhas) Respostas

(1)

π model (
  σ speed ≥ 3.00 (PC)
)

SELECT DISTINCT model
FROM PC
WHERE speed >= 3

(2)

A := σ hd ≥ 100 (Laptop)
π maker (Product ⨝ A)

SELECT DISTINCT maker
FROM Product
INNER JOIN
 ( SELECT * FROM Laptop WHERE hd >= 100 ) AS A
NATURAL

(3)

ProduzidosPorB := σ maker = 'B' (Product)
π model, price (ProduzidosPorB ⨝ PC)
∪ 
π model, price (ProduzidosPorB ⨝ Laptop)
∪
π model, price (ProduzidosPorB ⨝ Printer)

( SELECT DISTINCT model, price
FROM PC
INNER JOIN Product AS P NATURAL
WHERE maker = 'B' )
UNION
( SELECT DISTINCT model, price
FROM Laptop
INNER JOIN Product AS P NATURAL
WHERE maker = 'B' )
UNION
( SELECT DISTINCT model, price
FROM Printer
INNER JOIN Product AS P NATURAL
WHERE maker = 'B' )

(4)

π model (
  σ color = true ∧ type = 'laser' (Printer)
)

SELECT DISTINCT model
FROM Printer
WHERE color = true AND type = 'laser'

(5)

MakerFazPC := π maker ( σ type = 'pc' (Product) )
FazPC := Product ⨝ MakerFazPC
NaoFazPC := Product - FazPC

FazLaptop := σ type = 'laptop' (NaoFazPC)

π maker (FazLaptop)

(6)

π hd (
  σ oc ≥ 2 (
    γ hd, oc←count(hd) (PC)
  )
)

SELECT DISTINCT Hds.hd
FROM (
	SELECT hd, COUNT(hd) AS ocorrencia
	FROM PC
	GROUP BY hd
) AS Hds
WHERE Hds.ocorrencia >= 2

(7)

A1 := π m1←model, s1←speed, r1←ram (PC)
A2 := ρ m2←m1, s2←s1, r2←r1 (A1)

B := (A1) ⨝ m1 ≠ m2 ∧ s1 = s2 ∧ r1 = r2 (A2)

Pares := π m1, m2 (B)
σ m1 < m2 (Pares)

(8)

A := ( π maker, speed (Product ⨝ PC) ) ∪ ( π maker, speed (Product ⨝ Laptop) ) 

π maker ( σ speed ≥ 2.8 (A) )

(9)

Computador := (π speed, model (PC)) ∪ (π speed, model (Laptop))

-- mapear todos os fabricantes com os computadores
A := π maker, speed (Product ⨝ Computador)

-- cópia de A com os atributos 'maker' e 'speed' renomeados
B := ρ maker2←maker, speed2←speed (A)

-- deixar os maiores valores em 'speed2'
C := (A) ⨝ speed < speed2 (B)

-- deixar somente o maior valor de 'speed'
R := (π speed (A)) - (π speed (C))

-- deixar somente os fabricantes que possuem o maior valor em 'speed'
A ÷ R

(10)

A := π maker, speed (Product ⨝ PC)
B := γ maker, qtd_speed←count(speed) (A)

π maker ( σ qtd_speed ≥ 3 (B) )

(11)

A := γ maker, qtd_modelos←count(model) (Product)

σ qtd_modelos = 3 (A)

Raw

prova1_questoes.md

Considerando um disco magnético típico usado para armazenamento de dados em memória secundária, identifique, descreva e compare brevemente os componentes do tempo de acesso aos dados armazenados. O tempo de acesso para leitura ou escrita em disco requer três passos (cada um custa um tempo):

seek: busca da trilha; posicionamento do braço na trilha correta
rotação: espera para que o setor desejado seja posicionado até a cabeça de leitura/escrita
transferência: transferência dos bits (em bloco) armazenados no setor que está ao alcance da cabeça O tempo de transferência sempre será necessário, mas os outros dois podem ser ignorados se os blocos a serem lidos/escritos estiverem em setores sequenciais.

Discuta as vantagens e desvantagens em se utilizar (a) um arquivo não ordenado (b) um arquivo ordenado (c) um arquivo estático hash com buckets e encadeamento. Quais operações podem ser realizadas de maneira mais eficiente em cada um destes tipos de organização e quais são dispendiosas.
1. Um arquivo não ordenado tem seus registros inseridos sempre no final -- último bloco, logo a inserção será ótima. Consequentemente, a busca será sequencial, o que custará no desempenho.
2. Um arquivo ordenado tem melhor desempenho mas as inserções são complexas pois podem usar blocos de overflow (para reduzir o custo da inserção).
3. Um arquivo de hashing tem busca pelo campo de hashing bem rápido; as inserções também podem envolver blocos de overflow e isso prejudica o desempenho na busca. Mas é possível listar os itens ordenados de forma mais rápida que no uso de arquivos não ordenados (apesar da complexidade ser maior).
Considere um disco com blocos de B=1 Kbyte. Um apontador de blocos tem P=6 bytes e um apontador de registro tem PR=7 bytes. Um arquivo tem 50.000 registros EMPREGADO de tamanho fixo. Cada registro tem os seguintes campos: NOME (30 bytes), CPF (9 bytes), TELEFONE (9 bytes), DATANASC (8 bytes), SEXO (1 byte). Um byte adicional é usado como marcador de exclusão. Suponha que CPF é um campo-chave. Pede-se: (a) a ordem de uma árvore-B+ construída sobre CPF para este arquivo; (b) o número de blocos de índice necessários para manter os blocos 50% cheios; (c) o número de níveis da árvore neste caso.
Descreva a estrutura dos nós internos e dos nós folha de uma árvore-B+. Quais as vantagens deste tipo de estrutura em comparação com as arvores-B comuns?

Raw

prova2_questoes.md

(1) Um banco de dados é

Um conjunto de dados logicamente estruturados e que são usados para uma determinada aplicação

(2) Comparando a abordagem de banco de dados com a abordagem tradicional de processamento de arquivos, NÃO podemos afirmar que:

As aplicações que utilizam a abordagem BD apresentam, em geral, melhor tempo de execução

(3) Um modelo de dados é:

Um conjunto de conceitos que é utilizado para gerar descrições da estrutura de um banco de dados

(4) Escolha uma alternativa que contém apenas componentes da arquitetura de um SGBD típico:

Otimizador de consultas, subsistema de backups e recuperação de falhas e compilador LDD

(5) Quais as principais categorias de modelos de dados? Dê exemplos destes modelos e suas aplicações

Um modelo de BD é uma descrição dos tipos de informações que estão armazenadas nele (informa qual o tipo das informações que ele armazena). O esquema de banco de dados é uma descrição do modelo.

Uma para cada nível de abstração:

modelo conceitual
- registra QUE dados podem aparecer no BD
- representação de alto nível de abstração
- modela de forma mais natural os fatos do mundo real, suas características e relações
- preocupação semântica da aplicação
- independe de BD
- eg. modelo entidade-relacionamento
modelo lógico (ou modelos de BD)
- registra O QUE guardam os dados do BD
- representação dos dados alguma em estrutura (lógica) de armazenamento de dados
- depende de BD (mostra as ligações entre as tabelas, os atributos, etc)
- eg. modelo relacional, modelo OO
modelo físico
- registra COMO os dados estão armazenados
- organização dos arquivos de dados em disco (organização sequencial, uso de índices ou B-Trees)
- não são manipulados por usuários ou aplicações que acessam o BD
- implementação depende do SGBD

(7)

usando o https://dbis-uibk.github.io/relax/calc.htm

(a) obter nome das clínicas que tem médicos que atuam na especialidade denominada 'Geriatria'

EspeciGeriatria :=  σ Nome = 'Geriatria' (Especialidade)
Geriatras := Medico ⨝ EspeciGeriatria
Ambos  := Geriatras ⨝ ClinicaMedico

π NomeCli (Ambos ⨝ Clinica)

(b) obter os códigos dos médicos que atuam em todas as clínicas cadastradas no banco de dados

Medicos := γ CodMed, n←COUNT(CodMed) (ClinicaMedico)
TotalClinicas := γ n←COUNT(CodCli) (Clinica)

π CodMed( Medicos ÷ TotalClinicas )

(c) obter os nomes dos médicos que estão livres no dia 28/04/2016

CodMedicosLivres := π CodMed (
    σ Data ≠ '28/04/2016' (AgendaConsulta)
)

π NomeMed (Medico ⨝ CodMedicosLivres)

(d) obter uma tabela contendo as seguintes colunas: Código e nome da cada clínica, Nome de cada médico da clínica que atua na especilidade 'Obstetrícia'. Caso a clínica não tiver médicos ou, caso ela não tiver nenhum médico atuando nesta especilidade, o código e nome da clínica devem aparecer seguidos de NULL

Obstetras := σ nome = 'Obstetrícia' (Medico ⟕ Especialidade)
Clinicas := ClinicaMedico ⨝ Obstetras

π CodCli, NomeCli, NomeMed (Clinicas ⟕ Clinica)

(e) Para cada médico que atua em duas clínicas diferentes, obter nome do médico seguido do nome das clínicas

Medicos := σ qtdCli = 2 (
	γ CodMed; qtdCli←COUNT(CodCli) (ClinicaMedico)
)

MedicosClinicas := ClinicaMedico ⨝ Medicos
Nomes := Medico ⨝ MedicosClinicas 

π NomeMed, NomeCli (Nomes ⨝ Clinica)

Raw

prova2_questoes_revisao.md

Enunciados

(extra) O que são e como estão relacionados os conceitos de Esquemae Instância de Banco de Dados. Defina de forma precisa o que significa consistência de dados.

Qual a diferença entre um esquema de banco de dados e um estado ou instância de um banco de dados?
Defina os seguintes termos: domínio, atributo, tupla, esquema de relação, instância/estado de relação, grau de uma relação, esquema de um banco de dados relacional, instância/estado de um banco de dados relacional, chave
Defina chave estrangeira. Para que esse conceito é usado?
Liste as operações da álgebra relacional e a semântica de cada uma.
O que é compatibilidade de união? Por que as operações UNIÃO, INTERSEÇÃO e DIFERENÇA exigem que as relações nas quais elas forem aplicadas sejam união compatíveis?
Discuta os vários tipos de operações de junção interna. Por que a junção theta é necessária?
~~Relacione os tipos de dados que são permitidos como atributos SQL.~~
~~Como a SQL viabiliza a implementação das restrições de integridade de entidade e referencial?~~
Discuta como os NULLs são tratados em operadores de comparação na SQL. Como são tratados os NULLs quando funções agregadas são aplicadas em uma consulta em SQL? Como os NULLs são tratados se existirem em atributos agrupados?
Como a SQL implementa as restrições de integridade genéricas?
O que são triggers? Dê dois exemplos de sua utilização.
O que é uma visão em SQL e como é definida? Discuta os problemas que podem surgir quando se tenta atualizar uma visão

Respostas

(extra) O esquema é uma descrição (textual ou gráfica) da estrutura de um BD de acordo com um determinado modelo de dados (descrição das tabelas, domínios e restrições). A instância é um conjunto de dados armazenados em um banco de dados em um determinado instante de tempo. E deve seguir o esquema definido. Consistência é a propriedade que garante que todas as tuplas de uma relação obedecem o esquema da relação.

Um BD relacional é uma coleção de esquemas das relações presentes no banco de dados. O esquema especifica o nome da relação, o nome de cada atributo e o seu domínio. Uma instância de uma relação é um conjunto de tuplas, no qual cada uma tem o mesmo número de atributos que o esquema da relação. Naturalmente, cada instância deve satisfazer as restrições de domínio nesse esquema, a fim de mater a consistência.

relação é o principal construtor para representar dados no modelo relacional. Consiste em um esquema de relação e em uma instância de relação O modelo de dados é um conjunto de conceitos que podem ser usados para descrever a estrutura de um banco de dados.

termo	definição
instância/estado de relação	tabela
esquema de relação	descreve os cabeçalhos de coluna da tabela
atributo	campo ou coluna de uma relação
tupla	linha de uma relação (em um dado instante)
domínimo (de atributo)	conjunto de valores que um atributo pode assumir
grau/aridade de uma relação	número de atributos da relação
cardinalidade de uma instância	número de tuplas que a instância contém
instância/estado de um BD relacional	conjunto de instâncias de relação, uma por esquema de relação no esquema de BD (snapshot)
chave	conjunto de atributos de uma relação que devem ter valor único dentre todas as tuplas

Chave estrangeira é um tipo de restrição para relacionar relações distintas. A chave estrangeira na relação de referência deve corresponder à chave primária da relação referenciada.

União, Intersecção e Diferença
Seleção σ c (R): selecionar linhas de R que satisfazem um critério c
Projeção π L (R): selecionar colunas de R que estão listados em L separados por vírgula
Produto Cartesiano A ⨯ B: emparelha cada tupla de A com cada tupla de B
Junção Theta (e Natural) A ⨝ c B: toma o produto cartesiando das relações A e B e aplica a seleção com a condição c
Renomeação ρ R: modifica o esquema da relação
Divisão A ÷ B

A compatibilidade de união/tipo é a condição de que as duas relações sobre as quais uma as operações de conjuntos são aplicadas precisam ter o mesmo tipo de tuplas. Duas relações são consideradas compatíveis na união se tiverem o mesmo grau e cada par correspondente de atributos têm o mesmo domínio (i.e., mesmos esquemas).

Os tipos de junção interna são:

junção natural
equijunção
junção theta

A lógica das condições SQL aceita 3 valores: TRUE, FALSE e UNKNOWN. Comparando qualquer valor com NULL, retorna-se UNKNOWN

Gatilhos (triggers) são procedimentos de verificação executados quando ocorre uma condição específica. Por exemplo, inserção de tupla, atualização de valores. São mais fáceis de implementar do que restrições complexas.

Uma visão (view) é uma tabela virtual; uma relação definida em termos do conteúdo de outras tabelas ou visões. Modificações em uma view são possívels mas são limitadas a atualizações que podem ser refletidas nas tabelas base. Ainda é possível materializar a view para criar uma tabela real a partir dela.

Raw

prova3_questoes.md

Discuta suscintamente e compare as técnicas de Materialização e Pipelining para avaliação de consulta.

Duas formas de avaliação de árvores de expressão. Na Materialização os resultados das operações são armazenadas em disco como se fossem relações reais. Avalia um operador de cada vez, começando da folha para a raiz (bottom-up). E usa os resultados intermediários materializados em relações temporários para avaliar as operações dos níveis acima. As escritas e leituras dessas relações podem ser altos. Já na técnica de Pipelining os registros intermediários são encaminhados para a operação "pai" assim que gerados. Várias expressões são avaliadas simultaneamente. Tem um custo inferior mas nem sempre é aplicável (eg. hash-join, sort, etc). Pode ainda ser Orientado à Produção (push) ou Sob Demanta (pull).

Enumere e descreva os estados que uma transação pode assumir. Descreva também as ocorrências que causam as transições destes estados.

Considere a consulta abaixo.... Desenhe pelo menos duas árvores de consulta que podem representar essa consulta e compare as duas no que diz respeito a sua otimização no nível da álgebra relacional.

SELECT E.PNOME, E.UNOME, E.ENDERECO
FROM EMPREGADO E, DEPARTAMENTO D
WHERE D.DNOME='Pesquisa' AND D.NUMERO=E.DNUM

Temos uma versão com a seleção no ponto mais alto possível e outra com a mesma sendo executada mais cedo. Como o operador de seleção retorna uma relação onde o número de tuplas é menor ou igual ao original, geralmente esta relação terá menos tuplas, assim, o produto cartesiando que é realizado depois terá um impacto menor no custo pois menos tuplas serão processadas.

Com relação ao Algoritmo Merge-Join pede-se: esboço deste algoritmo em alto nível

Se os registros R e S estiverem fisicamente ordenados por valor dos atributos de junção A e B, respectivamente, podemos implementar a junção da maneira mais eficiente possível. Os dois arquivos são varridos simultaneamente na ordem dos atributos de junção, combinando os registro que têm os mesmos valores para A e B. A imagem abaixo apresenta um pseudocódigo assumindo que A e B não estão ordenados [foi retirada de ftp://vm1-dca.fee.unicamp.br/pub/docs/ricarte/apostilas/spbdaa.pdf].

Considerando as transações abaixo, use primitivas de bloqueio compartilhado ou exclusivo e de desbloqueio para construir:
1. Uma transação com 2PL não conservativo e não estrito a partir de T1;
  
  T
  
  lock(x)
  
  read_item(X)
  
  write_item(X)
  
  lock(y)
  
  unlock(x)
  
  read_item(y)
  
  write_item(y)
  
  unlock(y)
2. Uma transação com 2PL conservativo e não estrito a partir de T2;
  
  T
  
  read_lock(z)
  
  write_lock(y)
  
  write_lock(x)
  
  read_item(z)
  
  unlock(z)
  
  read_item(y)
  
  write_item(y)
  
  unlock(y)
  
  read_item(x)
  
  write_item(X)
  
  unlock(x)
3. Uma transação com 2PL não conservativo e estrito a partir de T3;
  
  T
  
  read_lock(y)
  
  read_item(y)
  
  read_lock(z)
  
  read_item(z)
  
  write_lock(y)
  
  write_item(y)
  
  unlock(y)
  
  write_lock(z)
  
  write_item(z)
  
  unlock(y)

T
lock(x)
read_item(X)
write_item(X)
lock(y)
unlock(x)
read_item(y)
write_item(y)
unlock(y)

T
read_lock(z)
write_lock(y)
write_lock(x)
read_item(z)
unlock(z)
read_item(y)
write_item(y)
unlock(y)
read_item(x)
write_item(X)
unlock(x)

T
read_lock(y)
read_item(y)
read_lock(z)
read_item(z)
write_lock(y)
write_item(y)
unlock(y)
write_lock(z)
write_item(z)
unlock(y)

T1	T2	T3
r(X)	r(Z)	r(Y)
w(X)	r(Y)	r(Z)
r(Y)	w(Y)	w(Y)
w(Y)	r(X)	w(Z)

Considerando as transações da questão anterior
1. Apresente um escalonamento não-serial destas transações e mostre que ele é serializável usando um grafo de precedência
  
  T1 T2 T3
  
  r(x)
  
  w(x)
  
  r(z)
  
  r(y)
  
  w(y)
  
  r(y)
  
  w(y)
  
  r(y)
  
  r(z)
  
  r(x)
  
  w(x)
  
  w(y)
  
  w(z)
  
  Um escalonamento serial equivalente seria: T1 → T2 → T3
2. Apresente um escalonamento não-serial destas transações e mostre que ele é não serializável (quanto ao conflito) usando um grafo de precedência
  
  T1 T2 T3
  
  r(x)
  
  w(x)
  
  r(z)
  
  r(y)
  
  r(y)
  
  r(z)
  
  r(y)
  
  w(y)
  
  w(y)
  
  r(x)
  
  w(x)
  
  w(y)
  
  w(z)

Raw

prova3_resumao_revisao.md

Processamento e Otimização de Consultas

consulta > Analisador de Consultas -> consulta analisada > Otimizador de Consultas -> plano avaliado > Avaliador de Planos de Consultas

O que é um plano de execução da consulta?

Sequência de passos executados pelo SGBD para obter a resposta a uma consulta.

Como as consultas SQL são transformadas em álgebra relacional? Como consequência, em qual classe de consultas da álgebra relacional um otimizador de consultas de concentra?

As consultas em linguagem de alto nível são otimizadas pela sua decomposição em um conjunto de unidades menores chamadas blocos (contém apenas uma clásula SELECT-FROM-WHERE). Um otimizador relacional típico se concentra na otimização de um único bloco por vez da classe de planos de profundidade à esquerda (na árvore de expressões).

Qual é o objetivo do processamento de consultas?

Transformar uma consulta escrita em uma linguagem declarativa de alto nível em uma estratégia de execução correta e eficiente expressa em uma linguagem de baixo nível. E então executar corretamente a estratégia para recuperar os dados.

Qual a principal tarefa de um otimizador?

Escolher a melhor (dentre um subconjunto de todas) estratégia de execução para processar uma consulta [a que minimiza o uso dos recursos].

Como um otimizador calcula o custo de um plano de avaliação de consulta?

Para cada plano enumerado, precisa-se estimar seu custo. Esse processo é feito em duas partes:

para cada nó na árvore, devemos estimar o custo da execução da operação correspondente;

Para cada nó na árvore, devemos estimar o tamanho do resultado e verificar se ele está ordenado.

Como um otimizador gera planos alternativos de avaliação de consulta? Qual é o espaço de planos considerado?

As equivalências algébricas formam a base da geração de planos alternativos, em conjunto com a escolha da técnica de implementação dos operadores relacionais presentes na consulta. Saber qual é o espaço de planos alternativos considerados para determinada consulta é o problema centro de um otimizador.

Como as consultas SQL aninhadas são otimizadas?

As consultas aninhadas são tratadas usando-se alguma forma de avaliação de loops aninhados.

Quais informações são armazenadas no catálogo do sistema de um SGBD e como são usadas na otimização de consultas?

Otimizadores recuperam do catálogo informações sobre os tipos e comprimentos dos campos, estatísticas sobre as relações referenciadas e os índices. Além do tamanho do arquivo, número de tuplas, número de blocos e o fator de bloco.

O que é um plano de avaliação de consultas?

Um plano consiste de uma árvore de álgebra relacional estendida, com anotações adicionais em cada nó indicando os métodos de acesso a usar por cada tabela e o método de implementação por cada operador relacional.

Cite as formas de avaliação de árvores

Materialização e Pipelining. Na materialização, os resultados das operações são armazenados em disco temporariamente. Avalia-se um operador por vez (bottom-up). É sempre aplicável mas os custos de I/O das relações temporárias pode ser alto. No pipelining, várias operações são avaliadas simultaneamente. Os resultados de uma operação são passados para a próxima assim que possível. Tem o custo inferior ao da Materialização mas seu uso nem sempre é possível (eg. hash-join, sort, etc). Há duas formas:

pipelining sob demanda (PULL; "lazy evaluation") -- o sistema requisita repetidamente a próxima tupla da operação de nível superior;

pipelining orientada à produção (PUSH; "eager") -- os operadores geram suas tuplas continuamente e passam para os operadores "pai";

Transações e Locks

O que é uma transação?

Uma transação é definida como qualquer execução única de um programa de usuário em um SGBD, ie., execução de um programa que acessa ou modifica o conteúdo de um BD. O conceito de transação é a base da execução concorrente e da recuperação de falhas de sistema em um SGBD.

Quais as propriedades das transações que são garantidas pelo SGBD? Quais são os estados de uma transação?

As 4 propriedades ACID são:

Atomicidade [gerenciador de transação] = ou todas as operações da transação são refletidas corretamente no BD ou nenhuma o será;

Consistência [responsabilidade do usuário] = toda transação enxerga uma instância consistente do BD;

Isolamento [controle de concorrência] = transações são protegidas dos efeitos do plano de execução concorrente de outras transações;

Durabilidade [log/recuperação] = persistência dos efeitos de uma transação comprometida.

Explique o "checkpoint" realizado por um SGBD

A intervalos regulares, o SGBD executa um checkpoint que consiste em:

suspender temporariamente a execução de transações;

atualizar todas as operações de escrita realizadas no banco de dados;

registrar no log uma entrada do tipo [CHECKPOINT]

liberar as execuções de transação.

Quais os principais problemas no controle de concorrência?

Atualização perdida, atualização temporária (dirty read: leituras de dirty data: dados escritos por transações não comitadas), sumarização incorreta e leitura dupla.

Por que um SGBD intercala transações

Por motivos de desempenho, assim pode realizar a concorrência das operações das transações (além de um melhor uso da CPU). Podendo aumentar o número médio de transações completadas em um determinado tempo (throughput do sistema). Além disso, a execução intercalada de uma transação curta com uma longa normalmente permite que a curta termine rapidamente (evita o starvation/inanição).

Quais tipos de anomalias as transações intercaladas podem causar?

As 3 situações anômalas podem ser descritas em termos de quando as operações de duas transações entram em conlito entre si: gravação-leitura (WR), leitura-gravação (RW) e gravação-gravação (WW).

Como um SGBD usa bloqueios para garantir intercalações corretas?

Através do uso de um protocolo de bloqueio, um conjunto de regras a ser seguidas por transação (e impostas pelo SGBD) para garantir que, mesmo intercalando as operações de várias transações, o resultado seja idêntico à execução de todas as transações em alguma ordem serial.

Qual o impacto do bloqueio no desempenho?

Bloqueio e cancelamento são os dois mecanismos básicos usados quando se usa locks para resolver conflitos entre transações. Esses mecanismos envolvem uma penalidade no desempenho: transações bloqueadas podem manter bloqueios que obriguem outras transações a esperar, e o cancelamento e o reinício de uma transação desperdiçam o trabalho feito até o momento por ela. O deadlock representa um caso extremo de bloqueio no qual um conjunto de transações fica bloqueado para sempre (a não ser que uma delas seja cancelada pelo SGBD).

Quais comandos SQL permitem que os programadores selecionem características da transação e reduzam a sobrecarga (overhead) do bloqueio?

O nível de isolamento e o modo de acesso podem ser configurados com o comando SET TRANSACTION ISOLATION LEVEL.

Como um SGBD garante a atomicidade da transação e a recuperação de falhas de sistema?

O gerenciador de recuperação (recovery manager) de um SGBD é responsável por garantir a atomicidade e a durabilidade das transações. Ele garante a atomicidade desfazendo as ações das transações que não são efetivadas (canceladas ou abortadas). Quando um SGBD é reiniciado após falhas, o gerenciador de recuperação recebe o controle deve levar o BD para um estado consistente.

Diferenças entre deadlock e concorrência

A concorrência ocorrre quando processos disputam um recurso compartilhado (causando race condition). Já o deadlock ocorre quando um conjunto de transações querem acessar um item/objeto de dados x que está bloqueado por uma outra transação que está nesse conjunto (causando uma fila circular de espera).

Em que situações duas operações em um schedule (plano de execução) são ditas "conflitantes"?

Quando pertencem a transações diferentes, acessam o mesmo item de dados X e pelo menos uma das duas é escrita X.

Quando um schedule é dito "completo"?

Um schedule S de n transações é dito ser completo se as seguintes condições ocorrem:

As operações de S são exatamente aquelas das suas n transações, inclusive as operações commit e abort como sendo as últimas operações de cada transação;

Para cada par de operações da mesma transação Ti em S, temos que a ordem em que estas operações aparecem na transação é preservada no schedule;

Para quaisquer duas operações conflitantes, uma das duas deve necessariamente ocorrer antes da outra no schedule.

Quando um schedule é dito "recuperável"?

Quando nenhuma transação T é comprometida até que todas as demais transações, que tenham escrito um item que T deve ler, estejam comprometidas [realizar commit em escritas antes que alguém precise ler].

O que é um Schedule/Escalonamento Estrito?

Nenhuma transação pode ler/escrever um item X até que a última transação que escreveu X seja comprometida ou abortada.

O que é um Schedule Serial?

É um schedule onde as operações das transações são executadas sem intercalação (ausência de concorrência); está de acordo com as propriedades ACID.

Diferencie o lock binário do lock multi-modo

O lock binário possui 2 estados: unlock e lock, enquanto o multi-modo possui 3 estados: read-lock, write-lock e unlock.
O lock binário é muito simples e restritivo, por isso não é utilizado na prática.
Garante a exclusão mútua em um item de dados.

O que é o Two-Phase Lock (2PL)?

É um protocolo para controle de concorrência baseado em bloqueios (locks).
Uma transação segue o 2PL se todos os locks (read_lock e write_lock) precedem o primeiro unlock. Na primeira fase ocorre a expansão, locks são obtidos mas nenhum é liberado. Na segunda fase ocorre a contração, locks são liberados mas nenhum novo lock é obtido.

Cite as variações do 2PL

2PL Conservativo: a transação deve bloquear todos os itens antes de iniciar, garantindo a ausência de deadlocks.

2PL Estrito*: nenhum write_lock é liberado até que a transação se efetive (execute abort ou commit); garante escalonamentos estritos.

2PL Rigoroso: nenhum write_lock ou read_lock é liberado até que a transação se efetive; mais restrito que anterior e mais simples de implementar.

Quais os quatro níveis de isolamento da SQL e quais os fenômenos (tipos de violação) que podem ocorrer em cada um?

O nível de isolamento define o comportamento da transação em relação ao controle de concorrência. Controla até que ponto uma transação é exposta às ações das outras que estão sendo executads concorrementemente.

nível	leitura suja	leitura dupla	tupla fantasma
`READ UNCOMMITED`	talvez	talvez	talvez
`READ COMMITED`	não	talvez	tavez
`REPEATABLE READ`	não	não	talvez
`SERIALIZABLE`	não	não	não

O que é um grafo de precedência no contexto de BDs? Dê um exemplo de uso.

Um plano de execução é serializável por conflito se ele for equivalente quanto ao conflito a algum plano serial. O grafo de precedência ajuda a visualizar todos os conflitos em potencial entre as transações de um PEC. Assim podemos saber se ela é serializável em relação às operações. Tendo duas transições A e B, o grafo é definido da seguinte forma: os vértices são as transações efetivadas e as arestas são criadas se o PEC tem uma das seguintes condições como verdadeira (o rótulo da aresta é o ítem de dados que está sendo compartilhado):

A executa w(X) antes de B executar r(X)

A executa r(X) antes de B executar w(X)

A executa w(X) antes de B executar w(X)

Se ocorrer ciclo no grafo, então o escalonamento é dito não serializável por conflito. EXEMPLO de um serializável por conflito:

R2(x); W3(x); C3; W1(x); C1; W2(y); R2(z); C2; R4(x); R4(y); C4;

TL;DR

Transações Atômicas: unidades lógicas de processamento sobre um BD.
Controle de Concorrência: garantia de que múltiplas transações ativadas por vários usuários produzirão resultados corretos quando manipulam o BD.
Recuperação de Falhas: garantia de que os efeitos das transações são mantidos no BD mesmo com a ocorrência de falhas.
Schedules de Transações: ordem para a execução de operações de transações; lista de ações/operações de um conjunto de transações.
Log: permite a recuperação de falhas de uma transação pois registra todas as operações que afetam os valores dos itens de dados.
Schedule Serializável: schedule não serial que equivale à um serial, ie., produzem o mesmo estado no BD.
Projeção Comprometida: schedule que contém somente as operações que pertencem a transações comprometidas.
Um schedule evita roolback em cascata se cada transação nele só lê itens que foram escritos por transações comprometidas.
Um lock/bloqueio é uma variável associada a um item de dados em um BD (geralmente 1 pra cada item). Técnica para controlar a execução concorrente de transações.
Se todas as transações de um plano seguem o 2PL, então, esse plano é garantidamente serializável (não é necessário aplicar o teste de serializabilidade).
A serialidade é o critério de correção geralmente aceito a para execução intercalada de determinado conjunto de transções.

T1	T2	T3
r(x)
w(x)
	r(z)
r(y)
w(y)
	r(y)
	w(y)
		r(y)
		r(z)
	r(x)
	w(x)
		w(y)
		w(z)

T1	T2	T3
r(x)
w(x)
	r(z)
	r(y)
		r(y)
		r(z)
r(y)
w(y)
	w(y)
	r(x)
	w(x)
		w(y)
		w(z)