Linguagens relacionais

Notações para expressar perguntas:


algébrica – aplicação de operadores a relações
lógica (cálculo relacional) – fórmula que os tuplos da resposta
devem satisfazer
• equivalentes em poder expressivo.

Limitações:

independência física dos dados
• linguagem só com construções relativas ao modelo de dados
(operações sobre relações) que não dependam da implementação
• não se pode aceitar programas genéricos

optimização das perguntas
• restrição no poder expressivo: sem recursão (incapaz de computar
o fecho transitivo)

relações finitas
• complementação proibida
Modelo relacional - 1
Operações Básicas
RS
1 - Reunião

é o conjunto dos tuplos que estão em R, em S, ou em ambas
• R e S da mesma aridade
• nomes dos atributos a especificar
2 - Diferença R – S

tuplos de R que não estão em S
• R e S da mesma aridade
S
R
RS
A
B
C
R-S
A
B
C
D
E
F
a
b
c
A
B
C
a
b
c
b
g
a
d
a
f
a
b
c
d
a
f
d
a
f
c
b
d
c
b
d
c
b
d
b
g
a
Modelo relacional - 2
Operações Básicas
3 - Produto cartesiano RS

aridades de R e S são k1 e k2  aridade de RS é k1 + k2
• contém todos os tuplos tais que os primeiros k1 componentes
formam um tuplo de R e os restantes k2 componentes formam um
tuplo em S
S
R
A
B
C
D
E
F
a
b
c
b
g
a
d
a
f
d
a
f
c
b
d
RS
A B
a b
a b
d a
d a
c b
c b
C
c
c
f
f
d
d
D
b
d
b
d
b
d
E
g
a
g
a
g
a
F
a
f
a
f
a
f
Modelo relacional - 3
Operações Básicas
4 - Projecção i1, i2, ..., im(R)

para cada tuplo em R existe um tuplo na projecção com os
componentes (e pela ordem) indicados pelos ij
• se aridade de R for k então os ij  1, ..., k e são distintos; aridade
da projecção é m
• números de componentes podem ser substituídos por atributos, se
existirem: 1,3 (R) = A,C (R)
1,3 (R)
R
A
B
C
A
C
a
b
c
a
c
d
a
f
d
f
c
b
d
c
d
Projecção escolhe colunas da tabela
Modelo relacional - 4
Operações Básicas
5 - Selecção F (R)

contém os tuplos de R que satisfazem F
• a fórmula F pode envolver
 operandos constantes ou número de componente ( $i )
 operadores aritméticos de comparação ( , , , , ,  )
 operadores lógicos ( , ,  ) ( e, ou, não )
• Números de componentes podem ser substituídos por atributos, se
existirem: $2=b(R) = B=b(R)
R
A
B
C
a
b
c
d
a
f
c
b
d
$2=b(R)
A
B
C
a
b
c
c
b
d
Selecção escolhe linhas da tabela
Modelo relacional - 5
Operações Compostas
6 - Intersecção R  S

contém os tuplos que pertencem a R e a S simultaneamente
• R e S da mesma aridade

R  S = R - (R-S)
RS
S
R
A
B
C
D
E
F
A
B
C
a
b
c
b
g
a
d
a
f
d
a
f
d
a
f
c
b
d
Modelo relacional - 6
Quociente
7 - Quociente R / S
• aridade de R é r e de S é s, rs, S

R
A
a
a
 b
e
e
 a
B
b
b
c
d
d
b
7
1
contém os (r-s)-tuplos (a1, ..., ar-s) tais que, para todos os stuplos (ar-s+1, ..., ar) em S, o tuplo (a1, ..., ar) está em R
S
R/S
C D
A B
E F
/ c d = a b
c d
e f
e f
e d
e f
R/S
S
(R/S)  S
c d
A B  E F
A B E
e f
a b
d e
c d =
a b c
e d
e f
a b e
3
e d c
23+1=7
e d e
2
F
d
f
d
f
Modelo relacional - 7
Explicação alternativa

