Conceitos Básicos de Banco de Dados II

Prévia do material em texto

BANCO DE DADOS II 
 
Conceitos Básicos 
 
1 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
 
 
 
DCC-UFLA, Lavras 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Banco de Dados (BD) 
 Uma coleção logicamente coerente de dados 
relacionados 
• Um agrupamento randômico de dados não pode ser 
considerado um BD 
 Dados devem ser interpretáveis → informação 
• Significado implícito 
 Um BD é projetado com um propósito específico 
• Grupo de usuários alvo 
• Acesso através de programas de aplicação 
2 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Banco de Dados (BD) 
3 
BD 
 Um BD representa determinados aspectos 
do mundo real: minimundo ou universo de 
discurso 
• Mudanças no minimundo são refletidas no BD 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Típico Cenário de Aplicação 
4 
App3 App1 App2 ... 
Informação Duplicada/ 
Inconsistente 
... 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Solução: SGBD 
5 
App3 App1 App2 
BD 
Sistema Gerenciador de Banco de Dados 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
SGBD: Vantagens 
 Independência física de dados 
• Detalhes sobre o armazenamento e acesso aos 
dados são “escondidos” de usuários e aplicações 
• Implantação de diferentes técnicas 
armazenamento (e.g., particionamento, 
clusterização, compressão) e métodos de acesso 
(e.g., índices) são transparentes para aplicações 
6 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
SGBD: Vantagens (2) 
 Independência lógica de dados 
• Informações sobre a estrutura dos dados e 
restrições de integridade é mantida e controlada 
de maneira centralizada e independente de 
aplicação, linguagem de programação, etc 
• O isolamento de aplicações de modificações como 
adição ou deleção de atributos ou 
relacionamentos e adição de novas restrições é 
facilitada (eg., através da definição de novos 
mapeamentos e visões) 
 
 7 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
SGBD: Vantagens (3) 
 Controle de redundância e consistência de 
dados 
• Dados duplicados inadvertidamente causam 
desperdício de espaço de armazenamento e 
overhead para manutenção da consistência entre 
múltiplas cópias dos dados 
 
 
 
8 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
SGBD: Vantagens (4) 
 Processamento de transações 
• Permite o compartilhamento e acesso 
concorrente a dados entre usuários e aplicações 
 Backup e recuperação de falhas 
 O conceito de transação garantido pelo SGBD 
• Aplicações podem ser desenvolvidas como se 
executassem em um ambiente isolado e livre de 
falhas 
9 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
SGBD: Vantagens (5) 
 Suporte de múltiplas visões dos dados 
• Frequentemente, diferentes grupos de usuários 
devem ter diferentes “perspectivas” sobre os 
dados; certos dados não devem ser “vistos” por 
todos usuários (e.g., dados de professores e 
alunos) 
 Mecanismo centralizado de controle de acesso 
e autenticação 
10 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
SGBD: Vantagens (6) 
 Linguagem comum de acesso 
• Transforma a necessidade de um mapeamento N-N entre 
linguagens na necessidade de um mapeamento 1-N 
 Linguagem declarativa de alto-nível 
• Usuário especifica “o que” e não “como” 
• Menos código precisa ser escrito -> facilidade de 
entendimento e manutenção 
• Facilita a obtenção da independência lógica 
• Performance não é seriamente afetada 
11 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
SGBD: Vantagens (7) 
 Mecanimos eficientes de acesso e modificação 
dos dados 
• Estruturas de armazenamento otimizadas 
• Controle de buffer “tailor-made” 
• Índices 
• Otimização de consultas 
 Aplicação de restrições integridade, acões 
automáticas ativadas por atualizações, 
inferências, etc 
12 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Conceitos Básicos 
 Abstração de Dados: 
• Supressão de detalhes a respeito da organização 
dos dados e armazenamento 
• Destaque de propriedades essenciais dos dados 
que permitam melhor entendimento e 
aproveitamento do mesmo 
13 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Modelo de Dados 
 Define os seguintes aspectos de um banco de 
dados: 
• Estrutura dos dados: tipos de (estrutura de dados) e 
seus relacionamentos 
• Manipulação dos dados: operadores ou regras de 
inferência que podem ser aplicados em qualquer 
instâncias válida dos dados para recuperar ou derivar 
dados de qualquer parte destas estruturas em 
qualquer combinação possível 
• Restrições de integridade: regras de integridades que 
implicitamente ou explicitamente definem os estado 
válidos de um banco de dados, mudanças de estados, 
ou ambos 
14 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Modelo de Dados (2) 
 Um modelo não precisa (e provavelmente não 
deve) ditar uma única linguagem para 
manipulação de dados e consulta porque 
diferentes categorias de usuários irão requerer 
provavelmente linguagens com diferentes 
características 
15 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Modelo de Dados (3) 
 Além dos dados em si, alguns modelos de dados 
