Álgebra relacional

Em ciências da computação, álgebra relacional é uma derivação descendente da lógica de primeira ordem e da álgebra de conjuntos em relação das operações sobre a relação finítimo, que auxilia o trabalho ao identificar os componentes de uma tupla por nome (chamado o atributo) ao invés de uma coluna de chaves numéricas, o qual é chamado a relação na terminologia de banco de dados.

A principal aplicação da álgebra relacional é sustentar a fundamentação teórica de banco de dados relacional, particularmente linguagem de consulta para tais bancos de dados, entre os maiores o SQL.

Introdução

A álgebra relacional recebia pouca atenção fora do campo da matemática pura até à publicação em 1970 do modelo relacional de dados de E.F. Codd. Codd propôs tal álgebra como a base das linguagens de consulta de banco de dados. (Ver secção Implementações.)

Na álgebra relacional, são admitidas ambas perspectivas de dar um nome ou não, dependendo se as tuplas são dotadas de nome de componente ou não. Na perspectiva sem nome, a tupla é simplesmente um membro de um produto cartesiano. Na perspectiva da tupla ter um nome de componente, tuplas são funções do conjunto finito de atributos U (da relação) a um dominío de valores (assumidos distintos dos de U). As álgebras relacionais obtidas das duas perspectivas são equivalentes. Um livro típico de graduação apresenta só a perspectiva de nomear e este artigo segue isso.

A álgebra relacional é equivalente em poder expressivo a cálculo relacional (e por conseguinte lógica de predicado ou primeira ordem); esse resultado é conhecido como o teorema de Codd. Na prática, deve ser prestada atenção em desambiguar as duas linguagens porque a negação quando aplicada a uma fórmula em cálculo, faz a construção da fórmula que pode ser verdadeira ou um conjunto infinito de tuplas, enquanto o operador diferença na álgebra relacional devolve sempre um resultado finito. Para ultrapassar estas dificuldades, Codd restringiu os operandos da álgebra relacional somente para relação finita e propôs suporte restrito para a negação (NOT) e a disjunção (OR). Restrições análogas são encontradas em muitas outras linguagens de programação lógicas. Codd definiu o termo completeza relacional para se referir a uma linguagem que está completa em respeito a cálculo de lógica da primeira ordem à parte com as restrições que ele propunha. Na prática as restrições têm um efeito adverso na aplicabilidade da sua álgebra relacional para usos de banco de dados.

Definimos assim a álgebra relacional como uma linguagem de consulta formal i.e. uma coleção de operações de alto nível sobre relações ou conjuntos. As operações em questão são: restrição (seleção), projeção, produto, união, interseção, diferença, junção e divisão. O leitor deve entender que as oito operações não são um conjunto mínimo. De facto, dos oito, só 5 são primitivos, nomeadamente restrição, projeção, produto, união, e diferença. Os outros três podem ser definidos destes cinco. Todas essas operações produzem uma nova relação como seu resultado.

Operadores primitivos

Como em qualquer álgebra, alguns operadores são primitivos e os outros são derivados em termos dos primitivos. É útil que a escolha dos operadores primitivos se compare a casos comuns onde se faça uso dos operadores lógicos primitivos.

Os cinco operadores primitivos de Codd na álgebra são o de seleção, a projeção, produto cartesiano (também chamado de produto cruz ou junção cruz), a união, e a diferença . Outro operador, renomear não foi aponte por Codd, (Na verdade, Codd omite o renomear, para proceder) mas a sua necessidade foi mostrada pelos inventores da ISBL. Estes seis operadores são fundamentais no sentido de que nenhum deles pode ser omitido sem perder poder expressivo. Muitos outros operadores foram definidos em termos destes seis. Entre os mais importantes são interseção, divisão e a junção natural. Na verdade a ISBL fez a substituição do produto cartesiano pela junção natural, dado que o produto cartesiano é um caso degenerado. Embora seja sabido que na lógica do E, OU e NÃO a escolha é um pouco arbitrária, Codd usou de escolha semelhantes para a sua álgebra.

Ao todo, os operadores da álgebra relacional têm poder expressivo idêntico ao do calculo de domínio relacional ou calculo de tuplas relacionais. No entanto, pelas razões apontadas na introdução acima, a álgebra relacional é estritamente menos expressiva do que a lógica de primeira ordem sem símbolos de função. Álgebra relacional efectivamente corresponde a um subconjunto da lógica de primeira ordem que é a cláusula de Horn sem recursividade e negação.

Operações de conjuntos

A álgebra relacional usa conjunto união, conjunto complementar e o produto cartesiano da Teoria dos conjuntos, mas adiciona restrições adicionais a esses operadores.

Para união de conjunto e conjunto complementar, as duas relações envolvidas devem ser compatíveis com união - isto é, as duas relações devem ter o mesmo conjunto de atributos. Porque a interseção de conjuntos pode definir-se em termos da diferença do conjunto, as duas relações envolvidas na diferença do conjunto devem ser compatíveis com união.

Para definir o produto Cartesiano, as duas relações envolvidas devem ter cabeçalhos disjuntivos - isto é, estes não podem partilhar um nome comum de atributo.