Forma de proceder à divisão



reordenar as colunas de forma a que as últimas correspondam
ao quociente
ordenar a tabela pelas primeiras colunas
cada subtuplo das primeiras colunas pertence ao resultado se o
conjunto de subtuplos das últimas colunas que lhe corresponde
contiver o quociente
R
S
R/S
A B C D
A B
E F
/ c d = a b
a b c d
e f
e f
e d
d e
b c e f
e d c d
e f
Modelo relacional - 8
Expressão do quociente


T = 1, ..., r-s (R)
W = (TS) - R
= universo dos tuplos possíveis no resultado
= todas as linhas T combinadas com S mas
que não estão em R, i.e., em que a condição falha


V = 1, ..., r-s (W)
R/S=T-V
= tuplos que não interessam
= tuplos que interessam
• reunindo numa só expressão algébrica
R
A
a
a
b
e
e
a
B
b
b
c
d
d
b
C
c
e
e
c
e
d
R / S= 1, ..., r-s (R) - 1, ..., r-s  1, ..., r-s (R)  S - R
W
S
T
TS
D A B E F A B E F A B E F
d a b c d a b c d b c c d
f
b c e f a b e f
V
R/S
f
e d
b c c d
A B
d
b c e f A B
a b
f
e d c d b c
e d
e
e d e f
Modelo relacional - 9
Quais as frases verdadeiras?
( R-S )  S = R
( R-S )  S  R
( R-S )  ( RS ) = R
( R-S )  ( S-R ) = ( RS ) - ( RS )
( R/S )  S = R
( R/S )  S  R
a–
b–
c–
d–
e–
f–

Respostas
• Erradas - a e e
• Correctas - b, c, d e f
Modelo relacional - 10
Junção
8 - -Junção R ⋈ S
ij
• se a aridade de R for r e a de S, s a aridade da -junção é r+s


contém os tuplos do produto cartesiano de R por S tais que o
componente i está na relação  com o componente r+j (i.e., o
correspondente ao j em S).
Expressão da -junção

R ⋈ S= $i  $(r+j) (R  S)
ij
• se  for =, a operação designa-se equijunção
• ( 7, 8, 9 ) é um tuplo pendente de R pois não aparece na -junção
R
A
1
4
7
B
2
5
8
C
3
6
9
S
D E
3 1
6 2
R⋈S =R⋈S
A
1
1
4
2<1
B
2
2
5
C
3
3
6
B<D
D
3
6
6
E
1
2
2
Modelo relacional - 11
Junção natural
9 - Junção natural R ⋈ S
• só é aplicável se os componentes dos tuplos em R e S forem
designados por atributos.
• a operação implícita na junção natural é a igualdade dos atributos
com o mesmo nome.
• cada par de atributos iguais dá origem a um único atributo, com o
mesmo nome, no resultado

expressão: R⋈S = i1, ..., im ( R.A1= S.A1.....R.Ak= S.Ak ( R  S ))
• k é o número de atributos comuns a R (aridade r) e S (aridade s) e
m= r+s-k
tuplo pendente 
R
A
a
d
b
c
B
b
b
b
a
C
c
c
f
d
S
B
b
b
a
C
c
c
d
R⋈S A
a
D
a
d
d
e
d
b
c
B
b
b
b
b
a
C
c
c
c
c
d
D
d
e
d
e
b
Modelo relacional - 12
Junção externa


tuplos pendentes, isto é desemparelhados, quer em R quer em
S, desaparecem na -junção e na junção natural
a junção externa (- ou natural) inclui os tuplos pendentes de
R ou S completados a nulos
• ( 7, 8, 9 ) é um tuplo pendente de R pois não aparece na -junção
• ( b, b, f ) idem, na junção natural
+
R⋈S
B<D
A
1
1
4
7
B
2
2
5
8
C
3
3
6
9
D
3
6
6