também podem expressar aspectos dinâmicos e 
comportamentais de aplicações em banco de 
dados (combinação de projetos de banco de 
dados e softwares). 
• Ex.: Operações definidas pelo usuário. 
• Ex. destes modelos de dados: modelo orientado a 
objetos e objeto-relacional 
• No modelo relacional, é possível associar 
comportamento para um relação através stored 
procedures e triggers (procedimentos 
armazenamentos) 
 
16 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Modelos de Dados (5) 
 Modelos de dados podem ser categorizados de acordo com 
os tipos de conceitos usados para descrever a estrutura dos 
dados. 
 Modelos conceituais: utiliza conceitos que são similares a 
maneira que os humanos percebem os dados, por exemplo, 
usando entidades, atributos, e relacionamentos (modelo 
Entidade-Relacionamento). 
 Modelos lógicos ou de representação: define um modelo, 
que apesar de definir um layout conceitual dos dados, é 
também adequado para operações de manipulação sobre 
os dados (e.g., modelo relacional) 
 Modelos físicos: utiliza conceitos que descreve detalhes 
sobre o como os dados são armazenados no computador 
 
17 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Modelo de Dados (6) 
 É importante notar que um mesmo modelo de 
dados pode ser empregado em diferentes 
níveis de abstração e para diferentes 
funcionalidades 
 Exemplo: modelos de dados XML 
 
18 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Modelo Relacional 
(Revisão) 
19 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Modelo Relacional 
 Estrutura dos dados 
• Relações 
• Mapeamento de E/R para Relacional 
• Normalização 
 Manipulação dos dados 
• Álgebra relacional 
• Cálculo relacional (tupla e domínio) 
 Integridade dos dados 
• Restrições ímplicitas e explícitas 
20 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Modelo Relacional 
 Modelo de dados formal criado por Edgar F. 
Codd em 1970 
 Base matemática 
• Teoria do conjuntos 
• Lógica de primeira ordem 
21 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Modelo Relacional 
 Origem de uma indústria bilionária (SGBDs 
Relacionais Oracle, IBM DB2, Microsoft SQL 
Server) 
• Em 2005, a revista Forbes elegeu o modelo relacional 
como uma das mais importantes inovações dos 
últimos 85 anos, na companhia de outras inovações 
extremamente conhecidas como o computador 
eletrônico digital, a televisão, a penicilina, o telefone 
celular, o transistor, o laser, a Internet, CD, etc 
 
22 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Modelo Relacional: 
Conceitos Básicos Principal conceito: relação 
• Representa entidades e relacionamentos 
• Informalmente: uma tabela de valores 
 Blocos de construção 
• Domínio 
• Esquema de relação 
• Atributo 
• Tupla 
23 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Domínio 
 Domínio: Um conjunto atômico de valores 
 É comum associar um nome e um formato (ou 
tipo de dados) a um domínio 
• Nome: Nome_Funcionário, Formato: string de até 
100 caracteres 
• Nome: Nr_CPF, Formato: número de 11 dígitos 
• Nome: Data_Nascimento, Formato: d/m/a, onde d 
em [01,31], m em [01,12], e a em [1900, ano atual] 
24 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Esquema de Relação 
 Esquema de relação = descrição de uma relação 
 Notação: R(A1, A2,..., An), onde: 
• R é o nome da relação 
• A1, A2,..., An é uma lista ordenada de atributos
 
• Cada atributo Ai, 1<=i<=n, é o nome de um papel 
desempenhado por algum domínio D no esquema 
de relação R; denotado por dom(Ai) 
• n é o grau da relação R 
 
 
25 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Esquema de Relação: Exemplo 
26 
Nome CPF D_Nascimento Endereço Fone 
Funcionário 
 R = Funcionário 
 Atributos: 
• A1 = Nome, dom(Nome) = Nome_Funcionário 
• A2 = CPF dom(CPF) = Nr_CPF 
• A3 = D_Nascimento dom(D_Nascimento) = Data_Nascimento 
• A4 = Endereço dom(Endereço) = Endereço 
• A5 = Fone dom(Fone) = Formato_Telefone 
 Grau = 5 
 
 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Relação 
 Dado um esquema de relação R(A1, A2,..., An), 
uma relação de R, denotado por r(R), é um 
conjunto de tuplas {t1, t2, …, tm} 
• Cada tupla ti, 1<=i<=m, é uma lista ordenada de 
valores <v1, v2, …, vn> 
• Cada valor vi, 1<=i<=n, é um elemento do domíminio 
dom(Ai) ou é o valor NULL 
• Dada uma tupla t, o valor na posição i (relativo ao 
atributo Ai) é denotada por t[Ai] 
 A cardinalidade de r(R), denotada por |r|, 