Em soma, o produto Cartesiano é definido de maneira diferente do produto em teoria do conjunto no sentido que tuplas são consideradas serem "baixinhas" para usos da operação. Isto é, o produto Cartesiano do conjunto de n-tuplas com um conjunto de m-tuplas resulta um conjunto (n + m)-tuplas "alisadas" (onde na teoria básica de conjuntos teríamos prescrito um conjunto de 2-tuplas, cada contendo uma n-tupla e outra m-tupla). Mais formalmente, R × S é definido como segue:

R × S = {(r₁, r₂, ..., r_n, s₁, s₂, ..., s_m) | (r₁, r₂, ..., r_n) ∈ R, (s₁, s₂, ..., s_m) ∈ S}

A cardinalidade do produto Cartesiano é o produto das cardinalidades dos seus fatores, i.e., |R × S| = |R| × |S|.

Projeção ($\pi$)

Ver artigo principal: Projeção (álgebra relacional)

A projeção é uma operação unária escrita como $\pi _{(a_{1},\dots ,a_{n})}(R)$ onde $a_{1},\dots ,a_{n}$ é um conjunto de nome de atributos. O resultado de tal projeção é definida como o conjunto que é obtido quando todas as tuplas em R são restritas ao conjunto $a_{1},\dots ,a_{n}$.

Isto especifica o subconjunto de colunas (atributos de cada tupla) a ser seleccionado. Para obter os nomes e número de telefones da lista de endereços, a projeção poderia ser escrita $\pi _{\text{Nomecontacto, Ntelefonecontacto}}({\text{livroendereços}})$. O resultado de tal projeção seria uma relação com apenas os Nomecontacto e Ntelefonecontacto para cada entrada única no livroendereços.

Seleção (σ)

Ver artigo principal: Seleção (álgebra relacional)

Uma seleção generalizada é uma operação unária escrita como $\sigma _{\varphi }(R)$ onde $\varphi$ é uma fórmula proposicional que consiste de átomos como é permitido na seleção normal e operadores os lógicos $\land$ (and), $\lor$ (or) e $\lnot$ (negação). Esta seleção seleciona todas as tuplas em R para cada valor de $\varphi$.

Para obter uma listagem de todos os amigos ou associados no livro de endereços, a selecão podia ser escrita como $\sigma _{{\text{eamigo = verdadeiro}}\lor {\text{econtactocomercial = verdadeiro}}}({\text{livroendereços}})$. O resultado seria uma relação que tinha todos atributos de todos os registo únicos onde eamigo é verdadeiro ou onde econtactocomercial é verdadeiro.

No paper académico de Codd de 1970, a seleção é chamada de restrição.

Renomear ($\rho$)

Ver artigo principal: Renomear (álgebra relacional)

Renomear é uma operação unária escrita como $\rho _{a/b}(R)$ onde o resultado é idêntico ao R excepto que o campo b em todas as tuplas é renomeado para um atributo a. Isto é simplesmente usado para mudar o nome do atributo de uma relação ou a relação em si.

Para renomear o atributo 'eamigo' para 'econtactocomercial' na relação, $\rho _{\text{econtatocomercial / eamigo}}({\text{Livroendereço}})$ pode ser utilizado.

Operadores de junção e de operações similares

Junção natural ($\bowtie$)

A junção natural é uma operação binária que é escrita como (R $\bowtie$ S) onde R e S são relações. O resultado da junção natural é uma tabela com todas as combinações das tuplas em R e S que seu atributos em comum são iguais. Por exemplo, considerando as tabelas Empregado e Departamento e sua junção natural:

Empregado Nome IdEmp DeptNome Harry 3415 Finanças Sally 2241 Vendas George 3401 Finanças Harriet 2202 Vendas

Departamento DeptNome Gerente Finanças George Vendas Harriet Produção Charles

Empregado $\bowtie$ Departamento Nome IdEmp DeptNome Gerente Harry 3415 Finanças George Sally 2241 Vendas Harriet George 3401 Finanças George Harriet 2202 Vendas Harriet

Isso também pode ser usado para definir as composição das relações. Na teoria das categorias, a junção é, precisamente, o produto fibrado.

A junção natural é, indiscutivelmente, uma das mais importante operações visto que ela é a contraparte relacional do AND (E) lógico. Observe com atenção que se as mesmas variáveis forem mostradas nos dois predicados que são conectados pelo AND, então essa variável representa a mesma coisa e ambas as aparências sempre devem ser substituídas pelo mesmo valor. Particularmente, a junção natural permite a combinação de relações que são associados por uma chave estrangeira. No exemplo que procedeu, provavelmente existe uma chave estrangeira em Empregado.DeptNome para Departamento.DeptNome e então a junção natural de Empregado e Departamento combina todos os empregados com seus departamentos. Nota que isso funciona porque a chave estrangeira detém os atributos entre os de mesmo nome. Se esse não for o caso, como em uma chave estrangeira de Departamento.Gerente para Empregado.número-emp, deve-se, então, renomear essas colunas antes de fazer a junção natural. Essa é, às vezes, uma equijunção (veja θ-junção).

Mais formalmente, a semântica da junção natural é definida como segue:

