Bancos de Dados
Mestrado em Engenharia de Computação
área de concentração Geomática
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
1
Tópicos
• O Modelo de Dados Relacional
(introduzido por Codd em 1970)
• Álgebra Relacional
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
2
Conceitos do Modelo Relacional...
• O banco de dados é representado como uma
coleção de relações (tabelas)
• Cada linha da tabela representa um conjunto de
valores de dados relacionados
• Estes valores podem ser interpretados como fatos
descrevendo uma entidade no mundo real ou um
relacionamento
• Os nomes escolhidos para a tabela e para as colunas
devem ajudar na interpretação do significado para
os valores que aparecem nas linhas
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
3
Conceitos do Modelo Relacional...
• Todos os valores em uma coluna são do
mesmo tipo de dados
• Terminologia do Modelo Relacional:
linha (row) = tuple
nome da coluna (column header) = atributo
nome da tabela = relação
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
4
Conceitos do Modelo Relacional...
Atributos
Nome da relação
tuplas
Domínio
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
Domínio
5
Conceitos do Modelo Relacional...
• Um domínio (domain) é um conjunto de valores
atômicos.
• Exemplos de domínios:
– Nomes de pessoas: combinação das letras do alfabeto
– Números (locais) de telefone: o conjunto de números de
telefones válidos em uma região
– Departamentos: o conjunto de departamentos acadêmicos de
uma universidade
– Placas de carro: conjunto das placas de carro em um estado
(combinação de letras e números admissíveis pelo DETRAN)
– Idade dos funcionários - valores entre 16 e 70
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
6
Conceitos do Modelo Relacional...
• Um domínio normalmente possui um nome, o qual
ajudar a interpretar os seus valores.
• Um tipo (data type) e um format descrevem
fisicamente um domínio.
• A descrição semântica ajuda na interpretação de seus
valores.
• Ex.: telefone - tipo: char(9) format: (99)999-9999
• Um mesmo domínio pode se aplicar a diferentes
atributos
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
7
Esquema de uma Relação
• Um Esquema de Relação R, denotado por R(A1, A2,
..., An), é formado por um nome de relação R e por
uma lista de atributos A1, A2, ..., An. Cada atributo Ai
é o nome de um papel desempenhado por algum
domínio D no esquema de relação R.
• D é chamado o domínio de Ai - dom(Ai)
• Um esquema de relação R é usado para descrever a
relação R (nome da relação)
• O grau de uma relação é dado pelo número n de
atributos em seu esquema.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
8
Instância de Relação...
• Uma relação (instância de relação) r de um esquema
de relação R(A1, A2, ..., An), também denotado por
r(R), é um conjunto de n tuplas r={t1, t2,..., tn}. Cada
n-tupla t é uma lista ordenada de n valores t=<v1, v2, ...,
vn>, onde cada valor vi, 1 i  n, é um elemento do
dom(Ai) ou é um valor nulo (null value) especial.
• Valor nulo - representa atributos cujos valores são
desconhecidos ou não existem para uma dada tupla.
• Intensão = esquema da relação
• Extensão (estado) = instância da relação
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
9
Intensão x Extensão
Intensão = esquema da relação
Extensão = instância da relação
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
10
Instância de Relação (def. alternativa 1)
• Uma relação r(R) é um subconjunto do produto
Cartesiano dos domínios que definem R.
r(R)  (dom(A1) x dom(A2) x ... x dom(An)
• Número de valores ou Cardinalidade de um Domínio
D = D
• no total de tuplas no produto cartesiano = dom(A1)
x  dom(A2) x ... X dom(An)
• O estado corrente da relação reflete somente as tuplas
válidas que representam um estado particular do minimundo.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
11
Instância de Relação (def. alternativa 2)...
• Um Esquema de Relação R = (A1, A2, ..., An), é um
conjunto de atributos e uma relação r(R) é um
conjunto finito de mapeamentos r={t1, t2,..., tn}, aonde
cada tupla ti é um mapeamento de R em D, e D é a
união dos domínios dos atributos, isto é, D = dom(A1)
 dom(A2)  ...  dom(An). Nesta definição t(Ai)
deve estar em dom(Ai) para 1 i  n, para cada
mapeamento t em r.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
12
Instância de Relação (def. alternativa 2)
• Uma tupla pode ser considerada como um
conjunto de pares (<atributo>, <valor>), aonde
cada par fornece o valor do mapeamento de um
atributo Ai em um valor vi, pertencente a dom(Ai).
• A nível lógico, a ordem dos atributos e seus
valores não é importante (teoria dos conjuntos).
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
13
Primeira Forma Normal
• Cada valor em uma tupla deve ser atômico
• Não são permitidos atributos compostos ou multivalorados
• Atributos multi-valorados devem ser representados
por diferentes relações
• Atributos compostos são representados pelos seus
atributos componentes mais simples
• valores nulos (null) - quando o valor de um atributo
é desconhecido ou não se aplica à tupla
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
14
Interpretação de uma Relação...
• O esquema de uma relação pode ser interpretado
como uma declaração ou uma assertiva.
Exemplo:
Um departamento possui um nome (Dname),
número (Dnumber), um gerente (Mgrssn) e uma
data (Mgrstartdate) na qual passou a ser
gerenciado pelo gerente.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
15
Interpretação de uma Relação
• Cada tupla na relação pode ser interpretada como
um fato de uma instância particular da assertiva.
• As relações podem representar fatos sobre
entidades ou sobre relacionamentos.
• O esquema de uma relação também pode ser
interpretado como um predicado.
• Neste caso, os valores em cada tupla são
interpretados como valores que satisfazem o
predicado.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
16
Notação do Modelo Relacional...
• Um Esquema de Relação R de grau n é denotado por
R(A1, A2, ..., An);
• Uma n-tupla t na relação r(R) é denotada por
t = <v1, v2, ..., vn>, onde vi é o valor correspondente ao
atributo Ai;
• t[Ai] refere-se ao valor vi em t, correspondente ao atributo
Ai;
• t[Au, Aw, ..., Az], onde Au, Aw, ..., Az é uma lista de atributos
de R, refere-se à sub-tupla de valores <vu, vw, ..., vz> de t
correspondente aos atributos especificados na lista;
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
17
Notação do Modelo Relacional
•
•
•
•
As letras Q, R e S denotam nomes de relações
As letras q, r e s denotam estados de relações
As letras t, u e v denotam tuplas
O nome de uma relação (em maiúsculas) indica o conjunto
atual de tuplas naquela relação - estado corrente da relação
- ou instância; Ex.: STUDENT
• STUDENT(Name, SSN, ...) refere-se ao esquema da
relação
• Os nomes dos atributos são, às vezes, qualificados com o
nome da relação qual pertencem; Ex.: STUDENT.Name ,
STUDENT.Age
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
18
Tipos de Restrições no Modelo Relacional
 Restrições de Domínio - especifica os valores que podem
ser assumidos por um atributo .
 Restrições de Chave - especifica uma chave (conjunto de
atributos) que identificam univocamente uma tupla .
 Restrições de Integridade - servem para manter a
consistência entre as tuplas das relações.
 Restrições Semânticas - impõem restrições adicionais nas
relações que representam situações no mini-mundo.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
19
Restrições do Modelo Relacional...
• Restrições de Domínio - especificam que o valor
de cada atributo A deve ser um valor atômico do
domínio dom(A).
• Especifica-se um domínio através de tipos
primitivos de dados, tais como integer, float,
char, date, time, money, etc.
• Adicionalmente, através de um subconjunto de
um tipo de dado ou como um tipo de dado
enumerável, em que todos os valores possíveis são
listados.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
20
Restrições do Modelo Relacional...
• Restrições de chave - uma relação é definida como um
conjunto de tuplas. Por definição, todos os elementos de um
conjunto são distintos. Portanto todos as tuplas em uma
relação devem ser distintas.
• Isto significa que não se pode ter duas tuplas com a mesma
combinação de valores para todos os seus atributos.
• Usualmente há subconjuntos de atributos de um esquema de
relação R com a propriedade que não existem tuplas, em
qualquer instância da relação r de R que possuam a mesma
combinação de valores para seus atributos.
t1[SK]  t2[SK]
SK é uma super-chave (superkey)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
21
• Super-chave - conjunto de um ou mais atributos que, tomados
coletivamente, nos permitem identificar de maneira unívoca uma
entidade em um conjunto de entidades (tipo-entidade).
• Uma chave K (minimal superkey) de um esquema de relação R é
uma superchave de R com a propriedade adicional de que, a
remoção de qualquer atributo A de K resulta em um conjunto de
atributos K´ que não é uma superchave de R.
• Chave candidata - é uma das chaves de um esquema de relação R.
• Chave primária - é uma chave candidata escolhida pelo projetista
do BD para a identificação de entidades em um conjunto de
entidades (por convenção são sublinhadas no esquema da relação).
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
22
Esquema e Instância de um BD Relacional
• Um Esquema de um Banco de Dados Relacional S é um
conjunto de esquemas de relações S={R1, R2, ..., Rm} e um
conjunto de restrições de integridade IC.
• Uma Instância de um Banco de Dados Relacional DB é
um conjunto de relações de instância DB={r1, r2, ..., rm}, tal
que cada ri é uma instância de Ri e tal que as relações ri
satisfazem as relações de integridade especificadas em IC.
• Quando nos referimos a um Banco de Dados Relacional,
implicitamente incluímos o seu esquema e a instância
corrente.
• As restrições de integridade são especificadas em um
esquema de um BD e valem para todas as suas instâncias.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
23
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
24
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
25
Restrições de Integridade...
• Integridade de Entidade - estabelece que
nenhuma chave primária pode ter valor nulo.
• Objetivo - garantir a identificação de todas as
tuplas, uma vez que a chave primária é usada para
identificar as tuplas na relação.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
26
Restrições de Integridade...
• Integridade Referencial - estabelece que uma tupla
em uma relação Ri, que se refere a uma outra relação
Rj, deve obrigatoriamente referenciar uma tupla
existente em Rj.
• Objetivo - serve para manter a consistência entre as
tuplas de duas relações.
• As restrições de integridade referencial surgem
tipicamente do relacionamento entre entidades.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
27
Chave Estrangeira
• Chave estrangeira - um conjunto de atributos FK em
um esquema de relação R1 é uma chave estrangeira de
R1, se satisfaz às seguintes condições:
Os atributos em FK têm os mesmos domínios que os
atributos de uma chave primária PK de um outro esquema
de relação R2. Diz-se que os atributos de FK referenciam a
relação R2.
Um valor de FK em uma tupla t1 de R1 ou ocorre como um
valor de PK para alguma tupla t2 de R2, ou é nulo. No
primeiro caso temos t1[FK]= t2[PK] e dizemos que a tupla t1
em R1 referencia a tupla t2 em R2.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
28
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
29
Atenção no Projeto de um BD!
• Todas as restrições de integridade devem ser
especificadas no esquema do banco de dados
relacional, para que estas restrições sejam
válidas em todas as instâncias da base de
dados.
• A DDL deve prover meios para se especificar
os diversos tipos de restrições, para que os
SGBDs as possam impor automaticamente.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
30
Operações no Modelo Relacional
• Retrieval (podem ser especificadas através da
Álgebra Relacional)
• Updates - inserção, exclusão e alteração
• As restrições de integridade especificadas no
esquema do banco de dados relacional não devem
ser violadas.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
31
A operação de inserção...
• Pode violar os quatro tipos de restrições do modelo
relacional:
 Restrições de Domínio: se o valor dado para o atributo não
pertence ao domínio correspondente.
 Restrições de Chave: se um valor de chave em uma nova
tupla t já existe em outra tupla na relação r(R).
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
32
A operação de inserção...
 Restrições de Integridade:
 Integridade de Entidade - se o valor de uma chave primária para a
nova tupla t é NULL.
 Integridade Referencial - se o valor de qualquer chave estrangeira
em t referencia uma tupla que não existe na relação que foi
referenciada.
 Restrições Semânticas - se algum valor de atributo assume
valores não permitido pelas restrições de ordem semântica.
• Alternativas quando restrições são violadas: i) rejeitar a
inserção, informando ao usuário o motivo; ii) tentar corrigir
o motivo que ocasionou a violação.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
33
A operação de exclusão
• Só pode violar restrições de integridade referencial nos
casos em que a tupla excluída é referenciada por chaves
estrangeiras de outras tuplas do banco de dados.
• Alternativas - o SGBD deve permitir ao usuário escolher entre:
rejeitar a exclusão da tupla;
tentar propagar (to cascade) a exclusão, procurando excluir
todas as tuplas no banco de dados que referenciam a tupla que
se pretende excluir;
modificar o valor do atributo de referência que causa a
violação:i) torná-lo NULL; ii) referenciar outra tupla válida.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
34
A operação de alteração
 Inicialmente, é necessário especificar uma condição sobre os