correspondente ao número de tuplas em r(R) 
27 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Intensão e Extensão 
28 
Metadados: 
Intensão 
Estado do Banco de Dados: 
Extensão 
Nome CPF D_Nascimento Endereço Fone 
José Silva 11111111 07/09/1969 Av. Brasil, 16 151515 
João Rocha 222222222 23/12/1969 Rua 9, 232 231231 
Alan Ribeiro 809333333 13/10/1971 Av. D, 150 131313 
Maria Santos 444444444 NULL Av. C126, 98 NULL 
Márcia Oliveira 555555555 18/11/1970 Rua 3, 25 NULL 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Relação: Exemplo 
29 
Nome CPF D_Nascimento Endereço Fone 
Funcionário 
José Silva 11111111 07/09/1969 Av. Brasil, 16 151515 
João Rocha 222222222 23/12/1969 Rua 9, 232 231231 
Alan Ribeiro 809333333 13/10/1971 Av. D, 150 131313 
Maria Santos 444444444 NULL Av. C126, 98 NULL 
Márcia Oliveira 555555555 18/11/1970 Rua 3, 25 NULL 
Atributos 
Tuplas 
Intensão Extensão Valores 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Relaçao: Definição Formal 
 Uma relação matemática de grau n sobre os 
domínios dom(A1), dom(A2), ..., dom(An), o 
que representa um subconjunto do produto 
Cartesiano do domínios que definem R: 
• r(R) ⊆ dom(A1) × dom(A2) × dom(An) 
30 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Características de Relações 
Relação: um conjunto de tuplas 
31 
 Não existe uma ordenação em particular definida 
sobre as tuplas de uma relação 
• Ordenações arbitrárias podem ser definidas 
logicamente baseando-se nos valores das tuplas 
− Ordenação alfabética baseada no valor atributo Nome da 
relação Funcionário 
 Todas tuplas são distintas (tuplas duplicadas, isto 
é, tuplas com os valores idênticos em todos 
atributos, não são permitidas) 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Esquema de Relação: 
Interpretações 
 Asserção (ou declaração) sobre entidades ou 
relacionamentos -> cada tupla representa um 
fato ou instância desta asserção 
 Predicado envolvendo entidades ou 
relacionamentos -> tuplas possuem valores que 
satisfazem estes predicados 
32 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Restrições do Modelo Relacional 
 Restrição de domínio 
• Especifica que o valor de cada atributo A deve ser 
um valor atômico (indivisível) do domínio dom(A) 
 Restrição em valores NULL 
• Especifica se valores NULL são permitidos para um 
determinado atributo 
• Ex.: “Todo funcionário deve um valor válido para 
os atributos Nome e CPF” 
33 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Restrições de Chave 
 Todo esquema de relação possui um subconjunto de 
atributos que possuem a propriedade de que nenhum par 
de tuplas possui valores idênticos para estes atributos 
• Inferência a partir da definição de que todas tuplas são distintas 
em uma relação 
• Subconjunto trivial: todos os atributos de um esquema de relação 
 Qualquer subconjunto com esta propriedade é chamado de 
super-chave de um esquema de relação R 
 Uma super-chave é denotada por SC, os valores de uma 
superchave para uma tupla t é t[SC] 
 Restrição de chave: Para quaisquer tuplas t1 e t2, t1 = t2, em 
um relação r(R), tem-se: t1*SC+ ≠ t2[SC] 
 
 
 
34 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Restrições de Chave (2) 
 Chave: uma super-chave com a restrição 
adicional de minimalidade 
• Removendo qualquer atributo de uma chave C faz 
com que C deixe de ser uma super-chave 
 Todas chaves em um esquema de relação são 
chamadas chave candidatas 
 Uma chave candidata é escolhida para ser a 
chave primária de um esquema de relação 
• Usada para identificar unicamente todas as tuplas de 
uma relação 
 Chaves primárias não podem ter o valor NULL 
35 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Chaves: Exemplo 
36 
Nome CPF D_Nascimento Endereço Fone 
Funcionário 
chave primária 
super-chave 
Nome Endereço 
Nome Fone 
chave candidatas 
Outras chaves? 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Banco de Dados Relacional 
 Esquema de um BD relacional: um conjunto 
de esquemas de relações S = {R1, R2, …, Rm} e 
um conjunto de restrições I 
 Banco de Dados Relacional: Um banco de 
dados BD relativo a S é um conjunto de 
relações BD = {r1(R1), r2(R2), …, rm(Rm)} onde 
cada ri(Ri), 1<=i<=m, satisfaz as restrições em I 
37 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Banco de Dados Relacional 
 Na prática, o termo banco de dados relacional 
