UFSC-CTC-INE
Curso de Ciência de Computação
INE 5336
Banco de Dados II
Ronaldo S. Mello
2007/2
http://www.inf.ufsc.br/~ronaldo/ine5336
Horário Atendimento:
Quintas-feiras, das 17h30 às 19h
Programa da Disciplina
•
•
•
•
•
Objetivo
Conteúdo
Avaliação
Bibliografia
Cronograma (Previsto) de Aulas
Objetivo
Esta disciplina apresenta técnicas de
gerenciamento interno de dados utilizados
por um SGBD para processamento de
consultas e controle de transações, além de
conceitos básicos de BD Distribuído (BDD) e
SQL embutida. Ao final da disciplina, o aluno
deverá ser capaz de entender e avaliar os
mecanismos de gerenciamento de SGBDs;
conhecer os fundamentos de um BDD e ser
capaz de utilizar instruções de SQL
embutida.
1. Processamento de Consultas
i.
ii.
iii.
Conteúdo
Etapas
Otimização Algébrica
Plano de Execução
2. Gerência de Transações
i.
ii.
iii.
Introdução a Transações
Recuperação de Falhas (recovery)
Controle de Concorrência (scheduler)
3. SQL Embutida
4. Fundamentos de BDs Distribuídos
i.
ii.
iii.
iv.
Conceitos e Arquiteturas
Noções de Projeto de BDD
Processamento de Consultas
Gerência de Transações
Avaliação
• 3 Provas: P1, P2 e P3;
• 1 Trabalho de Implementação (Ti).
Conteúdo da P1: processamento de consultas;
Conteúdo da P2: gerência de transações;
Conteúdo da P3: SQL embutida e BDD.
Nota Final (NF) = (P1 + P2 + P3 + Ti) / 4
Recuperação: prova abrangendo todo o
conteúdo ministrado na disciplina (PR). Aplicase somente a alunos com 3.0 <= NF < 5.75 e
nota Ti > 0. A nova nota final (NNF) será NNF =
(NF + PR) / 2.
Bibliografia Principal
1. Elmasri, R.; Navathe S. B. Sistemas de Banco de
Dados. 4a edição. Editora Addison-Wesley. 2005.
(em inglês: Elmasri, R.; Navathe S. B. Fundamentals of
Database Systems. 4th ed. Addison-Wesley. 2003).
2. Korth, H. F.; Sudarshan, S; Silberschatz, A. Sistema de
Banco de Dados. 5a edição. Editora Campus, 2006.
3. Ramakrishnan, R., Gehrke, J. Database Management
Systems. 3th ed. McGraw Hill. 2003.
4. Date, C. J. Introdução a Sistemas de Bancos de
Dados. 8a edição. Editora Campus, 2004.
5. Özsu, M.; Valduriez, P. Princípios de Sistemas de
Banco de Dados Distribuídos. 2a ed. Editora Campus,
2001.
6. Bernstein, P. A.; Hadzilacos, V.; Goodman, N.
Concurrency Control and Recovery in Database
Systems. Addison-Wesley, 1987.
Data
Conteúdo
6/ago
apresentação;etapas processamento consultas
8/ago
otimização algébrica
13/ago
IRI 2007 (sem aula)
15/ago
IRI 2007 (sem aula)
20/ago
otimização algébrica
22/ago
plano execução
27/ago
plano execução
29/ago
plano execução
3/set
DEXA 2007 (sem aula)
5/set
DEXA 2007 (sem aula)
10/set
plano execução
12/set
plano execução
17/set
PROVA 1
19/set
introdução a transações; recovery
24/set
recovery
26/set
recovery
1/out
recovery
3/out
scheduler
8/out
scheduler
10/out
scheduler
15/out
SBBD 2007 (sem aula)
17/out
SBBD 2007 (sem aula)
22/out
scheduler
Cronograma (Previsto)
de Aulas
Data
Conteúdo
24/out
scheduler
29/out
PROVA 2
31/out
SQL embutida
5/nov
SECCOM (sem aula)
7/nov
SECCOM (sem aula)
12/nov
SQL embutida; BDD
14/nov
BDD
19/nov
BDD
21/nov
BDD
26/nov
PROVA 3
28/nov
APRESENTAÇÃO TRABALHOS
3/dez
Divulgação Notas
5/dez
RECUPERAÇÃO
Sumário
1 Processamento de Consultas
2 Introdução a Transações
3 Recuperação de Falhas
4 Controle de Concorrência
5 SQL Embutida
6 Banco de Dados Distribuído
Processamento de Consultas
• Extração de informações do BD
• Consulta SQL
– adequada para uso humano
– não adequada para processamento pelo SGBD
• não descreve uma seqüência de passos
(procedimento) a ser seguida
• não descreve uma estratégia eficiente para a
implementação de cada passo no que diz respeito ao
acesso a nível físico (arquivos do BD)
• O SGBD deve se preocupar com este
processamento!
– módulo Processador de Consultas
Módulo Processador de Consultas
• Objetivo
– otimização do processamento de uma consulta
• tradução, transformação e geração de uma estratégia
(plano) de acesso
• plano de acesso
– leva em conta: (i) algoritmos predefinidos para implementação
de passos do processamento; (ii) estimativas sobre os dados
• Vale a pena todo este esforço? Sim!
– Tx = tempo para definir e executar uma estratégia
otimizada de processamento
– Ty = tempo para executar uma estratégia nãootimizada de processamento
– Quase sempre: Tx  Ty
Etapas de Processamento
Consulta em linguagem
de alto nível
Tradução
(consulta SQL, p. ex.)
Representação interna
Transformação
(árvore algébrica da consulta)
Representação transformada
(árvore otimizada algebricamente)
Gerador de Código
Código de
Execução
Definição do
Plano de Execução
Plano de Execução
(árvore com indicação de
estratégias de acesso)
Processador Run-time
Resultado da
Consulta
Etapas de Processamento
Consulta em linguagem
de alto nível
Tradução
(consulta SQL, p. ex.)
Transformação
Representação interna
(árvore algébrica da consulta)
Definição do
Representação transformada
• análise
léxica
(árvore
otimizada
algebricamente)
Plano de Execução
- cláusulas SQL e nomes válidos
• análise sintática
- validação da gramática
Plano de Execução
•Gerador
análise semântica
de Código
(árvore com indicação de
- nomes usados de acordo com a estrutura
estratégias de acesso)
do esquema
• conversão para uma árvore algébrica
Resultado da
Código de da consulta
Processador Run-time
Consulta
Execução
Árvore (Algébrica) da Consulta
• Estrutura que representa o mapeamento da
consulta para a álgebra relacional
– uma expressão da álgebra relacional “estendida”
• pode indicar alguma computação (função agregação, atributo
calculado, ...)
– nodos folha: relações (do BD ou resultados intermediários)
– nodos internos: operações da álgebra
• Processamento da árvore
– nodos internos são executados quando seus operandos
estão disponíveis
– são substituídos pela relação resultante
– a execução termina quando o nodo raiz é executado
Exemplo de Árvore da Consulta
select m.CRM, m.nome, a.número, a.andar
from Médicos m, Ambulatórios a
where m.especialidade = ‘ortopedia’
and a.andar = 2
and m.número = a.número
 m.CRM, m.nome,