E
1
2
2

+ S
R⋈
A B C
a b c
a b c
d b c
d b c
c a d
b b f
D
d
e
d
e
b

Modelo relacional - 13
Semi-junção
10 - Semi-junção R⋉S


projecção nos atributos de R da junção natural de R e S
R⋉S = R( R⋈S )
• R em R representa os atributos de R (o seu esquema); em R⋈S
R representa a relação (a instância)

outra expressão: R⋉S = R⋈RS(S)

dá os tuplos de R que têm par em S
R
A
a
d
b
c
B
b
b
b
a
C
c
c
f
d
S
B
b
b
a
C
c
c
d
D
d
e
b
R⋉S
A B
a b
d b
c a
C
c
c
d
Modelo relacional - 14
Relações com atributos


na junção natural e na semi-junção os atributos são
importantes; para os tornar explícitos escreve-se R(A1, ..., An)
é possível renomear colunas e fazer junções naturais como:
S = S(B,C,D)
B
b
b
a


C
c
c
d
D
d
e
b
S( E,F,G ) ⋈ S( G,H,I )
E F G H I
a d b c d
a d b c e
uma junção natural entre duas relações sem atributos comuns
redunda num produto cartesiano porque, após este, não há
nenhuma selecção a fazer (equivalente a fazer uma selecção
com a condição True)
R( A,B,C ) ⋈ S( G,H,I ) = R  S
Modelo relacional - 15
Leis algébricas

Reunião



Produto cartesiano



R(ST)=(RS)T
RS=SR
associativa:
comutativa:
associativo:
não comutativo:
R(ST)=(RS)T
RSSR
Junção natural


associativa e comutativa (independência da ordem das colunas
devida aos atributos): R ⋈ S = S ⋈ R
Por isso ⋈ generaliza facilmente:
R = R1 ⋈ ... ⋈ Rn
• R contém os tuplos  tais que, para 1 i  n,  restringido aos
atributos de Ri é um tuplo de Ri

 - junção

não é comutativa mas é associativa (no caso de os índices
serem válidos)
R⋈(S⋈T)=(R⋈S)⋈T
i 1 j
k 2 l
i 1 j
(r+k) 2 l
Modelo relacional - 16
Linguagem de Interrogação

Álgebra Relacional pode ser usada como
linguagem de interrogação à BD

P1 - Relativamente à BD “Cursos” (ver p.17),
quais os nomes dos professores do 12º grupo?
Πnome  grupo = ‘12’ ( Professor ) 

P2 - Quais os nomes e datas de nascimento dos
alunos do curso ‘CG1’ nascidos antes de 1983?
Πnome, data_nasc  codcurso = ‘CG1’  data_nasc < 1983-01-01 ( Aluno ) 
Modelo relacional - 17
Perguntas com junção

P3 - Nomes dos alunos inscritos à disciplina 327?

nenhuma relação contém nomes de alunos e códigos de disciplina

mas a junção Aluno ⋈ Inscrito = R contém:

R (bia, nome, morada, telefone, data_nasc, codcurso, ano, letra,
coddis, resultado)
( i ) - Πnome  coddis = 327 ( Aluno ⋈ Inscrito ) 
( ii ) - Πnome  Aluno ⋈ coddis = 327 ( Inscrito ) 

esta maneira de ligar informações no modelo de dados dá muita
liberdade para exprimir perguntas arbitrárias mas exige uma fase
de optimização para executar ( ii ) mesmo que a pergunta seja ( i )
Núcleo da álgebra relacional : Π, , ⋈
Modelo relacional - 18
Extensões à Álgebra

renomeação de atributos