se refere conjuntamente ao conjunto de 
esquemas e relações 
 Um BD é dito estar em estado válido se todas 
as retrições de integridade em I são satisfeitas; 
caso contrário, o estado do BD é inválido 
38 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Esquema 
de BD 
Relacional 
[EN07] 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
BD Relacional 
[EN07] 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Restrições de Integridade 
Referencial 
 Mantém a consistência entre tuplas de duas 
relações 
 Informalmente, se uma tupla de uma relação 
faz referência a uma outra relação, então esta 
tupla deve fazer referência a uma tupla que de 
fato exista nesta outra relação 
• Ex.: O valor (não NULL) do atributo Dno em toda 
tupla da relação EMPLOYEE deve ser idêntico ao 
valor do atributo Dnumber de alguma tupla da 
relação DEPARTMENT 
41 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Restrições de Integridade 
Referencial (2) 
 Definição formal através do conceito de chave 
estrangeira 
 Um conjunto de atributos CE em um esquema de 
relação R1 é uma chave estrangeira de R1 que faz 
referencia a um esquema de relação R2 se ele 
satisfaz as seguintes condições: 
• Os atributos em CE possuem o mesmo domínio que os 
atributros CP da chave primária de R2 
• Os valores de CEem uma tupla t1 da relação r1(R1) ou 
ocorrem como valores de CP em alguma tupla t2 de 
r2(R2), isto é t1[CE]=t2[CP], ou são NULL 
 
42 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Representação 
Gráfica [EN07] 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Outros Tipos de Restrições 
 Restrições de integridade semântica: 
• Exemplos: “O salário de um empregado não pode 
ser maior que o do seu supervisor”, “O número 
máximo de horas de trabalho por semana é 56” 
• Aplicadas no BD através de asserções e triggers 
ou nos programas de aplicação (mais comum) 
 Restrição de depêndencia funcional 
• Informalmente, o valor de um mais atributos 
determinam o valor de outros atributos 
• Conceito fundamental para o projeto de 
esquemas de BDs relacionais (normalização) 
44 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Outros Tipos de Restrições 
 Restrições de estado 
• Restrições que um banco de dados válido deve 
satisfazer 
 Restrições de transição 
• Definem alterações válidas em um BD. Ex.: O 
salário de um empregado pode apenas aumentar 
 
45 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Operações de Modificação 
 Três operações básicas: 
• Inserção: insere novas tuplas em uma relação 
• Deleção: remove tuplas de um relação 
• Atualização: atualiza o valor atributos em tuplas 
 O SGBD deve garantir que a execução de 
destas operações não viole restrições de 
integridade 
46 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Violações de Integridade: Inserção 
 Dominio: o valor de um ou mais atributos não 
faz parte do domínio 
 Chave: o valor de chave da nova tupla é NULL ou 
já ocorre em outra tupla 
 Integridade referencial: o valor de qualquer 
chave estrangeira da nova tupla faz referência a 
uma tupla inexistente na relação referenciada 
 Medida corretiva: A operação de inserção é 
rejeitada (medida mais comum) 
47 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Violações de Integridade: Deleção 
 Apenas restrições de integridade referencial 
podem ser violadas se a tupla sendo removida é 
referenciada pela chave estrangeira de outras 
tuplas 
 Medidas corretivas: 
• Rejeição da operação 
• Propagação da operação de deleção através da 
remoção da tuplas que referenciam a tupla deletada 
• Modificação dos valores dos atributos da chave 
estrangeira para NULL (pode não ser possível se estes 
valores fazem da chave primária) 
48 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Violações de Integridade: 
Atualização 
 Violação idênticas às operações de inserção e 
deleção quando os atributos atualizados não 
fazem parte da chave primária ou de alguma 
chave estrangeira 
• Atualização pode ser interpretada como a deleção 
de uma tupla e a inserção de uma nova 
 Caso contrário, apenas restrições de domínio 
podem ser violadas 
49 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 50 
Algebra Relacional 
(Revisão) 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Álgebra Relacional 
 Todo modelo de dados deve prover um conjunto 
básico de operações para manipulação de dados 
 O cojunto de operações para manipulação de dados 
do modelo relacional é a álgebra relacional 
 O resultado de cada operação é uma relação. 
Operações podem ser concatenadas formando uma 
expressão cujo resultado é também uma relação: 
• Propriedade de encerramento (closure) 
• Set-at-a-time 
51 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Álgebra Relacional 
 Fundação formal para operações do modelo 
relacional 
 Provê uma base para implementação e 
otimização de consultas em SGBDs (por 
exemplo, SQL) 
 