a.número, a.andar
 m.especialidade =
‘ortopedia’
 a.andar = 2
 m.número = a.número
X
Médicos
Ambulatórios
Etapas de Processamento
Consulta em linguagem
de alto nível
Tradução
(consulta SQL, p. ex.)
Representação interna
Transformação
(árvore algébrica da consulta)
Representação transformada
(árvore otimizada algebricamente)
Gerador de Código
Código de
Execução
Definição do
• definição de uma árvore de
Plano de Execução
consulta equivalente
- chega ao mesmo resultado
- processa de forma mais
Plano de Execução
eficiente
(árvorechamada
com indicação
• também
de de
estratégias de acesso)
Otimização Algébrica
Processador Run-time
Resultado da
Consulta
Exemplo de Árvore Equivalente
 m.CRM, m.nome,
a.número, a.andar
 m.CRM, m.nome,
 m.número = a.número
a.número, a.andar
 m.especialidade =
‘ortopedia’
 a.andar = 2
 m.número = a.número

X
X
 m.especialidade
a.andar = 2
= ‘ortopedia’
Médicos
Ambulatórios
Médicos
Ambulatórios
Etapas de Processamento
Consulta
linguagemde definição de
análise deem
alternativas
Tradução
de altodenível
estratégias
acesso
(consulta
SQL,
ex.)
- escolha
dep.algoritmos
para
implementação de operações
- existência de índices
Representação interna
Transformação
(árvore algébrica da consulta)
- estimativas sobre os dados
(tamanho de tabelas, seletividade, ...)
Representação transformada
(árvore otimizada algebricamente)
Gerador de Código
Código de
Execução
Definição do
Plano de Execução
Plano de Execução
(árvore com indicação de
estratégias de acesso)
Processador Run-time
Resultado da
Consulta
Exemplo de Plano de Execução
 m.CRM, m.nome,
