Banco de dados

Banco de dados

1. Tradução de consultas SQL

   • Uma consulta SQL é traduzida para uma expressão equivalente da álgebra relacional
     • Decompostas em blocos de consultas
       • Expressão única SELECT-FROM-WHERE
   • Operadores adicionais
     • Semijunção
       • Desaninhar subconsultas
         • EXISTS, IN e ANY
           • Sintaxe não padronizada
             • T1.X S = T2.Y
               • T1 só é retornada assim que T1.X encontrar uma combinação com valor de T2.Y sem procurar outras combinações
     • Antijunção
       • Desaninhar subconsultas
         • NOT EXISTS, NOT IN e ALL
           • Sintaxe fora do padrão
             • T1.x A = T2.y
               • T1 é rejeitada assim que T1.x encontrar uma correspondência com valor de T2.y. T1 só é retornado se T.1x não corresponder a qualquer valor de T2.y

2. Algoritmos para ordenação externa

   • Componente-chave nos algoritmos de ordenação-intercalação e de eliminação
   • Refere-se à algoritmos de ordenação adequado para arquivos grandes
     • Que estão armazenados em disco e não cabem na memória principal
   • Usa a estratégia Merge-sort
     • Começa ordenando pequenos arquivos dos arquivo principal
       • Depois mescla os arquivos ordenados
         • Criam subarquivos maiores
           • Esses são intercalados
     • Exige espaço de buffer na memória principal
   • Fases
     • Ordenação
       • Parte dos arquivos que cabem no espaço buffer são lidos para a memória principal
         • Ordenados e gravados de volta para o disco com os subarquivos ordenados temporários
       • Número de pedaços iniciais é dito pelo número de blocos de arquivos e o espaço de buffer disponível
     • Intercalação
       • Os pedaços são intercalados usando um ou mais passos de intercalação
         • Cada passo de intercalação pode ter várias etapas de intercalação
       • O grau de intercalação corresponde ao número de subarquivos ordenados que podem ser mesclados na etapa de intercalação

3. Algoritmos para a operação SELECT

   • Operação de pesquisa para localizar registro de um arquivo que satisfazem uma condição
   • Tipos de algoritmos de pesquisa para seleção simples
     • S1 - Pesquisa linear
       • recupera registros e testa se seus valores satisfazem a condição de seleção
     • S2 - Pesquisa binária
       • A condição e seleção deve envolver uma igualdade sobre um atributo-chave que satisfaça a condição de seleção
     • S3a - Usando um índice primário
       • Usado se a condição de seleção envolver uma comparação de igualdade sobre um atributo-chave com um índice primário
     • S3b - Usando uma chave hash
       • Usado se a condição de seleção envolver uma comparação de igualdade sobre um atributo-chave com uma chave hash
     • S4 - Usando índice primário para recuperar registros
       • Usado se a condição de comparação for >,>=, < ou <= sobre um campo-chave para encontrar o o registro que satisfaz a igualdade
     • S5 - Usando índice de agrupamento para recuperar vários registros
       • Usado se a condição de seleção envolver uma comparação de igualdade sobre um atributo não chave com índice de agrupamento
     • S6 - Usando índice secundário em uma comparação de igualdade
       • Usado para comparação envolvendo >, >=, < ou <=. Utilizado para recuperar um único registro ou múltiplos registros
     • S7a - Usando índice bitmap
       • Usado se a condição de seleção envolver um conjunto de valores para um atributo
   • Métodos de pesquisa para seleção conjuntiva
     • S8 - Usando índice individual
       • Usado se um atributo em qualquer condição simples isolada tiver um caminho de acesso que permita o uso dos métodos S2 a S6
     • S9 - Usando índice composto
       • Usado se dois ou mais atributos estiverem envolvidos nas condições de igualdade
     • S10 - Interseção de ponteiros de registro
       • Usado se os índices secundários estiverem disponíveis em mais de um dos campos envolvidos