atributos da relação R, para selecionar-se a(s) tupla(s) a
ser(em) modificada(s).
 A modificação de um atributo que não seja uma chave
primária ou uma chave estrangeira usualmente não causa
problemas.
 A alteração de uma chave primária é equivalente a excluir
uma tupla e inserir uma outra.
 Se o valor de uma chave estrangeira é alterado , o SGBD
deve ter certeza de que o novo valor refere-se a uma tupla
que realmente exista na relação referenciada.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
35
O Projeto do Schema da Base de Dados...
Dar um nome para o esquema do banco de dados
relacional (relational database schema)
Declarar os domínios necessários para os atributos
Definir as relações individuais
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
36
O Projeto do Schema da Base de Dados...
 ...
DECLARE SCHEMA COMPANY;
 ...
DECLARE DOMAIN PERSON_SSNS TYPE FIXED_CHAR(9);
DECLARE DOMAIN PERSON_NAMES TYPE VARIABLE_CHAR(15);
DECLARE DOMAIN PERSON_INITIALS TYPE ALPHABETIC_CHAR(1);
DECLARE DOMAIN DATES TYPE DATE;
DECLARE DOMAIN ADDRESSES TYPE VARIABLE_CHAR(35);
DECLARE DOMAIN PERSON_SEX TYPE ENUMERATED {M,F};
DECLARE DOMAIN PERSON_SALARIES TYPE MONEY;
DECLARE DOMAIN DEPT_NUMBERS TYPE INTEGER_RANGE[1,10];
DECLARE DOMAIN DEPT_NAMES TYPE VARIABLE_CHAR(20);
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
37
O Projeto do Schema da Base de Dados...
 ...
