Livro - Banco de Dados II_compressed

Prévia do material em texto

Código Logístico
59714
BANCO DE DADOS II
Paulo Sérgio Cougo
Fundação Biblioteca Nacional
ISBN 978-85-387-6717-6
9 7 8 8 5 3 8 7 6 7 1 7 6
Banco de Dados II 
Paulo Sérgio Cougo
IESDE BRASIL
2021
Todos os direitos reservados.
IESDE BRASIL S/A. 
Al. Dr. Carlos de Carvalho, 1.482. CEP: 80730-200 
Batel – Curitiba – PR 
0800 708 88 88 – www.iesde.com.br
© 2021 – IESDE BRASIL S/A. 
É proibida a reprodução, mesmo parcial, por qualquer processo, sem autorização por escrito do autor e do 
detentor dos direitos autorais.
Projeto de capa: IESDE BRASIL S/A. Imagem da capa: DrHitch/Shutterstock
CIP-BRASIL. CATALOGAÇÃO NA PUBLICAÇÃO 
SINDICATO NACIONAL DOS EDITORES DE LIVROS, RJ
C892b
Cougo, Paulo Sérgio
Banco de dados II / Paulo Sérgio Cougo. - 1. ed. - Curitiba [PR] : Iesde, 
2021.
114 p. : il.
Inclui bibliografia
ISBN 978-85-387-6717-6
1. Banco de dados. 2. Banco de dados - Gerência. 3. Sistemas de recu-
peração da informação. 4. Estruturas de dados (Computação). 5. Organiza-
ção de arquivos - Computação. I. Título.
21-68695 CDD: 005.7
CDU: 004.658
Paulo Sérgio Cougo Pós-graduado em Análise de Sistemas na Administração 
de Empresas pela Pontifícia Universidade Católica do 
Paraná (PUCPR). Tecnólogo em Processamento de Dados 
pela Universidade Federal do Paraná (UFPR). Profissional 
com atuação nas funções de administrador de banco 
de dados e administrador de dados. Responsável 
pela modelagem e pelo projeto e monitoramento de 
bancos de dados corporativos. Instrutor de cursos de 
modelagem de banco de dados e professor em curso de 
pós-graduação em banco de dados. Autor e revisor de 
livros sobre modelagem e projeto de banco de dados.
Agora é possível acessar os vídeos do livro por 
meio de QR codes (códigos de barras) presentes 
no início de cada seção de capítulo.
Acesse os vídeos automaticamente, direcionando 
a câmera fotográ�ca de seu smartphone ou tablet 
para o QR code.
Em alguns dispositivos é necessário ter instalado 
um leitor de QR code, que pode ser adquirido 
gratuitamente em lojas de aplicativos.
Vídeos
em QR code!
SUMÁRIO
1 Armazenamento e estruturas de dados 9
1.1 Armazenamento em disco 10
1.2 Organização de arquivos 17
1.3 Técnicas de hashing 21
1.4 Estrutura de indexação de arquivos 24
2 Processamento e otimização de consultas 31
2.1 Medidas de avaliação de custo de consultas 31
2.2 Avaliação de expressões 39
2.3 Algoritmos para processamento e otimização 47
3 Gerenciamento de transações 54
3.1 Conceitos de transações 55
3.2 Propriedades de uma transação 59
3.3 Suporte a transações no SQL 66
3.4 Técnicas de controle de concorrência 69
4 Técnicas de recuperação em banco de dados 75
4.1 Classificação das falhas 76
4.2 Estruturas de recuperação 80
4.3 Técnicas de recuperação 85
5 Data warehousing e data mining 93
5.1 Conceitos 94
5.2 Arquitetura 102
5.3 Aplicabilidade 106
 Gabarito 110
Agora é possível acessar os vídeos do livro por 
meio de QR codes (códigos de barras) presentes 
no início de cada seção de capítulo.
Acesse os vídeos automaticamente, direcionando 
a câmera fotográ�ca de seu smartphone ou tablet 
para o QR code.
Em alguns dispositivos é necessário ter instalado 
um leitor de QR code, que pode ser adquirido 
gratuitamente em lojas de aplicativos.
Vídeos
em QR code!
A utilização de estruturas de banco de dados para dar suporte 
aos sistemas de informação já é comum entre projetistas de grande 
parte dos sistemas corporativos, departamentais e até pessoais.
Apesar de os sistemas gerenciadores de bancos de dados 
(SGBD) simplificarem excessivamente as tarefas de manipulação 
dos dados, ainda podemos considerar como essencial 
conhecer quais são esses tratamentos e processos executados 
automaticamente pelos SGBD.
Com o intuito de melhor organizar o conhecimento das técnicas 
utilizadas por um SGBD e compreender a importância de se tomar 
alguns cuidados durante o projeto e a construção dos nossos 
bancos de dados, organizamos este livro em cinco capítulos. 
No Capítulo 1 veremos quais são as estruturas físicas 
utilizadas por um sistema gerenciador de banco de dados para 
armazenar e recuperar os dados. Reconheceremos as estruturas 
de organização de arquivos utilizadas na criação de um banco 
para recuperação de dados por meio de índices, mediante a 
utilização de técnicas de hashing e indexação.
Já no Capítulo 2, tendo compreendido como os dados são 
organizados e mantidos, trataremos das técnicas de otimização 
de consultas utilizadas pelos sistemas gerenciadores de bancos 
de dados, de modo a permitir que os comandos SQL possam 
ter sua estrutura declarativa transformada em uma estrutura 
procedimental otimizada.
No Capítulo 3 apresentaremos as técnicas de gerenciamento 
de transações concorrentes, permitindo que vários processos 
possam consultar e atualizar simultaneamente o mesmo conjunto 
de dados. Conheceremos quais são as características de uma 
transação e como elas asseguram a manutenção da integridade de 
um banco de dados. Também entenderemos como o SQL permite 
que o controle de concorrência seja executado com sucesso.
Chegando ao Capítulo 4, abordaremos os tipos de falha 
que podem ocorrer e os recursos de recuperação de falhas 
que um SGBD pode prover, bem como as estruturas de dados 
APRESENTAÇÃOVídeo
8 Banco de Dados II
complementares que o sistema cria para permitir que as integridades lógica e 
física de um banco de dados sejam asseguradas.
Já no Capítulo 5, após conhecermos todas as técnicas e as estruturas 
utilizadas pelos SGBD para assegurar a integridade de um banco de dados 
transacional, estudaremos as estruturas de dados, o processo de modelagem 
e a criação de data warehouses e data smarts focados em sistemas de apoio 
à decisão. Veremos também as diferenças de abordagem entre os sistemas 
transacionais (OLTP) e de apoio à decisão (OLAP).
Com todo esse conteúdo, participaremos de uma jornada que apresentará 
desde os primeiros conceitos, passando por métodos e técnicas para 
gerenciamento seguro de dados, chegando até estruturas não convencionais 
orientadas a sistemas de apoio à decisão. Esperamos que você tenha uma 
gratificante experiência.
Bons estudos!
Armazenamento e estruturas de dados 9
1
Armazenamento e 
estruturas de dados
Todos os aspectos envolvidos na modelagem conceitual, 
lógica e física de um banco de dados requerem que estruturas 
físicas de armazenamento sejam utilizadas para materializar e 
tornar fisicamente acessíveis os dados do banco projetado e 
criado.
As melhores práticas utilizadas para o projeto irão requerer 
também tecnologias equivalentes para produzir os resultados 
de desempenho, segurança, acessibilidade e compartilhamen-
tos desejados. De pouco adiantaria ter planejado um banco de 
dados com altos requisitos de compartilhamento e desempe-
nho, se pelo lado da oferta tecnológica não houver meios para 
liberar esses resultados aos usuários.
A oferta de diferenciais tecnológicos por diferentes fabri-
cantes, tanto de software como de hardware, acaba, por fim, 
por determinar o alcance ou não dos resultados esperados 
pelas áreas de negócio das corporações que dependem dos 
bancos de dados para o sucesso de suas operações.
Neste capítulo veremos os conceitos e estruturas físicas 
utilizadas para o armazenamento e acesso aos dados físicos 
nos bancos de dados. Por meio desta abordagem poderemos 
reconhecer as estruturas físicas de armazenamento de dados 
em disco, os modelos de organização de arquivos, as alternati-
vas para construção de índices de acesso, bem como ver como 
estas impactam as estruturas de bancos de dados em sua cria-
ção e manipulação.
10 Banco de Dados II
1.1 Armazenamento em disco 
Vídeo Desde os primórdios da informática, um desafio sempre fez parte 
do dia a dia dos profissionais desta área: como e onde armazenar os 
dados. Com a habilidade da informática de simular a capacidade hu-
mana de interpretar, decidir, avaliar, transformar e produzirdados, o 
primeiro desafio do armazenamento de dados, que era o próprio pro-
cessamento dos dados, deixava de ser o foco. Mesmo os computado-
res mais rudimentares, por meio de um modelo de máquinas baseado 
em processamento sequencial de comandos, tinham então a capaci-
dade de processar dados, oferecendo um processamento com maior 
velocidade, para volumes maiores e com menores taxas de erro. O de-
safio de reproduzir a capacidade de processamento humano havia sido 
superado pelas máquinas.
Mas e o que dizer sobre a capacidade de reter grandes volumes de 
dados para servirem de entrada para estes programas e de reter os 
dados produzidos como saídas por estes programas? Um novo desafio 
então surgiu e, com o passar do tempo, várias alternativas foram cria-
das. O armazenamento de dados passou então por várias gerações, 
desde os cartões perfurados, as fitas perfuradas, as fitas magnéticas, 
os discos magnéticos, chegando hoje até os discos de estado sólido, 
cada um com suas características, benefícios e desvantagens.
Hoje, quando falamos em armazenamento físico de dados, seja ele 
de uma simples mensagem, de um documento, de uma agenda, ou 
até de um banco de dados corporativo, várias opções surgem como 
alternativas. Do pequeno ao grande dispositivo, do pequeno ao grande 
banco de dados, quase tudo pode ser armazenado em vários tipos de 
dispositivos. Imagine hoje quantos gigabytes um simples telefone celu-
lar é capaz de armazenar – sejam eles sob a forma de agendas, bancos 
de dados de contatos, banco de dados de imagens etc.
Dentre os dispositivos de armazenamento mais comumente encon-
trados nos dispositivos eletrônicos baseados em microprocessadores, 
podemos ter:
 • Memória Cache