$R\bowtie S=\left\{t\cup s\ \vert \ t\in R\ \land \ s\in S\ \land \ {\mathit {Fun}}(t\cup s)\right\}$

onde Fun é um predicado que é verdadeiro para uma relação binária r se e somente se $r$ é uma relação funcional binária. Normalmente, é necessário que R e S tenham, pelo menos, um atributo em comum, mas se essa restrição é omitida, então a junção natural torna-se, exatamente, o produto cartesiano.

A junção natural pode ser simulada com primitivos de Codd, como segue. Supõem-se que b₁,…,b_m são nomes de atributos comuns em R, S, a₁,…,a_n são os atributos de nome único de R e c₁,…,c_k são os atributos de nome único de S. Além disso, assume-se que os nomes dos atributos d₁,…,d_m não são nem de R ou de S. Primeiramente, nós podemos mudar, agora, o nome do atributo em comum em S:

$T=\rho _{d_{1}/b_{1},\ldots ,d_{m}/b_{m}}(S)=\rho _{d_{1}/b_{1}}(\rho _{d_{2}/b_{2}}(\ldots \rho _{d_{m}/b_{m}}(S)\ldots ))$

Então toma-se o produto cartesiano e faz-se a seleção as tuplas que devem ser ligadas:

$P=\sigma _{b_{1}=d_{1},\ldots ,b_{m}=d_{m}}(R\times T)=\sigma _{b_{1}=d_{1}}(\sigma _{b_{2}=d_{2}}(\ldots \sigma _{b_{m}=d_{m}}(R\times T)\ldots ))$

Finalmente, pegue a projeção para se livrar dos atributos renomeados:

$U=\pi _{a_{1},\ldots ,a_{n},b_{1},\ldots ,b_{m},c_{1},\ldots ,c_{k}}(P)$

θ-junção e equijunção

Equacionaríamos como tabelas Carro e Barco os quais listam modelos de carros e barcos e seus respectivos preços. Por exemplo, suponha que um cliente quer comprar um carro e um barco, mas não quer gastar mais dinheiro para o barco do que para o carro. A θ-junção ($\bowtie$_θ) na relação PreçoCarro ≥ PreçoBarco produz uma tabela com todas as opções possíveis. Ao utilizar uma condição em que os atributos são iguais, por exemplo, preço, então a condição pode ser especificada como Preço=Preço ou alternativamente (preço) sozinho.

Carro CarroModelo PreçoCarro CarroA 20,000 CarroB 30,000 CarroC 50,000

Barco BarcoModelo PreçoBarco Barco1 10,000 Barco2 40,000 Barco3 60,000

${\begin{matrix}Carro\bowtie Barco\\\scriptstyle PrecoCarro\geq PrecoBarco\end{matrix}}$ CarroModelo PreçoCarro BarcoModelo PreçoBarco CarroA 20,000 Barco1 10,000 CarroB 30,000 Barco1 10,000 CarroC 50,000 Barco1 10,000 CarroC 50,000 Barco2 40,000

Se quisermos combinar tuplas de duas relações em que a condição combinação não é simplesmente a igualdade de atributos comuns, então é conveniente ter uma forma mais geral do operador de junção, que é o θ-junção (ou theta-junção). A θ-junção é um operador binário que é escrito como ${\begin{matrix}R\ \bowtie \ S\\a\ \theta \ b\end{matrix}}$ ou ${\begin{matrix}R\ \bowtie \ S\\a\ \theta \ v\end{matrix}}$, onde a e b são nomes de atributos, θ é uma relação binária no conjunto {<, ≤, =,>, ≥}, v é um valor constante, e R e S são relações. O resultado desta operação consiste em todas as combinações de tuplas em R e S que satisfazem a relação θ. O resultado do θ-junção é definida somente se os cabeçalhos de S e R são disjuntos, ou seja, não contêm um atributo comum.

A simulação da operação nas operações fundamentais é, por conseguinte, como se segue:

R $\bowtie$_θ S = σ_θ(R × S)

No caso de o operador θ é o operador de igualdade (=), então este essa junção também é chamado de equijunção.

Note-se, no entanto, que uma linguagem de computador que suporta os operadores naturais junção e renomear não precisa θ-junção, assim, como isso pode ser alcançado por meio da seleção a partir do resultado de uma junção natural (que degenera em produto cartesiano quando não há compartilhada de atributos).

Semijunção (⋉)(⋊)

A semijunção esquerdo está juntando semelhante à junção natural e escrito como R $\ltimes$ S onde R e S são relações. O resultado desta semijunção é o conjunto de todas as tuplas em R para o qual existe uma tupla em S que é igual em seus nomes de atributos comuns. Por exemplo, considere as tabelas Empregado e e seu Dept e suas semijunções:

Empregado Nome IdEmp NomeDept Harry 3415 Finanças Sally 2241 Vendas George 3401 Finanças Harriet 2202 Produção

Dept NomeDept Gerente Vendas Bob Vendas Thomas Produção Katie Produção Marco

Empregado ⋉ Dept Nome IdEmp NomeDept Sally 2241 Vendas Harriet 2202 Produção