DECLARE RELATION EMPLOYEE
FOR SCHEMA COMPANY
ATTRIBUTES FNAME
DOMAIN PERSON_NAMES,
MINIT
DOMAIN PERSON_INITIALS,
LNAME
DOMAIN PERSON_NAMES,
SSN
DOMAIN PERSON_SSNS,
BDATE
DOMAIN DATES,
ADDRESS
DOMAIN ADDRESSES,
SEX
DOMAIN PERSON_SEX,
SALARY
DOMAIN PERSON_SALARIES,
SUPERSSN DOMAIN PERSON_SSNS,
DNO
DOMAIN DEPT_NUMBERS
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
38
O Projeto do Schema da Base de Dados
CONSTRAINTS PRIMARY_KEY (SSN),
FOREIGN_KEY (SUPERSSN) REFERENCES EMPLOYEE;
FOREIGN_KEY (DNO) REFERENCES DEPARTMENT;
DECLARE RELATION DEPARTMENT
FOR SCHEMA COMPANY
ATTRIBUTES DNAME
DOMAIN DEPT_NAMES,
DNUMBER
DOMAIN DEPT_NUMBERS,
MGRSSN
DOMAIN PERSON_SSNS,
MGRSTARTDATE DOMAIN DATES
CONSTRAINTS PRIMARY_KEY (DNUMBER),
KEY (DNAME),
FOREIGN_KEY (MGRSSN) REFERENCES EMPLOYEE;
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
39
Álgebra Relacional
• Coleção de operações que são utilizadas para manipular relações
inteiras.
• permite:
– selecionar tuplas de relações individuais
– combinar tuplas relacionadas de várias relações com o propósito de
especificar uma consulta (query)
– o resultado de cada operação é uma nova relação, que também pode ser
manipulada
• 2 categorias de operações:
– as matemáticas, da Teoria dos Conjuntos (UNIÃO, INTERSECÇÃO,
DIFERENÇA e PRODUTO CARTESIANO
– as especificamente desenvolvidas para bancos de dados relacionais
(SELECT, PROJECT, JOIN, etc.)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
40
A Operação SELECT...
• Função: utilizada para selecionar um subconjunto de
tuplas de uma relação, que satisfazem uma condição
de seleção.
• Notação: <condição de seleção>(<nome da relação>)
• Exemplos:
DNO=4(EMPLOYEE)
SALARY>30000(EMPLOYEE)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
41
A Operação SELECT...
•  => é o operador de seleção (sigma)
• A condição de seleção é uma expressão Booleana
especificada sobre os atributos da relação.
• A expressão Booleana compreende uma série de cláusulas
da forma:
<nome do atributo> <operador de comparação> <valor constante>
ou
<nome do atributo> <operador de comparação> < nome do
atributo>
• O <operador de comparação>  a { = , < ,  ,  ,  ,  }
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
42
A Operação SELECT...
• Cláusulas podem ser conectadas pelos operadores Booleanos AND, OR e NOT,
para formar uma condição de seleção.
• Ex.: (DNO=4 AND SALARY>25000) OR (DNO=5AND SALARY>30000)(EMPLOYEE)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
43
A Operação SELECT...
• Se o domínio de um atributo é um conjunto de
valores não ordenados aplicam-se apenas os
operadores  a {=, }.
• Domínios de cadeias (strings) de caracteres são
ordenados baseados na collating sequence.
• Alguns domínios permitem tipos adicionais de
operadores de comparação (ex.: SUBSTRING_OF).
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
44
A Operação SELECT
• O operador SELECT é unário.
• A operação de seleção aplica-se a cada tupla individualmente.
• A relação resultante de um SELECT tem o mesmo grau da
relação original.
• Conceito de seletividade da condição.
• A operação SELECT é comutativa
<cond_1>(<cond_2>(R)) = <cond_2>(<cond_1>(R))
• Uma cascata de SELECTs pode ser combinado em um único
SELECT
<cond_1>(<cond_2>(... <cond_n>( R))...)) =
<cond_1>AND<cond_2> AND...AND<cond_n>(R)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
45
A Operação PROJECT...
• Função: utilizada para selecionar determinadas
colunas de uma relação.
• Notação: <lista de atributos> (<nome da relação>)
• Exemplos:
 SEX, SALARY(EMPLOYEE)
 FNAME, LNAME, BDATE(EMPLOYEE)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