Este tipo de memória é aquela utilizada para o armazenamento de 
dados perenes ou temporários; é um dos componentes básicos asso-
Armazenamento e estruturas de dados 11
ciados ao próprio processador. Essa é a forma mais rápida de memória 
para acesso de dados, porém é também a mais cara. Ela é normalmen-
te limitada e pequena (um processador Intel 7, por exemplo, pode ter 
até o máximo de 12 megabytes de cache) e não é um tema de preocu-
pação quanto se fala de um banco de dados. Não é, portanto, usada 
por um software gerenciador de banco de dados para a manipulação 
dos dados.
 • Memória principal (ou memória RAM, Random Access Memory)
A memória RAM é uma que já pode ter maior capacidade de arma-
zenamento – da ordem dos gigabytes, podendo chegar a terabytes –, 
mas ainda não é usada como fonte de armazenamento perene de da-
dos, devido ao fato de depender de energização para retenção de seus 
dados. Caso ocorra a interrupção do fornecimento de energia, essa 
memória deixará de reter os dados nela carregados. Ela tem um papel 
importante no cenário dos gerenciadores de banco de dados, pois será 
utilizada como meio de aceleração para acesso aos dados usados mais 
frequentemente. Ou seja, aquela porção do banco de dados acessada 
com maior frequência será carregada na memória RAM, pois o acesso 
dela é muito mais rápido.
 • Memória flash
Esta memória difere da memória principal tradicional, pois os dados 
armazenados numa memória flash não são perdidos em caso de in-
terrupção do fornecimento de energia. Podemos então utilizá-las para 
armazenamento perene de dados. Essas são as memórias utilizadas 
mais recentemente para dar origem aos discos de estado sólido, que 
na verdade não são discos, mas sim bancos de memória, compostos 
por vários chips de memória flash. É uma tecnologia promissora que 
promete substituir os discos magnéticos.
 • Discos magnéticos
Estes têm sido ao longo de décadas o meio mais efetivo para o ar-
mazenamento de grandes volumes de dados. Há décadas os discos 
magnéticos de uso corporativo não chegavam a armazenar sequer 512 
megabytes. Hoje, facilmente você irá encontrar um notebook para uso 
pessoal com um disco magnético de mais de 1 terabyte. Os sistemas 
gerenciadores de banco de dados se baseiam predominantemente 
nesse tipo de armazenamento.
No vídeo Como funciona 
a memória cache?, 
publicado pelo canal 
The Hardware Show, 
você verá a arquitetura 
básica de um processa-
dor e como a memória 
cache se insere neste 
contexto. Uma aborda-
gem bastante didática 
e esclarecedora poderá 
lhe trazer informações, 
como os benefícios e 
restrições que a memória 
cache apresenta para a 
otimização de tempo de 
processamento das ins-
truções e para o tempo 
de acesso a dados.
Disponível em: https://
www.youtube.com/
watch?v=uS3XnXgr1DE. Acesso 
em: 24 nov. 2020.
Vídeo
https://www.youtube.com/watch?v=uS3XnXgr1DE
https://www.youtube.com/watch?v=uS3XnXgr1DE
https://www.youtube.com/watch?v=uS3XnXgr1DE
12 Banco de Dados II
 • Discos de estado sólido (Solid State Drive – SSD)
A tecnologia de discos magnéticos evoluiu incrivelmente nos últi-
mos anos, produzindo discos fisicamente menores, mas com capaci-
dades de armazenamento enormes. Com a capacidade que possui, um 
disco que hoje está dentro de um notebook, décadas atrás ocuparia 
uma sala com uma área de mais de 10m², exigindo toda uma estrutura 
de ar condicionado, piso falso (para manutenção) etc. Porém, o fato de 
serem menores e terem maior capacidade não foi suficiente. Os discos 
de antigamente esbarraram no limite de tempo demandado para me-
canicamente acessarem os dados que estavam gravados em suas su-
perfícies, isto é, tornaram-se lentos se comparados aos acessos feitos 
eletronicamente em memória RAM, e este tempo não poderia mais ser 
baixado. Surge então a ideia de agrupar vários chips de memória flash 
para criar discos de estado sólidos. Teríamos alta capacidade de arma-
zenamento, pequeno espaço físico e ausência de movimentos mecâni-
cos, ou seja, alta velocidade de acesso.
 • Discos óticos
Com o objetivo de superar os limites mecânicos e físicos do arma-
zenamento dos discos magnéticos, um novo método de armazena-
mento e leitura de dados foi desenvolvido. O Compact Disc Read-Only 
Memory, mais conhecido como CD-Rom, utiliza-se de tecnologia laser 
para leitura e gravação de dados em formato ótico. Eles apresentam 
limitações para regravação de dados e, também, um pior tempo de 
acesso se comparado aos discos de estado sólido, contudo transfor-
maram-se por muito tempo em excelentes alternativas para backup 
de dados.
 • Armazenamento em fita magnética
Quando falamos em fitas magnéticas podemos nos lembrar daque-
las velhas fitas usadas para guardar tanto os primeiros arquivos se-
quenciais, usados nos antigos sistemas das décadas de 1970, 1980 e 
1990. Porém, não são essas as fitas utilizadas atualmente. Hoje temos 
cartuchos lacrados em que a fita se enrola e desenrola dentro de um 
mesmo cartucho, não sendo transferida de um rolo A para um rolo B, 
como antigamente.
Segundo Elmasri e Navathe (2006), o acesso aos blocos de dados 
na ordem sequencial é a principal característica de uma fita. Esse aces-
so se dá quando o cabeçote de leitura/escrita percorre um bloco no 
No texto Como funcionam 
os discos rígidos (ART943), 
o autor Newton Braga 
mostra em detalhes a 
tecnologia de gravação e 
leitura em discos magné-
ticos, tanto do ponto de 
vista mecânico (como o 
acesso é feito) quanto do 
ponto de vista eletrônico 
(como saber o que está 
gravado no disco). É 
uma oportunidade de 
compreender como algo 
tão complexo pode ter 
se transformado em algo 
tão amplamente utilizado 
no mercado.
Disponível em: https://www.
newtoncbraga.com.br/index.php/
como-funciona/7727-como-
funcionam-os-discos-rigidos-
art943. Acesso em: 24 nov. 2020.
Leitura
https://www.newtoncbraga.com.br/index.php/como-funciona/7727-como-funcionam-os-discos-rigidos-art943
https://www.newtoncbraga.com.br/index.php/como-funciona/7727-como-funcionam-os-discos-rigidos-art943
https://www.newtoncbraga.com.br/index.php/como-funciona/7727-como-funcionam-os-discos-rigidos-art943
https://www.newtoncbraga.com.br/index.php/como-funciona/7727-como-funcionam-os-discos-rigidos-art943
https://www.newtoncbraga.com.br/index.php/como-funciona/7727-como-funcionam-os-discos-rigidos-art943Armazenamento e estruturas de dados 13
meio de um cartucho até chegar ao bloco requisitado. Por essa razão 
o acesso à fita pode ser lento e as fitas podem não ser utilizadas para 
armazenar dados on-line, exceto para aplicações específicas. Entretan-
to, elas atendem a uma função muito importante: o backup do banco 
de dados.
 • Estrutura de disco