52 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Processamento de Consultas SQL 
53 
SELECT C.ID, C.Nome, COUNT( * ) 
FROM Aluno as A, Curso as C 
WHERE A.CID = C.ID 
GROUP BY C.ID, C.Nome 
HAVING COUNT( * ) >= 100 
Consulta SQL 
Query 
SELECT FROM WHERE GROUP BY HAVING 
C.ID C.Nome Count( * ) Aluno Curso C.ID C.Nome Condição 
Count ( * ) >= 100 
Condição 
A.CID = C.ID 
Árvore Sintática Abstrata 
Parsing/Validação 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Processamento de Consultas SQL 
54 
Query 
SELECT FROM WHERE GROUP BY HAVING 
C.ID C.Nome Count( * ) Aluno Curso C.ID C.Nome Condição 
Count ( * ) >= 100 
Condição 
A.CID = C.ID 
Árvore Sintática Abstrata 
𝐴 ← 𝐴𝑙𝑢𝑛𝑜 𝐶 ← 𝐶𝑢𝑟𝑠𝑜 
⋈𝐴.𝐶𝐼𝐷=𝐶.𝐼𝐷 
𝛾𝐶.𝐼𝐷,𝐶.𝑁𝑜𝑚𝑒, 𝑐𝑡←𝐶𝑂𝑈𝑁𝑇(∗) 
𝜎𝑐𝑡≥100 
𝜋𝐶.𝐼𝐷,𝐶.𝑁𝑜𝑚𝑒 
Árvore de Operadores Algebraicos 
 A árvore sintática abstrata é convertida em uma 
árvore de operadores da álgebra relacional 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Processamento de Consultas SQL 
55 
Scan Aluno Scan Curso 
Hash Join 
[A.CID=C.ID] 
SORT 
[A.CID,C.NOME] 
Stream Agregate 
TMP ←COUNT(*) 
FILTER , PROJ 
[TMP≥ 100, C.ID, C.Nome] 
Árvore de Operadores Físicos 
𝐴 ← 𝐴𝑙𝑢𝑛𝑜 𝐶 ← 𝐶𝑢𝑟𝑠𝑜 
⋈𝐴.𝐶𝐼𝐷=𝐶.𝐼𝐷 
𝛾𝐶.𝐼𝐷,𝐶.𝑁𝑜𝑚𝑒, 𝑐𝑡←𝐶𝑂𝑈𝑁𝑇(∗) 
𝜎𝑐𝑡≥100 
𝜋𝐶.𝐼𝐷,𝐶.𝑁𝑜𝑚𝑒 
Árvore de Operadores Algebraicos 
 Finalmente a árvore de operadores algebraicos é convertida em 
uma árvore de operadores físicos (implementação da árvore 
algebraica) que irá então executar a consulta 
 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Por que Não Usar Diretamente a 
Álgebra Relacional? 
 Algebra relacional provê um método procedural para 
consultar o banco de dados 
 Define quais operações a serem usadas e qual a sequência 
de execução destas operações 
 Em outras palavras, a álgebra relacional 
 SQL é uma linguagem declarativa para acesso a 
dados 
 
56 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Componentes da Álgebra 
Relacional 
 Categorias de operações 
• Operações baseada na teoria dos conjuntos: 
União, Diferença, Interseção, Produto Cartesiano 
• Operações específicas para o modelo relacional: 
Select, Project, Join, etc 
• Extensões: operações de agregação e 
agrupamento 
57 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
A Operação SELECT (σ) 
 Seleciona um subconjunto das tuplas de uma 
relação que satisfaçam a condição de seleção 
 Interpretações: 
• Filtro 
• Particionamento horizontal 
 Notação: σ<condição de seleção> (R) 
 Exemplo: σ<Salary > 30000> (EMPLOYEE) 
58 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
A Operação SELECT (σ) 
 Condição de seleção é um expressão Booleana 
formada por um conjunto de cláusulas com o 
seguinte formato: 
<nome do atributo> <op de comparação> <constante>, ou 
<nome do atributo> <op de comparação> <nome de atributo> 
 Op de Comparação: ,=, ≠, <, ≤, >, ≥- 
 Conectivos: and, or, not 
 Exemplo: 
σ<(Dno = 4 AND Salary > 25000) OR (Dno = 5 AND Salary > 30000)> (EMPLOYEE) 
 
 
59 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
A Operação SELECT (𝜎) 
 Operador unário 
 Operação aplicada em cada tupla individualmente 
• Condição de seleção não pode envolver mais de uma tupla 
 Mantém o grau da relação original 
 Seletividade: # tuplas_relação_resultante / 
 # tuplas_relação_original 
 Operação comutativa: 