46
A Operação PROJECT...
•  => é o operador de seleção (pi)
• A relação resultante possui somente os atributos
especificados na <lista de atributos>.
• O seu grau é o número de atributos na <lista de
atributos>.
• Tuplas duplicatas, resultante de PROJECT são
automaticamente removidas, de forma a se ter uma
relação válida (duplicate elimination).
• <lista_1>( <lista_2>(R)) = <lista_1>(R),
sempre que lista_1  lista_2
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
47
A Operação PROJECT...
• Ex.:  LNAME, FNAME, SALARY(EMPLOYEE)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
48
A Operação PROJECT
• As operações na Álgebra Relacional podem estar aninhadas em
uma única expressão ou pode-se aplicar uma operação de cada
vez, criando relações com os resultados intermediários.
• Neste caso devemos nomear as relações que guardam os
resultados intermediários. Pode-se, inclusive, renomear os seus
atributos.
Consulta_02_c06
 LNAME, FNAME, SALARY(EMPLOYEE)
R(SOBRENOME, NOME, SALÁRIO)
SALARY(EMPLOYEE)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
 LNAME, FNAME,
49
Operações da Teoria dos Conjuntos
• Aplicam-se ao Modelo Relacional porque uma
relação é definida como um conjunto de tuplas.
• operações fundamentais:
- UNIÃO, INTERSECÇÃO, DIFERENÇA
São operações binárias. As relações a que se
aplicam devem ter o mesmo tipo de tuplas, i. e.,
serem UNIÃO-compatíveis.
- PRODUTO CARTESIANO
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
50
Relações UNIÃO-compatíveis
• Duas relações R(A1, A2, ..., An) e S(B1, B2, ..., Bn)
são ditas UNIÃO-compatíveis se elas têm o mesmo
grau n e se dom(Ai)=dom(Bi), para 1  i  n.
• Significa que possuem o mesmo número de
atributos e que cada par de atributos
correspondentes possuem o mesmo domínio.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
51
Operações Fundamentais
• UNIÃO:
R S = {t | t R  t S}
• INTERSEÇÃO:
R  S = {t | t R  t S}
• DIFERENÇA:
R - S = {t | t R  t S}
• PRODUTO CARTESIANO:
R x S = {t | t[A1, ...,An] R  t [An+1, ...,An+m] S}
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
52
RESULT = RESULT_1  RESULT_2
Salary < 30000
Salary > 35000
(Salary < 30000) OR (Salary > 35000)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
53
RESULT_A = RESULT_3  RESULT_4
Salary < 40000
30000 < Salary < 40000
Salary > 30000
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
54
RESULT_B = RESULT_3 - RESULT_4
Salary < 40000
Salary > 30000
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
55
Propriedades das operações
• A UNIÃO e a INTERSECÇÃO são comutativas
RS=SR
RS=SR
• A UNIÃO e a INTERSECÇÃO são associativas
R  (S  T) = (R  S)  T
(R  S)  T = R  (S  T)
• Atenção! A DIFERENÇA não é comutativa
R - S  S - R (em geral)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
56
Produto Cartesiano (X)...
Definição:
• R(A1, A2, ..., An) X S(B1, B2, ..., Bm) é uma relação
Q (A1, A2, ..., An, B1, B2, ..., Bm) com n+m atributos
e nesta ordem.
• Q possui uma tupla para cada combinação de tuplas,
uma de R e outra de S.
• Se R possui nr tuplas e S, ns tuplas, então Q possui
nr*ns tuplas.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
57
Produto Cartesiano (X)...
• Operação binária sobre conjuntos.
• As relações sobre as quais se aplicam não precisam
ser UNIÃO-compatíveis.
• CARTESIAN PRODUCT=CROSS JOIN=CROSS
PRODUCT
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
58
Produto Cartesiano (X)
Exemplo: recuperar, para cada empregado do sexo
feminino, a lista de seus dependentes
FEMALE_EMPS
SEX=‘F’(EMPLOYEE)
EMPNAMES
 FNAME, LNAME, SSN(FEMALE_EMPS)