Sendo os discos magnéticos as principais mídias de armazena-
mento de grandes volumes de dados, é importante que se conheçam 
alguns dos elementos e das características que os compõem. Conhe-
cendo estas estruturas poderemos entender quais são os pontos que 
merecem atenção, até mesmo durante o projeto relacional e o projeto 
físico. Poderemos entender, por exemplo, por que o acesso a duas ta-
belas distintas para obter um conjunto de dados pode ser mais lento 
do que acessar uma única tabela.
Figura 1
Estrutura física de um disco magnético
Trilha/Cilindro
trilha 1
trilha 10
setor 1
setor 20
Cabeçotes
8 Cabeçotes 
Pratos
Fonte: Canal Tech, 2021.
O primeiro ponto a ser observado é que existem diversos elemen-
tos mecânicos envolvidos no acesso a um disco (braços, cabeçotes, eixo 
etc). Esses elementos mecânicos precisam ter acesso a todas as trilhas 
e setores de um disco. Olhando a Figura 1, podemos imaginar que se 
um dado X se encontra gravado no setor 1, mas um outro dado Y se 
14 Banco de Dados II
encontra gravado no setor 20, haverá um tempo gasto para que se es-
pere o disco girar saindo do setor 1 e chegando até o setor 20, para 
então a leitura do dado Y ser feita. Se um dado X estiver gravado na 
trilha 1, mas um dado Y estiver gravado na trilha 10, teremos também 
que aguardar um deslocamento do braço do disco, para que ele saia 
da área mais externa do disco e se desloque para a área mais interna. 
Estes dois tempos, também chamados de latência, precisam ser consi-
derados como um atraso na entrega dos dados que venhamos a solici-
tar ao sistema de gerenciamento de banco de dados – SGBD.
Na estrutura apresentada podemos observar a presença de setores, 
que são as menores unidades de leitura e gravação em disco, portanto, 
mesmo que você deseje somente uma porção dos dados que estão 
no setor 20, na trilha 1, acabará tendo que aguardar o mecanismo fa-
zer a leitura de todo o setor 20, trazendo eventualmente dados que 
você nem desejava ter acesso naquele momento. Também o tempo de 
transferência de todos os dados, relevantes ou não do setor 20, devem 
ser computados como tempo adicional na entrega dos dados solicita-
dos pelo SGBD ao sistema operacional.
Do ponto de vista do SGBD, um outro elemento deve ser conhecido: 
o bloco ou página. Essa é a unidade que o SGBD utilizará como mínima 
porção para leitura ou gravação de dados. Mais à frente veremos deta-
lhes sobre esta estrutura.
Todos os dispositivos de armazenamento vistos operam de modo 
cooperado, cumprindo finalidades diferentes em função do aproveita-
mento de suas características. Assim, por exemplo, a memória RAM, por 
ter uma velocidade de acesso maior, é usada para manter dados que 
precisam mais constantemente ser acessados. Já um disco magnético, 
por ter um tempo de acesso mais lento, é usado para manter dados 
que tenham menor frequência de acesso.
Chamamos de armazenamento primário aquele que é operado e 
controlado diretamente pelo sistema operacional, tal como a memó-
ria RAM e a memória cache. Já o armazenamento secundário é aquele 
que exige intermediação do armazenamento primário, tal como discos 
magnéticos, fitas magnéticas etc.
Esta intermediação do armazenamento secundário feita pelo arma-
zenamento primário potencializa os resultados e o desempenho das 
leituras e gravações de dados pelo SGBD e por outros programas que 
Armazenamento e estruturas de dados 15
exigem interação com dispositivos de entrada e saída de dados. Ve-
remos as seguir como este processo acontece, segundo descrito por 
Elmasri e Navathe (2006).
Como os dados de um banco de dados estarão sempre armazena-
dos em um disco magnético, ao solicitar a leitura de um dado X, pode-
ríamos imaginar que o sistema operacional pudesse ir sempre ao disco 
para procurar pelo bloco físico de dados (bloco 0001) onde se encontra 
o dado X e que trouxesse, então, X para ser processado pela memória 
RAM.
Figura 2
Transferência de dados entre disco e memória sem buffer
Memória RAM
Disco MagnéticoX
X Y Z A B
Bloco 0001 Bloco 0002
Fonte: Elaborada pelo autor.
Porém, caso esse processo fosse sempre executado, na próxima vez 
em que outro usuário solicitasse o acesso ao dado X (imaginando que 
ele é um dado frequentemente requisitado), o sistema operacional te-
ria que novamente executar um acesso ao disco, com todo o consumo 
de tempo já apresentado anteriormente (esperar o deslocamento do 
braço de leitura até a trilha e o giro do disco até o setor necessário). 
Para agilizar esse processo, e imaginando que o dado X possa ser re-
quisitado novamente no futuro, um recurso extra de memória cache é 
adicionado, conforme apresentado na Figura 3.
Figura 3
Transferência de dados entre disco e memória com buffer
BufferMemória RAM
Disco MagnéticoX
X Y Z
X Y Z
A B
Bloco 0001
Bloco 0001
Bloco 0002
Fonte: Elaborada pelo autor.
16 Banco de Dados II
Assim sendo, ao ser solicitado o dado X, primeiramente o siste-
ma operacional irá verificar se ele já não se encontra na área de 
buffer (que tem um acesso muito rápido). Caso já esteja lá, não 
será necessário ir até o disco buscá-lo. Caso não esteja localizado 
no buffer, então ele será procurado no disco e o bloco ao qual ele 
pertence será carregado para o buffer, ficando disponível para uma 
próxima busca futura.
Esse mesmo processo acontece também quando um dado é inse-
rido ou atualizado no banco de dados. Antes de realizar a atividade 
de atualização diretamente no banco de dados em disco (que é mais 
demorada), essa atualização é realizada primeiramente na área de 
buffer, ficando disponível para outros processos e, desse modo, re-
plicada para o dispositivo de disco magnético, não no exato momen-
to em que ela acontece.
Essas operações através de buffers atuam sempre sobre blo-
cos (ou páginas) físicos de dados, que são gerenciadas pelo siste-
ma operacional. Esses blocos anteriormente eram compostos por 
512bytes, mas atualmente o padrão utilizado pelos fabricantes é 
de 4Kbytes, ou seja, 8 blocos anteriores deram origem a somente 
um bloco atual. Isso faz com que mais dados estejam armazena-
dos em um único bloco, que uma quantidade menor de bytes de 
controle e sincronismo sejam consumidos, maximizando o uso do 
espaço físico do disco.
Figura 4
Transição de blocos de 512 bytes para 4Kbytes
Data
ECC: = 
100 Bytes 
Eight 512-byte legacy 
sectors become a single 
4K-byte sector
Fonte: Seagate, 2021.
Conhecer todos esses elementos físicos ligados ao armazenamento 
de dados poderá lhe trazer uma breve compreensão de alguns recur-
sos utilizados pelos sistemas gerenciadores de banco de dados para 
maximizar o desempenho de consultas e atualizações.
Armazenamento e estruturas de dados 17
1.2 Organização de arquivos 
Vídeo Os dados que iremos armazenar nos mais diversos tipos de dispositi-
vos de armazenamento, predominantemente em discos magnéticos, são 
organizados de modo a formar registros. Cada registro é, portanto, uma 
sequência de campos de dados elementares que agrupados formam uma 
unidade de leitura ou de gravação. Esses registros ocupam por sua vez 
espaços físicos em blocos de dados, conforme já vimos. Isto é, um bloco 
físico em um disco será utilizado para armazenar um certo número de re-
gistros. A quantidade de registros possível de ser armazenada num bloco 
dependerá do tamanho total do bloco e do tamanho individual de cada 
registro. Imagine então que temos um bloco de 4Kbytes e um registro que 
ocupe 512bytes. Teríamos a possibilidade de armazenar 8 registros por 
bloco. Precisamos lembrar que, tanto na estrutura do bloco como na es-
trutura do registro, podemos ter áreas de dados reservadaspara contro-
les internos do sistema operacional, por exemplo, o número do bloco, o 
status do bloco etc.
Outra característica relevante é o fato de que eventualmente nem to-
dos os registros tenham o mesmo tamanho. Existem duas modalidades 
de criação de registros: os de tamanho fixo e os de tamanho variável. Os 
registros de tamanho fixo são originados do agrupamento de campos 
de tamanho fixo (todos eles) – um exemplo de campo de tamanho fixo 
é aquele que solicita o CEP. Já os registros de tamanho variável são ori-
ginados do agrupamento de campos, onde pelo menos um deles possa 
ser de tamanho variável. Veremos mais a frente que nos SGBDs é muito 
frequente a existência de registros de tamanho variável, pois algumas das 
colunas que irão compor um tupla (registro) de uma tabela, poderão ter 
tamanho variável, ou até mesmo não possuírem conteúdo, tendo, portan-
to, tamanho igual a zero.
É de se imaginar que, quando os registros de dados são de tamanho 
fixo, o gerenciamento de espaço físico ocupado num bloco de disco seja 
mais fácil do que o gerenciamento de armazenamento de registros de 
tamanho variável. Dissemos há pouco que se um registro tem tamanho 
de 512bytes, então teríamos 8 registros num bloco de disco de 4Kbytes. 
Mas, e se cada registro tiver um tamanho? Suponha que um registro tenha 
512bytes, mas que outro tenha 600bytes, e outro 300bytes. Quantos re-
gistros caberiam em cada bloco? E o que aconteceria com o bloco quando 
um desses registros fosse atualizado e o seu tamanho fosse alterado?
18 Banco de Dados II
Todo este gerenciamento de espaços é executado pelo SGBD em 
conjunto com o sistema operacional, de modo a permitir que registros 
novos sejam incluídos num bloco, registros existentes sejam alterados 
em seus tamanhos, ou até que registros sejam excluídos, liberando es-
paços que futuramente terão de ser utilizados por novos registros, os 
quais devam ser armazenados no mesmo bloco.
Para que isso seja possível, são criados nos blocos estruturas de 
controle (chamadas de header) em que o controle de espaço disponível 
no bloco, os espaços liberados e outros controles são todos guardados 
como dados de controle do bloco. Esse é mais um elemento que ocu-
pará espaço em seu futuro banco de dados. Se tivermos 1.000 registros 
de 1.000 bytes cada, não terá um espaço físico de somente 1.000.000 
bytes. Teremos que considerar também que o sistema irá criar áreas 
de dados de controle em cada bloco (ou página) gerenciada pelo SGBD.
Porém, somente armazenar e gerenciar um conjunto de registros 
em um disco, não nos daria capacidade suficiente para manipulá-los lo-
gicamente por meio de uma linguagem de programação. Temos então 
um novo elemento: o arquivo; isto é, uma reunião de vários registros 
formando logicamente um arquivo. Podemos dizer que o arquivo do 
cadastro de funcionários será a reunião de todos os registros de dados 
de cada um dos funcionários.
Os arquivos, por sua vez, possuem um tipo de organização e estru-
turação dos registros que compõem o que determina algumas caracte-
rísticas associadas aos métodos de acesso que poderão ser utilizados 
para acessar os dados deste arquivo. Temos, então, dois possíveis mé-
todos de acesso, conforme o Quadro 1.Quadro 1
Métodos de acesso
Método de acesso Característica
Sequencial
Para acessar o registro de posição N+1 é necessário antes acessar o registro de posição N.
Deverá existir um único critério de ordenação entre a coleção de registros para que possa 
então identificar se o registro procurado está antes ou após a posição N em que estamos.
A leitura dos dados ocorre somente no sentido “para frente”. Ou seja, seguindo a ordem: N-1, 
N, N+1.
Direto
Para acessar qualquer registro, em qualquer posição, basta que se forneça um valor de uma 
chave de localização do registro.
Poderá existir mais de um critério de ordenação entre a coleção de registros, cada um defini-
do por uma diferente chave.
Pode-se acessar o registro de posição N+1 sem ter previamente acessado o registro de posição N.
Fonte: Elaborado o autor.
Armazenamento e estruturas de dados 19
Esses métodos de acesso estarão vinculados ao tipo de organização 
de um arquivo que pode ser: heap (pilha), sequencial ou hash (indexa-
da), cada um deles tendo vantagens e desvantagens.
A organização heap é a que oferece melhor desempenho para a 
operação de inserção de novos registros no arquivo, pois cada novo 
registro irá sempre ser armazenado como o último da pilha (ao final 
do arquivo). Imagine que cada novo funcionário contratado teria seus 
dados armazenados no final do arquivo, após os dados do último fun-
cionário já registrado. Porém, como não existe nenhuma ordem prees-
tabelecida entre os registros, mas somente uma ordem cronológica, 
então a futura busca por um registro específico seria muito difícil. Onde 
encontraríamos, por exemplo, o funcionário de nome “João da Silva”, a 
funcionária de matrícula “123456”? Jamais saberíamos onde se encon-
tram. Eles podem ser o primeiro ou o último registro do arquivo, pois 
somente a ordem de inserção é que os fez ocupar esta posição. Caso 
existam exclusões de registros em posições intermediárias do arquivo 
(e não no seu final), acabaremos por ficar com espaços inutilizados, 
pois o próximo registro a ser armazenado não ocupará esse espaço 
livre, e sim irá para o final do arquivo.
A organização sequencial é uma evolução desse modelo. Ela já agre-
ga o conceito de uma chave de ordenação de uma lista sequencial de 
registros. A inserção de novos registros deverá ser feita exatamente 
na posição em que a chave de ordenação defina. Se, por exemplo, já 
temos um registro de “Pedido de Férias” para o funcionário com a ma-
trícula “0005” e logo depois outro “Pedido de Férias” para o funcionário 
“0015”, então quando o funcionário de matrícula “0007” solicitar suas 
férias, teremos que inserir esse pedido, entre o “0005” e o “0015” para 
que tenhamos então os pedidos: “0005”, “0007” e “0015” corretamen-
te ordenados. A inserção de novos registros intercalados aos registros 
que já existiam exige técnicas de programação específicas. A vantagem 
dessa organização é que se estivermos posicionados no registro “0007”, 
saberemos que o registro “0015” estará mais a frente e que o registro 
“0005” estará mais atrás. É como procurar uma carta em um baralho 
que esteja organizado por naipe e números em comparação a procurar 
a mesma carta em um baralho que foi embaralhado aleatoriamente.
A última organização de arquivos, e talvez a mais próxima daquela 
que um SGBD irá aplicar em seus métodos de acesso, é a organização 
hash (ou indexada). Como o próprio nome diz, haverá uma organização 
20 Banco de Dados II
dos registros que permitirá que se use o método de acesso direto. Po-
deremos acessar qualquer registro de toda a coleção de registros que 
forma o arquivo a qualquer momento, com praticamente uma única 
leitura de um bloco de dados. É como se conseguíssemos identificar a 
trilha, o setor, o bloco e o registro dentro bloco diretamente, sem ter 
que passar por nenhum outro registro previamente. Além de permitir 
acesso direto na leitura, essa organização de arquivos também permite 
novas inserções de registros, alterações de tamanhos de registros, e 
até a exclusão de registros pode ser realizada com menor complexida-
de e esforço para o SGBD e para o sistema operacional.
A organização indexada surgiu como evolução da organização se-
quencial, que limitava o acesso direto aos dados. Não poderíamos 
imaginar um sistema on-line como temos hoje, em que uma pessoa 
consegue acessar rapidamente o dado que deseja, sem que a organi-
zação indexada tivesse sido criada. Nenhum sistema transacional seria 
viável se para atualizar um único registro num banco de dados, tivésse-
mos que ler todos os registros anteriores ao registro que desejássemos 
atualizar. Também os sistemas gerenciadores de banco de dados não 
teriam sido viáveis sem terem sido concebidos como uma evolução dos 
arquivos com organização indexada.Nessa organização, além do próprio arquivo de dados, composto 
por seus registros e campos, teremos uma estrutura complementar 
de apoio para o acesso. Essa estrutura é chamada de índice de acesso. 
Através dela poderemos localizar um registro com o menor esforço 
possível. Diferentemente do arquivo sequencial, que só poderia ter 
uma chave de ordenação, um arquivo indexado pode ter vários arqui-
vos de índices, cada um criado com base em uma chave de ordenação. 
Poderíamos assim, por exemplo, ter nosso cadastro de funcionários, 
com índices criados por “nome”, “matrícula”, “data de nascimento” etc. 
Cada índice deste nos permitiria fornecer um valor para o campo chave 
e, rapidamente, obter o registro desejado.
Muitas pessoas se questionam sobre o fato de a organização se-
quencial ser bastante limitada e qual o motivo dela ter sido criada e 
utilizada por tanto tempo. Isso se deve, na verdade, a uma questão his-
tórica. Os primeiros dispositivos de armazenamento de dados que sur-
giram para permitir o processamento de dados corporativos (em maior 
volume) foram os cartões perfurados. Eram dispositivos rudimentares 
Armazenamento e estruturas de dados 21
para armazenamento tanto dos códigos dos programas quanto dos da-
dos de entrada para tais programas. Um conjunto de cartões era então 
lido sequencialmente, um cartão após o outro. Com a evolução dos 
dispositivos de armazenamento magnético, os cartões deixaram de ser 
usados, mas foram então substituídos por outro dispositivo de leitura 
e gravação (uma novidade) sequencial: as fitas.
 