• σ<cond1> (σ<cond2> (R)) = σ<cond2> (σ<cond1> (R)) 
• σ<cond1> (σ<cond2> (…(σ<condN> (R))…)) = 
 σ<cond1> AND <cond2> AND … AND condN> (R) 
 
60 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
A Operação PROJECT (𝜋) 
 Interpretação: 
• Seleção de colunas em uma tabela 
• Particionamento vertical 
 Notação: 𝜋<lista de atributos>(R) 
 Exemplo: 𝜋<Fname, Lname, Salary>(EMPLOYEE) 
 O grau da relação resultante é igual ao número 
de atributos na lista 
 
 
 
61 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
A Operação PROJECT (𝜋) 
Se a lista de atributos não contém chaves, 
eliminação de duplicatas é necessária (ou 
então o resultado seria uma bag) 
 PROJECT não é comutativo 
• 𝜋<lista1>(𝜋<lista2>(R)) = 𝜋<lista1>(R), se lista2 ⊆ lista1, 
ou então a operação é inválida 
62 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Sequência de Operações 
 Uma sequência de operações pode ser 
representada de duas maneiras: 
1. Uma única expressão de álgebra relacional 
2. Usando resultados intermediários (nomeados) 
63 
1. 𝜋<Fname,Lname,Salary>(σDno=5(EMPLOYEE)) 
2. TEMP ← σDno=5(EMPLOYEE) 
 RESULT ← π<Fname,Lname,Salary>(TEMP) 
 
 
 
Melhor 
legibilidade 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Renomeando Relações e Atributos 
 Para facilitar legibilidade podemos renomear 
relações e atributos 
 𝑅𝑒𝑠𝑢𝑙𝑡𝑎𝑑𝑜 ← 𝑇𝑀𝑃 
• Muda o nome da relação 𝑇𝑀𝑃 para 𝑅𝑒𝑠𝑢𝑙𝑡𝑎𝑑𝑜 
 𝑅 𝑎, 𝑏, 𝑐 ← 𝑅 𝑟, 𝑠, 𝑡 
• Muda o nome dos atributos 𝑟, 𝑠 𝑒 𝑡 de 𝑅 para 
𝑎, 𝑏 𝑒 𝑐, respectivamente 
 𝑅 𝑎, 𝑏, 𝑐 ← 𝑆 𝑟, 𝑠, 𝑡 
• Muda o nome e os atributos de 𝑆 
 
 
 
 
 
 
64 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
UNIÃO ∪ , INTERSEÇÃO 𝜋 , 
DIFERENÇA − 
 Operações binárias 
 Esquemas de relações devem ser compatíveis na união 
• Dois esquemas são compatíveis na união se eles possuem 
o mesmo grau e cada par de atributos possui o mesmo 
domínio 
 UNIÃO e INTERSEÇÃO são comutativas e associativas 
 Diferença não é comutativa 
 INTERSEÇÃO pode ser representada em termos de 
UNIÃO e DIFERENÇA 
• R ∩ S = R ∪ S – (R – S) – (S – R) 
65 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Produto Cartesiano × 
 Produz um novo conjunto através da 
combinação de todas as tuplas em uma 
relação com todas tuplas de outra relação 
 O grau da relação resultante é 𝑛 + 𝑚, onde n é 
e m são os graus das relações participantes 
 A cardinalidade da relação resultante é 
|𝑟| ∗ |𝑠|, onde |𝑟| e |𝑠| são as cardinalidades 
das relações participantes 
66 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Produto Cartesiano (2) 
 Como padrão, atributos com o mesmo nome 
em ambas relações são renomeados para 
nome_da_relação.nome_do_atributo 
 Exemplo: 
• Considere duas relações 𝑅 𝑎, 𝑏, 𝑐 e 𝑆 𝑠, 𝑏, 𝑐 e 
relação 𝑇 que é o resultado do produto 
cartesiando entre 𝑅 e 𝑆 
• Portanto: 𝑇 𝑎, 𝑅. 𝑏, 𝑆. 𝑏, 𝑠, 𝑅. 𝑐, 𝑆. 𝑐 ← 𝑅 × 𝑆 
 
 67 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
A Operação JOIN 
 Combina tuplas relacionadas de duas 
relações em um única tupla 
 Notação: R⋈<condição>S 
 Exemplo: 
• DEPARTMENT⋈<Mgr_ssn=Ssn>EMPLOYEE 
 Interpretação: Produto Cartesiano 
seguido de uma seleção 
• σ<Mgr_ssn=Ssn>(DEPARTMENT×EMPLOYEE) 
 Seletividade: # 𝑡𝑢𝑝𝑙𝑎𝑠_𝑟𝑒𝑙𝑎çã𝑜_𝑟𝑒𝑠𝑢𝑙𝑡𝑎𝑛𝑡𝑒/ 
 # |𝑅| ∗ |𝑆| 
 68 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Variantes Básicas 
