Álgebra Relacional
Álvaro Vinícius de Souza Coêlho
[email protected]
Álgebra Relacional
• Porque dizer Álgebra?
a  R, b  R
 operação
a b  c  c R
Para o caso da Álgebra
Relacional
• Se  e  são relações (tabelas)
• Uma operação sobre  e  precisa resultar
em algum  que igualmente será uma
relação
Para que Álgebra Relacional?
• Um formalismo
• Definição de operações sobre os conjuntos de
dados
• Útil para implementar
– Execução de consultas
– Otimização de consultas
• Afinal: como garantir que as operações (em SQL
por exemplo) são efetivamente executáveis?
• SQL “implementa” a Álgebra Relacional
Álgebra de “Sacos” e de
Conjuntos
• Conjuntos – coleção de exemplares
– Sem repetição
• Sacos – coleção de objetos
– Com repetição
• Ex:
– {A, B, C} é um conjunto
– {A, B, B, C, C} é um “saco”
Na prática há diferença?
• Há operações sobre conjuntos que são
análogas
– União
• Conjuntos: Omitem as repetições
• Sacos: Permite repetições
– Intersecção
– Diferença
Exemplos
• Conjuntos
– {A, B, C, D}  {A, C, D, E} = {A, B, C, D, E}
– {A, B, C, D}  {A, C, D, E} = {A, C, D}
– {A, B, C, D} – {A, C, D, E} = {B}
• Operar {1, 3, 5, 7, 9, 11, 13} com {2, 3, 5,
7, 11, 13}
Exemplos
• Sacos
– {A, B, B, B, C}  {A, A, B, D} = {A, A, A, B,
B, B, C, D} (lista cada elemento m+n vezes)
– {A, B, B, B, C}  {A, A, B, D} = {A, B} (lista
cada elemento m vezes, m o menor número)
– {A, B, B, B, C} – {A, A, B, D} = {B, B, C}
(lista cada elemento m-n vezes, no mínimo 0)
• Operar {1, 1, 2, 2, 2, 3, 4} com {1, 2, 3, 5}
Para efeitos práticos
• Redefinição de operações
– União e União Total (Union e Union All)
• União elimina as duplicações
– Intersecção e Intersecção Total (Intersection e
Intersection All)
• Intersecção elimina as duplicações
– Diferença e Diferença Total (Minus e Minus
All)
• Diferença elimina duplicações
Definições
• Álgebra relacional: operadores
– Sobre relações (não sobre tuplas individuais)
possivelmente unitárias
– Resultando relações
• Permite aninhamento de operações
Operadores definidos
•
•
•
•
•
•
•
•
Seleção – Restringe tuplas (linhas)
Projeção – Restringe atributos (colunas)
Junção – Combina tuplas segundo uma condição
Divisão – Restringe tuplas e atributos
União – União das relações (atributos iguais)
Intersecção – Intersecção das relações (idem)
Diferença – Diferença das relações (idem)
Produto Cartesiano – Gera combinações
Observação importante
• As linguagens disponíveis para acesso a
Bancos de Dados relacionais, incluindo
SQL, não utilizam os mesmos operadores
ou nomes definidos pela álgebra relacional.
Entretanto todos os operadores da álgebra
relacional podem ser escritos usando estas
linguagens
União
Fornecedor
Matricula
001
010
100
Cliente
Nome
José
Carla
Jaqueline
Matricula
000
001
002
Fornecedor  Cliente
Matricula
001
010
100
000
002
Nome
José
Carla
Jaqueline
Maria
Jaqueline
Nome
Maria
José
Jaqueline
Considerações
• União é a operação entre duas tabelas cujo
resultado contém todas as linhas presentes
em uma das tabelas originais ou em ambas,
onde
– As tabelas devem ter uma estrutura similar,
com o mesmo número de colunas e domínios
compatíveis dos atributos correspondentes.
– Linhas duplicadas são eliminadas
Intersecção
Fornecedor
Matricula
001
010
100
Cliente
Nome
José
Carla
Jaqueline
Matricula
000
001
002
Fornecedor  Cliente
Matricula
101
Nome
José
Nome
Maria
José
Jaqueline
Considerações
• Interseção é a operação entre duas tabelas
de estrutura similar cujo resultado contém
todas as linhas presentes em ambas.
– Linhas duplicadas são eliminadas
Diferença
Fornecedor
Matricula
001
010
100
Cliente
Nome
José
Carla
Jaqueline
Matricula
000
001
002
Fornecedor – Cliente
Matricula
010
100
Nome
Carla
Jaqueline
Nome
Maria
José
Jaqueline
Considerações
• Diferença é a operação entre duas tabelas de
estrutura similar cujo resultado contém
todas as linhas que estão na primeira tabela
e não aparecem na segunda.
– A - B é diferente de B - A (mostre)
Representação Gráfica
União
Intersecção
Diferença
Seleção condição(relação)
• O operador de seleção opera sobre uma
relação
• Gera uma relação contendo todos os
atributos das tuplas selecionadas
Exemplo
Alunos
Matricula
Nome
Sexo
Curso
01001
01002
02001
Antônio
Jaqueline
Núbia
M
F
F
Comp
Comp
Quim
Matricula
Nome
Sexo
Curso
01002
Jaqueline
F
Comp
02001
Núbia
F
Quim
Sexo=’F’(Alunos)
Sexo=’F’  Curso=’Quim’(Alunos)
Matricula
Nome
Sexo
Curso
02001
Núbia
F
Quim
Projeção A1,A2…An(relação)
• A operação de projeção opera sobre uma
relação gerando outra que contém todas as
tuplas da original, com alguns de seus
atributos
Exemplo
Nome, Sexo(Alunos)
Nome
Sexo
Antonio
Jacqueline
Núbia
M
F
F
Sexo(Alunos)
Sexo
M
F
F
Produto Cartesiano
Relação1 X Relação2
• O operador produto cartesiano combina
duas relações gerando uma cujas tuplas são
as possíveis combinações das tuplas das
relações originais
A
B
C
X
Y
=
A
X
A
Y
B
X
B
Y
C
X
C
Y
Exemplo
Cursos
Cod
Comp
Filos
Quim
Nome_Curso
B. Ciência da Computação
B. Filosofia
Quimica
Área
Exatas
Humanas
Exatas
Alunos
Matricula
Nome
01001
01002
02001
03001
Antônio
Jaqueline
Núbia
Léa
Sex
oM
F
F
F
Curso
Comp
Comp
Quim
Filos
Cursos X Alunos
Cod
Comp
Filos
Quim
Comp
Filos
Quim
Comp
Filos
Quim
Comp
Filos
Quim
Exemplo (cont)
Nome_Curso
B. Ciência da Computação
B. Filosofia
Quimica
B. Ciência da Computação
B. Filosofia
Quimica
B. Ciência da Computação
B. Filosofia
Quimica
B. Ciência da Computação
B. Filosofia
Quimica
Área
Exatas
Human
as
Exatas
Exatas
Human
as
Exatas
Exatas
Human
as
Exatas
Exatas
Human
as
Exatas
Matr.
01001
01001
01001
01002
01002
01002
02001
02001
02001
03001
03001
03001
Nome
Antônio
Antônio
Antônio
Jaquelin
eJaquelin
eJaquelin
eNúbia
Núbia
Núbia
Léa
Léa
Léa
Sexo
M
M
M
F
F
F
F
F
F
F
F
F
Curso
Comp
Comp
Comp
Comp
Comp
Comp
Quim
Quim
Quim
Filos
Filos
Filos
Junção
Relação1><condição Tabela_2
• O operador de junção combina as tuplas de
duas relações segundo uma ou mais
condições.
– A condição de junção deve ser baseada em um
ou mais atributos de cada uma das relações
cujos valores compartilhem um domínio
comum.
– As linhas das relações são combinadas sempre
que a condição de junção for verdadeira.
– Geralmente a condição é uma igualdade entre
atributos
Exemplo
Cursos
Cod
Comp
Filos
Quim
Nome_Curso
B. Ciência da Computação
B. Filosofia
Quimica
Área
Exatas
Humanas
Exatas
Alunos
Matricula
Nome
01001
01002
02001
03001
Antônio
Jaqueline
Núbia
Léa
Sex
oM
F
F
F
Curso
Comp
Comp
Quim
Filos
Exemplo
Cursos ><Cursos.cod = Alunos.Curso Alunos
Cod
Comp
Comp
Quim
Filos
Nome_Curso
B. Ciência da Computação
B. Ciência da Computação
Quimica
B. Filosofia
Área
Exatas
Exatas
Exatas
Human
Matr.
01001
01002
02001
03001
Nome
Antônio
Jaquelin
eNúbia
Léa
Sexo
M
F
F
F
Curso
Comp
Comp
Quim
Filos
Junção Igual
• Quando a condição de uma junção é a
igualdade, a junção é chamada de Equijoin
(observar que a tabela resultante terá
sempre duas colunas idênticas).
• Além da igualdade outras condições podem
utilizadas em uma junção, como maior
Exemplo
Receitas
Num
001
002
003
Valor
150
175
85
Receitas
Num
101
102
103
Valor
140
155
170
Exemplo
Receitas ><Receitas.valor < Despesas.ValorDespesas
Num
001
003
003
003
Valor
150
85
85
85
Num
101
101
102
103
Valor
140
140
155
170
Junção Natural
Relação1><Relação2
• Uma Junção Natural é um Equijoin onde um dos
atributos idênticos é eliminado.
• O operador de junção natural combina as tuplas de
duas relações que tem atributos comuns (mesmo
nome), resultando numa relação que contém
apenas as tuplas onde todos os atributos comuns
apresentam o mesmo valor.
• Um dos atributos idênticos é eliminado, evitando a
duplicidade
Exemplo
Observar os atributos
Com mesmo nome!
Cursos
Curso
Comp
Filos
Quim
Nome_Curso
B. Ciência da Computação
B. Filosofia
Quimica
Área
Exatas
Humanas
Exatas
Alunos
Matricula
Nome
01001
01002
02001
03001
Antônio
Jaqueline
Núbia
Léa
Sex
oM
F
F
F
Curso
Comp
Comp
Quim
Filos
Exemplo
Cursos ><Alunos
Curso
Comp
Comp
Quim
Filos
Nome_Curso
B. Ciência da Computação
B. Ciência da Computação
Quimica
B. Filosofia
Área
Exatas
Exatas
Exatas
Human
Um único atributo “Curso”
Matr.
01001
01002
02001
03001
Nome
Antônio
Jaquelin
e
Núbia
Léa
Sexo
M
F
F
F
Junção Interna (Inner Join)
• Originalmente o modelo relacional definiu o
operador de junção apenas com as características
apresentadas até aqui. Posteriormente este tipo
ficou conhecido como Inner Join e a operação de
junção foi estendida com a definição de Outer
Join.
• Em um Inner Join existe a possibilidade de que
algumas das tuplas de uma ou ambas as relações
de uma junção não façam parte da tabela
resultante.
Exemplo
Funcionarios
Mat
301
482
127
185
079
246
128
248
Nome
João
Miguel
Roberto
Dora
Esmeralda
Jaqueline
Leandro
Marcos
Setores
Setor
01
02
04
02
01
03
Seto
r01
02
03
04
05
06
Nome_Setor
Rec. Humanos
Contabilidade
Vendas
Diretoria
Informática
Patrimônio
Exemplo
Funcionarios >< Setores
Mat
301
482
127
185
079
246
Nome
João
Miguel
Roberto
Dora
Esmeralda
Jaqueline
Setor
01
02
04
02
01
03
Nome_Setor
Rec. Humanos
Contabilidade
Diretoria
Contabilidade
Rec. Humanos
Vendas
Funcionários sem setor não são relacionados!
Junção Externa (Outer Join)
• O Outer Join é uma extensão do operador
de junção utilizado para tratamento de
ausência de informações.
• A operação Outer Join mantém na relação
resultante TODAS as tuplas de uma ou mais
relações participantes da junção.
Junção Externa (Outer Join)
• Utilizada quando é necessário incluir tuplas
de uma relação onde os valores não têm
correspondência com a outra.
• Outer Join =
Resultado do Inner Join + Tuplas da relação sem
correspondência (na outra relação do join)
• As tuplas da relação que não tem
correspondência são completadas com nulos
Junção Externa (Outer Join)
• Foram definidos três tipos de Outer Joins
entre duas relações:
– Left Outer Join =><
– Right Outer Join ><=
– Full Outer Join =><=
Left Outer Join
Funcionarios =>< Setores
Mat
301
482
127
185
079
246
128
248
Nome
João
Miguel
Roberto
Dora
Esmeralda
Jaqueline
Leandro
Marcos
Setor
01
02
04
02
01
03
Nome_Setor
Rec. Humanos
Contabilidade
Diretoria
Contabilidade
Rec. Humanos
Vendas
Inner Join + Tuplas não relacionadas
da relação à esquerda
Right Outer Join
Funcionarios ><= Setores
Mat
301
482
127
185
079
246
Nome
João
Miguel
Roberto
Dora
Esmeralda
Jaqueline
Setor
01
02
04
02
01
03
05
06
Nome_Setor
Rec. Humanos
Contabilidade
Diretoria
Contabilidade
Rec. Humanos
Vendas
Informática
Patrimônio
Inner Join + Tuplas não relacionadas
da relação à direita
Full Outer Join
Funcionarios =><= Setores
Mat
301
482
127
185
079
246
128
248
Nome
João
Miguel
Roberto
Dora
Esmeralda
Jaqueline
Leandro
Marcos
Setor
01
02
04
02
01
03
Nome_Setor
Rec. Humanos
Contabilidade
Diretoria
Contabilidade
Rec. Humanos
Vendas
05
06
Informática
Patrimônio
Inner Join + Tuplas não relacionadas
das relação à direita e à esquerda
Divisão
Relação1Relação2
• Divisão é a operação entre duas relações
onde:
– Uma é o dividendo e outra o divisor
– As relações devem possuir um ou mais
atributos em comum
– A relação dividendo (A) deve possuir atributos
adicionais
Divisão
Relação1Relação2
• Divisão é a operação entre duas relações
onde:
– A relação resultante é formada pelos atributos
da relação dividendo (A) que não fazem parte
da relação divisor (B).
– A relação resultante contém apenas tuplas da
relação dividendo (A) que satisfazem a
comparação com todas as tuplas da relação
divisor (B)
Exemplo
MatFunc
301
301
301
482
482
127
127
127
Proj
73
02
11
02
11
73
43
02
 =
Proj
02
11
MatFunc
301
482
O atributo que sobra da primeira relação, com
os valores que ele possui nas tuplas onde ele se
casa com algum atributo da segunda relação!
Operações Aninhadas
• Para o uso efetivo da álgebra relacional
• Por ser “álgebra”
– Operadores sobre elementos de certos
conjuntos (relações)
– O resultado de qualquer operação pertende ao
mesmo conjunto (relações)
• Pode-se usar o resultado de uma operação
como entrada para outra
Exemplos
Nome, Matricula (departamento= ‘DCET’ ( ALUNO ><
CURSO))
 Nome, Matricula (ALUNO >< (departamento= ‘DCET’
(CURSO) ) )
• O nome e a matrícula dos alunos
matriculados em cursos do DCET
• Qual a diferença?
Álgebra Relacional.
FIM!
Escher
“Quando se corta a cabeça de um intelectual, ele morre”
Francis Picabia