Figura 5
Cartões perfurados e fitas magnéticas
No
m
ad
_S
ou
l/S
hu
tte
rs
to
ck
Agora já era possível ler e gravar de modo sequencial um arquivo. 
Lia-se cada um dos registros da fita número 1, alterava-se o que fosse 
necessário, incluíam-se ou excluíam-se registros e o resultado era gra-
vado na fita de saída número 2. No próximo processamento, a fita nú-
mero 2 voltava a ser a fita de entrada para o próximo processamento. 
Ou seja: o uso do método de acesso sequencial foi uma imposição dos 
recursos tecnológicos que se dispunham naquele momento.
1.3 Técnicas de hashing 
Vídeo Como vimos acima, o acesso direto ao registro de um arquivo, ou 
especialmente de um banco de dados, deixou de ser uma opção e se 
transformou basicamente em um requisito para qualquer projeto de 
sistema de informação que trabalhe como transações on-line.
Também vimos que, para ter acesso direto usando índices de 
acesso, teríamos que criar e manter estruturas adicionais além dos 
22 Banco de Dados II
próprios dados que armazenaremos. Isso terá dois impactos diretos 
nos sistemas que venhamos a criar: consumo adicional de espaço físi-
co (apesar do custo estar cada vez menor no mercado) e tempo adicio-
nal para processamento. Isso se deve ao fato de que com estruturas 
de índices sendo utilizadas, teremos que primeiro ler e processar da-
dos em estruturas de índices, para depois poder através delas chegar 
até os dados reais, conforme demonstrado na Figura 6.
Figura 6
Estrutura de índice convencional
número conta nome agência valor conta
A-217 Brighton 750
A-101 Downtown 500
A-110 Downtown 600
A-215 Mianus 700
A-102 Perryridge 400
A-201 Perryridge 900
A-218 Perryridge 700
A-222 Redwood 700
A-305 Round Hill 350
ÍNDICE (Nome Agência)
ARQUIVO DE DADOS – CONTAS
Brighton
Downtown
Mianus
Perryridge
Redwood
Round Hill
Fonte: Silberschatz, 2012, p. 323.
Isto é, se você desejasse ter acesso às contas da agência 
“Downtown”, poderia fornecer o “nome da agência”, que seria então 
localizado na área de índices que, por sua vez, apontaria para a primei-
ra conta (A-101) desta agência na área de dados. Isso significa que se 
faria uma primeira leitura dos dados do índice para depois localizar o 
item “Downtown” e então descobrir a informação que o levaria para a 
posição em disco onde se encontra o registro “A101”.
Esse processo, apesar de ser funcional, poderia ser otimizado se 
pudéssemos utilizar um método mais ágil e com menor gasto de espa-
ço em disco para armazenamento de índices. Este novo método cha-
ma-se de hashing. Ele utiliza uma função hash.
Para que possamos entender melhor o conceito do processo de 
hashing deveremos primeiro estabelecer o conceito de um bucket 
(balde). Um bucket é uma área de armazenamento de um ou mais 
registros. Normalmente um bucket está associado a um bloco físico, 
mas ele pode ser maior ou menor que um bloco.
Armazenamento e estruturas de dados 23
O processo de hashing é baseado em uma função matemática que 
permite que, para o conteúdo de um campo de registro, possamos ge-
rar um número de bucket entre uma lista de buckets disponíveis para 
onde ele deveria ser destinado. Vamos imaginar que temos uma lista 
de buckets definida por B e uma lista de valores de entrada para um 
campo definida por V. A função hash é uma função do tipo:
B = hash (V)
Isso significa que para cada valor de V, situado dentro do domínio 
de valores possíveis de V, fornecido para a função hash, esta será capaz 
de produzir um valor B, dentro do domínio de valores que B pode assu-
mir. Se tivermos 1.000 valores diferente para V, e 100 valores diferentes 
para B (100 buckets), então uma função ideal de hash deveria ser capaz 
de fazer uma distribuição homogênea de 10 valores de V em cada um 
dos 100 buckets existentes.
Figura 7
Função de hash alocando registros nos buckets ideais
001 - João da Silva
050 - Zélia de Souza
003 - João de Souza
017 - Maria Marq 
Bucket 1
001 – João da Silva 
017 – Maria Marq
Bucket 2 050 – Zélia de Souza
Bucket X 003 – João de Souza
Dados fornecidos Função Área de armazenamento
Função 
hash
Fonte: Elaborada pelo autor.
Podemos ver na Figura 7 que tanto o nome “João da Silva” como o 
nome “Maria Marq” geraram o mesmo número de bucket. Isso não é 
um problema, pois, como vimos, um bucket será um bloco de disco e 
nele poderemos ter vários registros. Se para o armazenamento destes 
dois registros distintos eles forem direcionados para o bucket 1, então 
quando desejarmos acessá-los numa consulta futura, a mesma função 
de hash será aplicada e, ao receber o nome “João da Silva”, o SGBD po-
derá automaticamente identificar que deve procurar por esse dado no 
bucket 1 que se encontra em disco, criando assim um mecanismo de 
acesso direto sem a necessidade de um índice.
A eficiência desse processo de hashing está, portanto, baseada em 
uma função que consiga executar a melhor distribuição possível dos va-
24 Banco de Dados II
lores recebidos em sua entrada, dentre todos os espaços de buckets dis-
poníveis. No exemplo hipotético que demos, de nada adiantaria ter uma 
função em que os 1.000 registros de entrada acabassem sendo alocados 
em somente 10 dos 100 buckets disponíveis. Teríamos uma taxa de ocu-
pação muito alta em cada bucket (100 registros por buckets) e muitos 
buckets vazios (90% deles). Ou seja, uma função de hashing deve ter a 
habilidade de fazer a dispersão homogênea dos registros recebidos.
Isto poderia parecer simples de ser feito se soubéssemos o padrão de 
dados que receberíamos. Porém, temos que imaginar que em uma função 
de hashing teremos como parâmetro de entrada os mais diversos tipos de 
conteúdo, como um nome, um CPF, uma data, um código alfabético, um 
código numérico etc. O sucesso de uso de uma função de hashing depen-
deria, portanto, do sucesso da função de distribuição de registros. Como 
isso nem sempre pode ser assegurado, temos tido então o predomínio do 
uso de estruturas de índices, que apesar de mais custosas em termos de 
espaço, podem assegurar uma taxa de sucesso maior.
1.4 Estrutura de indexação de arquivos 
Vídeo Como alternativa para o acesso direto aos registros de um arqui-
vo, temos a possibilidade de utilizar estrutura de índices. Por isso, esta 
organização de arquivos era, muitas vezes, referenciada como associa-
da ao termo arquivos indexados. Inicialmente os arquivos tinham uma 
única chave (que até poderia ser composta por vários campos) paraa 
qual uma estrutura de índice era construída, de modo a permitir que 
o acesso direto fosse realizado. Atualmente esse mesmo método de 
acesso é usado para acesso aos dados das tabelas em um banco de da-
dos. A vantagem atual é que uma mesma tabela pode ter vários índices 
criados simultaneamente. 
O primeiro índice é aquele criado obrigatoriamente para a coluna 
que representa a chave primária da tabela. Ele não pode ter valores 
duplicados na chave (restrição de domínio) e é denominado de índi-
ce primário. Os demais índices, criados então sobre as demais colunas 
da tabela podem ser criados com valores duplicados em suas chaves, 
permitindo diferentes chaves alternativas para acesso direto são deno-
minados de índices secundários. O fato de um índice permitir ou não 
valores duplicados não é uma restrição da estrutura do índice, mas sim 
uma restrição do modelo relacional.
Armazenamento e estruturas de dados 25
Seja para um arquivo indexado tradicional (ainda disponível em sis-
temas de mainframe tradicionais existentes em grandes instituições 
financeiras) ou para uma tabela de um moderno banco de dados rela-
cional criado com um dos mais recentes SGBDs existentes no mercado, 
teremos o mesmo princípio e tecnologias similares sendo utilizadas.
Veremos a seguir dois tipos de arquitetura de índices que podem 
ser aplicados na criação de uma estrutura de acesso direto: os índices 
densos e os índices esparsos. Porém, primeiramente precisamos defi-
nir o que é um índice e como ele opera. Um índice é uma estrutura de 
dados sequencial e ordenada que mantém somente os dados essen-
ciais da chave de acesso a um registro, no qual temos agregado um 
ponteiro (campo que faz o endereçamento do registro final que será 
acessado) que serve de vínculo entre o índice o arquivo de dados.
Figura 8
Estrutura de um índice
Índice
Ana Bloco 9
Cesar Bloco 5
... ...
Arquivo de dados
Ana Maria 02/10/1980
Beatriz 22/05/1981
João 09/11/1992
Cesar 11/11/1997
Carlos 25/03/1962
Localizar nome = “Cesar”
Fonte: Elaborada pelo autor.
Essa estrutura permite que, sabendo o nome de um funcionário, 
por exemplo, “Cesar”, possamos fornecer este valor para o mecanismo 
de busca, que irá identificar no índice (estrutura sequencial e ordena-
da) qual é o endereço físico onde este registro se encontra no arquivo 
de dados (utilizando um ponteiro). Assim, os registros no arquivo po-
dem até estar dispersos, mas serão facilmente localizados, pois o índice 
provê ordenação e acesso imediato. O mecanismo de busca do nome 
“Cesar” dentro do índice poderá usar diferentes estratégias, sendo uma 
delas a busca em árvores binárias.
Como a estrutura de índices acabará por ocupar um espaço físico 
em disco e precisará estar constantemente sendo reorganizada para 
ficar ordenada, tornou-se necessário pensar em um meio de fazer com 
que essa estrutura pudesse ser o menor possível. Imagine, por exem-
plo, que tenhamos um arquivo com 1.000 registros. Se cada um desses 
26 Banco de Dados II
precisasse de uma entrada na estrutura de índices, teríamos então 
1.000 chaves ordenadas no índice, ocupando um espaço X em disco. 
Porém, se para os 1.000 registros do arquivo, pudéssemos somente 
criar 250 chaves na estrutura de índice teríamos uma estrutura com 
25% do uso de espaço físico para guardar todo o índice e para futura-
mente percorrer o índice durante uma busca. É verdade que com esta 
segunda opção não conseguiríamos acessar cada um dos 1.000 regis-
tros do arquivo diretamente. Teríamos sempre que localizar a chave 
mais próxima da chave desejada e , a partir daí, executar uma busca 
sequencial.
Um índice denso é, portanto, uma estrutura de índices para a qual 
cada valor de chave no arquivo gera uma entrada distinta no índice 
(1000 registros com 1000 chaves no índice). Já um índice esparso, ou 
não denso, é uma estrutura para a qual algumas das chaves do arquivo 
são criadas no índice e pelo acesso a essas chaves, as chaves subse-
quentes são recuperadas (1000 registros com 250 chaves no índice). 
Segundo Date (2004), o termo não denso refere-se ao fato do índice não 
conter uma entrada para cada ocorrência de registro armazenado no 
arquivo indexado. Apesar de os índices densos ocuparem mais espaço 
em disco, eles podem prover mais velocidade de acesso ao arquivo, 
pois, para uma dada chave, o registro é recuperado imediatamente. 
Já um índice esparso ocupa menos espaço em disco, porém exige um 
processamento adicional para se chegar ao registro desejado.
Além disso, quando um índice se torna muito grande por ter que 
endereçar um número muito grande de registros (por exemplo, 1 mi-
lhão de registros), passa a ser necessário o uso de uma estrutura de 
índices multinível.
Imagine que tenhamos 200 mil blocos, cada um com seus 5 regis-
tros indexados (exemplo de 1 milhão de registros). Teríamos então na 
estrutura de índice interno uma quantidade de 1 mil blocos de índices 
cada um apontando para até 200 blocos de dados (totalizando 200 mil 
apontadores para blocos de dados). Já no índice externo poderíamos 
ter somente 10 mil chaves de referência apontando para os 10 mil blo-
cos do índice interno. Perceba que ao invés de ter um único índice com 
1 milhão de entradas, teremos um índice externo com somente 10 mil 
chaves, capazes de chegar a 1 milhão de registros através de índices 
internos.
No material MC202 - 
Estrutura de Dados você 
poderá ver em detalhes o 
processo de atualização 
de uma estrutura de 
índices baseada em uma 
árvore binária (Árvore-B). 
São exemplificadas 
inserções e remoções de 
elementos na estrutura 
da árvore, demonstrando 
como a reorganização 
de ponteiros é feita pelo 
sistema gerenciador. 
Pode-se compreender 
então a complexidade e o 
custo de manutenção da 
estrutura de índices.
Disponível em: https://www.
ic.unicamp.br/~afalcao/mc202/
aula13-ArvoreBinariaBusca.pdf. 
Acesso em: 25 nov. 2020.
Leitura
https://www.ic.unicamp.br/~afalcao/mc202/aula13-ArvoreBinariaBusca.pdf
https://www.ic.unicamp.br/~afalcao/mc202/aula13-ArvoreBinariaBusca.pdf
https://www.ic.unicamp.br/~afalcao/mc202/aula13-ArvoreBinariaBusca.pdf
Armazenamento e estruturas de dados 27
Figura 9
Estrutura de índice multinível
bloco de 
índice 0
bloco de 
dados 0
Índice externo
Índice interno
bloco de 
índice 1
bloco de 
dados 1
Fonte: Silberschatz; Korth; Sudarshan, 2012, p. 325.
Como podemos imaginar, quanto maior a quantidade de registros 
que precise ser armazenado, maior a estrutura de índice que deverá 
ser criada para suportar o acesso direto a todos os registros. Uma es-
trutura comumente utilizada para dar suporte a esse tipo de índice é a 
árvore B+, ou árvore balanceada.
Segundo Silberschatz, Korth e Sudarshan (2012), a estrutura de ín-
dice de árvores B+ é a mais utilizada por ser a que melhor mantém sua 
eficiência apesar da inserção e exclusão de dados. Um índice de árvore 
B+ tem a forma de uma árvore balanceada, em que cada caminho da 
raiz até uma folha da árvore é do mesmo tamanho.
28 Banco de Dados II
Apesar da alta eficiência para localização de registros, esse tipo de 
estrutura sobrecarrega de certo modo o processo de inserção e exclu-
são de registros, pois constantemente a árvore precisa ser balanceada, 
fazendo com que o SGBD tenha que, por instantes, bloquear toda a es-
trutura de índices para reorganizá-lo. Desse modo, se você está inserin-
do um único registro de um funcionário, toda a tabela de funcionários 
terá que ser bloqueada por alguns instantes indiretamente, pois o seu 
índice foi bloqueado para ser reorganizado.
Figura 10
Estrutura de árvore B+
I
K MC F
(A,4) (B,8) (C,1) (D,9) (E,4)
(L,4) (J,8) (K,1) (L,6) (M,4) (N,8) (P,6)
(F,7) (G,3) (H,3)
Fonte: Silberschatz; Korth; Sudarshan, 2012, p. 334.
Cada fabricante de SGBD implementa suas estruturas e algoritmos 
de reorganização, tanto de espaços físicos das áreas de dados quanto 
das áreas de índice, de modo a procurar prover o melhor desempenhopossível em seus produtos e de se diferenciar de seus concorrentes. 
Muitas vezes após o lançamento de uma nova versão de um produto 
do mesmo fabricante de SGBD, são anunciados ganhos de performan-
ce no acesso ou inclusão de registros justamente pela implementação 
de melhorias nesses algoritmos internos.
Isso mostra que, apesar de serem conceitos e aspectos muitas ve-
zes pouco considerados quando se modela e se projeta um banco de 
dados, e até mesmo quando se utiliza uma aplicação desenvolvida com 
um SGBD, esses detalhes técnicos podem sim trazer impactos no resul-
tado final. Conhecer e explorar esses recursos pode resultar em um sis-
tema com melhor ou pior performance em termos de tempo de acesso, 
ou tempo de resposta para a busca de uma informação.
Armazenamento e estruturas de dados 29
CONSIDERAÇÕES FINAIS
As estruturas físicas de armazenamento dos dados de um banco de 
dados não se distanciam muito das estruturas de armazenamento que 
há décadas vem sendo utilizadas para arquivos sequenciais e arquivos 
indexados. Com certeza, melhorias nos processos de armazenamento, 
nas tecnologias e nos materiais usados para o armazenamento, e o 
poder computacional otimizado gerado por sistemas operacionais e 
sistemas gerenciadores de bancos de dados, geraram novas possibi-
lidades de exploração dos dados armazenados nos bancos de dados.
Porém, conhecer os conceitos e princípios que regem a manipula-
ção física desses dados vai nos dar condições de nos próximos capí-
tulos compreender a necessidade de implementar novos controles e 
recursos nos sistemas gerenciadores de dados. Muitas vezes uma sim-
ples limitação física imposta pelo tempo de acesso a disco, que exige 
um movimento mecânico do braço do leitor de disco, poderá ser usada 
como justificativa para que se crie um mecanismo com os buffers de 
acesso a dados no SGBD.
O que pode parecer neste momento um conteúdo muito distante 
do real papel do sistema gerenciador de banco de dados, criado para 
dar uma grande facilidade para manuseio do banco de dados, é, na 
verdade, um conteúdo muito importante para compreender o próprio 
funcionamento do sistema gerenciador do banco de dados.
ATIVIDADES
1. Justifique por que nas primeiras estruturas de arquivos criadas os 
pesquisadores optaram por estruturas sequenciais, sendo que já 
sabiam que elas não eram as que apresentariam melhor desempenho.
2. Por que um disco magnético sempre será mais lento para nos devolver 
um dado solicitado, se comparado a uma memória RAM?
3. Qual é a principal característica esperada de um bom algoritmo de 
hash?
4. Por que uma estrutura de índice, apesar de consumir espaço em disco, 
pode ser uma boa opção para se implementar acesso direto a um 
grande volume de registros?
30 Banco de Dados II
REFERÊNCIAS
CANAL TECH. Como funcionam os discos rígidos, 2021. Disponível em: https://canaltech.
com.br/hardware/Como-funcionam-os-discos-rigidos/. Acesso em: 18 jan. 2021.
DATE, C. J. Introdução a sistemas de banco de dados. São Paulo: Elsevier, 2004.
ELMASRI, R; NAVATHE, S. Sistemas de banco de dados. 4. ed. São Paulo: Pearson Addison 
Wesley, 2006.
SEAGATE. Transição para discos rígidos de formato avançado com setores de 4K, 2021. 
Disponível em: https://www.seagate.com/br/pt/tech-insights/advanced-format-4k-sector-
hard-drives-master-ti/. Acesso em: 18 jan 2021.
SILBERSCHATZ, A.; KORTH, H. F.; SUDARSHAN, S. Sistema de banco de dados. 6. ed. Rio de 
Janeiro: Elsevier, 2012.
Processamento e otimização de consultas 31
2
Processamento e 
otimização de consultas
Tendo modelado e construído nosso banco de dados e po-
pulado os dados em suas tabelas, passamos a contar com uma 
estrutura que poderá ser acessada por meio da linguagem estru-
turada de consultas (SQL). Os sistemas gerenciadores de bancos 
de dados proverão, então, algoritmos complexos e muito bem 
elaborados, a fim de nos munir de meios ágeis para acessar os 
dados mediante as SQL que iremos construir. Vamos conhecer 
aqui alguns aspectos ligados às estratégias de acesso utilizadas 
por essas ferramentas.
O conhecimento desses aspectos nos permitirá identificar as 
eventuais causas de um comando não ter o melhor desempenho, 
conforme o esperado. Identificaremos também por que, algumas 
vezes, o próprio SGBD está construindo caminhos de acesso aos 
dados diferentes daqueles que imaginamos serem os ideais.
Neste capítulo, observaremos, ainda, como são avaliados 
os custos de execução de uma consulta, de modo que possam 
ser aplicados algoritmos de otimização e de processamento de 
consultas.
2.1 Medidas de avaliação de custo de consultas 
Vídeo A terminologia custo de uma consulta é o primeiro conceito que 
devemos estabelecer. Esse conceito expressa uma medida normal-
mente estabelecida em tempo ou em quantidade de leituras feitas 
no banco de dados para retornar um conjunto de dados solicitado. 
Assim, podemos estabelecer, por exemplo, que se uma consulta con-
some 200 leituras para nos retornar todos os registros de funcioná-
rios que foram contratados no último mês de uma tabela funcionário 
32 Banco de Dados II
e outra consulta consome somente 100 leituras no banco de dados 
para nos retornar esses mesmos registros, logo essa segunda tem um 
“custo” menor.
Veremos, mais à frente, que outra unidade de medida é o tempo, 
o qual, na verdade, é diretamente dependente da própria quantida-
de de leituras feitas no banco de dados, já que cada uma demanda 
uma unidade de tempo e, quanto mais leituras fizermos, mais tempo 
gastaremos.
Desse modo, como você deve estar imaginando, sempre um custo 
menor será melhor do que um custo maior. Nossa meta, assim como 
a dos algoritmos utilizados pelo SGBD, será sempre reduzir o custo de 
uma consulta. Esse custo poderá ser continuamente medido e avalia-
do, procurando identificar se durante a evolução de uso do banco de 
dados ele melhora ou piora.
Os próprios sistemas gerenciadores de banco de dados oferecem 
ferramentas para que esse custo seja medido, avaliado e reduzido. 
É possível executar um comando de busca de um conjunto de dados e 
verificar qual foi o consumo de leituras para cumprir essa tarefa.
Como sabemos, monitorar e otimizar a performance de acesso ao 
banco de dados são uma tarefa do administrador de banco de dados, 
e não do programador. A linguagem SQL é uma linguagem declarativa, 
em que se especifica quais dados se deseja obter, mas não como eles 
serão obtidos. Justamente por esse fato é que o programador não será 
o responsável por medir, avaliar e otimizar os comandos SQL que es-
creve (apesar de em alguns casos poder ajudar, nesse aspecto, conhe-
cendo alguns conceitos que veremos aqui), porém deverá contar com 
a ajuda do administrador de banco de dados para obter melhorias de 
desempenho nos programas que escreve.
A medição e a otimização do custo de uma consulta podem ser fei-
tas basicamente utilizando dois métodos: regras heurísticas e dados 
históricos armazenados. Veremos a seguir uma rápida caracterização 
de cada um deles.
 • Regras heurísticas
