Baixe o app para aproveitar ainda mais
Prévia do material em texto
BANCO DE DADOS II Conceitos Básicos 1 Prof. Dr.-Ing. Leonardo Andrade Ribeiro DCC-UFLA, Lavras Prof. Dr.-Ing. Leonardo Andrade Ribeiro Banco de Dados (BD) Uma coleção logicamente coerente de dados relacionados • Um agrupamento randômico de dados não pode ser considerado um BD Dados devem ser interpretáveis → informação • Significado implícito Um BD é projetado com um propósito específico • Grupo de usuários alvo • Acesso através de programas de aplicação 2 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Banco de Dados (BD) 3 BD Um BD representa determinados aspectos do mundo real: minimundo ou universo de discurso • Mudanças no minimundo são refletidas no BD Prof. Dr.-Ing. Leonardo Andrade Ribeiro Típico Cenário de Aplicação 4 App3 App1 App2 ... Informação Duplicada/ Inconsistente ... Prof. Dr.-Ing. Leonardo Andrade Ribeiro Solução: SGBD 5 App3 App1 App2 BD Sistema Gerenciador de Banco de Dados Prof. Dr.-Ing. Leonardo Andrade Ribeiro SGBD: Vantagens Independência física de dados • Detalhes sobre o armazenamento e acesso aos dados são “escondidos” de usuários e aplicações • Implantação de diferentes técnicas armazenamento (e.g., particionamento, clusterização, compressão) e métodos de acesso (e.g., índices) são transparentes para aplicações 6 Prof. Dr.-Ing. Leonardo Andrade Ribeiro SGBD: Vantagens (2) Independência lógica de dados • Informações sobre a estrutura dos dados e restrições de integridade é mantida e controlada de maneira centralizada e independente de aplicação, linguagem de programação, etc • O isolamento de aplicações de modificações como adição ou deleção de atributos ou relacionamentos e adição de novas restrições é facilitada (eg., através da definição de novos mapeamentos e visões) 7 Prof. Dr.-Ing. Leonardo Andrade Ribeiro SGBD: Vantagens (3) Controle de redundância e consistência de dados • Dados duplicados inadvertidamente causam desperdício de espaço de armazenamento e overhead para manutenção da consistência entre múltiplas cópias dos dados 8 Prof. Dr.-Ing. Leonardo Andrade Ribeiro SGBD: Vantagens (4) Processamento de transações • Permite o compartilhamento e acesso concorrente a dados entre usuários e aplicações Backup e recuperação de falhas O conceito de transação garantido pelo SGBD • Aplicações podem ser desenvolvidas como se executassem em um ambiente isolado e livre de falhas 9 Prof. Dr.-Ing. Leonardo Andrade Ribeiro SGBD: Vantagens (5) Suporte de múltiplas visões dos dados • Frequentemente, diferentes grupos de usuários devem ter diferentes “perspectivas” sobre os dados; certos dados não devem ser “vistos” por todos usuários (e.g., dados de professores e alunos) Mecanismo centralizado de controle de acesso e autenticação 10 Prof. Dr.-Ing. Leonardo Andrade Ribeiro SGBD: Vantagens (6) Linguagem comum de acesso • Transforma a necessidade de um mapeamento N-N entre linguagens na necessidade de um mapeamento 1-N Linguagem declarativa de alto-nível • Usuário especifica “o que” e não “como” • Menos código precisa ser escrito -> facilidade de entendimento e manutenção • Facilita a obtenção da independência lógica • Performance não é seriamente afetada 11 Prof. Dr.-Ing. Leonardo Andrade Ribeiro SGBD: Vantagens (7) Mecanimos eficientes de acesso e modificação dos dados • Estruturas de armazenamento otimizadas • Controle de buffer “tailor-made” • Índices • Otimização de consultas Aplicação de restrições integridade, acões automáticas ativadas por atualizações, inferências, etc 12 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Conceitos Básicos Abstração de Dados: • Supressão de detalhes a respeito da organização dos dados e armazenamento • Destaque de propriedades essenciais dos dados que permitam melhor entendimento e aproveitamento do mesmo 13 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Modelo de Dados Define os seguintes aspectos de um banco de dados: • Estrutura dos dados: tipos de (estrutura de dados) e seus relacionamentos • Manipulação dos dados: operadores ou regras de inferência que podem ser aplicados em qualquer instâncias válida dos dados para recuperar ou derivar dados de qualquer parte destas estruturas em qualquer combinação possível • Restrições de integridade: regras de integridades que implicitamente ou explicitamente definem os estado válidos de um banco de dados, mudanças de estados, ou ambos 14 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Modelo de Dados (2) Um modelo não precisa (e provavelmente não deve) ditar uma única linguagem para manipulação de dados e consulta porque diferentes categorias de usuários irão requerer provavelmente linguagens com diferentes características 15 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Modelo de Dados (3) Além dos dados em si, alguns modelos de dados também podem expressar aspectos dinâmicos e comportamentais de aplicações em banco de dados (combinação de projetos de banco de dados e softwares). • Ex.: Operações definidas pelo usuário. • Ex. destes modelos de dados: modelo orientado a objetos e objeto-relacional • No modelo relacional, é possível associar comportamento para um relação através stored procedures e triggers (procedimentos armazenamentos) 16 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Modelos de Dados (5) Modelos de dados podem ser categorizados de acordo com os tipos de conceitos usados para descrever a estrutura dos dados. Modelos conceituais: utiliza conceitos que são similares a maneira que os humanos percebem os dados, por exemplo, usando entidades, atributos, e relacionamentos (modelo Entidade-Relacionamento). Modelos lógicos ou de representação: define um modelo, que apesar de definir um layout conceitual dos dados, é também adequado para operações de manipulação sobre os dados (e.g., modelo relacional) Modelos físicos: utiliza conceitos que descreve detalhes sobre o como os dados são armazenados no computador 17 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Modelo de Dados (6) É importante notar que um mesmo modelo de dados pode ser empregado em diferentes níveis de abstração e para diferentes funcionalidades Exemplo: modelos de dados XML 18 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Modelo Relacional (Revisão) 19 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Modelo Relacional Estrutura dos dados • Relações • Mapeamento de E/R para Relacional • Normalização Manipulação dos dados • Álgebra relacional • Cálculo relacional (tupla e domínio) Integridade dos dados • Restrições ímplicitas e explícitas 20 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Modelo Relacional Modelo de dados formal criado por Edgar F. Codd em 1970 Base matemática • Teoria do conjuntos • Lógica de primeira ordem 21 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Modelo Relacional Origem de uma indústria bilionária (SGBDs Relacionais Oracle, IBM DB2, Microsoft SQL Server) • Em 2005, a revista Forbes elegeu o modelo relacional como uma das mais importantes inovações dos últimos 85 anos, na companhia de outras inovações extremamente conhecidas como o computador eletrônico digital, a televisão, a penicilina, o telefone celular, o transistor, o laser, a Internet, CD, etc 22 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Modelo Relacional: Conceitos Básicos Principal conceito: relação • Representa entidades e relacionamentos • Informalmente: uma tabela de valores Blocos de construção • Domínio • Esquema de relação • Atributo • Tupla 23 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Domínio Domínio: Um conjunto atômico de valores É comum associar um nome e um formato (ou tipo de dados) a um domínio • Nome: Nome_Funcionário, Formato: string de até 100 caracteres • Nome: Nr_CPF, Formato: número de 11 dígitos • Nome: Data_Nascimento, Formato: d/m/a, onde d em [01,31], m em [01,12], e a em [1900, ano atual] 24 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Esquema de Relação Esquema de relação = descrição de uma relação Notação: R(A1, A2,..., An), onde: • R é o nome da relação • A1, A2,..., An é uma lista ordenada de atributos • Cada atributo Ai, 1<=i<=n, é o nome de um papel desempenhado por algum domínio D no esquema de relação R; denotado por dom(Ai) • n é o grau da relação R 25 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Esquema de Relação: Exemplo 26 Nome CPF D_Nascimento Endereço Fone Funcionário R = Funcionário Atributos: • A1 = Nome, dom(Nome) = Nome_Funcionário • A2 = CPF dom(CPF) = Nr_CPF • A3 = D_Nascimento dom(D_Nascimento) = Data_Nascimento • A4 = Endereço dom(Endereço) = Endereço • A5 = Fone dom(Fone) = Formato_Telefone Grau = 5 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Relação Dado um esquema de relação R(A1, A2,..., An), uma relação de R, denotado por r(R), é um conjunto de tuplas {t1, t2, …, tm} • Cada tupla ti, 1<=i<=m, é uma lista ordenada de valores <v1, v2, …, vn> • Cada valor vi, 1<=i<=n, é um elemento do domíminio dom(Ai) ou é o valor NULL • Dada uma tupla t, o valor na posição i (relativo ao atributo Ai) é denotada por t[Ai] A cardinalidade de r(R), denotada por |r|, correspondente ao número de tuplas em r(R) 27 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Intensão e Extensão 28 Metadados: Intensão Estado do Banco de Dados: Extensão Nome CPF D_Nascimento Endereço Fone José Silva 11111111 07/09/1969 Av. Brasil, 16 151515 João Rocha 222222222 23/12/1969 Rua 9, 232 231231 Alan Ribeiro 809333333 13/10/1971 Av. D, 150 131313 Maria Santos 444444444 NULL Av. C126, 98 NULL Márcia Oliveira 555555555 18/11/1970 Rua 3, 25 NULL Prof. Dr.-Ing. Leonardo Andrade Ribeiro Relação: Exemplo 29 Nome CPF D_Nascimento Endereço Fone Funcionário José Silva 11111111 07/09/1969 Av. Brasil, 16 151515 João Rocha 222222222 23/12/1969 Rua 9, 232 231231 Alan Ribeiro 809333333 13/10/1971 Av. D, 150 131313 Maria Santos 444444444 NULL Av. C126, 98 NULL Márcia Oliveira 555555555 18/11/1970 Rua 3, 25 NULL Atributos Tuplas Intensão Extensão Valores Prof. Dr.-Ing. Leonardo Andrade Ribeiro Relaçao: Definição Formal Uma relação matemática de grau n sobre os domínios dom(A1), dom(A2), ..., dom(An), o que representa um subconjunto do produto Cartesiano do domínios que definem R: • r(R) ⊆ dom(A1) × dom(A2) × dom(An) 30 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Características de Relações Relação: um conjunto de tuplas 31 Não existe uma ordenação em particular definida sobre as tuplas de uma relação • Ordenações arbitrárias podem ser definidas logicamente baseando-se nos valores das tuplas − Ordenação alfabética baseada no valor atributo Nome da relação Funcionário Todas tuplas são distintas (tuplas duplicadas, isto é, tuplas com os valores idênticos em todos atributos, não são permitidas) Prof. Dr.-Ing. Leonardo Andrade Ribeiro Esquema de Relação: Interpretações Asserção (ou declaração) sobre entidades ou relacionamentos -> cada tupla representa um fato ou instância desta asserção Predicado envolvendo entidades ou relacionamentos -> tuplas possuem valores que satisfazem estes predicados 32 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Restrições do Modelo Relacional Restrição de domínio • Especifica que o valor de cada atributo A deve ser um valor atômico (indivisível) do domínio dom(A) Restrição em valores NULL • Especifica se valores NULL são permitidos para um determinado atributo • Ex.: “Todo funcionário deve um valor válido para os atributos Nome e CPF” 33 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Restrições de Chave Todo esquema de relação possui um subconjunto de atributos que possuem a propriedade de que nenhum par de tuplas possui valores idênticos para estes atributos • Inferência a partir da definição de que todas tuplas são distintas em uma relação • Subconjunto trivial: todos os atributos de um esquema de relação Qualquer subconjunto com esta propriedade é chamado de super-chave de um esquema de relação R Uma super-chave é denotada por SC, os valores de uma superchave para uma tupla t é t[SC] Restrição de chave: Para quaisquer tuplas t1 e t2, t1 = t2, em um relação r(R), tem-se: t1*SC+ ≠ t2[SC] 34 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Restrições de Chave (2) Chave: uma super-chave com a restrição adicional de minimalidade • Removendo qualquer atributo de uma chave C faz com que C deixe de ser uma super-chave Todas chaves em um esquema de relação são chamadas chave candidatas Uma chave candidata é escolhida para ser a chave primária de um esquema de relação • Usada para identificar unicamente todas as tuplas de uma relação Chaves primárias não podem ter o valor NULL 35 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Chaves: Exemplo 36 Nome CPF D_Nascimento Endereço Fone Funcionário chave primária super-chave Nome Endereço Nome Fone chave candidatas Outras chaves? Prof. Dr.-Ing. Leonardo Andrade Ribeiro Banco de Dados Relacional Esquema de um BD relacional: um conjunto de esquemas de relações S = {R1, R2, …, Rm} e um conjunto de restrições I Banco de Dados Relacional: Um banco de dados BD relativo a S é um conjunto de relações BD = {r1(R1), r2(R2), …, rm(Rm)} onde cada ri(Ri), 1<=i<=m, satisfaz as restrições em I 37 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Banco de Dados Relacional Na prática, o termo banco de dados relacional se refere conjuntamente ao conjunto de esquemas e relações Um BD é dito estar em estado válido se todas as retrições de integridade em I são satisfeitas; caso contrário, o estado do BD é inválido 38 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Esquema de BD Relacional [EN07] Prof. Dr.-Ing. Leonardo Andrade Ribeiro BD Relacional [EN07] Prof. Dr.-Ing. Leonardo Andrade Ribeiro Restrições de Integridade Referencial Mantém a consistência entre tuplas de duas relações Informalmente, se uma tupla de uma relação faz referência a uma outra relação, então esta tupla deve fazer referência a uma tupla que de fato exista nesta outra relação • Ex.: O valor (não NULL) do atributo Dno em toda tupla da relação EMPLOYEE deve ser idêntico ao valor do atributo Dnumber de alguma tupla da relação DEPARTMENT 41 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Restrições de Integridade Referencial (2) Definição formal através do conceito de chave estrangeira Um conjunto de atributos CE em um esquema de relação R1 é uma chave estrangeira de R1 que faz referencia a um esquema de relação R2 se ele satisfaz as seguintes condições: • Os atributos em CE possuem o mesmo domínio que os atributros CP da chave primária de R2 • Os valores de CEem uma tupla t1 da relação r1(R1) ou ocorrem como valores de CP em alguma tupla t2 de r2(R2), isto é t1[CE]=t2[CP], ou são NULL 42 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Representação Gráfica [EN07] Prof. Dr.-Ing. Leonardo Andrade Ribeiro Outros Tipos de Restrições Restrições de integridade semântica: • Exemplos: “O salário de um empregado não pode ser maior que o do seu supervisor”, “O número máximo de horas de trabalho por semana é 56” • Aplicadas no BD através de asserções e triggers ou nos programas de aplicação (mais comum) Restrição de depêndencia funcional • Informalmente, o valor de um mais atributos determinam o valor de outros atributos • Conceito fundamental para o projeto de esquemas de BDs relacionais (normalização) 44 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Outros Tipos de Restrições Restrições de estado • Restrições que um banco de dados válido deve satisfazer Restrições de transição • Definem alterações válidas em um BD. Ex.: O salário de um empregado pode apenas aumentar 45 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Operações de Modificação Três operações básicas: • Inserção: insere novas tuplas em uma relação • Deleção: remove tuplas de um relação • Atualização: atualiza o valor atributos em tuplas O SGBD deve garantir que a execução de destas operações não viole restrições de integridade 46 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Violações de Integridade: Inserção Dominio: o valor de um ou mais atributos não faz parte do domínio Chave: o valor de chave da nova tupla é NULL ou já ocorre em outra tupla Integridade referencial: o valor de qualquer chave estrangeira da nova tupla faz referência a uma tupla inexistente na relação referenciada Medida corretiva: A operação de inserção é rejeitada (medida mais comum) 47 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Violações de Integridade: Deleção Apenas restrições de integridade referencial podem ser violadas se a tupla sendo removida é referenciada pela chave estrangeira de outras tuplas Medidas corretivas: • Rejeição da operação • Propagação da operação de deleção através da remoção da tuplas que referenciam a tupla deletada • Modificação dos valores dos atributos da chave estrangeira para NULL (pode não ser possível se estes valores fazem da chave primária) 48 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Violações de Integridade: Atualização Violação idênticas às operações de inserção e deleção quando os atributos atualizados não fazem parte da chave primária ou de alguma chave estrangeira • Atualização pode ser interpretada como a deleção de uma tupla e a inserção de uma nova Caso contrário, apenas restrições de domínio podem ser violadas 49 Prof. Dr.-Ing. Leonardo Andrade Ribeiro 50 Algebra Relacional (Revisão) Prof. Dr.-Ing. Leonardo Andrade Ribeiro Álgebra Relacional Todo modelo de dados deve prover um conjunto básico de operações para manipulação de dados O cojunto de operações para manipulação de dados do modelo relacional é a álgebra relacional O resultado de cada operação é uma relação. Operações podem ser concatenadas formando uma expressão cujo resultado é também uma relação: • Propriedade de encerramento (closure) • Set-at-a-time 51 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Álgebra Relacional Fundação formal para operações do modelo relacional Provê uma base para implementação e otimização de consultas em SGBDs (por exemplo, SQL) 52 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Processamento de Consultas SQL 53 SELECT C.ID, C.Nome, COUNT( * ) FROM Aluno as A, Curso as C WHERE A.CID = C.ID GROUP BY C.ID, C.Nome HAVING COUNT( * ) >= 100 Consulta SQL Query SELECT FROM WHERE GROUP BY HAVING C.ID C.Nome Count( * ) Aluno Curso C.ID C.Nome Condição Count ( * ) >= 100 Condição A.CID = C.ID Árvore Sintática Abstrata Parsing/Validação Prof. Dr.-Ing. Leonardo Andrade Ribeiro Processamento de Consultas SQL 54 Query SELECT FROM WHERE GROUP BY HAVING C.ID C.Nome Count( * ) Aluno Curso C.ID C.Nome Condição Count ( * ) >= 100 Condição A.CID = C.ID Árvore Sintática Abstrata 𝐴 ← 𝐴𝑙𝑢𝑛𝑜 𝐶 ← 𝐶𝑢𝑟𝑠𝑜 ⋈𝐴.𝐶𝐼𝐷=𝐶.𝐼𝐷 𝛾𝐶.𝐼𝐷,𝐶.𝑁𝑜𝑚𝑒, 𝑐𝑡←𝐶𝑂𝑈𝑁𝑇(∗) 𝜎𝑐𝑡≥100 𝜋𝐶.𝐼𝐷,𝐶.𝑁𝑜𝑚𝑒 Árvore de Operadores Algebraicos A árvore sintática abstrata é convertida em uma árvore de operadores da álgebra relacional Prof. Dr.-Ing. Leonardo Andrade Ribeiro Processamento de Consultas SQL 55 Scan Aluno Scan Curso Hash Join [A.CID=C.ID] SORT [A.CID,C.NOME] Stream Agregate TMP ←COUNT(*) FILTER , PROJ [TMP≥ 100, C.ID, C.Nome] Árvore de Operadores Físicos 𝐴 ← 𝐴𝑙𝑢𝑛𝑜 𝐶 ← 𝐶𝑢𝑟𝑠𝑜 ⋈𝐴.𝐶𝐼𝐷=𝐶.𝐼𝐷 𝛾𝐶.𝐼𝐷,𝐶.𝑁𝑜𝑚𝑒, 𝑐𝑡←𝐶𝑂𝑈𝑁𝑇(∗) 𝜎𝑐𝑡≥100 𝜋𝐶.𝐼𝐷,𝐶.𝑁𝑜𝑚𝑒 Árvore de Operadores Algebraicos Finalmente a árvore de operadores algebraicos é convertida em uma árvore de operadores físicos (implementação da árvore algebraica) que irá então executar a consulta Prof. Dr.-Ing. Leonardo Andrade Ribeiro Por que Não Usar Diretamente a Álgebra Relacional? Algebra relacional provê um método procedural para consultar o banco de dados Define quais operações a serem usadas e qual a sequência de execução destas operações Em outras palavras, a álgebra relacional SQL é uma linguagem declarativa para acesso a dados 56 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Componentes da Álgebra Relacional Categorias de operações • Operações baseada na teoria dos conjuntos: União, Diferença, Interseção, Produto Cartesiano • Operações específicas para o modelo relacional: Select, Project, Join, etc • Extensões: operações de agregação e agrupamento 57 Prof. Dr.-Ing. Leonardo Andrade Ribeiro A Operação SELECT (σ) Seleciona um subconjunto das tuplas de uma relação que satisfaçam a condição de seleção Interpretações: • Filtro • Particionamento horizontal Notação: σ<condição de seleção> (R) Exemplo: σ<Salary > 30000> (EMPLOYEE) 58 Prof. Dr.-Ing. Leonardo Andrade Ribeiro A Operação SELECT (σ) Condição de seleção é um expressão Booleana formada por um conjunto de cláusulas com o seguinte formato: <nome do atributo> <op de comparação> <constante>, ou <nome do atributo> <op de comparação> <nome de atributo> Op de Comparação: ,=, ≠, <, ≤, >, ≥- Conectivos: and, or, not Exemplo: σ<(Dno = 4 AND Salary > 25000) OR (Dno = 5 AND Salary > 30000)> (EMPLOYEE) 59 Prof. Dr.-Ing. Leonardo Andrade Ribeiro A Operação SELECT (𝜎) Operador unário Operação aplicada em cada tupla individualmente • Condição de seleção não pode envolver mais de uma tupla Mantém o grau da relação original Seletividade: # tuplas_relação_resultante / # tuplas_relação_original Operação comutativa: • σ<cond1> (σ<cond2> (R)) = σ<cond2> (σ<cond1> (R)) • σ<cond1> (σ<cond2> (…(σ<condN> (R))…)) = σ<cond1> AND <cond2> AND … AND condN> (R) 60 Prof. Dr.-Ing. Leonardo Andrade Ribeiro A Operação PROJECT (𝜋) Interpretação: • Seleção de colunas em uma tabela • Particionamento vertical Notação: 𝜋<lista de atributos>(R) Exemplo: 𝜋<Fname, Lname, Salary>(EMPLOYEE) O grau da relação resultante é igual ao número de atributos na lista 61 Prof. Dr.-Ing. Leonardo Andrade Ribeiro A Operação PROJECT (𝜋) Se a lista de atributos não contém chaves, eliminação de duplicatas é necessária (ou então o resultado seria uma bag) PROJECT não é comutativo • 𝜋<lista1>(𝜋<lista2>(R)) = 𝜋<lista1>(R), se lista2 ⊆ lista1, ou então a operação é inválida 62 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Sequência de Operações Uma sequência de operações pode ser representada de duas maneiras: 1. Uma única expressão de álgebra relacional 2. Usando resultados intermediários (nomeados) 63 1. 𝜋<Fname,Lname,Salary>(σDno=5(EMPLOYEE)) 2. TEMP ← σDno=5(EMPLOYEE) RESULT ← π<Fname,Lname,Salary>(TEMP) Melhor legibilidade Prof. Dr.-Ing. Leonardo Andrade Ribeiro Renomeando Relações e Atributos Para facilitar legibilidade podemos renomear relações e atributos 𝑅𝑒𝑠𝑢𝑙𝑡𝑎𝑑𝑜 ← 𝑇𝑀𝑃 • Muda o nome da relação 𝑇𝑀𝑃 para 𝑅𝑒𝑠𝑢𝑙𝑡𝑎𝑑𝑜 𝑅 𝑎, 𝑏, 𝑐 ← 𝑅 𝑟, 𝑠, 𝑡 • Muda o nome dos atributos 𝑟, 𝑠 𝑒 𝑡 de 𝑅 para 𝑎, 𝑏 𝑒 𝑐, respectivamente 𝑅 𝑎, 𝑏, 𝑐 ← 𝑆 𝑟, 𝑠, 𝑡 • Muda o nome e os atributos de 𝑆 64 Prof. Dr.-Ing. Leonardo Andrade Ribeiro UNIÃO ∪ , INTERSEÇÃO 𝜋 , DIFERENÇA − Operações binárias Esquemas de relações devem ser compatíveis na união • Dois esquemas são compatíveis na união se eles possuem o mesmo grau e cada par de atributos possui o mesmo domínio UNIÃO e INTERSEÇÃO são comutativas e associativas Diferença não é comutativa INTERSEÇÃO pode ser representada em termos de UNIÃO e DIFERENÇA • R ∩ S = R ∪ S – (R – S) – (S – R) 65 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Produto Cartesiano × Produz um novo conjunto através da combinação de todas as tuplas em uma relação com todas tuplas de outra relação O grau da relação resultante é 𝑛 + 𝑚, onde n é e m são os graus das relações participantes A cardinalidade da relação resultante é |𝑟| ∗ |𝑠|, onde |𝑟| e |𝑠| são as cardinalidades das relações participantes 66 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Produto Cartesiano (2) Como padrão, atributos com o mesmo nome em ambas relações são renomeados para nome_da_relação.nome_do_atributo Exemplo: • Considere duas relações 𝑅 𝑎, 𝑏, 𝑐 e 𝑆 𝑠, 𝑏, 𝑐 e relação 𝑇 que é o resultado do produto cartesiando entre 𝑅 e 𝑆 • Portanto: 𝑇 𝑎, 𝑅. 𝑏, 𝑆. 𝑏, 𝑠, 𝑅. 𝑐, 𝑆. 𝑐 ← 𝑅 × 𝑆 67 Prof. Dr.-Ing. Leonardo Andrade Ribeiro A Operação JOIN Combina tuplas relacionadas de duas relações em um única tupla Notação: R⋈<condição>S Exemplo: • DEPARTMENT⋈<Mgr_ssn=Ssn>EMPLOYEE Interpretação: Produto Cartesiano seguido de uma seleção • σ<Mgr_ssn=Ssn>(DEPARTMENT×EMPLOYEE) Seletividade: # 𝑡𝑢𝑝𝑙𝑎𝑠_𝑟𝑒𝑙𝑎çã𝑜_𝑟𝑒𝑠𝑢𝑙𝑡𝑎𝑛𝑡𝑒/ # |𝑅| ∗ |𝑆| 68 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Variantes Básicas da Operação JOIN NATURAL JOIN: Junção onde a condição é determinada pela operação de igualdade e pelos atributos com o mesmo nome entre as duas relações Além disso, elimina automaticamente da relação resultante um atributo de cada dupla de atributos de mesmo nome Representada apenas por 𝑅 ⋈ 𝑆 (dispensa especificação da junção) Exemplo • Considere duas relações 𝑅 𝑎, 𝑏 e 𝑆 𝑏, 𝑐 . Portanto: • 𝑅 ⋈ 𝑆 ≡ 𝑅 ⋈𝑅.𝑏=𝑆.𝑏 𝑆 e • 𝑇 𝑎, 𝑏, 𝑐 ← 𝑅 ⋈ 𝑆 69 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Variantes Básicas da Operação JOIN (2) EQUI-JOIN: Junções contendo apenas condições envolvendo apenas o operador de igualdade • Exemplo: Considere duas relações 𝑅 𝑎, 𝑏 e 𝑆 𝑐, 𝑑 • Temos que 𝑅 ⋈𝑅.𝑏=𝑆.𝑐 𝐴𝑁𝐷 𝑅.𝑎=𝑆.𝑑 𝑆 é um EQUI-JOIN Theta-JOIN: Demais tipos de junções envolvendo condições arbitrárias • Exemplo: 𝑅 ⋈𝑅.𝑏>𝑆.𝑐 𝑆 70 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Conjunto Completo de Operações da Algebra Relacional Todas operações da algebra relacional podem ser expressas como uma sequência das operações {σ, π, ∪, -, ×} 71 Prof. Dr.-Ing. Leonardo Andrade Ribeiro A Operação de Divisão A operação de Divisão é aplicada em duas relações R(Z) ÷ S(X), onde X ⊆ Z. Seja Y = Z – X (e portanto Z = X ∪ Y), isto é, Y é o conjunto de atributos em R que não são atributos de S. O resultado da divisão é uma relação T(Y) que inclui uma tupla t se tuplas tR aparecem em R com tR[Y] = t, e com tR[X] = tS para toda tupla tS em S Para uma tupla t aparecer no resultado T da divisão, os valores em t devem aparecer em R em combinação com todas as tuplas em S 72 Prof. Dr.-Ing. Leonardo Andrade Ribeiro A Operação de Divisão As tuplas no denominador restringem relação no numerador através da seleção das tuplas no resultados que são pareadas com todos valores no denoninador Útil para representar a quantificação universal • Recupe o nome de todos funcionários que trabalham em todos projetos controlados pelo departmento nr. 5. A divisão pode ser expressada através da sequência: • T1 <- πY(R) • T2 <- πY((S × T1) – R) • T <- T1 – T2 73 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Considerando Bags Informalmente, bags (ou multiconjuntos) são “conjuntos” que permitem múltiplas ocorrências de um elemento • Isto é, duplicatas são permitidas Banco de dados comerciais são geralmente baseados uma generalização do modelo relacional para bags Permite evitar ou adiar a operação de eliminação de duplicatas, que é custosa computacionalmente 74 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Operações sobre Bags A adaptação dos operadores 𝜎, 𝜋, × e ⋈ é intuitiva para a semântica baseada em bags • A única diferença é que a eliminação de duplicatas, se necessária, não é aplicada Por outro lado, as operações ∪, ∩, e − possuem semântica diferente 75 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Operações ∪, ∩, e − sobre Bags União entre bags: a multiplicidade dos elementos é somada • Exemplo: Se 𝑎 é um elemento que aparece 2 vezes em 𝑅 e três vezes em 𝑆, então 𝑎 irá aparecer 5 vezes em 𝑅 ∪ 𝑆 Interseção entre bags: a multiplicidade de um elemento na interseção entre dois conjuntos corresponde à menor multiplicidade entre os dois conjuntos • Exemplo: Se 𝑎 aparece 𝑚 vezes em 𝑅 e 𝑛 vezes em 𝑆, então a irá aparecer min (𝑚, 𝑛) vezes em 𝑅 ∪ 𝑆 Diferença entre bags: a multiplicidade de um elemento 𝑡 na diferença entre um conjunto 𝑅 e um conjunto 𝑆 é dada pelo maior valor entre 0 e a multiplicidade de 𝑡 em 𝑅 subtraída pela multiplicidade de 𝑡 em 𝑆 • Exemplo: Se 𝑎 aparece 𝑚 vezes em 𝑅 e 𝑛 vezes em 𝑆, então a irá aparecer m𝑎𝑥 (0, 𝑚 − 𝑛) vezes em 𝑅 − 𝑆 76 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Conjuntos e Bags Note que um conjunto é um caso especial de uma bag, onde as multiplidades dos elementos é 0 ou 1 Dado dois conjuntos, as operações de ∩ e − ainda produzem conjuntos quando interpretadas usando a semântica para bags Entretanto a operação de ∪ entre dois conjuntos irá resultar em bags quando interpretada usando a semântica para bags 77 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Extensões para Álgebra Relacional Algumas operações frequentemente necessárias em aplicações de banco de dados não podem ser expressadas em álgebra relacional Exemplo • Eliminação de duplicatas • Agregação de valores • Agrupamento de valores Por este motivo, operações adicionais foram criadas para aumentar o poder de expressão do modelo relacional 78 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Eliminação de Duplicatas (𝛿) Este operador converte uma bag em um conjunto Seja 𝑅 uma bag, então 𝛿 𝑅 retorna um conjunto contendo apenas uma cópia para todos elementos que uma ou mais vezes em 𝑅 79 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Agregação Operadores usados para sumarizar ou agregar valores de uma tabela Retornam uma relação (e não um valor escala) contendo apenas um valor Operações: • 𝑆𝑈𝑀𝐴 𝑅 : retorna a soma dos valores da coluna R.A; o domínio do atributo A deve ser do tipo numérico • 𝐴𝑉𝐺𝐴 𝑅 : retorna a soma dos valores da coluna R.A; o domínio do atributo A deve ser do tipo numérico • 𝑀𝐼𝑁𝐴 𝑅 e 𝑀𝐴𝑋𝐴 𝑅 retorna o maior e o menor valor entre os valores da R.A. Caso A seja do tipo alfanumérico, o valor retornado será o primeiro (MIN) ou último (MAX) valor em ordem alfabética • COUNT 𝑅 : retorna o número de tuplas em R; note que R pode ser uma BAG 80 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Agrupamento (𝛾) Agrupamento: agrupa as tuplas em uma relação baseado no valor de alguns atributos • Exemplo: agrupamento das tuplas da relação Funcionário baseando no número do departamento A operação 𝛾 𝐿 𝑅 particiona R de acordo com os valores da lista de atributos 𝐿 Para cada grupo é retornada uma tupla contendo os atributos do agrupamento 81 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Agrupamento e Agregação Operações de agrupamento são frequentemente combinadas com funões de agregação Denotado por 𝛾 𝐿 𝐴𝐺𝐺 𝑅 , onde AGG é uma ou mais funções de agregação • “Retorne o menor e o maior salário dos funcionários de cada departamento, assim como o número de funcionários do departamento” • Expressão: RES(dno, min_sal, max_sal, count) ← 𝛾𝐷𝑁𝑢𝑚𝑀𝐴𝑋𝑆𝑎𝑙𝑎𝑟𝑖𝑜𝑀𝐼𝑁𝑆𝑎𝑙𝑎𝑟𝑖𝑜𝐶𝑜𝑢𝑛𝑡 𝐹𝑢𝑛𝑐𝑖𝑜𝑛𝑎𝑟𝑖𝑜 82 Prof. Dr.-Ing. Leonardo Andrade Ribeiro Projeções Generalizadas Projeções generalizadas: permite expressões sobre atributos a serem aplicados na lista de atributos 83 Prof. Dr.-Ing. Leonardo Andrade Ribeiro JOIN Variantes EQUIJOIN : Quando o único operador de comparação é a igualdade NATURAL JOIN: Remove atributo repetidos THETA JOIN: Condições arbitrárias INNER JOIN: Operação padrão em que apenas tuplas satisfazendo a condição são retornadas LEFT/RIGHT OUTER JOIN: mantém todas as tuplas da relação da esquerda (direita); quando não existe nenhum tupla relacionada na relação da direita (esquerda), os valores dos atributos desta relação são NULL FULL OUTER JOIN: Mantém todos as tuplas de todas relações • Qual a diferença entre FULL OUTER JOIN e Produto Cartesiano • Todos OUTER JOIN são extensões para a álgebra relacional original 84
Compartilhar