Algebra Relacional - Banco de Dados

Prévia do material em texto

A´lgebra Relacional
Slides Baseados no Livro
A First Course in Database Systems (Ullman)
Pedro de Azevedo Berger
30 de marc¸o de 2015
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Linguagem de consultas alge´bricas
Um modelo representacional na˜o envolve apenas estrutura, mas
tambe´m uma forma de consultar e modificar os dados.
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Linguagem de consultas alge´bricas
Um modelo representacional na˜o envolve apenas estrutura, mas
tambe´m uma forma de consultar e modificar os dados.
A a´lgebra relacional oferece operac¸o˜es simples, mas
expressivas, para construir novas relac¸o˜es (a`s vezes na˜o
materializadas) em termos de relac¸o˜es existentes. Tais
operac¸o˜es sa˜o a base da linguagem SQL.
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
O que e´ uma a´lgebra?
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
O que e´ uma a´lgebra?
Em geral consiste de operadores e operandos atoˆmicos
Permite a criac¸a˜o de expresso˜es atrave´s da composic¸a˜o de
operadores com operandos atoˆmicos e / ou outras expresso˜es
da a´lgebra.
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
A´lgebra Relacional
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Operandos
varia´veis que correspondem a`s relac¸o˜es
constantes que correspondem ao estado das relac¸o˜es
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Operac¸o˜es
(a) Operac¸o˜es de conjuntos aplicadas a`s relac¸o˜es
unia˜o
diferenc¸a
intersec¸a˜o
(b) Operac¸o˜es para remover partes de uma relac¸a˜o
Projec¸a˜o (elimina algumas colunas)
Selec¸a˜o (remove algumas colunas)
(c) Operac¸o˜es para combinar duas relac¸o˜es
Produto cartesiano entre relac¸o˜es
Junc¸o˜es entre relac¸o˜es
(d) Renomeac¸a˜o
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Exemplos
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Unia˜o (R ∪ S)
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Diferenc¸a (R − S)
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Intersec¸a˜o (R ∩ S)
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Projec¸a˜o πA(R)
O operac¸a˜o de projec¸a˜o e´ usada para produzir, a partir de uma
relac¸a˜o R , uma nova relac¸a˜o que possui apenas algumas das
colunas de R . Ou seja, o valor da expressa˜o πA1,A2,...,AN (R) e´ a
relac¸a˜o que possui apenas os atributos A1,A2, ...,AN de R .
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Exemplo
πtitle,year ,length(Movies)
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Exemplo
πtitle,year ,length(Movies)
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Qual o resultado da operac¸a˜o
πgenre(Movies)
???
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Na a´lgebra relacional, tuplas
duplicadas sa˜o sempre eliminadas das
relac¸o˜es.
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Selec¸a˜o σC (R)
O operac¸a˜o de selec¸a˜o e´ usada para produzir, a partir de uma
relac¸a˜o R , uma nova relac¸a˜o com um subconjunto das tuplas de R ,
que satisfazem uma condic¸a˜o C sobre os atributos de R .
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Exemplo
σlength>=100(Movies)
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Exemplo
σlength>=100(Movies)
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Como selecionar os filmes produzidos pela Fox com pelo
menos 100 minutos de durac¸a˜o?
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Como selecionar os filmes produzidos pela Fox com pelo
menos 100 minutos de durac¸a˜o?
σlength>=100 ∧ studioName=′Fox ′(Movies)
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Produto Cartesiano (R × S)
O produto cartesiano entre duas relac¸o˜es R(A1,A2, ...,AN) e
S(B1,B2, ...,BM) e´ uma nova relac¸a˜o
((R × S)(A1,A2, ...,AN ,B1,B2, ...,BM)), contendo o nu´mero total
de linhas de R multiplicado pelo nu´mero total de linhas de S .
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Exemplo
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Junc¸a˜o Natural (R ⊲⊳ S)
Em geral, em vez de um produto cartesiano completo, estamos
interessados na junc¸a˜o de duas relac¸o˜es dado que exista a
correspondeˆncia entre atributos comuns.
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Junc¸a˜o Natural (R ⊲⊳ S)
Em geral, em vez de um produto cartesiano completo, estamos
interessados na junc¸a˜o de duas relac¸o˜es dado que exista a
correspondeˆncia entre atributos comuns.
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Junc¸a˜o Theta (R ⊲⊳ CS)
Possibilita a junc¸a˜o entre duas relac¸o˜es R e S usando condic¸o˜es
mais expressivas que a suportada pela junc¸a˜o natural.
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Junc¸a˜o Theta (R ⊲⊳ CS)
Possibilita a junc¸a˜o entre duas relac¸o˜es R e S usando condic¸o˜es
mais expressivas que a suportada pela junc¸a˜o natural. O resultado
e´ constru´ıdo como segue:
(1) Computa o produto cartesiano R × S
(2) Seleciona do produto apenas as tuplas que satisfazem a
condic¸a˜o C
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Exemplo
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
U ⊲⊳ A<DV
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Operac¸o˜es podem ser combinadas de duas formas
Inline
πFNAME ,LNAME ,SALARY (σDNO=5(Employee))
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Operac¸o˜es podem ser combinadas de duas formas
Inline
πFNAME ,LNAME ,SALARY (σDNO=5(Employee))
Com atribuic¸o˜es a varia´veis
DEP5 EMPS ← σDNO=5(Employee)
πFNAME ,LNAME ,SALARY (DEP5 EMPS)
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Renomeac¸a˜o de atributos
Quando combinamos relac¸o˜es, frequ¨entemente precisamos
renomear alguns atributos.
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Renomeac¸a˜o de atributos
Quando combinamos relac¸o˜es, frequ¨entemente precisamos
renomear alguns atributos. Isso pode ser feito com o uso de
atribuic¸o˜es a varia´veis.
R(FIRSTNAME , LASTNAME )← (DEP5 EMPS)
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Conjunto completo de operac¸o˜es
Selec¸a˜o (σ)
Projec¸a˜o (π)
Unia˜o (∪)
Diferenc¸a (−)
Produto cartesiano (×)
Pedro de Azevedo Berger A´lgebra RelacionalSlides Baseados no Livro A First Course in Database
Func¸o˜es agregadas e agrupamento
Na˜o e´ poss´ıvel expressar func¸o˜es agregadas em colec¸o˜es de valores
usando a A´lgebra Relacional ba´sica. Como exemplos da aplicac¸a˜o
dessas func¸o˜es, temos:
Calcular a quantidade de funciona´rios alocados em um projeto
Calcular o total de horas alocadas em projetos dos funciona´rios
Calcular a me´dia salarial dos funciona´rios agrupada por
departamento
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Func¸a˜o Agregada
grouping attributesℑ<function list>(R)
Onde,
grouping attributes e´ uma lista de atributos em R
< function list > e´ uma lista de pares
(< function >< attribute >), em que < function > e´ uma
das func¸o˜es permitidas— SUM, AVERAGE, MAXIMUM,
MINIMUM, COUNT— e < attribute > e´ um atributo em R.
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Tabela de Projetos
PRJNO DPTNO Nome Descricao
---------- ---------- --------------- ----------------
1 2 Projeto MPOG 01 ...
2 1 Projeto Aeronau ...
3 1 Projeto Positiv ...
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Tabela de alocac¸a˜o
CPF PRJNO Horas
---------- ---------- ----------
1 2 10
1 3 5
2 2 5
2 3 20
4 1 10
5 1 10
6 1 5
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
O que se quer:
Quantidade de pessoas alocadas e total de horas por projeto,
apresentando o nome do projeto.
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
O que se quer:
Quantidade de pessoas alocadas e total de horas por projeto,
apresentando o nome do projeto.
PessoasAlocadas TotalHoras Projeto
--------------- ----------- ---------------
3 25 Projeto MPOG
2 15 Projeto Aeronautica
2 25 Projeto Positivo
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
PRJ ALC ← PROJETO ⊲⊳ ALOCACAO FUNCIONARIO
TOTAIS ←PRJNO ℑCOUNTCPF,SUMhoras (PRJ ALC )
R(Projeto,PessoasAlocadas,TotalHoras)← TOTAIS
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Operac¸o˜es Outer Joins
As operac¸o˜es de junc¸a˜o entre duas relac¸o˜es R e S descritas sa˜o
restritivas
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Operac¸o˜es Outer Joins
As operac¸o˜es de junc¸a˜o entre duas relac¸o˜es R e S descritas sa˜o
restritivas, apenas as linhas que satisfazem a`s restric¸o˜es (impl´ıcitas
ou na˜o) aparecem na relac¸a˜o resultante.
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Operac¸o˜es Outer Joins
As operac¸o˜es de junc¸a˜o entre duas relac¸o˜es R e S descritas sa˜o
restritivas, apenas as linhas que satisfazem a`s restric¸o˜es (impl´ıcitas
ou na˜o) aparecem na relac¸a˜o resultante.
A operac¸a˜o left outer join (R E S) procede da mesma forma
que as operac¸o˜es de join discutidas anteriormente; mas
mante´m todas as linhas da primeira relac¸a˜o R que na˜o
satisfazem a condic¸a˜o.
A operac¸a˜o right outer join (R D S) procede da mesma forma
que as operac¸o˜es de join discutidas anteriormente; mas
mante´m todas as linhas da segunda relac¸a˜o S que na˜o
satisfazem a condic¸a˜o.
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Tabela Funcionario
* Funcionario
CPF DPTNO Nome
---------- ---------- -----------
0 1 Rodrigo ...
1 1 Guilherme .
2 1 Andre ...
3 2 Genaina ...
4 2 Maristela .
5 3 Aleteia ...
6 3 Priscila ..
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Departamento e Gerente Departamento
* Departamento
DPTNO Nome
---------- ---------------------
1 Ciencia da Computacao
2 Departamento de Engen
3 Arquitetura e Urbanis
* GerenteDepartamento
DT_INICIO DT_FIM CPF DPTNO
---------- ---------- ---------- ----------
01-01-2010 12-31-2010 0 1
01-01-2011 05-30-2010 1 1
06-01-2011 0 1
01-01-2011 3 2
01-01-2011 5 3
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Como listar os nomes dos funciona´rios e dos departamentos que
eles gerenciam, caso o funciona´rio gerencie um departamento?
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Como listar os nomes dos funciona´rios e dos departamentos que
eles gerenciam, caso o funciona´rio gerencie um departamento?
GER ← πCPF ,DPTNO(σDT FIM=null (GerenteDepartamento))
GER DPT (DPTNOME ,DPTGER)← πNOME ,CPF (GER ⊲⊳ DEPARTAMENTO))
RES ← πNOME ,DPTNOME (FUNCIONARIO ECPF=DPTGER GER DPT )
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
. . . ou em SQL
SELECT f . nome , d . nome
FROM
( Fun c i o n a r i o f LEFT OUTER JOIN
GerenteDepartamento g ON f . c p f = g . cp f )
INNER JOIN Departamento d ON g . dptno = d . dptno
WHERE d t f im IS NULL ;
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
A a´lgebra relacional pode ser considerada uma forma
procedural para estabelecer uma consulta
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
A a´lgebra relacional pode ser considerada uma forma
procedural para estabelecer uma consulta, uma vez que
precisamos escrever uma sequ¨eˆncia de operac¸o˜es que deve ser
seguida em uma ordem particular.
Tal ordem influencia a estrate´gia de avaliac¸a˜o das consultas
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Ca´lculo Relacional
No Ca´lculo Relacional, escrevemos uma expressa˜o declarativa para
especificar uma consulta, sem uma descric¸a˜o sobre como a
expressa˜o deve ser avaliada.
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Ca´lculo Relacional
No Ca´lculo Relacional, escrevemos uma expressa˜o declarativa para
especificar uma consulta, sem uma descric¸a˜o sobre como a
expressa˜o deve ser avaliada.
Existem provas que consultas especificadas na a´lgebra
relacional ba´sica podem ser expressas usando o ca´lculo
relacional; e vice-versa (o poder de expressividade dessas
linguagens e´ o mesmo)
Consiste na especificac¸a˜o de varia´veis de tupla, muitas vezes
definida em termos de uma relac¸a˜o de banco de dados
particular.
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Ca´lculo Relacional
No Ca´lculo Relacional, escrevemos uma expressa˜o declarativa para
especificar uma consulta, sem uma descric¸a˜o sobre como a
expressa˜o deve ser avaliada.
Existem provas que consultas especificadas na a´lgebra
relacional ba´sica podem ser expressas usando o ca´lculo
relacional; e vice-versa (o poder de expressividade dessas
linguagens e´ o mesmo)
Consiste na especificac¸a˜o de varia´veis de tupla, muitas vezes
definida em termos de uma relac¸a˜o de banco de dados
particular. Por exemplo:
{t | FUNCIONARIO(t) ∧ t.SALARIO > 5000}
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Estrutura das expresso˜es em Ca´lculo Relacional
Um conjunto de atributos a ser recuperado
Para cada varia´vel tupla t, especificar a relac¸a˜o de dom´ınio R
Uma condic¸a˜o para selecionar combinac¸o˜es particulares de
tuplas
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Estrutura das expresso˜es em Ca´lculo Relacional
Um conjuntode atributos a ser recuperado
Para cada varia´vel tupla t, especificar a relac¸a˜o de dom´ınio R
Uma condic¸a˜o para selecionar combinac¸o˜es particulares de
tuplas, usando operadores relacionais, quantificadores e
conectivos.
=, ! =, <,>,<= . >=
∨,∧,¬
∀, ∃
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Estrutura das expresso˜es em Ca´lculo Relacional
Um conjunto de atributos a ser recuperado
Para cada varia´vel tupla t, especificar a relac¸a˜o de dom´ınio R
Uma condic¸a˜o para selecionar combinac¸o˜es particulares de
tuplas, usando operadores relacionais, quantificadores e
conectivos.
=, ! =, <,>,<= . >=
∨,∧,¬
∀, ∃
{t1.Aj , t2.Ak , ...,TN .Am|Formula}
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
. . . onde Formula e´ composta por a´tomos do ca´lculo de
predicados
1 Podendo ser na forma R(ti ), onde R e´ uma relac¸a˜o e ti e´ uma
varia´vel tupla.
2 Um a´tomo na forma ti .A op tj .B , onde ti e tj sa˜o varia´veis tuplas;
A e B sa˜o atributos de relac¸o˜es definidas no escopo das tuplas ti e
tj , respectivamente; e op e´ um dos operadores de comparac¸a˜o.
3 Um a´tomo na forma ti .A op c ou c op tj .B onde ti e tj sa˜o
varia´veis tuplas; A e B sa˜o atributos de relac¸o˜es definidas no escopo
das tuplas ti e tj , respectivamente; op e´ um dos operadores de
comparac¸a˜o; e c e´ uma constante.
4 Fo´rmulas sa˜o compostas por um ou mais a´tomos conectados por
operadores lo´gicos ∧,∨,¬, ou seja, se F1 e F2 sa˜o fo´rmulas, enta˜o
F1 ∧ F2, F1 ∨ F2, ¬(F1) e ¬(F2) tambe´m sa˜o fo´rmulas.
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Ale´m disso, os quantificadores ∀ e ∃ tambe´m aparecem nas
fo´rmulas
1 Se F e´ uma fo´rmula e t e´ uma varia´vel tupla, enta˜o (∃t)(F )
tambe´m e´ uma fo´rmula.
2 Se F e´ uma fo´rmula e t e´ uma varia´vel tupla, enta˜o (∀t)(F )
tambe´m e´ uma fo´rmula.
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Exemplo 01
Encontre o nome e o sala´rio de todos os servidores do CIC.
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Exemplo 01
Encontre o nome e o sala´rio de todos os servidores do CIC.
Q1 : {t.NOME , t.SALARIO|FUNCIONARIO(t) ∧ (∃d)(DEPARTAMENTO(d) ∧
d .NOME =′ CIC ′ ∧ d .DPTNO = t.DPTNO)}
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Exemplo 02
Encontre o nome de cada funciona´rio que trabalha em algum
projeto controlado pelo departamento CIC.
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database
Exemplo 02
Encontre o nome de cada funciona´rio que trabalha em algum
projeto controlado pelo departamento CIC.
Q2 : {f .NOME |FUNCIONARIO(f ) ∧ (∃d)(∃p)(∃a)(DEPARTAMENTO(d) ∧
PROJETO(p) ∧ ALOCACAO(a) ∧ d .nome =′ CIC ′ ∧ p.DPTNO =
d .DPTNO ∧ a.PRJNO = p.PRJNO ∧ a.CPF = a.CPF )}
Pedro de Azevedo Berger A´lgebra Relacional Slides Baseados no Livro A First Course in Database