Esse processo de medição e otimização de custos de consultas utiliza 
regras básicas, ou regras simples, estabelecidas na álgebra relacional, 
que é derivada da álgebra matemática, ou seja, pode ser demonstrada. 
Processamento e otimização de consultas 33
A álgebra relacional, segundo Date (2004, p. 193), é “um conjunto de 
operações e relações. Cada operação usa uma ou mais relações como 
seus operandos, e produz outra relação como seu resultado”. Com isso, 
podemos, por exemplo, demonstrar que combinar dois conjuntos de 
vogais e números para depois remover somente os pares que têm a 
vogal a tem o mesmo efeito que primeiro selecionar a vogal a e, em 
seguida, combinar somente ela com os números.
Quadro 1
Exemplo de uma regra heurística
Combinar e selecionar
Selecionar e combinar
· Vogais = a, e, i, o, u
· Números = 1, 2, 3
· Combinação = a1, a2, a3, e1, e2, e3, i1, i2, i3, o1, o2, o3, u1, u2, u3
· Seleção onde vogal = “a” => a1, a2, a3
· Vogais = a, e,i, o, u
· Números = 1, 2, 3
· Seleção onde vogal = “a” => a
· Combinação = a1, a2, a3
Conclusão: combinar e selecionar = selecionar e combinar.
Fonte: Elaborado pelo autor.
Várias regras como essas estão disponíveis na álgebra relacional 
e podem ser aplicadas para otimizar o custo de uma consulta. Ima-
gine que, no Quadro 1, a produção de cada uma das combinações 
possíveis pudesse gerar uma unidade de custo. A opção combinar e 
selecionar gerou 15 combinações, para depois remover delas somente 
três itens. Já a opção selecionar e combinar gerou só três combinações. 
Essa segunda opção teria um custo de consulta cinco vezes menor do 
que a primeira.
 • Dados históricos armazenados
