Baixe o app para aproveitar ainda mais
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
Compartilhar