Mais formalmente a semântica do semijunção é definido como segue:

R $\ltimes$ S = { t $\in$ R, s $\in$ S, Fun (t $\cup$ s) }

Onde Fun(r) é como na definição de junção natural.

A semijunção pode ser simulada usando a junção natural como segue. Se a₁, ..., a_n são nomes de atributo de R, segue

R $\ltimes$ S = $\pi$_a1,..,an(R $\bowtie$ S).

Uma vez que pode simular a junção natural com os operadores básicos segue-se que isso também vale para o semijunção.

Antijunção

A antijunção, escrito como R $\triangleright$ S onde R e S são relações, é similar à semijunção (junção natural), mas o resultado de uma antijunção é apenas aquelas tuplas em R para as quais NÃO existe uma tupla em S que possua os mesmos nomes de atributos.

Por exemplo, considerando as tabelas Empregado e Departamento e sua antijunção:

Empregado Nome IdEmp DeptNome Harry 3415 Finanças Sally 2241 Vendas George 3401 Finanças Harriet 2202 Produção

Departamento DeptNome Gerente Vendas Harriet Produção Charles

Empregado $\triangleright$ Departamento Nome IdEmp DeptNome Harry 3415 Finanças George 3401 Finanças

A antijunção é formalmente definida como segue:

R $\triangleright$ S = { t : t $\in$ R $\land$ $\neg \exists$s $\in$ S : fun (t $\cup$ s) }

ou

R $\triangleright$ S = { t : t $\in$ R, não existe uma tupla s de S que satisfaz fun (t $\cup$ s) }

onde fun(r) está definida como na junção natural.

A antijunção também pode ser definida como o complemento da semijunção, como segue:

R $\triangleright$ S = R - R $\ltimes$ S

Sendo assim, a antijunção às vezes é chamada de anti-semijunção, e o operador de antijunção às vezes é escrito como um símbolo da semijunção com uma barra acima, ao invés de $\triangleright$.

Divisão

A divisão é uma operação binária que é escrita como R ÷ S. O resultado consiste em restrições de tuplas em R até ao nome dos atributos únicos a R, i.e., no cabeçalho de R mas não no cabeçalho de S, onde é verificável que todas as suas combinações de tuplas S estão presentes em R. Por exemplo, considerando as tabelas Finalizado, ProjectoBD e sua divisão:

Finalizado Estudante Tarefa Fred Basedados1 Fred Basedados2 Fred Compiladores1 Pedro Basedados1 Pedro Compiladores1 Sara Basedados1 Sara Basedados2

ProjectoBD Tarefa Basedados1 Basedados2

Finalizado ÷ ProjectoBD Estudante Fred Sara

Se ProjectoBD contêm todas as tarefas do projecto Basedados, deduz-se que o resultado da divisão do exemplo contêm exactamente os estudantes que completaram ambas as tarefas no projecto Basedados.

Mais formalmente, as semânticas da divisão são definidas como:

R ÷ S = { t[a₁,...,a_n] : t $\in$ R $\wedge$ $\forall$s $\in$ S ( (t[a₁,...,a_n] $\cup$ s) $\in$ R) }

onde {a₁,...,a_n} é o conjunto de nomes de atributos únicos a R e t[a₁,...,a_n] é a restrição de t a este conjunto. É normalmente requerido que os nomes do atributo no cabeçalho de S são subsets do mesmo que R porque de outra maneira o resultado da operação vai ser vazio.

A simulação da divisão com operações básicas segue assim. Assumindo que a₁,...,a_n são os nomes do atributos únicos de R e b₁,...,b_m são os nomes do atributos únicos de S. No primeiro passo projectamos R no seu nome de atributo único e construímos todas as combinações de tuplas em S:

T := π_a1,...,an(R) × S

No anterior exemplo, T iria representar uma tabela no qual todos os Estudantes (porque Estudante é a chave / atributo única da tabela Finalizada) é combinada com todas as Tarefas dadas. Por isso Fred, por exemplo, tinha duas linhas, Fred -> Basedados1 e Fred -> Basedados2 em T.

Na próxima etapa nós subtraímos R da sua relação:

U := T − R

Nota que em U nós temos possíveis combinações que "poderia estar" em R, mas não estavam. Por isso se nós agora fizermos a projeção nos nome de atributos únicos a R agora temos as restrições das tuplas em R para o qual nem todas as combinações de tuplas em S estavam presentes em R:

V := π_a1,...,an(U)

Agora o que sobra fazer e tomar a projeção de R em seus nomes de atributos e subtrair o que estão em V:

W := π_a1,...,an(R) − V

Extensões comuns

Na prática, a álgebra relacional clássica descrita acima é estendido com várias operações, como junções externas, funções de agregação e até de encerramentos transitivos.

Junção de fora

Considerando que o resultado de um junção (ou Junção de dentro) consiste em combinar tuplas correspondentes nos dois operandos, uma junção de fora contém essas tuplas e mais algumas formadas pelo "enchimento" dos valores que não casam em um operador com cada atributo do outro operador. Note que os que as junçõos de fora não são considerados parte da álgebra clássica relacional, discutida até aqui.