R ( A, B, C )
R’( X,Y, Z ) = ΠX = A, Y = B, Z = C  R( A, B, C ) 
• onde não houver ambiguidades, a simples menção dos atributos,
em conjunto com o nome da relação, faz a renomeação
OU
– R’ ( X, Y, Z ) = R ( A, B, C )
OU
– R’ = ΠX = A, Y = B, Z = C ( R )
• expressões aritméticas ( +, -, *, / )


este mecanismo serve para dar nomes a expressões
S = ΠW = A * B – C, U = C/B,A ( R )
OU

S ( W, U, A )= ΠA * B – C, C/B, A ( R )
Modelo relacional - 19
Expressões aritméticas

P4 - Obtenha uma relação de inscrições com as
classificações inflaccionadas de 20%.



Πcoddis, bia, resultado,
Πcoddis, bia, resultado,
novo = resultado*1.2 (
Inscrito )
novo = resultado + (20-resultado)/10 ( Inscrito )
nos parâmetros da projecção:
• no membro direito só podem ser usados nomes de atributos do
argumento de Π; no esquerdo só pode estar um atributo (novo...)
Modelo relacional - 20
Agregações

Operadores de agregação


S = ΠV = CNT (B) ( R )


CNT (contagem), SUM (adição), AVG (média), MAX
(máximo), MIN (mínimo)
S( V ) tem um único valor, o número de tuplos de R com valor
não nulo no atributo B ( CNT (*) conta todas as linhas )  toda
a relação agregada
T = ΠA, M = MAX (B) ( R )



T ( A, M ) tem tantos pares quantos os valores diferentes de A,
sendo indicado para cada A o respectivo valor máximo de B
(não nulo ... );
é feita uma partição segundo os atributos de projecção sem
operadores de agregação e cada classe é agregada num só tuplo;
é possível misturar agregações e aritmética
Modelo relacional - 21
Perguntas com agregação

P5 - Qual o número de inscrições, nota média das
inscrições, soma de todas as notas e número de
resultados não nulos ?


R( NI, M, T, NR ) = ΠCNT(*), AVG( resultado), SUM( resultado ), CNT( resultado) (
Inscrito )
pode ser M  T/NI se houver inscrições ainda sem resultado
(valor nulo); tem que ser M = T/ NR
Inscrito
coddis
PA
PA
ITI
ITI
H
H
bia resultado
97
14
38
12
97
17
25
14
97
10
25
R
NI M T NR
6 13.4 67 5
Modelo relacional - 22
Agregação com partição

P6 - Quais as notas mínima, média e máxima de cada
disciplina (independentemente do aluno)?

R = Πcoddis, MI = MIN( resultado ), ME = AVG(resultado ), MA = MAX(resultado) (Inscrito)
Inscrito
coddis
PA
PA
ITI
ITI
H
H
bia resultado
97
14
38
12
97
17
25
14
97
10
25
R
coddis
PA
ITI
H
MI ME MA
12 13 14
14 15.5 17
10 10 10
Modelo relacional - 23
Quantificação existencial

P7 - Obtenha os códigos dos alunos com inscrição a
pelo menos uma das disciplinas do curso LEEC.

ΠBIA (INSCRITO ⋈ CODCURSO= ‘LEEC’ ( PLANO ))
Modelo relacional - 24
Quantificação universal

P8 - Obtenha o código dos alunos com inscrição a
todas as disciplinas do curso LEEC.

A = ΠBIA ( ALUNO )
• conjunto dos alunos

D = ΠCODDIS  CODCURSO= ‘LEEC’ (PLANO)
• conjunto das disciplinas do curso LEEC

AD
• conjunto de todos os pares (aluno, disciplina da LEEC)

NI = AD – ΠBIA, CODDIS ( INSCRITO )
• pares (aluno, disciplina da LEEC) tais que o aluno não tem
inscrição à disciplina

R = A – ΠBIA ( NI )
• resultado (notar a dupla subtracção)

R = ΠBIA, CODDIS( INSCRITO ) / D
Modelo relacional - 25