da Operação JOIN 
 NATURAL JOIN: Junção onde a condição é determinada 
pela operação de igualdade e pelos atributos com o 
mesmo nome entre as duas relações 
 Além disso, elimina automaticamente da relação 
resultante um atributo de cada dupla de atributos de 
mesmo nome 
 Representada apenas por 𝑅 ⋈ 𝑆 (dispensa 
especificação da junção) 
 Exemplo 
• Considere duas relações 𝑅 𝑎, 𝑏 e 𝑆 𝑏, 𝑐 . Portanto: 
• 𝑅 ⋈ 𝑆 ≡ 𝑅 ⋈𝑅.𝑏=𝑆.𝑏 𝑆 e 
• 𝑇 𝑎, 𝑏, 𝑐 ← 𝑅 ⋈ 𝑆 
 
 69 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Variantes Básicas 
da Operação JOIN (2) 
 EQUI-JOIN: Junções contendo apenas condições 
envolvendo apenas o operador de igualdade 
• Exemplo: Considere duas relações 𝑅 𝑎, 𝑏 e 𝑆 𝑐, 𝑑 
• Temos que 𝑅 ⋈𝑅.𝑏=𝑆.𝑐 𝐴𝑁𝐷 𝑅.𝑎=𝑆.𝑑 𝑆 é um EQUI-JOIN 
 Theta-JOIN: Demais tipos de junções envolvendo 
condições arbitrárias 
• Exemplo: 𝑅 ⋈𝑅.𝑏>𝑆.𝑐 𝑆 
 
 
70 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Conjunto Completo de Operações 
da Algebra Relacional 
 Todas operações da algebra relacional podem 
ser expressas como uma sequência das 
operações {σ, π, ∪, -, ×} 
71 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
A Operação de Divisão 
 A operação de Divisão é aplicada em duas 
relações R(Z) ÷ S(X), onde X ⊆ Z. Seja Y = Z – X (e 
portanto Z = X ∪ Y), isto é, Y é o conjunto de 
atributos em R que não são atributos de S. O 
resultado da divisão é uma relação T(Y) que inclui 
uma tupla t se tuplas tR aparecem em R com tR[Y] 
= t, e com tR[X] = tS para toda tupla tS em S 
 Para uma tupla t aparecer no resultado T da 
divisão, os valores em t devem aparecer em R em 
combinação com todas as tuplas em S 
72 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
A Operação de Divisão 
 As tuplas no denominador restringem relação no 
numerador através da seleção das tuplas no resultados 
que são pareadas com todos valores no denoninador 
 Útil para representar a quantificação universal 
• Recupe o nome de todos funcionários que trabalham em 
todos projetos controlados pelo departmento nr. 5. 
 A divisão pode ser expressada através da sequência: 
• T1 <- πY(R) 
• T2 <- πY((S × T1) – R) 
• T <- T1 – T2 
 
 
73 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Considerando Bags 
 Informalmente, bags (ou multiconjuntos) são 
“conjuntos” que permitem múltiplas ocorrências 
de um elemento 
• Isto é, duplicatas são permitidas 
 Banco de dados comerciais são geralmente 
baseados uma generalização do modelo 
relacional para bags 
 Permite evitar ou adiar a operação de eliminação 
de duplicatas, que é custosa 
computacionalmente 
74 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Operações sobre Bags 
 A adaptação dos operadores 𝜎, 𝜋, × e ⋈ é 
intuitiva para a semântica baseada em bags 
• A única diferença é que a eliminação de 
duplicatas, se necessária, não é aplicada 
 Por outro lado, as operações ∪, ∩, e − 
possuem semântica diferente 
 
 
75 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Operações ∪, ∩, e − sobre Bags 
 União entre bags: a multiplicidade dos elementos é somada 
• Exemplo: Se 𝑎 é um elemento que aparece 2 vezes em 𝑅 e três 
vezes em 𝑆, então 𝑎 irá aparecer 5 vezes em 𝑅 ∪ 𝑆 
 Interseção entre bags: a multiplicidade de um elemento na 
interseção entre dois conjuntos corresponde à menor 
multiplicidade entre os dois conjuntos 
• Exemplo: Se 𝑎 aparece 𝑚 vezes em 𝑅 e 𝑛 vezes em 𝑆, então a 
irá aparecer min (𝑚, 𝑛) vezes em 𝑅 ∪ 𝑆 
 Diferença entre bags: a multiplicidade de um elemento 𝑡 na 