Outra estratégia que pode ser utilizada, ou até combinada com a es-
tratégia das regras heurísticas, é o armazenamento de dados sobre as 
34 Banco de Dados II
tabelas, sobre os custos previamente identificados, sobre a frequência 
de uso de uma determinada consulta etc. Isto é, por exemplo, ao aces-
sarmos um banco de dados, solicitando uma lista do nome de todos 
os funcionários e os estados onde nasceram, recebemos os dados da 
consulta. Porém, o SGBD aproveita o trabalho realizado para guardar 
informações, como as descritas a seguir.
Quadro 2
Dados de uma consulta armazenados
Dados obtidos e armazenados após a 
consulta para uso estatístico
· Total de registros na tabela FUNCIONÁRIO = 1300
· Total de registros na tabela ESTADO = 27
· Total de diferentes estados referenciados por funcionários = 15
· Tempo gasto para acesso = X milissegundos
· Consulta executada = muito frequentemente
SQL: consultar os nomes de todos os funcionários e estados onde nasceram.
Fonte: Elaborado pelo autor.
Perceba que o SGBD não só foi capaz de realizar a função de devol-
ver uma lista de 1.300 funcionários com seus devidos estados de nasci-
mento, como também produziu uma informação estatística que pode 
ser usada na próxima vez que alguém desejar executar o mesmo SQL. 
Talvez, ao saber que somente 15 estados de um total de 27 existen-
tes na tabela são referenciados, o SGBD possa escolher uma estratégia 
heurística melhor do que a última utilizada.
Esses dados históricos fazem com que as estratégias de otimização 
das consultas possam ser continuamente otimizadas, enquanto o ban-
co de dados vai gradativamente evoluindo em termos de novos dados 
armazenados, alterados ou excluídos.
Segundo Silberschatz, Korth e Sudarshan (2012), temos alguns ele-
mentos que determinam o custo final de uma consulta, entre eles, a 
quantidade de acessos ao disco, o tempo de processamento (CPU), 
o custo de comunicação e o próprio tempo de avaliação, enquanto 
outras fontes incluem também o custo de uso da memória. Vejamos 
cada um deles.
Processamento e otimização de consultas 35
 • Custo de acessos a disco