EMP_DEPENDENTS
EMPNAMES X DEPENDENT
ACTUAL_DEPENDENTS
SSN=ESSN(EMP_DEPENDENTS)
RESULT
 FNAME, LNAME, DEPENDENT_NAME (ACTUAL_DEPENDENTS)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
59
Exemplo...
FEMALE_EMPS
EMPNAMES
UERJ - Agosto 2000
SEX=‘F’(EMPLOYEE)
 FNAME, LNAME, SSN(FEMALE_EMPS)
© Oscar Luiz Monteiro de Farias
60
Exemplo...
EMP_DEPENDENTS
UERJ - Agosto 2000
EMPNAMES X DEPENDENT
© Oscar Luiz Monteiro de Farias
61
Exemplo...
ACTUAL_DEPENDENTS
RESULT
UERJ - Agosto 2000
SSN=ESSN(EMP_DEPENDENTS)
 FNAME, LNAME, DEPENDENT_NAME (ACTUAL_DEPENDENTS)
© Oscar Luiz Monteiro de Farias
62
A operação JOIN (
)...
• JOIN = CARTESIAN PRODUCT + SELECT
• Possibilita processar relacionamentos entre relações
• Exemplo: Desejamos recuperar o nome do gerente de cada
departamento.
Para obtermos o nome do gerente de cada depto, necessitamos
combinar a tupla de cada depto com a tupla do empregado cujo
valor de SSN é idêntico ao valor de MGRSSN na tupla do
depto.
DEPT_MGR
DEPARTMENT
MGRSSN=SSN EMPLOYEE
RESULT
DNAME, LNAME,FNAME, (DEPT_MGR)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
63
A operação JOIN (
DEPT_MGR
RESULT
UERJ - Agosto 2000
DEPARTMENT
)...
MGRSSN=SSN
EMPLOYEE
DNAME, LNAME,FNAME, (DEPT_MGR)
© Oscar Luiz Monteiro de Farias
64
A operação JOIN (
)...
• A forma geral da operação JOIN sobre duas relações R(A1,
A2, ..., An) e S(B1, B2, ..., Bm) é:
R <condição join> S.
• O resultado de JOIN é uma relação Q com m+n atributos Q
(A1, A2, ..., An, B1, B2, ..., Bm), nesta ordem.
• Q tem uma tupla para cada combinação de tuplas - uma de R
e uma de S - sempre que a condição JOIN é satisfeita ( do
produto Cartesiano).
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
65
A operação JOIN (
)...
• THETA JOIN - quando a condição JOIN é da forma:
<condição>AND<condição>AND .... AND<condição>, onde
cada condição é do tipo Ai  Bj, Ai é um atributo de R e Bj é um
atributo de S, Ai e Bj têm o mesmo domínio e  é um dos
operadores de comparação {=, <, , , , }.
• EQUIJOIN - quando o único operador de comparação utilizado é
“=“.
• No resultado de um EQUIJOIN sempre temos um ou mais pares
de atributos com o mesmo valor.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
66
A operação NATURAL JOIN (*)...
• NATURAL JOIN (*) - quando abandonamos o segundo atributo
em uma condição EQUIJOIN.
• A definição padrão de NATURAL JOIN requer que os dois
atributos JOIN(ou cada par de atributos JOIN) tenham o mesmo
nome.
• Em alguns casos é necessário renomear-se um dos atributos.
• Ex.:
DEPT (DNAME, DNUM, MGRSSN, MGRSTARTDATE)
DEPARTMENT
PROJ_DEPT
PROJECT * DEPT
O atributo DNUM é o atributo de junção (join atribute).
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
67
A operação NATURAL JOIN (*)
• Definição mais geral de NATURAL JOIN:
Q
R*(<list1>), (<list2>)S
• <list1> especifica uma lista de i atributos de R e , <list2>,
uma lista de i atributos de S.
• Estas listas são usadas para condições de comparação de
igualdade entre os pares de atributos correspondentes em R
e S.
• Efetua-se então, um AND entre as condições.
• Somente os atributos de list1 são mantidos no resultado Q.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
68
Conjunto Completo de Operações da AR
• O conjunto das operações da Álgebra Relacional
{, , , -, } é um conjunto completo, no
sentido de que qualquer outra operação da AR
pode ser expressa como uma seqüência de
operações deste conjunto.
• R  S = (R  S) - ((R - S)  (S - R))
• R
<condição> S =  <condição>(R  S)
• NATURAL JOIN = PRODUTO CARTESIANO +
SELECT + PROJECT
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
69
A operação DIVISION...
• Query: recuperar o nome dos empregados que trabalham em
todos os projetos em que John Smith trabalha.
 Recuperar a lista de números de projetos em que John Smith