Os operadores definidos nessa seção assumem que existe um valor null(ω), que não definem, para ser utilizado para os valores de "enchimento"; na prática, isso corresponde ao valor NULL em SQL. A fim de tornar as operações de seleção subsequentes na tabela resultante significativa, um significado semântico precisa ser atribuído ao nulos, na abordagem de Codd a lógica proposicional usada pela seleção é estendido a uma lógica de três valores, embora elidimos os detalhes neste artigo.

Três operadores junção de fora são definidos: junção de fora esquerda, junção de fora direita, e junção de fora cheia. (Algumas vezes a palavra de fora é omitida.)

Junção de fora esquerda (⟕)

A junção de fora esquerda é escrito como R =X S onde R e S são relações. O resultado do junção esquerda é o conjunto de todas as combinações das tuplas em R e S que seus atributos em comum são iguais , além disso, tuplas em R que não tem correspondência em S.

Por exemplo considere as tabelas Empregado e Departamento e seu esquerda outer junção:

Empregado Nome IdEmp DeptNome Harry 3415 Finanças Sally 2241 Vendas George 3401 Finanças Harriet 2202 Vendas Tim 1123 Executivo

Departamento DeptNome Gerente Vendas Harriet Produção Charles

Empregado =X Departamento Nome IdEmp DeptNome Gerente Harry 3415 Finanças ω Sally 2241 Vendas Harriet George 3401 Finanças ω Harriet 2202 Vendas Harriet Tim 1123 Executivo ω

Na relação resultante, tuplas em S que não tem valores com os mesmos nomes de atributos com tuplas em R recebem um valor null, ω.

Dado que não existem tuplas em Departamento com DeptNome igual a Finanças ou Executivo, ωs aparecem na relação resultante onde tuplas em DeptNome tem Finanças ou Executivo.

Sendo r₁, r₂, …, r_n atributos da relação R e {(ω, …, ω)} os únicos atributos que são únicos para a relação S (aqueles que não são atributos de R). Então o junção de fora esquerda pode ser escrito em termos do junção natural(utilizando operadores básicos) como segue:

$(R\bowtie S)\cup ((R-\pi _{r_{1},r_{2},\dots ,r_{n}}(R\bowtie S))\times \{(\omega ,\dots \omega )\})$

Junção de fora direita (⟖)

Se comporta da mesma maneira que o anterior, só que os papéis da tabela são comutados.

A junção de fora direita das relações R e S é escrito como R X= S. O resultado do junção direita é é o conjunto de todas as combinações das tuplas em R e S que seus atributos em comum são iguais, além disso, tuplas em S que não possuem correspondência com tuplas em R.

Por exemplo considere as tabelas Empregado e Departamento e a junção de fora direita:

Empregado Nome IdEmp DeptNome Harry 3415 Finanças Sally 2241 Vendas George 3401 Finanças Harriet 2202 Vendas Tim 1123 Executivo

Departamento DeptNome Gerente Vendas Harriet Produção Charles

Empregado X= Departamento Nome IdEmp DeptNome Gerente Sally 2241 Vendas Harriet Harriet 2202 Vendas Harriet ω ω Produção Charles

Na relação resultante, tuplas em R que não tem valores com os mesmos nomes de atributos com tuplas em S recebem um valor null, ω.

Dado que não existem tuplas em Empregado com DeptNome igual a Produção, ωs aparecem na relação resultante onde tuplas em DeptNome tem tuplas com Produção.

Sendo s₁, s₂, …, s_n atributos da relação S e {(ω, …, ω)} os únicos atributos que são únicos para a relação R (aqueles que não são atributos de S). Então, como no esquerda junção, o junção de fora direita pode ser escrito em termos da junção natural(utilizando operadores básicos) como segue:

$(R\bowtie S)\cup ((S-\pi _{s_{1},s_{2},\dots ,s_{n}}(R\bowtie S))\times \{(\omega ,\dots ,\omega )\})$

Junção de fora cheia

A junção de fora ou junção de fora cheia combina os efeitos dos resultados da esquerda e da junção de fora direita.

A junção de fora cheia é escrito como R =X= S onde R e S são relações. O resultado do junção de fora cheia é o conjunto de todas as combinações em R e S que são iguais em seus atributos com nomes iguais, além de tuplas em S que não possuem casamento com tuplas em R e tuplas em R que não possuem casamento com tuplas em S em seus atributos com nomes iguais.

Por exemplo, considere as tabelas Empregado e Departamento e a junção de fora:

Empregado Nome IdEmp DeptNome Harry 3415 Finanças Sally 2241 Vendas George 3401 Finanças Harriet 2202 Vendas Tim 1123 Executivo

Departamento DeptNome Gerente Vendas Harriet Produção Charles

Empregado =X= Departamento Nome IdEmp DeptName Gerente Harry 3415 Finanças ω Sally 2241 Vendas Harriet George 3401 Finanças ω Harriet 2202 Vendas Harriet Tim 1123 Executivo ω ω ω Produção Charles

Na relação resultante, tuplas em R que não têm valores em comum nos nomes dos atributos com as tuplas em S recebem um valor null", ω. Tuplas em S que não têm valores em comum nos nomes dos atributos com as tuplas em S também recebem um valor null", ω.