4. Métodos para implementar junções

   • J1 - Loop aninhado
     • Não exige caminhos de acesso especiais em nenhum arquivo na junção
   • J2 - Loop aninhado baseada em índice
     • Utiliza uma estrutura de acesso para recuperar os registros correspondentes
   • J3 - Merge-sort
     • Algoritmo eficiente de ordenação por divisão e conquista
   • J4 - Partição-hash
     • Registros são particionados em arquivos menores que os originais
       • Utilizando a função hashing
     • Junção de partição hash
       • Arquivo é particionado em várias partes e depois e juntado novamente
     • Junção hash híbrida
       • Umas das partições está diretamente ligada e incluída na fase de particionamento

5. Algoritmos para operações Projeção e de conjunto

   • Após projetar R sobre apenas as colunas na lista de atributos, quaisquer duplicatas serão removidas
   • A operação Produto Cartesiano é muito tendenciosa
     • Seu resultado inclui um registro para cada combinação de registros
     • Evitar utilizar a operação de Produto Cartesiano
       • Substituir por outras operações como a junção, por exemplo
   • Hashing também pode ser utilizado para implementar a união, interseção e a diferença
   • Uso da antijunção Diferença
     • Utilizado para subtrair o conjunto de resultados obtido pela primeira consulta SELECT do conjunto de resultados obtido pela segunda consulta SELECT
     • Existem duas variações dessa operação de conjunto
       • Union, Intersection e Expect (ou Minus)
         • Se aplicam a conjuntos tradicionais, onde não há registros duplicados no resultado
       • Union All, Intersection All e Expect All
         • Se aplicam a multiconjuntos (ou bags)

6. Operações de Agregação e tipos de Joins

   • Operadores de agregação
     • Podem ser aplicados a uma tabela inteira
       • MIN
         • Retorna o menor valor da coluna selecionada
       • MAX
         • Retorna o maior valor da coluna selecionada
       • COUNT
         • Retorna o número de linhas que corresponde a um critério especificado
       • AVERAGE
         • Retorna o valor médio de uma coluna numérica
       • SUM
         • Retorna a soma total de uma coluna numérica
   • Tipos de JOINS
     • INNER JOIN
       • Seleciona os registros que possuem valores correspondentes em ambas as tabelas
     • LEFT JOIN
       • Retorna todos os registros da tabela da esquerda e os registros correspondentes da tabela da direita
     • RIGHT JOIN
       • Retorna todos os registros da tabela da direita e os registros correspondentes da tabela da esquerda
     • FULL JOIN
       • Retorna todos os registros quando há uma correspondência na tabela esquerda ou direita

7. Iteradores para implementação de operações físicas

   • Iterador: Operação implementada que resulta em uma tupla por vez
     • Interface
       • Open
         • Inicializa o operador alocando buffers para sua entrada e saída
       • Get_next
         • Chama o método Get_next e o código da operação sobre as entradas
       • Close
         • Encerra a interação depois que as tuplas que podem ser geradas tiverem sido geradas

8. Algoritmos para processamento de consulta

   • Arquitetura de memória compartilhada
     • Vários processadores conectados a uma rede
       • Podem acessar uma região comum da memória principal
   • Arquitetura de disco compartilhado
     • Cada processador possui sua memória
       • Cada máquina tem acesso a todos os discos através da interconexão
   • Arquitetura de nada compartilhado
     • Cada processador acessa sua memória principal e armazenamento em disco
     • Níveis de paralelismo
       • Nível de Operador
         • Particionar dados entre os discos
           • Particionamento Horiontal
           • Particionamento round-robin
           • Particionamento por intervalo
       • Ordenação
       • Seleção
       • Projeção e eliminação de duplicatas
       • Junção
         • Particionada baseada em igualdade
         • Desigualdade com particionamento e replicação
         • Hash particionada em paralelo
       • Agregação
     • Paralelismo dentro da consulta
       • Execução de uma única consulta em um processo paralelo em diferentes CPU's
     • Paralelismo entre consultas
       • No paralelismo entre consultas, há uma execução de várias transações por cada CPU