trabalha em uma lista intermediária
SMITH
FNAME=John AND LNAME=Smith(EMPLOYEE)
SMITH_PNOS
PNO(WORKS_ON*ESSN=SSNSMITH)
 Criar uma relação SSN_PNOS que inclui uma tupla
<PNO, ESSN>, sempre que o empregado cujo security social
number é ESSN trabalhar em um projeto de número PNO
SSN_PNOS
PNO, ESSN(WORKS_ON)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
70
A operação DIVISION...
 Aplicar a operação de DIVISÃO às duas relações
SSNS(SSN)
SSN_PNOS  SMITH_PNOS
RESULT
FNAME, LNAME (SSNS*EMPLOYEE)
A operação de DIVISÃO aplica-se a duas relações R(Z)  S(X),
onde X  Z. Seja Y=Z-X, i.e., seja Y o conjunto de atributos de R
que não sejam atributos de S. O resultado da divisão é a relação
T(Y) que inclui a tupla t se a tupla tr, cuja tr[Y] = t aparece em R,
com tr[X]=ts para cada tupla ts em S.
Significa que para uma tupla t aparecer no resultado T da
DIVISÃO, os valores em t devem paarecer em R em combinação
com toda tupla em S.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
71
A operação DIVISION...
Y
X
R(Z)  S(X)
Z
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
72
A operação DIVISION...

UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias

73
A operação DIVISION
• Pode ser expressa como uma seqüência das
operações ,  e T1= Y(R)
T2= Y((S T1) - R)
T = T1 - T2
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
74
Operações Relacionais Adicionais...
• Funções agregadas:
SUM, AVERAGE, MAXIMUM, MINIMUM, COUNT
• Grupar um no de tuplas da relação, segundo o valor de
algum de seus atributos e, então, aplicar uma função
agregada independente a cada grupo.
<atributos de grupo><lista de funções>(<nome da relação>)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
75
Operações Relacionais Adicionais...
• Exemplo: recuperar, para cada n0 de dept0, o n0 de
empregados no dept0 e o seu salário médio.
R(DNO, NUMBER_OF_EMPLOYEES, AVERAGE_SAL)
DNOCOUNT SSN, AVERAGE SALARY(EMPLOYEE)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
76
Recursive Closure Operations
• Em geral não podem ser especificadas na AR
• Ex. recuperar todos os supervisionados de um empregado em
todos os níveis.
Nível_1 - todos os empregados diretamente supervisionados por
James Borg.
BORG_SSN
SSN(FNAME=‘James’ AND LNAME=‘Borg’ (EMPLOYEE))
SUPERVISION(SSN1, SSN2)
SSN, SUPERSSN (EMPLOYEE))
RESULT1(SSN)
SSN1(SUPERVISION SSN2=SSNBORG_SSN)
Nível_2 - RESULT2(SSN)
SSN1(SUPERVISION
SSN2=SSN RESULT1)
FINAL_RESULT = (RESULT1  RESULT2)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
77
Outer Join e Outer Union
• Extensões das operações JOIN e UNIÃO
• Usadas quando desejamos guardar todas as tuplas de R ou S ou
ambas no resultado, independentemente de haver tuplas
correlacionadas na outra relação.
• LEFT OUTER JOIN • Exemplo: desejamos uma lista com o nome de todos os
empregados e também do nome dos deptos que eles gerenciam, no
caso de gerenciarem um depto.
TEMP
(EMPLOYEE
SSN=MGRSSNDEPARTMENT)
RESULT
FNAME, MINIT, LNAME, DNAME(TEMP)
• RIGHT OUTER JOIN UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
78
LEFT OUTER JOIN Exemplo: desejamos uma lista com o nome de todos os empregados e também do nome
dos deptos que eles gerenciam, no caso de gerenciarem um depto.
TEMP
(EMPLOYEE
SSN=MGRSSNDEPARTMENT)
RESULT
FNAME, MINIT, LNAME, DNAME(TEMP)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
79
Exemplos de queries em AR...
 Recuperar os nomes e endereços de todos os empregados que