O junção de fora cheia pode ser simulado usando a esquerda e a junção de fora direita (e, consequentemente, a junção natural e união) como segue:

R=X=S = (R=XS) $\cup$ (RX=S)

Operações para o domínio computacional

Não há nada na álgebra relacional introduzido até agora, que permitiria cálculos sobre os domínios de dados (exceto avaliação de expressões proposicionais envolvendo igualidade). Por exemplo, não é possível usando apenas a álgebra introduzida até agora para escrever uma expressão que iria multiplicar os números de duas colunas, por exemplo, preço unitário com a quantidade para obter um preço total. Linguagens de consulta práticas têm tais instalações, por exemplo, o SQL SELECT permite operações aritméticas para definir novas colunas no resultado SELECT unit_price * quantidade AS total_price FROM t e uma facilidade semelhante é fornecida de forma mais explícita pelo Tutorial D EXTEND palavra-chave. Em teoria banco de dados, isto é chamadoprojecção alargada.Predefinição:Rp

Agregação

Além disso, a computação de várias funções numa coluna, como no somatório de seus elementos, também não é possível utilizar a álgebra relacional introduzida até o momento. Existem cinco operações de agregação que são incluídas na maioria dos bancos de dados. Esses operadores são Soma, Contagem, Média, Máximo e Mínimo. Na álgebra relacional a operação de agregação escreve-se ao longo de um esquema (A₁, A₂, ... A_n), é escrito como G₁, G₂, ..., G_m g _{f1(A1'), f2(A2'), ..., fk(Ak')} (r)

onde cada A_j', 1 ≤ j ≤ k, é um dos atributos originais A_i, 1 ≤ i ≤ n.

Os atributos que antecedem o g são os atributos de agrupamento, que funcionam como um "grupo de" cláusula SQL. Depois, há um número arbitrário de funções de agregação aplicados aos atributos individuais. A operação é aplicada a uma relação arbitrária r. Os atributos de agrupamento são opcionais, e se eles não são fornecidos, as funções de agregação são aplicadas em toda a relação com o qual a operação é aplicada.

Vamos assumir que temos uma tabela chamada Conta com três colunas, a saber Número_conta, Nome_ramo e Saldo. Queremos encontrar o máximo de saldo de cada ramo. Isto é realizado por _{Nome_ramo}G_{Max (Saldo)}(Conta). Para encontrar o maior saldo de todas as contas, independentemente do ramo, poderíamos simplesmente escrever G_{Max (Saldo)}(Conta).

Limitação da álgebra relacional

Embora a álgebra relacional pareça suficientemente poderosa para a maioria dos efeitos práticos, existem alguns operadores simples e naturais nas relações que não podem ser expressos pela álgebra relacional. O fecho transitivo de uma relação binária é um deles. Dado um domínio D, a relação binária R é um subconjunto de D×D. O encerramento transitivo R⁺ de R é o menor subconjunto de D×D contendo''R que satisfaz a seguinte condição:

$\forall x\forall y\forall z\left((x,y)\in R^{+}\wedge (y,z)\in R^{+}\Rightarrow (x,z)\in R^{+}\right)$

Isto pode provar que não existe uma expressão de álgebra relacional E(R), tendo R como argumento variável que produz R⁺. A prova é baseada no fato de que, dada uma expressão relacional E que se alega que E(R) = R⁺, onde R é uma variável, podemos sempre encontrar uma instância r ou R (e um domínio correspondente d), de modo que E(r) ≠ r⁺.

O SQL porém suporta oficialmente tais consultas hierárquicas e recursivas em SQL (consultas Fixpoint) desde 1999, e tinha extensões específicas do fornecedor neste sentido bem antes disso.

Uso das propriedades algébricas para optimização de consultas

Banco de dados relacional pode ser representado como uma árvore, onde

• Os nodos internos são operadores,
• Folhas são as relações,
• Sub árvores são sub-expressões;

Nosso principal objectivo é transformar a expressão de árvores em expressões equivalentes de árvores, onde a dimensão média das relações geradas por sub-expressões na árvore são menores do que eram antes da optimização. Nosso segundo objectivo é tentar formar sub-expressões comuns dentro de uma única consulta, ou se houver mais de uma consulta a ser avaliada, ao mesmo tempo, em todas essas consultas. A lógica subjacente é a de que o segundo objectivo é o suficiente para computar sub-expressões comuns uma vez, e os resultados podem ser utilizados em todas as consultas que contenham essa sub-expressão.

Aqui, apresentamos um conjunto de regras, que podem ser utilizados em tais transformações.

Seleção

Regras sobre operadores de seleção desempenham papel mais importante na optimização da busca. Seleção é um operador que de forma muito eficaz diminui o número de linhas no seu operando, por isso, se nós conseguirmos passar as seleções em uma árvore de expressão para as folhas, as relações internas (geradas por sub-expressões) provavelmente irão encolher.

Propriedades básicas de seleção

Seleção é uma operação idempotente (múltiplas aplicações da mesma seleção têm o mesmo efeito de uma única aplicação), e comutativa (a ordem em que as seleções são aplicadas não influencia o resultado).

1. $\sigma _{A}(R)=\sigma _{A}\sigma _{A}(R)\,\!$
2. $\sigma _{A}\sigma _{B}(R)=\sigma _{B}\sigma _{A}(R)\,\!$

Quebrando seleções com condições complexas

Uma seleção cuja condição é uma conjunção de condições mais simples é equivalente a uma sequência de seleções com as mesmas condições individuais, e a seleção cuja condição é uma disjunção é equivalente a uma união de seleções. Essas identidades podem ser usadas para mesclar seleções de modo que menos seleções precisem de ser avaliadas, ou para dividir-las de modo a que a componente seleções possa ser movida ou optimizada separadamente.

1. $\sigma _{A\land B}(R)=\sigma _{A}(\sigma _{B}(R))=\sigma _{B}(\sigma _{A}(R))$
2. $\sigma _{A\lor B}(R)=\sigma _{A}(R)\cup \sigma _{B}(R)$

Seleção e cruzamento de produto

O operador de cruzamento de produto é o de maior custo computacional para avaliar. Se a entrada da relação tem $N$ e $M$linhas, o resultado irá conter $NM$ linhas. Portanto isso é muito importante para ter um menor tamanho de ambos os operadores antes de ser aplicado o operador de cruzamento de produto.

Isso pode ser feito de forma eficaz, se o cruzamento de produto for seguido de um operador de seleção, ex. $\sigma _{A}$($R$ × $P$). Considerando a definição de seleção, isto é o caso mais provável. Se o cruzamento de produto não for seguido de um operador de seleção, podemos tentar descer até um nível mais baixo a partir de níveis mais altos da árvore de expressões usando outra regra de seleção.

No caso acima quebramos a condição $A$ introduzindo a condição $B$, $C$ e $D$ usando regras de divisão sobre complexas condições de seleção, de modo que $A$ = $B$ $\wedge$$C$ $\wedge$ $D$ e $B$ somente contém atributos de $R$, $C$contém atributos somente de $P$ e $D$ contém partes de $A$ que contém os atributos tanto de$R$ como de $P$. Observe que $B$, $C$ ou $D$ podem ser possivelmente vazios. Depois os seguintes detém:

$\sigma _{A}(R\times P)=\sigma _{B\wedge C\wedge D}(R\times P)=\sigma _{D}(\sigma _{B}(R)\times \sigma _{C}(P))$

Seleção e produto cartesiano

O produto cartesiano é o operador mais caro de avaliar. Se as relações de entrada têm N e M linhas, o resultado irá conter NM linhas. Por isso, é muito importante fazer o nosso melhor para diminuir o tamanho de ambos os operandos antes de aplicar o operador produto cartesiano.

Isto pode ser feito eficazmente, se o produto cartesiano é seguido por um operador de seleção, por exemplo, $\sigma _{A}(R\times P)$. Considerando a definição de junção, isto é o caso mais provável. Se o produto cartesiano não é seguido por um operador de seleção, podemos tentar empurrar para baixo uma seleção a partir de níveis mais altos da árvore de expressão usando a outra regra de seleção.

$\sigma _{A}(R\times P)=\sigma _{B\wedge C\wedge D}(R\times P)=\sigma _{D}(\sigma _{B}(R)\times \sigma _{C}(P))$

Seleção e operadores de conjuntos

Seleção é distributiva ao longo dos operadores setminus, intersecção e união. As três regras seguintes são utilizadas para definir as operações na árvore de expressão. Note, que nos operadores setminus e intersecção, é possível aplicar o operador seleção apenas em um dos operandos após a transformação. Isso pode fazer sentido nos casos em que um dos operandos é pequeno, e os custos gerais da avaliação do operador de seleção superam os benefícios de se utilizar uma menor relação como um operando.

1. $\sigma _{A}(R\setminus P)=\sigma _{A}(R)\setminus \sigma _{A}(P)=\sigma _{A}(R)\setminus P$
2. $\sigma _{A}(R\cup P)=\sigma _{A}(R)\cup \sigma _{A}(P)$
3. $\sigma _{A}(R\cap P)=\sigma _{A}(R)\cap \sigma _{A}(P)=\sigma _{A}(R)\cap P=R\cap \sigma _{A}(P)$

Seleção e projeção

Seleção é associativo com projeção se e somente se os campos referenciados na condição da seleção são um subconjunto dos campos na projeção. Fazer a seleção antes da projeção pode ser útil se o operando é um produto cartesiano ou junção. Em outros casos, se a condição da seleção é relativamente cara na computação, mover a seleção para fora da projeção pode reduzir o número de tuplas que devem ser testadas (desde que a projeção possa produzir menos tuplas devido à eliminação de duplicados, resultado da omissão de campos).

$\pi _{a_{1},...,a_{n}}(\sigma _{A}(R))=\sigma _{A}(\pi _{a_{1},...,a_{n}}(R))\;\;\;\mathrm {onde} \;\;\mathrm {campos\ em} \ A\subseteq \{a_{1},...,a_{n}\}$

Projeção

Propriedades básicas da projeção

Projeção é idempotente, de forma que uma série de projeções (válida) é equivalente a projeção mais de fora.

$\pi _{a_{1},...,a_{n}}(\pi _{b_{1},...,b_{m}}(R))=\pi _{a_{1},...,a_{n}}(R)\;\;\;\mathrm {onde} \;\;\{a_{1},...,a_{n}\}\subseteq \{b_{1},...,b_{m}\}$

Projeção e operadores de conjunto

Projeção é distributiva sobre a união de conjunto.

$\pi _{a_{1},\ldots ,a_{n}}(R\cup P)=\pi _{a_{1},\ldots ,a_{n}}(R)\cup \pi _{a_{1},\ldots ,a_{n}}(P).\,$

Projeção não distribui sobre intersecção e diferença de conjuntos. Contra-exemplos são dados por:

$\pi _{A}(\{\langle A=a,B=b\rangle \}\cap \{\langle A=a,B=b'\rangle \})=\emptyset$

$\pi _{A}(\{\langle A=a,B=b\rangle \})\cap \pi _{A}(\{\langle A=a,B=b'\rangle \})=\{\langle A=a\rangle \}$

e

$\pi _{A}(\{\langle A=a,B=b\rangle \}\setminus \{\langle A=a,B=b'\rangle \})=\{\langle A=a\}$

$\pi _{A}(\{\langle A=a,B=b\rangle \})\setminus \pi _{A}(\{\langle A=a,B=b'\rangle \})=\emptyset \,,$

onde b é assumido distinto de bPredefinição:'.

Renomear

Propriedades básicas de renomear

Renomear sucessivamente uma variável pode se desmanchar em um único renome. Operações de renomear que não possuem variáveis em comum podem ser arbitrariamente reordenadas, uma com relação a outra, e podem ser aproveitadas para fazer sucessivas nomeações adjacentes.

1. $\rho _{a/b}(\rho _{b/c}(R))=\rho _{a/c}(R)\,\!$
2. $\rho _{a/b}(\rho _{c/d}(R))=\rho _{c/d}(\rho _{a/b}(R))\,\!$

Renomear e operações de conjuntos

Renomear é distributivo sobre a diferença, união e intersecção.

1. $\rho _{a/b}(R\setminus P)=\rho _{a/b}(R)\setminus \rho _{a/b}(P)$
2. $\rho _{a/b}(R\cup P)=\rho _{a/b}(R)\cup \rho _{a/b}(P)$
3. $\rho _{a/b}(R\cap P)=\rho _{a/b}(R)\cap \rho _{a/b}(P)$

Implementações

A primeira linguagem de consulta que foi baseada na da álgebra Codd foi ISBL, e este trabalho pioneiro tem sido aclamado por várias autoridades como tendo mostrado o caminho para tornar a ideia de Codd em uma linguagem útil. Business System 12 foi uma indústria de vida curta que usava a força do SGBD relacional que o exemplo seguiu do ISBL.

Em 1998, Chris Data e Hugh Darwen propôs uma linguagem chamada Tutorial D destinado a ser utilizada no ensino de teoria de banco de dados relacional, e sua linguagem de consulta também usa as ideias do ISBL. Rel é uma implementação do Tutorial D.

Mesmo a linguagem de consulta SQL é vagamente baseada em uma álgebra relacional, embora os operandos em SQL (tabelas) não são exatamente a relação e diversos teoremas úteis sobre a álgebra relacional não detêm homólogo no SQL (provavelmente em detrimento de otimizadores e ou usuários). O modelo da tabela SQL é um saco (multiconjunto), ao invés de um conjunto. Por exemplo, a expressão (R ∪ S) - T = (R - T) ∪ (S - T) é um teorema de álgebra relacional em conjuntos, mas não para álgebra relacional em sacos, para um tratamento de álgebra relacional em sacos ver capítulo 5 do livro "Complete" por Garcia-Molina, Ullman e Jennifer Widom.

Ver também

• Produto cartesiano
• Banco de dados
• Projeção (matemática)
• Projeção (álgebra relacional)
• Relação
• Banco de dados relacional
• Modelo relacional

Bibliografia

• Practicamente qualquer livro académico sobre banco de dados tem um tratamento clássico da álgebra relacional.
• Imieliński, Tomasz; Witold (1 de janeiro de 1984). «The relational model of data and cylindric algebras». Journal of Computer and System Sciences. 28 (1). doi:10.1016/0022-0000(84)90077-1   (Para relações com álgebras cilíndricas).

Ligações externas

• Software Rational Algebra Translator to SQL. en.
• ELMASRI, Ramez; NAVATHE, Shamkant B. Sistemas de Banco de Dados. (PDF) São Paulo: Addison Wesley, 2005. pt.
• Notas de Aulas: Álgebra Relacional - Um tutorial rápido para adaptar consultas SQL em álgebra relacional. en.
• Query Optimization Este artigo é uma introdução sobre o uso da álgebra relacional na otimização de consultas e inclui numerosas citações para um estudo mais aprofundado. en.
• Relational Algebra System for Oracle and Microsoft SQL Server. en.
• LEAP – An implementation of the relational algebra]. en.