Com certeza, esse é o custo mais impactante de todos os envolvidos 
em uma consulta ao banco de dados. Muitas vezes, ele acaba sendo o 
único custo avaliado e considerado, pois, caso seja reduzido, terá im-
pacto sobre o custo final, que efetivamente acaba sendo o real alvo de 
todas as análises.
Quando estudamos os aspectos do armazenamento físico de 
dados em dispositivos magnéticos, vimos que o tempo de latência 
para uma leitura em disco é infinitamente maior do que todos os 
demais tempos envolvidos em uma transação. Desse modo, quanto 
maior for a quantidade de acessos consecutivos ou esparsos ao dis-
co, maior será o tempo total de transferência desses dados para a 
memória para o processamento.
Ao se falar de custo de uma consulta, precisamos ser mais precisos 
e, do ponto de vista de análise de um comando SQL, temos que nos 
dedicar aos comandos de atualização, inclusão e exclusão de dados. 
Apesar de a linguagem SQL falar em consulta (palavra associada ao 
termo query), sabemos que ela comporta comandos para todas as 
funções de manipulação dos dados. Logo, nosso custo de consulta 
pode também representar o custo de atualização, o de exclusão e o 
de inclusão.
Essa observação é importante, pois, se já existe um elevado cus-
to associado à leitura de um bloco de dados em disco, causado pelos 
aspectos mecânicos e pela transferência do bloco (que pode ter tama-
nhos maiores ou menores e gerar assim um tempo maior), o custo será 
duas vezes maior quando estivermos falando de uma inclusão ou atua-
lização de registro. Isso porque, ao gravar um novo dado em disco, o 
sistema operacional aguarda a gravação ser finalizada e realiza uma 
nova leitura sobre o bloco atualizado para verificar se a gravação foi fei-
ta com sucesso e se os dados estão corretamente formatados. Levando 
isso em consideração, cada gravação representa o dobro de tempo: o 
tempo de gravação e o de releitura.
Sabemos que para evitar que os dados frequentemente usados se-
jam constantemente acessados em disco, o sistema operacional ofere-
ce uma área de buffer (ou cache), onde mantém uma cópia dos dados 
para um acesso mais veloz. Se por um lado isso propicia algum benefí-
36 Banco de Dados II
cio, por outro, consome um tempo adicional, visto que os dados serão 
primeiro retirados em blocos do disco e depois movidos para o buffer, 
que eventualmente deverá ser reorganizado, para então serem provi-
dos para o programa que os solicitou.
Como dissemos, todos esses tempos compõem o tempo total de 
uma operação de consulta ao banco de dados. No entanto, sem dú-
vidas, o tempo de latência do disco será o predominante e, por isso, 
qualquer redução na quantidade de leituras em disco é essencial na 
otimização das consultas.
 • Tempo de CPU
Outro fator que pode ser avaliado é o tempo total de CPU consu-
mido para concluir uma consulta. Essa informação também é provida 
pelas ferramentas de análise de performance de comandos SQL ofere-
cidas pelo SGBD.
Quando falamos em tempo de CPU, temos que imaginar que quan-
to mais tempo a CPU trabalhar para finalizar um mesmo comando SQL, 
mais complexa terá sido sua execução. Talvez tenhamos uma situação 
em que, apesar de reduzirmos o custo de acesso ao disco, teremos um 
aumento no consumo de CPU para finalizar a execução do mesmo co-
mando. Isso significa que tivemos menor transferência de dados entre 
disco e memória, mas muito mais processamento em memória.
Uma vez que o tempo de processamento de CPU é muito menor do 
que o tempo de acesso ao disco, podemos continuar a ter a preocu-
pação de buscar uma redução desse tempo (pois qualquer economia 
é sempre benéfica), porém sempre mantendo a visão de que reduzir 
80% do tempo de CPU, enquanto o consumo de disco aumentar em 
somente 1%, pode não ser um benefício real ao final. Isso porque 
reduziremos muito um elemento com pouco impacto, em detrimento 
do aumento em um elemento que gera alto impacto – nesse caso, o 
acesso ao disco.
 • Custo de comunicação
Com o advento do uso de bancos de dados distribuídos, ou mesmo 
dos bancos de dados centralizados, mas hospedados em nuvens pri-
vadas ou públicas, bem como do acesso a esses bancos de dados por 
meio de dispositivos remotos (APPs) e de webservices, um outro ele-
mento passou a ser agregado ao custo final da execução de uma con-
sulta no banco de dados: o custo de comunicação. Canais para acesso 
Processamento e otimização de consultas 37
com maior latência (um servidor de banco de dados hospedado em 
outro continente pode agregar até quatro segundos de tempo de latên-
cia entre receber um pedido e devolver um dado) podem representar 
um custo importante a ser considerado na execução de uma consulta. 
Uma consulta que retorne maiores volumes de dados em contraste 
com uma que retorne um menor volume pode acabar sendo um fator 
importante a ser considerado.
 • Tempo de avaliação
Um dos elementos que pode ser utilizado para a avaliação de uma 
melhor estratégia para executar uma consulta é o armazenamento 
de dados estatísticos dessa própria consulta. Sendo assim, temos que 
considerar que, além de retornar os dados solicitados, o SGBD tem ain-
da três trabalhos adicionais que consomem tempo: consultaros dados 
históricos, elaborar uma estratégia de montagem da consulta e final-
mente armazenar novos dados históricos, pois o panorama pode ter se 
alterado desde a última consulta.
Desse modo, temos um consumo de tempo adicional para que 
possamos otimizar nossas consultas. Normalmente, esse tempo será 
bem menor do que o tempo final da execução da própria consulta e 
o do efetivo acesso ao disco para obtenção dos dados. Portanto, po-
demos considerar que é um tempo bem investido pelo SGBD e pode 
praticamente ser desconsiderado.
 • Custo de armazenamento temporário
Se o acesso ao disco para leitura é demorado e o para gravação é 
duas vezes mais demorado, imagine a situação em que essa gravação 
e leitura são realizadas somente para armazenar dados temporários 
durante a execução de uma consulta. No Quadro 1, vimos que durante 
a execução de um comando SQL tínhamos a criação de um vetor tem-
porário com a combinação das vogais com os números. Isso gera uma 
área de armazenamento temporário de dados, a qual pode represen-
tar muitos megabytes de dados, considerando, por exemplo, a combi-
nação de duas tabelas bastante grandes e a geração de um produto 
cartesiano (combinação completa) entre elas.
Estamos, então, falando de um consumo elevado de tempo para 
gravação e leitura de dados em disco que sequer serão utilizados ao 
final da execução do comando, ou que nem ao menos serão vistos por 
quem solicitou os dados finais.
38 Banco de Dados II
Após termos visto os principais elementos geradores de consumo 
de recursos – principalmente tempo – na execução de uma consulta, 
podemos imaginar que pequenos ganhos podem ser significativos a 
partir do momento que uma consulta tenha uma grande frequência 
de execução. Alguns segundos reduzidos em uma única consulta ou al-
guns acessos ao disco que não sejam realizados podem significar mui-
tas horas de processamento reduzido e, principalmente, uma maior 
performance não só para a transação em análise, mas também para as 
demais transações do banco de dados.
Precisamos lembrar que estamos falando de um recurso finito e 
compartilhado. Isto é, o mesmo SGBD que não executa uma consulta 
de modo otimizado prejudica todas as outras transações que executam 
consultas otimizadas. O tempo que ele dedica às transações com alto 
consumo de recursos é subtraído do tempo e dos recursos que poderia 
oferecer às demais consultas.
O cuidado com esses aspectos é uma preocupação contínua do 
administrador de banco de dados, que deve monitorar o desempenho 
de cada consulta, podendo atuar de modo top-down, ou seja, reconhe-
cendo algumas transações mais consumidoras de recursos e, em se-
guida, as decompondo em unidades menores até chegar a comandos 
específicos executados por um programa ou uma função específica.
Dessa maneira, ele deverá propor ajustes que podem ir desde 
mudanças no modelo de dados relacional (criação de novas tabelas, 
desnormalização, criação de índices etc.), passando por alterações no 
código das aplicações e chegando até as mudanças na infraestrutura 
de execução do SGBD (aumento de memória e de quantidade de CPUs, 
processamento paralelo etc.).
De modo geral, alguns cuidados e estratégias são adotados para 
o caso de grandes bancos de dados, que são aqueles cujas tabelas 
armazenam muitos registros (centenas de milhões). Uma dessas es-
tratégias é a recomendação de que os dados sejam segmentados, o 
volume de armazenamento seja reduzido, as informações históricas 
não estejam on-line o tempo todo, as consolidações de dados sejam 
geradas, entre outras.
Já para bancos de dados de pequeno volume, talvez seja muito mais 
efetivo o processo de otimização de consumo de recursos de compu-
tação, e não necessariamente o de redução de acessos ao disco, visto 
No vídeo Análise de 
Desempenho de Consultas 
SQL em Banco de Dados 
Oracle, publicado pelo ca-
nal de Leonardo Mairene 
Muniz, é possível ver 
exemplos do processo de 
monitoração dos planos 
de execução de coman-
dos SQL sendo executa-
dos no gerenciador de 
banco de dados Oracle. 
A análise do resultado de 
cada comando é comen-
tada e demonstrada com 
base nos dados indicados 
em tela pelo SGBD.
Disponível em: https://youtu.
be/I604SeSK_d8. Acesso em: 26 
nov. 2020.
Vídeo
https://youtu.be/I604SeSK_d8
https://youtu.be/I604SeSK_d8
Processamento e otimização de consultas 39
que parte significativa desses dados poderão estar em buffer, quase 
todo o tempo, reduzindo a latência geral.
Além disso, caso o banco de dados tenha uma forte dependência 
da camada de comunicação, seja distribuído, ou tenha acesso remo-
to, uma atenção especial deve ser dedicada ao tempo de latência da 
camada de comunicação. É nítido que, eventualmente, teremos um 
banco de dados de grande ou pequeno volume que também depen-
derá fortemente de uma camada de comunicação. Nesses casos, um 
conjunto de iniciativas será necessário para equalizar os elementos 
geradores de alto consumo de recursos e tempo na execução das 
consultas.
2.2 Avaliação de expressões 
Vídeo A avaliação de expressões da álgebra relacional tem correlação 
direta com a otimização dos comandos SQL que serão submetidos à 
execução pelo SGBD. Ao ser elaborado um comando SQL para recupe-
ração ou atualização de dados, por exemplo, temos em sua estrutura 
boa parte das funções da álgebra relacional, como a seleção, projeção, 
junção, entre outras.
Nos próximos exemplos será importante ter a correta interpreta-
ção das expressões, a fim de poder perceber de que modo elas podem 
ser otimizadas ou quais regras o SGBD aplica para transformar essas 
expressões.
No quadro a seguir veremos algumas das principais operações, 
suas características e aplicabilidades.
Quadro 3
Operações da álgebra relacional (lista parcial)
Operação Símbolo Sintaxe
Seleção ou restrição σ σ condição (Relação)
Projeção π π lista de atributos (Relação)
União ∪ Relação 1 ∪ Relação 2
Interseção ∩ Relação 1 ∩ Relação 2
Produto cartesiano Χ Relação 1 Χ Relação 2
Junção |Χ| Relação 1 |Χ| Relação 2
Fonte: Elaborado pelo autor.
40 Banco de Dados II
 • Características das operações