trabalham para o depto ‘Research’
RESEARCH_DEPARTMENT
DNAME=‘RESEARCH’(DEPARTMENT)
-RESEARCH_DEPARTMENT_EMPS
(RESEARCH_DEPARTMENT
DNUMBER=DNOEMPLOYEE )
-RESULT
FNAME, LNAME, ADDRESS(RESEARCH_DEPARTMENT_EMPS)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
80
Exemplos de queries em AR...
 Para cada projeto localizado em ‘Stafford’, recupere o no do
projeto, o no do depto que o controla e o sobrenome, endereço e
data de nascimento do gerente deste depto.
STAFFORD_PROJS
PLOCATION=‘STAFFORD’(PROJECT)
-CONTR_DEPT
STAFFORD_PROJS DNUM=DNUMBERDEPARTMENT
-PROJ_DEPT_MGR
CONTR_DEPT
MGRSSN=SSNEMPLOYEE
-RESULT
PNUMBER, DNUM, LNAME, ADDRESS, BDATE(PROJ_DEPT_MGR)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
81
Exemplos de queries em AR...
 Encontre o nome de todos os empregados que trabalham em
todos os projetos controlados pelo depto de no 5.
DEPT5_PROJS(PNO)
 PNUMBER(DNUM=5(PROJECT))
-EMP_PROJ(SSN, PNO)
 ESSN, PNO (WORKS_ON)