a.número, a.andar
(processamento pipeline)
 m.número = a.número
X
(pesquisa linear)
(loop-aninhado)
 m.especialidade
= ‘ortopedia’
Médicos
a.andar = 2
(pesquisa indexada)
Ambulatórios
Etapas de Processamento
Consulta em linguagem
de alto nível
Tradução
(consulta SQL, p. ex.)
Representação interna
Transformação
(árvore algébrica da consulta)
Representação transformada
(árvore otimizada algebricamente)
Gerador de Código
Código de
Execução
Definição do
Plano de Execução
Plano de Execução
(árvore com indicação de
estratégias de acesso)
Processador Run-time
Resultado da
Consulta
Etapas de Processamento
Consulta em linguagem
de alto nível
Tradução
(consulta SQL, p. ex.)
Representação interna
Transformação
(árvore algébrica da consulta)
Representação transformada
(árvore otimizada algebricamente)
Definição do
Plano de Execução
FOCO:
OTIMIZADOR DE
CONSULTA
Plano de Execução
Gerador de Código
(árvore com indicação de
estratégias de acesso)
Código de
Execução
Processador Run-time
Resultado da
Consulta
Otimização Algébrica
• Objetivo do passo de Transformação
– entrada: árvore da consulta inicial
– saída: árvore da consulta otimizada (pode manter
a mesma árvore)
• Base
– regras de equivalência algébrica
• devem ser conhecidas pelo otimizador para que
possam ser geradas transformações válidas
– algoritmo de otimização algébrica
• indica a ordem de aplicação das regras e de outros
processamentos de otimização
Regras de Equivalência Algébrica
1. Cascata de Seleções
c1  c2  ... cn (R)  c1 (c2 (... (cn (R))))
2. Comutatividade de Seleções
c1 (c2 (R))  c2 (c1 (R))
3. Cascata de Projeções
listaAtributos1 (R)  listaAtributos1 (listaAtributos2 (...(listaAtributosN (R))))
- válido em que situação?
Regras de Equivalência Algébrica
4. Comutatividade de Seleções e Projeções
(a)
a1, a2 , ..., an (c (R))  c (a1, a2 , ..., an (R))
(b)
a1, a2 , ..., an (c (R))  c (a1, a2 , ..., an, ap, ..., at (R))
ou
- válidas em quais situações?
5. Comutatividade de Operações Produtórias (“X”)
R “X” S  S “X” R
- por “X” entenda-se: X ou X  ou
- a ordem dos atributos e tuplas do resultado não é relevante
Regras de Equivalência Algébrica
6. Comutatividade de Seleções e Operações Produtórias
(a)
c (R “X” S)  (c (R)) “X” S
(b)
c (R “X” S)  (c1 (R)) “X” (c2 (S))
ou
- válidas em quais situações?
7. Comutatividade de Projeções e Operações Produtórias
listaAtributos1 (R “X” S)  (listaAtributos2 (R)) “X” S
ou
(b) listaAtributos1 (R “X” S)  (listaAtributos2 (R)) “X” (listaAtributos3 (S)) ou
(c) listaAtributos1 (R “X” S)  listaAtributos1 ((listaAtributos2 (R)) “X”
(listaAtributos3 (S)))
(a)
- válidas em quais situações?
Regras de Equivalência Algébrica
8. Comutatividade de Operações de Conjunto
RS  SR
e
RS  SR
- por quê a “” não é comutativa?
9. Associatividade de Operações Produtórias e de Conjunto (“X”)
(R “X” S) “X” T  R “X” (S “X” T)
- por “X” entenda-se: X ou X  ou
- por quê a “” não é associativa?
ou  ou 
Regras de Equivalência Algébrica
9. Associatividade de Operações Produtórias e de Conjunto (“X”)
(R “X” S) “X” T  R “X” (S “X” T)
Observação: predicados de junção devem ser devidamente
ajustados na associatividade de operações produtórias
Exemplo: seja 1 um predicado sobre atributos de R e
S, 2 um predicado sobre atributos de S e T, e 3 um
predicado sobre atributos de R e T. Então:
(R “X” 1 S) “X” 2  3 T  R “X” 1  3 (S “X” 2 T)
Regras de Equivalência Algébrica
10. Comutatividade de Seleção e Operações de Conjunto (“”)
c (R “” S)  (c (R)) “” (c (S))
- por “” entenda-se:  ou  ou 
11. Comutatividade de Projeção e União
listaAtributos (R  S)  (listaAtributos (R))  (listaAtributos (S))
- supõe-se atributos de R e S renomeados para manter os mesmos nomes
- por quê a “” e a “” não são comutativas?
Regras de Equivalência Algébrica
12. Fusão de Seleções e Operações Produtórias
(a)
c (R X S)  R X  = 
(b)
c (R X S)  R
(c)
R X  = c S  R
c
S
S
c
- válidas em quais situações?
c
S
ou
ou
Algoritmo de Otimização Algébrica
• Algoritmo de alto (altíssimo!) nível (heurístico)
• Composto de 6 grandes passos
• Passo 1
– aplicar a regra 1
• desmembrar operações de seleção
– maior flexibilidade para mover seleções
• Passo 2
– aplicar as regras 2, 4, 6 e 10
• objetivo
– mover seleções para níveis inferiores da árvore o máximo
possível
Algoritmo de Otimização Algébrica
• Passo 3
– aplicar a regra 9
• mudar de posição sub-árvores envolvidas em
operações produtórias
• objetivos
– combinar prioritariamente sub-árvores com menor número
de dados
» investigar sub-árvores com seleções mais restritivas
– evitar produtos cartesianos
» combinações sem atributos de junção
• como saber quais as seleções mais restritivas?
– análise do grau de seletividade de um predicado
» estatística geralmente mantida no DD
Grau de Seletividade (GSai(R))
• Definido pela seguinte razão
– GSai (R) = tp(R) / |R|, onde tp(R) é o número de tuplas
que satisfazem o predicado aplicado sobre um atributo
ai em uma relação R e |R| é o número de tuplas em R
(GS  [0,1])
• GSai (R) pequeno ( 0)  seleção mais restritiva
• Um atributo chave ac possui baixo GS em
predicados de igualdade
– GSac (R) = 1 / |R|
• Geralmente mantém-se uma estimativa de
distribuição uniforme de valores de atributos
– GSai (R) = (|R| / V(ai)) / |R| = 1 / V(ai), onde V(ai) é o
número de valores distintos de ai
Algoritmo de Otimização Algébrica
• Passo 4
– aplicar a regra 12
• otimizar operações produtórias
• Passo 5
– aplicar as regras 3, 4, 7 e 11
• desmembrar e mover projeções para níveis inferiores da árvore,
tanto quanto possível, definindo novas projeções conforme se
faça necessário
• Passo 6
– identificar sub-árvores que representem grupos de
operações que possam ser executados por um único
algoritmo
• defina-os uma única vez (uma única sub-árvore) na “árvore”
Passo 6 - Exemplo
 r1, s1, s2, t1, t2
 r1, s1, s2, t1, t2
X
X
 r1 = x
s1 > y s1 > y
R
S
S
 t2 < z
 r1 = x
s1 > y
 t2 < z
T
R
S
T
Exercício – Operadores Lógicos
• Considerando que p1, p2 e p3 são
predicados de seleção, as leis abaixo são
úteis no algoritmo de otimização algébrica
(Passo 1)? Justifique suas respostas.
• Leis de De Morgan
(a)  (p1  p2)  ( p1)  ( p2)
(b)  (p1  p2)  ( p1)  ( p2)
• Leis da Distributividade
(a) p1  (p2  p3)  (p1  p2)  (p1  p3)
(b) p1  (p2  p3)  (p1  p2)  (p1  p3)