1. Seleção σ: seleciona tuplas (linhas) que satisfazem certa 
condição.
Indicada pela letra grega sigma, é uma operação que, dentro 
de um conjunto originalmente fornecido, gera um subconjunto 
com a mesma estrutura, mas apenas com os elementos do 
conjunto original que atendem à condição estabelecida. A seleção 
realiza uma filtragem de linhas de uma tabela.
Relação R1:
Nome Data de nascimento
Estado de 
nascimento
José 25/03/1962 PR
Maria 11/07/1964 SC
Pedro 11/11/1997 PR
Aplicando a operação: σ estado de nascimento = SC (R1), 
temos:
R2:
Nome Data de nascimento
Estado de 
nascimento
Maria 11/07/1964 SC
2. Projeção π: mantém somente os atributos solicitados na 
relação de saída.
Indicada pela letra grega pi, gera um conjunto de saída, 
contendo uma tupla para cada tupla de entrada, porém 
possuindo somente os atributos informados na lista de 
argumentos da operação. A projeção realiza uma filtragem de 
colunas de uma tabela.
Relação R1:
Nome Data de nascimento
Estado de 
nascimento
José 25/03/1962 PR
Maria 11/07/1964 SC
Pedro 11/11/1997 PR
Aplicando a operação: π nome, estado de nascimento (R1), 
temos:
Processamento e otimização de consultas 41
R2:
Nome Estado de nascimento
José PR
Maria SC
Pedro PR
3. Produto Cartesiano Χ: gera a combinação de tuplas de 
duas relações.
O resultado do produto cartesiano de duas relações quaisquer 
é uma terceira relação contendo todas as combinações 
possíveis entre os elementos das relações originais.
Na relação gerada pelo produto cartesiano, teremos um total 
de linhas resultante, que é a multiplicação do total de linhas da 
Relação R1 com o total de linhas da Relação R2. Em cada linha 
produzida, teremos todas as colunas da Relação R1 agregadas 
a todas as da Relação R2. Essa é uma operação denominada 
binária, ou seja, ela combina duas relações.
Relação R1:
Nome Data de nascimento
Estado de 
nascimento
José 25/03/1962PR
Maria 11/07/1964 SC
Pedro 11/11/1997 PR
Relação R2:
Produto Valor
001 R$ 10,00
005 R$ 12,00
Aplicando a operação: R1 Χ R2, produzimos:
R3:
Nome Data de nascimento
Estado 
nascimento Produto Valor
José 25/03/1962 PR 001 R$ 10,00
Maria 11/07/1964 SC 001 R$ 10,00
Pedro 11/11/1997 PR 001 R$ 10,00
José 25/03/1962 PR 005 R$ 12,00
Maria 11/07/1964 SC 005 R$ 12,00
Pedro 11/11/1997 PR 005 R$ 12,00
42 Banco de Dados II
4. União ∪: retorna a união das tuplas de duas relações R1 e R2.
Une todas as linhas da relação R2 às da relação R1, removendo 
as eventuais duplicatas. A quantidade e as características dos 
atributos entre as relações devem ser similares. A relação 
resultante terá também os mesmos atributos em igual 
quantidade e características.
Relação R1: 
Nome Data de nascimento
Estado de 
nascimento
Eliana 25/03/1962 PR
Maria 11/07/1964 SC
Karla 11/11/1997 PR
 Relação R2:
Nome Data de nascimento
Estado de 
nascimento
Eliana 25/03/1962 PR
Ricardo 14/08/1984 SP
Humberto 10/02/2009 RJ
João 08/08/2010 SP
Aplicando a operação: R1 ∪ R2, produzimos:
Nome Data de nascimento
Estado de 
nascimento
Eliana 25/03/1962 PR
Maria 11/07/1964 SC
Karla 11/11/1997 PR
Ricardo 14/08/1984 SP
Humberto 10/02/2009 RJ
João 08/08/2010 SP
5. Interseção ∩: gera uma relação com as tuplas comuns a R1 
e R2.
Essa operação produz como resultado uma relação que 
contém, sem repetições, todos os elementos que são comuns 
às duas tabelas fornecidas como operandos.
As tabelas também devem possuir o mesmo número de 
colunas e as características semelhantes.
Processamento e otimização de consultas 43
Relação R1: 
Nome Data de nascimento
Estado de 
nascimento
Eliana 25/03/1962 PR
Maria 11/07/1964 SC
Karla 11/11/1997 PR
Relação R2:
Nome Data de nascimento
Estado de 
nascimento
Eliana 25/03/1962 PR
Ricardo 14/08/1984 SP
Karla 11/11/1997 PR
João 08/08/2010 SP
Aplicando a operação: R1 ∪ R2, obtemos:
R3:
Nome Data de nascimento
Estado de 
nascimento
Eliana 25/03/1962 PR
Karla 11/11/1997 PR
6. Junção Natural |Χ|: retorna à combinação de tuplas de duas 
relações R1 e R2 que satisfazem a uma regra de correlação.
Diferentemente do produto cartesiano, essa operação 
estabelece um vínculo entre a relação R1 e a relação R2 
por meio de um ou mais atributos em comum (criando um 
vínculo), e não simplesmente combinando todas as tuplas 
de uma relação com as tuplas de outra. Somente as tuplas 
que têm uma vinculação em um ou mais atributos serão 
combinadas.
Relação R1:
Nome Data de nascimento
Estado de 
nascimento
Produto 
comprado
José 25/03/1962 PR 001
Maria 11/07/1964 SC 005
Pedro 11/11/1997 PR 001
44 Banco de Dados II
Relação R2:
Produto Valor
001 R$ 10,00
005 R$ 12,00
Aplicando a operação: R1 |Χ| R2 por meio do atributo/produto, 
produzimos:
R3:
Nome Data de nascimento
Estado de 
nascimento
Produto 
comprado Produto Valor
José 25/03/1962 PR 001 001 R$ 10,00
Maria 11/07/1964 SC 005 005 R$ 12,00
Pedro 11/11/1997 PR 001 001 R$ 10,00
Nos exemplos, pudemos ver a execução de operações relacionais 
isoladas – assim, uma ou mais relações eram submetidas a somente 
uma operação de cada vez, produzindo uma nova relação de saída. No 
entanto, a realidade mais comumente encontrada em situações do dia 
a dia é aquela em que diversas operações relacionais são executadas 
em conjunto, uma condicionada à execução da outra.
Nesse caso, temos que estabelecer uma ordem de precedência para 
a avaliação e execução de cada uma das operações, de modo a obter 
o resultado desejado, porém tendo o desempenho mais adequado. 
Segundo o exemplo dado por Silberschatz, Korth e Sudarshan (2012), 
considere a expressão da álgebra relacional para a consulta: “encontrar 
os nomes de todos os clientes que tenham uma conta em qualquer 
agência localizada no Brooklyn”.
π nome-cliente (σ cidade-agência = Brooklyn 
(agência |Χ| (conta |Χ| depositante)
A representação dessa expressão também pode ser feita por meio 
de uma estrutura gráfica, chamada de árvore de operação, conforme a 
figura a seguir.
Processamento e otimização de consultas 45
Figura 1
Representação gráfica da expressão da álgebra relacional
π
σ
|Χ|
|Χ|
nome_cliente
agência
conta depositante
cidade_agência = Brooklyn
Fonte: Silberschatz; Korth; Sudarshan; 2012, p. 383.
Nesse exemplo fica evidente que temos quatro operações relacio-
nais a serem executadas. A análise desse tipo de estrutura requer, além 
das otimizações possíveis, uma ordem de precedência. A execução das 
operações deve ser sempre realizada nos nós mais inferiores da ár-
vore – esses que, após produzirem seus resultados, alimentam os nós 
imediatamente superiores e assim por diante até que atinjam a raiz.
Assim sendo, só podemos executar a projeção depois de ter execu-
tado a seleção, que por sua vez só pode ser executada depois da jun-
ção entre as relações de agência, conta e depositante ser feita. Temos, 
então, que começar executando a junção entre depositante e conta 
para que, ao obter esse resultado, possamos combiná-lo com a relação 
agência, produzindo um novo resultado, o qual será submetido à se-
leção, retornando mais um novo resultado, que por fim terá sobre ele 
aplicada a operação de projeção.
São justamente esses resultados intermediários das operações exe-
cutadas anteriormente, os quais precisam ser repassados para os ní-
veis superiores, que podem se utilizar de dois tipos de estratégias do 
sistema gerenciador de banco de dados: a materialização de relações 
temporárias ou a passagem por pipeline (canalização de resultados).
Na materialização de resultados, são todos gravados em discos em 
relações temporárias gerenciadas pelo SGBD. Nessa estratégia, temos, 
portanto, um grande volume de operações de gravação e leitura em 
disco, as quais sabemos que são os pontos de maior causa de lentidão 
46 Banco de Dados II
no processamento de um comando SQL. Cada relação temporária será 
inteiramente gravada em disco para, depois, já na próxima fase, ser to-
talmente lida e processada. Dessa maneira, temos um processamento 
baseado na passagem de relações de uma operação para outra.
Com o intuito de evitar todo esse grande volume de gravações e 
leituras físicas em disco, eis que surge uma nova estratégia, chamada 
de pipeline ou canalização de resultados. Nessa estratégia, ao invés de 
serem geradas relações intermediárias para armazenamento dos 
resultados nos níveis mais inferiores das árvores de operações, esses 
resultados são passados para os níveis superiores, tupla por tupla, e 
não mais como relações. Evita-se, desse modo, ter que produzir toda 
uma relação – por exemplo, para 10.000 tuplas – para então repassar 
todo esse conjunto. Assim, pode-se produzir a tupla 1 e passá-la au-
tomaticamente para o nível superior da árvore para que ela seja pro-
cessada no nível superior, enquanto o nível inferior volta a trabalhar 
produzindo a tupla 2, e assim por diante. É como se uma tupla gerada 
no nível mais inferior da árvore fosse canalizada e seguisse até a raiz 
da árvore, passando por um túnel onde cada uma das operações seria 
executada sobre essa tupla. Logo atrás dela viria outra tupla, também 
seguindo o mesmo canal, até que todas as 10.000 tuplas do exemplo 
fossem processadas uma a uma pela canalização.
Essa estratégia se mostra muito mais produtiva e apresenta um de-
sempenho muito melhor, principalmente quando cada uma das ope-
rações da árvore pode ser alocada em diferentes threads (processos) 
e, também, quando essas threads podem se aproveitar de múltiplos 
processadores (CPUs), gerando uma capacidade de criar o paralelismo 
entre níveis da árvore. Porém, infelizmente, nem sempre ela se mostra 
viável; nesses casos, o sistema gerenciador de banco de dados volta a 
utilizar a materialização como alternativa.
Outro aspecto relativo à avaliação das expressões da álgebra rela-
cional diz respeito à análise de precedência dos operadores lógicos. 
Como já vimos, quando submetemos uma SQL complexa, ela acaba 
sendo decomposta