-RESULT_EMP_SSNS
(EMP_PROJ  DEPT5_PROJS
-RESULT
 LNAME, FNAME(RESULT_EMP_SSNS * EMPLOYEE)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
82
Exemplos de queries em AR...
 Faça uma lista de no de projetos para aqueles projetos em que
trabalham um empregado cujo sobrenome é ‘Smith’, seja como
empregado, seja como gerente, do dept0 que controla o projeto.
SMITHS(ESSN)
 SSN(LNAME=‘Smith’(EMPLOYEE))
-SMITH_WORKER_PROJS
 PNO (WORKS_ON * SMITHS)
-MGRS
 LNAME, DNUMBER (EMPLOYEE
SSN=MGRSSN DEPARTMENT)
-SMITH_MGRS
LNAME=‘Smith’(MGRS)
-UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
83
Exemplos de queries em AR...
 ...
SMITH_MANAGED_DEPTS(DNUM)
 DNUMBER(SMITH_MGRS)
-SMITH_MGR_PROJS(PNO)
 PNUMBER (SMITH_MANAGED_DEPTS * PROJECT)
-RESULT
(SMITH_WORKER_PROJS  SMITH_MGR_PROJS)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
84
Exemplos de queries em AR...
 Liste os nomes de todos os empregados que tenham um ou mais
dependentes.
Obs. Não pode ser resolvido com as operações padrões da AR.
Devemos usar as operações adicionais FUNCTION e COUNT.
T1(SSN, NO_OF_DEPS)
ESSNCOUNT DEPENDENT_NAME(DEPENDENT)
--
T2
 NO_OF_DEPS=2(T1)
-RESULT
UERJ - Agosto 2000
 LNAME, FNAME (T2 * EMPLOYEE)
© Oscar Luiz Monteiro de Farias
85
Exemplos de queries em AR...
 Recupere os nomes de todos os empregados que não tenham
dependentes.
ALL_EMPS
--
 SSN (EMPLOYEE)
EMPS_WITH_DEPS(SSN)
 ESSN(DEPENDENT)
-EMPS_WITHOUT_DEPS
(ALL_EMPS - EMPS_WITH_DEPS)
-RESULT
 LNAME, FNAME (EMPS_WITHOUT_DEPS * EMPLOYEE)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
86
Exemplos de queries em AR...
 Liste os nomes dos gerentes que tenham pelo menos um
dependente.
MGRS(SSN)
--
 MGRSSN (DEPARTMENT)
EMPS_WITH_DEPS(SSN)
 ESSN(DEPENDENT)
-MGRS_WITH_DEPS
(MGRS  EMPS_WITH_DEPS)
-RESULT
 LNAME, FNAME (MGRS_WITH_DEPS * EMPLOYEE)
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
87
Mapeamento ER
Relacional
• Um esquema de Banco de Dados Relacional pode
ser derivado de um Modelo Conceitual que utilize
o Modelo Entidade-Relacionamento
• Propriedade incorporada em ferramentas CASE e
usadas pelos projetistas de BD
• A conversão de um modelo em outro é automática,
fundamentada em um algoritmo
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
88
Algoritmo ER
Relacional...
Passo 1: (incluir as Relações Entidades)
• Para cada tipo entidade E regular do esquema ER, crie uma
tabela R que inclua todos os atributos simples de E.
– Inclua somente os componentes simples de um atributo
composto.
– Escolha um dos atributos chaves de E como uma chave
primária para R. Se a chave escolhida for composta, o
conjunto de atributos simples que a formam definirão a chave
primária de R.
Atenção! Não incluir (ainda) chaves-estrangeiras e atributos de
relacionamento.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
89
Algoritmo ER
Relacional...
• Após o passo 1:
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
90
Algoritmo ER
Relacional...
Passo 2: (incluir as Relações Tipo-Entidades Fracas)
• Para cada tipo-entidade fraco W, com tipo-entidade proprietária E
do esquema ER, crie uma tabela R e inclua todos os atributos
simples (ou componentes simples de atributos compostos) de W
como atributos de R.
• Inclua como chave estrangeira de R a chave primária da tabela
que corresponde ao tipo-entidade proprietário E (de W). Isto
corresponde ao relacionamento de identificação (identifying
relationship). A chave primária de R é a combinação da(s)
chave(s) primária(s) do(s) proprietário(s) de W e da chave parcial
da entidade fraca W.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
91
Algoritmo ER
Relacional...
• Após o passo 2 :
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
92
Algoritmo ER
Relacional...
Passo 3: (trata dos relacionamentos 1:1 do esquema ER)
• Para cada relacionamento binário R (1:1) do esquema ER,
identifique as tabelas S e T que correspondem aos tipos-entidades
que participam de R.
• Escolha uma das tabelas, p. ex. S, e inclua, como chave
estrangeira de S, a chave primária de T (para o papel de S é
melhor escolher o tipo-entidade com participação total em R)
• Inclua todos os atributos simples (ou componentes simples de
atributos compostos) do relacionamento R (1:1) como atributos
de S.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
93
Algoritmo ER
Relacional...
• Após o passo 3 :
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
94
Algoritmo ER
Relacional...
• Observe que um mapeamento alternativo para um
relacionamento 1:1 é possível, incluindo-se os dois tiposentidades e o relacionamento em uma única tabela. É
indicado quando ambas as participações são totais e
quando as entidades-tipos não participam de outros
relacionamentos
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
95
Algoritmo ER
Relacional...
Passo 4: (trata dos relacionamentos 1:N do esquema ER)
• Para cada relacionamento binário regular (não-fraco) R (1:N) do
esquema ER, identifique a tabela S que representa o tipoentidade que participa no lado N do relacionamento.
• Inclua, como chave estrangeira em S a chave primária da tabela
T que representa o outro tipo-entidade participante de R.
• Inclua qualquer atributo simples (ou componentes simples de
atributos compostos) do relacionamento 1:N como atributos de
S.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
96
Algoritmo ER
Relacional...
• Após o passo 4:
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
97
Algoritmo ER
Relacional...
Passo 5: (trata dos relacionamentos M:N do esquema ER)
• Para cada relacionamento binário R (M:N) crie uma nova tabela
S para representar R.
• Inclua, como chaves estrangeiras em S, as chaves primárias das
tabelas que representam os tipo-entidades participantes do
relacionamento. A combinação destas chaves estrangeiras
formará a chave primária de S.
• Inclua qualquer atributo simples do relacionamento M:N como
atributo de S.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
98
Algoritmo ER
Relacional...
• Após o passo 5:
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
99
Algoritmo ER
Relacional...
Passo 6: (trata dos atributos multi-valorados no esquema ER)
• Para cada atributo multi-valorado A crie uma nova tabela R que
inclua um atributo correspondente de A mais a chave primária K
(como chave estrangeira em R) da tabela que representa o tipoentidade ou relacionamento que possua A como atributo. A
chave primária de R é a combinação de A e K. Se o atributo A é
composto deve-se incluir todos os seus componentes simples.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
100
Algoritmo ER
Relacional...
• Após o passo 6:
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
101
Algoritmo ER
Relacional...
Passo 7: (trata dos relacionamentos de grau n no esquema
ER)
• Para cada relacionamento R de grau n, n > 2, crie uma
nova tabela S para representar R. Inclua como chaves
estrangeiras em S as chaves primárias das tabelas que
representam as entidades-tipos participantes.
• Inclua também qualquer atributo simples do
relacionamento n-ário (ou componentes simples de
atributos compostos) como atributos de S.
• A chave primária de S usualmente é uma combinação de
todas as chaves estrangeiras que referenciam as tabelas que
representam os tipos-entidades participantes.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
102
Algoritmo ER
Relacional...
Passo 7: (trata dos relacionamentos de grau n no esquema ER)
• Se a restrição de participação (min, max) de um dos tiposentidades E participantes em R possui max=1, então a chave
primária de S pode ser a única chave estrangeira que referencia a
tabela E´ correspondente a E, porque, neste caso, cada entidade
e em E participará com no máximo uma instância no
relacionamento R e assim pode identificar univocamente aquela
instância do relacionamento.
UERJ - Agosto 2000
© Oscar Luiz Monteiro de Farias
103
Algoritmo ER
Relacional...
Exemplo:
SUPPLIER
SNAME
...
PROJECT
PROJNAME
PART
PARTNO
SUPPLY
SNAME
UERJ - Agosto 2000
...
...
PROJNAME
PARTNO
© Oscar Luiz Monteiro de Farias
QUANTITY
104