diferença entre um conjunto 𝑅 e um conjunto 𝑆 é dada 
pelo maior valor entre 0 e a multiplicidade de 𝑡 em 𝑅 
subtraída pela multiplicidade de 𝑡 em 𝑆 
• Exemplo: Se 𝑎 aparece 𝑚 vezes em 𝑅 e 𝑛 vezes em 𝑆, então a 
irá aparecer m𝑎𝑥 (0, 𝑚 − 𝑛) vezes em 𝑅 − 𝑆 
 
 76 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Conjuntos e Bags 
 Note que um conjunto é um caso especial de 
uma bag, onde as multiplidades dos 
elementos é 0 ou 1 
 Dado dois conjuntos, as operações de ∩ e − 
ainda produzem conjuntos quando 
interpretadas usando a semântica para bags 
 Entretanto a operação de ∪ entre dois 
conjuntos irá resultar em bags quando 
interpretada usando a semântica para bags 
 
77 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Extensões para Álgebra Relacional 
 Algumas operações frequentemente necessárias 
em aplicações de banco de dados não podem ser 
expressadas em álgebra relacional 
 Exemplo 
• Eliminação de duplicatas 
• Agregação de valores 
• Agrupamento de valores 
 Por este motivo, operações adicionais foram 
criadas para aumentar o poder de expressão do 
modelo relacional 
78 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Eliminação de Duplicatas (𝛿) Este operador converte uma bag em um 
conjunto 
 Seja 𝑅 uma bag, então 𝛿 𝑅 retorna um 
conjunto contendo apenas uma cópia para 
todos elementos que uma ou mais vezes em 𝑅 
79 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agregação 
 Operadores usados para sumarizar ou agregar valores de 
uma tabela 
 Retornam uma relação (e não um valor escala) contendo 
apenas um valor 
 Operações: 
• 𝑆𝑈𝑀𝐴 𝑅 : retorna a soma dos valores da coluna R.A; o domínio 
do atributo A deve ser do tipo numérico 
• 𝐴𝑉𝐺𝐴 𝑅 : retorna a soma dos valores da coluna R.A; o domínio 
do atributo A deve ser do tipo numérico 
• 𝑀𝐼𝑁𝐴 𝑅 e 𝑀𝐴𝑋𝐴 𝑅 retorna o maior e o menor valor entre os 
valores da R.A. Caso A seja do tipo alfanumérico, o valor 
retornado será o primeiro (MIN) ou último (MAX) valor em 
ordem alfabética 
• COUNT 𝑅 : retorna o número de tuplas em R; note que R pode 
ser uma BAG 
80 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agrupamento (𝛾) 
 Agrupamento: agrupa as tuplas em uma 
relação baseado no valor de alguns atributos 
• Exemplo: agrupamento das tuplas da relação 
Funcionário baseando no número do 
departamento 
 A operação 𝛾 𝐿 𝑅 particiona R de acordo 
com os valores da lista de atributos 𝐿 
 Para cada grupo é retornada uma tupla 
contendo os atributos do agrupamento 
81 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agrupamento e Agregação 
 Operações de agrupamento são frequentemente 
combinadas com funões de agregação 
 Denotado por 𝛾 𝐿 𝐴𝐺𝐺 𝑅 , onde AGG é uma ou 
mais funções de agregação 
• “Retorne o menor e o maior salário dos funcionários 
de cada departamento, assim como o número de 
funcionários do departamento” 
• Expressão: RES(dno, min_sal, max_sal, count) ← 
𝛾𝐷𝑁𝑢𝑚𝑀𝐴𝑋𝑆𝑎𝑙𝑎𝑟𝑖𝑜𝑀𝐼𝑁𝑆𝑎𝑙𝑎𝑟𝑖𝑜𝐶𝑜𝑢𝑛𝑡 𝐹𝑢𝑛𝑐𝑖𝑜𝑛𝑎𝑟𝑖𝑜 
 
 82 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Projeções Generalizadas 
 Projeções generalizadas: permite expressões 
sobre atributos a serem aplicados na lista de 
atributos 
83 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
JOIN Variantes 
 EQUIJOIN : Quando o único operador de comparação é a 
igualdade 
 NATURAL JOIN: Remove atributo repetidos 
 THETA JOIN: Condições arbitrárias 
 INNER JOIN: Operação padrão em que apenas tuplas 
satisfazendo a condição são retornadas 
 LEFT/RIGHT OUTER JOIN: mantém todas as tuplas da 
relação da esquerda (direita); quando não existe nenhum 
tupla relacionada na relação da direita (esquerda), os 
valores dos atributos desta relação são NULL 
 FULL OUTER JOIN: Mantém todos as tuplas de todas 
relações 
• Qual a diferença entre FULL OUTER JOIN e Produto Cartesiano 
• Todos OUTER JOIN são extensões para a álgebra relacional 
original 
84