Adriano da Silva Castro
Mateus de Moura Stock
Tradução das Consultas
 Transações do Usuário são convertidas em instruções
de manipulação de dados;
 Ao usuário, base de dados distribuída é única;
 Tradução deve ser correta;
 Plano gerado deve ser ótimo;
 O custo total é igual ao custo da transmissão de dados
+ custo no processamento local;
 Minimização do custo;
Processamento de Consultas
Consulta de alto
nível
SQL, OQL...
Processador de
Consultas
Comandos de
manipulação de dados
de baixo nível
Plano de Execução
Otimização
 Busca Exaustiva
 Custo;
 Solução ótima;
 Heurísticas
 Solução boa, mas não é a ótima;
 Exemplo:


Seleções antes de projeções;
Substituir junções por combinações de semi-junções.
Otimização - Granularidade
 Nível de detalhamento dos dados dentro do banco;
 Uma consulta de cada vez – não usa resultados
intermediários em comum;
 Múltiplas consultas de uma vez:
 Eficiente se existem muitas consultas similares;
 Espaço de soluções muito maior.
Otimização - Sincronização
 Estática
 Antes da execução (em tempo de compilação);
 Propagação de erros e custo acumulado em várias execuções;
 Dificuldade em fazer estimativas do banco.
 Dinâmica
 Em tempo de execução;
 Custo repetido para cada execução;
 Informação exata sobre o tamanho dos resultados intermediários;
 Híbrida
 Compilação usa algoritmo estático;
Otimização - Estatísticas
 “Objetos que contêm informações estatísticas sobre a
distribuição de valores em uma ou mais colunas de uma tabela”;
 Estimar a cardinalidade, ou número de linhas, no resultado de consulta.
 Permitem que o otimizador crie um plano de consulta de alta qualidade.
 Relações / Fragmentos
 Cardinalidade
 Tamanho das tuplas
 Fração de tuplas que participam de junções
 Atributos
 Cardinalidade do domínio;
 Número de valores distintos;
 Informação exata sobre o tamanho dos resultados intermediários;
 Premissas comuns
 Valores distintos de atributos independentes;
Otimização – Sites de Decisão
 Centralizada
 Simples; Único nó determina a “melhor” estratégia;
 Necessidade de conhecimento global do BD distribuído;
 Distribuída
 Requer apenas informações locais;
 Nós cooperam entre si para determinar a estratégia (Custos de cooperação);
 Híbrida
 Estratégia global determinada por um nó único!
 Cada nó otimiza subconsultas locais;
A maioria dos sistemas usa a abordagem de decisão centralizada
Otimização – Topologia da Rede
 WAN
 Largura de banda e velocidade baixas;
 Alta sobrecarga do protocolo;
 Estratégia global minimiza custo de comunicação;
 Custo de comunicação é dominante!
 LAN
 Broadcasting para operações de junção;
 Custo de comunicação não é tão dominante!
Metodologia
Fase 1 – Decomposição de
Consultas
 Normalização
 Transformação de qualificadores e quantificadores;
 Análise
 Reconhecer e rejeitar consultas “incorretas”;
 Simplificação
 Eliminar predicados redundantes;
 Reescrita e Reestruturação
 Cálculo  Álgebra (árvore de operadores);
 Regras de transformação (mais de uma tradução possível);
Fase 2 – Localização de Dados
 Entrada:
 Consulta algébrica das relações distribuídas
 Relação de fragmentos envolvidos
 Programa de Localização
 Substituição de cada relação global pelo seu programa
de localização



Programa em álgebra relacional
Operandos são os fragmentos
Utilizar regras de reconstrução
 Otimização
 Redução de consultas
Fase 3 – Otimização Global
 Entrada: Consulta de fragmentos
 Geração da melhor estratégia global(plano de execução de
consultas)




Minimização da função de custo
Processamento distribuído de junções
 Árvores de junção lineares x “Bushy”
 Que relação (operando) enviar para onde?
 Envio total x envio sob demanda
Decisão sobre o uso de semijunções
 Menos comunicação, mais processamento local
Métodos de junção
 Loops aninhados x junções ordenadas (“merge join” ou “hash
join”)
Processo de Otimização de
Consultas
Espaço de Busca
 Planos de execução de consulta
equivalentes
 Foco é nas árvores de junção
 Para N relações, existem O(N!) árvores
de junção equivalentes
 Comutatividade e associatividade
SELECT ENAME,RESP
FROM EMP, ASG, PROJ
WHERE EMP.ENO=ASG.ENO
AND ASG.PNO=PROJ.PNO
Espaço de Busca
 Restrição através de heurísticas
 Operações unárias antes das binárias
 Restrição da forma da árvore de junção
 Considere apenas árvores lineares, ignore as “bushy”
Fase 4 – Otimização Local
 Input: Melhor plano de execução global
 Selecionar o melhor caminho de acesso
 Usar técnicas de otimização centralizadas
Problemas
 Modelo de Custo
 Otimizações de consultas múltiplas
 Heurísticas para reduzir alternativas
 Conjunto maior de consultas
 Necessidade de tratar consultas mais complexas (uniões,
disjunções, agregações, ordenações)
 Avaliação de custo “Otimização” X “Execução”
 Intervalo entre a otimização e re-otimização
Principais Desafios
 Confiabilidade
 Como tornar o sistema tolerante a falhas

SGBDs componentes, redes de comunicação
 Durabilidade e Atomicidade
Controle de Concorrência
Distribuído
 Sincronização de acessos concorrentes
 Consistência X Concorrência
 Problemas
 Gerência de cópias múltiplas
 Falhas locais em nós
 Falha nas ligações de comunicação
 Finalização (commit) distribuída
 Bloqueio perpétuo (deadlock) distribuído
 Alternativas de Implementação
 Tempos separados para leitura e modificação
 Duas cópias da base da dados distribuída



Uma para consultas
Uma para atualizações
Atualizações periódicas na base de consultas
Aspectos Importantes
 Suporte do Sistema Operacional
 SGBDs – Aplicação muito diferente das convencionais
 Suporte apropriado a operações de bancos de dados


Situação ainda mais crítica no caso dos SBDDs
Ex: Suporte a transações distribuídas com controle de
concorrência e reconstrução
Aspectos Importantes
 Processamento de Transações Distribuído
 Manter um estado consistente da base de dados com
replicação
 Protocolos sofisticados de controle de réplicas.

O método mais imediato é o ROWA (read one write many)
 Muito caro.
 Avaliar três tipos de replicação
 Dados
 Processamento
 Comunicação
Bibliografia
 Özsu, M.T. Valduriez, P. "Principles of Distributed




Database Systems", Prentice Hall, 1999, 2ª edição
Mattoso, M.L.Q. " Introdução a Banco de Dados
Distribuídos", 2003
www.wikipedia.org/wiki/Banco_de_dados_distribuídos
www.inf.ufsc.br/~frank/BDD/
www.uniriotec.br/~fernanda.baiao/BDDDW/