Álgebra Relacional - Relational algebra

Na teoria de banco de dados , álgebra relacional é uma teoria que usa estruturas algébricas com uma semântica bem fundamentada para modelar dados e definir consultas sobre eles. A teoria foi introduzida por Edgar F. Codd .

A principal aplicação da álgebra relacional é fornecer uma base teórica para bancos de dados relacionais , particularmente linguagens de consulta para tais bancos de dados, o principal entre os quais é o SQL . Os bancos de dados relacionais armazenam dados tabulares representados como relações . As consultas em bancos de dados relacionais frequentemente retornam dados tabulares representados como relações . A premissa principal da álgebra relacional é definir operadores que transformam uma ou mais relações de entrada em uma relação de saída. Dado que esses operadores aceitam relações como entrada e produzem relações como saída, eles podem ser combinados e usados ​​para expressar consultas potencialmente complexas que transformam potencialmente muitas relações de entrada (cujos dados são armazenados no banco de dados) em uma única relação de saída (os resultados da consulta) . Os operadores unários aceitam como entrada uma única relação; exemplos incluem operadores para filtrar certos atributos (colunas) ou tuplas (linhas) de uma relação de entrada. Os operadores binários aceitam como entrada duas relações; tais operadores combinam as duas relações de entrada em uma única relação de saída, por exemplo, tomando todas as tuplas encontradas em qualquer relação, removendo as tuplas da primeira relação encontrada na segunda relação, estendendo as tuplas da primeira relação com as tuplas na segunda relação corresponder a certas condições e assim por diante. Outros operadores mais avançados também podem ser incluídos, onde a inclusão ou exclusão de certos operadores dá origem a uma família de álgebras.

Introdução

Álgebra relacional recebeu pouco fora atenção de matemática pura até a publicação da EF Codd 's modelo relacional de dados em 1970. Codd propôs tal álgebra como base para linguagens de consulta de banco de dados. (Consulte a seção Implementações .)

Os cinco operadores primitivos da álgebra de Codd são a seleção , a projeção , o produto cartesiano (também chamado de produto cruzado ou junção cruzada ), a união do conjunto e a diferença do conjunto .

Operadores de conjunto

A álgebra relacional usa união de conjuntos , diferença de conjuntos e produto cartesiano da teoria de conjuntos , mas adiciona restrições adicionais a esses operadores.

Para união e diferença de conjuntos, as duas relações envolvidas devem ser compatíveis com a união - ou seja, as duas relações devem ter o mesmo conjunto de atributos. Como a interseção de conjuntos é definida em termos de união e diferença de conjuntos, as duas relações envolvidas na interseção de conjuntos também devem ser compatíveis com a união.

Para que o produto cartesiano seja definido, as duas relações envolvidas devem ter cabeçalhos disjuntos - ou seja, não devem ter um nome de atributo comum.

Além disso, o produto cartesiano é definido de forma diferente da teoria dos conjuntos , no sentido de que as tuplas são consideradas "rasas" para os fins da operação. Ou seja, o produto cartesiano de um conjunto de n -tuplas com um conjunto de m -tuplas produz um conjunto de ( n  +  m ) -tuplas "achatadas" (enquanto a teoria dos conjuntos básica teria prescrito um conjunto de 2-tuplas, cada contendo uma n- dupla e uma m- dupla). Mais formalmente, R × S é definido da seguinte forma:

${\ displaystyle R \ times S: = \ {(r_ {1}, r_ {2}, \ dots, r_ {n}, s_ {1}, s_ {2}, \ dots, s_ {m}) | ( r_ {1}, r_ {2}, \ dots, r_ {n}) \ in R, (s_ {1}, s_ {2}, \ dots, s_ {m}) \ in S \}}$

A cardinalidade do produto cartesiano é o produto das cardinalidades de seus fatores, isto é, | R × S | = | R | × | S |.

Projeção ( Π )

Uma projeção é uma operação unária escrita como onde está um conjunto de nomes de atributos. O resultado dessa projeção é definido como o conjunto que é obtido quando todas as tuplas em R estão restritas ao conjunto . ${\ displaystyle \ Pi _ {a_ {1}, \ ldots, a_ {n}} (R)}$${\ displaystyle a_ {1}, \ ldots, a_ {n}}$${\ displaystyle \ {a_ {1}, \ ldots, a_ {n} \}}$

Nota: quando implementado no padrão SQL , a "projeção padrão" retorna um multiset em vez de um conjunto, e a projeção Π para eliminar dados duplicados é obtida pela adição da DISTINCTpalavra - chave .

Seleção ( σ )

Uma seleção generalizada é uma operação unária escrita como onde φ é uma fórmula proposicional que consiste em átomos conforme permitido na seleção normal e os operadores lógicos ( e ), ( ou ) e ( negação ). Esta seleção seleciona todas aquelas tuplas em R para as quais φ é válido. ${\ displaystyle \ sigma _ {\ varphi} (R)}$${\ displaystyle \ wedge}$${\ displaystyle \ lor}$${\ displaystyle \ neg}$

Para obter uma lista de todos os amigos ou sócios comerciais em um catálogo de endereços, a seleção pode ser escrita como . O resultado seria uma relação contendo todos os atributos de cada registro exclusivo onde isFriend é verdadeiro ou onde isBusinessContact é verdadeiro. ${\ displaystyle \ sigma _ {{\ text {isFriend = true}} \, \ lor \, {\ text {isBusinessContact = true}}} ({\ text {addressBook}})}$

Renomear ( ρ )

Uma renomeação é uma operação unária escrita onde o resultado é idêntico a R, exceto que o atributo b em todas as tuplas é renomeado para um atributo a. Isso é usado simplesmente para renomear o atributo de uma relação ou a própria relação. ${\ displaystyle \ rho _ {a / b} (R)}$

Para renomear o atributo 'isFriend' para 'isBusinessContact' em uma relação, pode ser usado. ${\ displaystyle \ rho _ {\ text {isBusinessContact / isFriend}} ({\ text {addressBook}})}$

Há também a notação, onde R é renomeado para x e os atributos são renomeados para . ${\ displaystyle \ rho _ {x (A_ {1}, \ ldots, A_ {n})} (R)}$${\ displaystyle \ {a_ {1}, \ ldots, a_ {n} \}}$${\ displaystyle \ {A_ {1}, \ ldots, A_ {n} \}}$

Operadores de junções e semelhantes

Junção natural (⋈ )

A junção natural (⋈) é um operador binário que é escrito como ( R ⋈ S ) onde R e S são relações . O resultado da junção natural é o conjunto de todas as combinações de tuplas em R e S que são iguais em seus nomes de atributos comuns. Por exemplo, considere as tabelas Employee e Dept e sua junção natural:

Observe que nem a funcionária chamada Mary nem o departamento de Recursos Humanos aparecem no resultado.

Isso também pode ser usado para definir a composição das relações . Por exemplo, a composição de Employee e Dept é sua junção conforme mostrado acima, projetada em todos, exceto no atributo comum DeptName . Na teoria da categoria , a junção é precisamente o produto de fibra .

A junção natural é indiscutivelmente um dos operadores mais importantes, pois é a contraparte relacional do operador lógico AND. Observe que se a mesma variável aparece em cada um dos dois predicados que estão conectados por AND, então essa variável representa a mesma coisa e ambas as aparências devem ser sempre substituídas pelo mesmo valor (isso é uma consequência da idempotência do AND lógico) . Em particular, a junção natural permite a combinação de relações associadas por uma chave estrangeira . Por exemplo, no exemplo acima, uma chave estrangeira provavelmente detém de Employee . NOMEDEPTO para Dept . DeptName e a junção natural de Employee e Dept combinam todos os funcionários com seus departamentos. Isso funciona porque a chave estrangeira é mantida entre atributos com o mesmo nome. Se este não é o caso, como na chave estrangeira de Dept . Gerente para empregado . Nomeie então essas colunas devem ser renomeadas antes de fazer a junção natural. Essa junção às vezes também é chamada de equijoin (consulte θ -join).

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

${\ displaystyle R \ bowtie S = \ left \ {r \ cup s \ \ vert \ r \ in R \ \ land \ s \ in S \ \ land \ {\ mathit {Fun}} (r \ cup s) \ direito\}}$

( 1 )

onde Fun (t) é um predicado verdadeiro para uma relação t (no sentido matemático) se f t for uma função. Normalmente é necessário que R e S tenham pelo menos um atributo comum, mas se essa restrição for omitida e R e S não tiverem atributos comuns, então a junção natural torna-se exatamente o produto cartesiano.

A junção natural pode ser simulada com as primitivas de Codd da seguinte maneira. Suponha que c ₁ , ..., c _m são os nomes de atributos comuns a R e S , r ₁ , ..., r _n são os nomes de atributos exclusivos de R e s ₁ , ..., s _k são os atributos nomes exclusivos para S . Além disso, suponha que os nomes de atributo x ₁ , ..., x _m não são nem em R nem em S . Em uma primeira etapa, os nomes de atributos comuns em S podem ser renomeados:

${\ displaystyle T = \ rho _ {x_ {1} / c_ {1}, \ ldots, x_ {m} / c_ {m}} (S) = \ rho _ {x_ {1} / c_ {1}} (\ rho _ {x_ {2} / c_ {2}} (\ ldots \ rho _ {x_ {m} / c_ {m}} (S) \ ldots))}$

( 2 )

Em seguida, pegamos o produto cartesiano e selecionamos as tuplas que devem ser unidas:

${\ displaystyle P = \ sigma _ {c_ {1} = x_ {1}, \ ldots, c_ {m} = x_ {m}} (R \ times T) = \ sigma _ {c_ {1} = x_ { 1}} (\ sigma _ {c_ {2} = x_ {2}} (\ ldots \ sigma _ {c_ {m} = x_ {m}} (R \ vezes T) \ ldots))}$

( 3 )

Por fim, fazemos uma projeção para nos livrar dos atributos renomeados:

${\ displaystyle U = \ Pi _ {r_ {1}, \ ldots, r_ {n}, c_ {1}, \ ldots, c_ {m}, s_ {1}, \ ldots, s_ {k}} (P )}$

( 4 )

θ -join e equijoin

Considere as tabelas Carro e Barco que listam os modelos de carros e barcos e seus respectivos preços. Suponha que um cliente queira comprar um carro e um barco, mas não quer gastar mais dinheiro com o barco do que com o carro. O θ -join (⋈ _θ ) no predicado CarPrice ≥ BoatPrice produz os pares achatados de linhas que satisfazem o predicado. Ao usar uma condição em que os atributos são iguais, por exemplo Preço, a condição pode ser especificada como Preço = Preço ou, alternativamente, ( Preço ) em si.

Para combinar tuplas de duas relações onde a condição de combinação não é simplesmente a igualdade de atributos compartilhados, é conveniente ter uma forma mais geral de operador de junção, que é a junção θ (ou junção teta). O θ -join é um operador binário que é escrito como ou onde a e b são nomes de atributos, θ é um operador relacional binário no conjunto {<, ≤, =, ≠,>, ≥} , υ é uma constante de valor, e R e S são relações. O resultado dessa operação consiste em todas as combinações de tuplas em R e S que satisfazem θ . O resultado de θ -join é definido apenas se os cabeçalhos de S e R são disjuntos, ou seja, não contêm um atributo comum. ${\ displaystyle {R \ \ bowtie \ S \ no topo de um \ \ theta \ b}}$${\ displaystyle {R \ \ bowtie \ S \ sobre um \ \ theta \ v}}$

A simulação desta operação nas operações fundamentais é, portanto, a seguinte:

R ⋈ _θ S = σ _θ ( R × S )

No caso de o operador θ ser o operador de igualdade (=), essa junção também é chamada de equijoin .

Observe, no entanto, que uma linguagem de computador que suporta os operadores de junção e seleção natural não precisa de junção- θ também, pois isso pode ser alcançado pela seleção do resultado de uma junção natural (que degenera em produto cartesiano quando não há junção atributos).

Em implementações SQL, a junção em um predicado é geralmente chamada de junção interna , e a palavra - chave on permite especificar o predicado usado para filtrar as linhas. É importante observar: formar o produto cartesiano achatado e, em seguida, filtrar as linhas é conceitualmente correto, mas uma implementação usaria estruturas de dados mais sofisticadas para acelerar a consulta de junção.

Semijoin (⋉) (⋊)

A semi-junção esquerda é uma junção semelhante à junção natural e escrita como R ⋉ S onde R e S são relações . O resultado é o conjunto de todas as tuplas em R para as quais existe uma tupla em S que é igual em seus nomes de atributos comuns. A diferença de uma junção natural é que outras colunas de S não aparecem. Por exemplo, considere as tabelas Employee e Dept e sua semi-junção:

Mais formalmente, a semântica da semijoin pode ser definida da seguinte forma:

R ⋉ S = { t  : t ∈ R ∧ ∃ s ∈ S ( Diversão ( t ∪ s ))}

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

A semi-junção pode ser simulada usando a junção natural da seguinte maneira. Se a ₁ , ..., a _n são os nomes dos atributos de R , então

R ⋉ S = _{a 1 , .., a n} ( R ⋈ S ).${\ displaystyle \ Pi}$

Como podemos simular a junção natural com os operadores básicos, segue-se que isso também é válido para a semijoin.

No artigo de Codd de 1970, o semijoin é chamado de restrição.

Antijoin (▷)

A antijunção, escrita como R ▷ S onde R e S são relações , é semelhante à semijunção, mas o resultado de uma antijunção são apenas aquelas tuplas em R para as quais não há nenhuma tupla em S igual em seus nomes de atributos comuns.

Por exemplo, considere as tabelas Employee e Dept e seu antijoin:

O antijoin é formalmente definido da seguinte forma:

R ▷ S = { t  : t ∈ R ∧ ¬∃ s ∈ S ( Diversão ( t ∪ s ))}

ou

R ▷ S = { t  : t ∈ R , não há tupla s de S que satisfaça Fun ( t ∪ s )}

onde Fun ( t ∪ s ) é como na definição de junção natural.

A antijoin também pode ser definida como o complemento da semi-junta, da seguinte forma:

R ▷ S = R  -  R ⋉ S

( 5 )

Diante disso, o antijoin às vezes é chamado de anti-semijoin, e o operador de antijoin às vezes é escrito como o símbolo de semijoin com uma barra acima dele, em vez de ▷.

Divisão (÷)

A divisão é uma operação binária que é escrito como R ÷ S . A divisão não é implementada diretamente no SQL. O resultado consiste nas restrições de tuplas em R para os nomes de atributos únicos para R , isto é, no cabeçalho de R mas não no cabeçalho do S , para o qual sustenta que todas as suas combinações com tuplas em S estão presentes em R . Veja um exemplo nas tabelas Completed , DBProject e sua divisão:

Se DBProject contém todas as tarefas do projeto de banco de dados, então o resultado da divisão acima contém exatamente os alunos que completaram ambas as tarefas no projeto de banco de dados. Mais formalmente, a semântica da divisão é definida da seguinte forma:

R ÷ S = { t [ a 1 , ..., a n ]: t ∈ R ∧ ∀ s ∈ S (( t [ a 1 , ..., a n ] ∪ s ) ∈ R )}

( 6 )

onde { a ₁ , ..., a _n } é o conjunto de nomes de atributos únicos para R e t [ a ₁ , ..., a _n ] é a restrição de t a este conjunto. Normalmente, é necessário que os nomes dos atributos no cabeçalho de S sejam um subconjunto dos de R, pois, caso contrário, o resultado da operação sempre estará vazio.

A simulação da divisão com as operações básicas é a seguinte. Assumimos que a ₁ , ..., a _n são os nomes de atributos únicos para R e b ₁ , ..., b _m são os nomes de atributos de S . Na primeira etapa, projetamos R em seus nomes de atributos exclusivos e construímos todas as combinações com tuplas em S :

T  : = π _{a 1 , ..., a n} ( R ) × S

No exemplo anterior, T representaria uma tabela tal que cada Aluno (porque Aluno é a chave / atributo exclusivo da tabela Concluída) é combinado com cada Tarefa dada. Portanto, Eugene, por exemplo, teria duas linhas, Eugene → Database1 e Eugene → Database2 em T.

EG: Primeiro, vamos fingir que "Concluído" tem um terceiro atributo chamado "nota". É uma bagagem indesejada aqui, por isso devemos projetá-la sempre. Na verdade, nesta etapa, podemos retirar 'Tarefa' de R também; a multiplicação o coloca de volta.

T  : = π _Student ( R ) × S // Isso nos dá todas as combinações desejadas possíveis, incluindo aquelas que realmente não existem em R e excluindo outras (por exemplo, Fred | compilador1, que não é uma combinação desejada)

Na próxima etapa, subtraímos R de T

relação :

U  : = T - R

Em U , temos as combinações possíveis que "poderiam" estar em R , mas não estavam.

EG: Novamente com as projeções - T e R precisam ter nomes / cabeçalhos de atributo idênticos.

U  : = T - π _{Student, Task} ( R ) // Isso nos dá uma lista de "o que está faltando".

Portanto, se agora fizermos a projeção nos nomes de atributos exclusivos de R

então temos as restrições das tuplas em R para as quais nem todas as combinações com tuplas em S estavam presentes em R :

V  : = π _{a 1 , ..., a n} ( U )

EX: Projeto U reduzido apenas para o (s) atributo (s) em questão (Aluno)

V  : = π _Student ( U )

Então, o que resta a ser feito é pegar a projeção de R em seus nomes de atributos exclusivos e subtrair aqueles em V :

W  : = π _{a 1 , ..., a n} ( R ) - V

EG: W  : = π _Student ( R ) - V .

Extensões comuns

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

Junções externas

Enquanto o resultado de uma junção (ou junção interna) consiste em tuplas formadas pela combinação de tuplas correspondentes nos dois operandos, uma junção externa contém essas tuplas e, adicionalmente, algumas tuplas formadas estendendo uma tupla sem correspondência em um dos operandos por valores de "preenchimento" para cada um dos atributos do outro operando. Junções externas não são consideradas parte da álgebra relacional clássica discutida até agora.

Os operadores definidos nesta seção assumem a existência de um valor nulo , ω , que não definimos, a ser usado para os valores de preenchimento; na prática, isso corresponde ao NULL no SQL. Para tornar significativas as operações de seleção subsequentes na tabela resultante, um significado semântico precisa ser atribuído a nulos; na abordagem de Codd, a lógica proposicional usada pela seleção é estendida a uma lógica de três valores , embora omitamos esses detalhes neste artigo.

Três operadores de junção externa são definidos: junção externa esquerda, junção externa direita e junção externa completa. (A palavra "externo" às vezes é omitida.)

União externa esquerda (⟕)

A junção externa esquerda é escrita como R ⟕ S onde R e S são relações . O resultado da junção externa esquerda é o conjunto de todas as combinações de tuplas em R e S que são iguais em seus nomes de atributos comuns, além (vagamente falando) para tuplas em R que não têm tuplas correspondentes em S .

Por exemplo, considere as tabelas Employee e Dept e sua junção externa esquerda:

Na relação resultante, tuplas em S que não têm valores comuns em nomes de atributos comuns com tuplas em R assumem um valor nulo , ω .

Como não há tuplas em Dept com um DeptName of Finance ou Executive , ω s ocorrem na relação resultante em que as tuplas em Employee têm um DeptName of Finance ou Executive .

Sejam r ₁ , r ₂ , ..., r _n os atributos da relação R e seja {( ω , ..., ω )} a relação singleton sobre os atributos únicos da relação S (aqueles que não são atributos de R ). Em seguida, a junção externa esquerda pode ser descrita em termos de junção natural (e, portanto, usando operadores básicos) da seguinte maneira:

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

Junção externa direita (⟖)

A junção externa direita se comporta quase de forma idêntica à junção externa esquerda, mas as funções das tabelas são trocadas.

A junção externa direita de relações R e S é escrito como R ⟖ S . O resultado da junção externa direita é o conjunto de todas as combinações de tuplas em R e S que são iguais em seus nomes de atributos comuns, além de tuplas em S que não têm tuplas correspondentes em R .

Por exemplo, considere as tabelas Employee e Dept e sua junção externa direita:

Na relação resultante, tuplas em R que não têm valores comuns em nomes de atributos comuns com tuplas em S assumem um valor nulo , ω .

Como não há tuplas em Employee com um DeptName of Production , ω s ocorrem nos atributos Name e EmpId da relação resultante onde as tuplas em Dept tinham DeptName of Production .

Sejam s ₁ , s ₂ , ..., s _n os atributos da relação S e seja {( ω , ..., ω )} a relação singleton sobre os atributos únicos da relação R (aqueles que não são atributos de S ). Então, como com a junção externa esquerda, a junção externa direita pode ser simulada usando a junção natural da seguinte maneira:

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

Junção externa completa (⟗)

A junção externa ou junção externa completa em vigor combina os resultados das junções externas esquerda e direita.

A junção externa completa é escrita como R ⟗ S, onde R e S são relações . O resultado da junção externa completa é o conjunto de todas as combinações de tuplas em R e S que são iguais em seus nomes de atributos comuns, além de tuplas em S que não têm tuplas correspondentes em R e tuplas em R que não têm tuplas correspondentes em S em seus nomes de atributos comuns.

Por exemplo, considere as tabelas Employee e Dept e sua junção externa completa:

Na relação resultante, tuplas em R que não têm valores comuns em nomes de atributos comuns com tuplas em S assumem um valor nulo , ω . As tuplas em S que não têm valores comuns em nomes de atributos comuns com tuplas em R também assumem um valor nulo , ω .

A junção externa completa pode ser simulada usando as junções externas esquerda e direita (e, portanto, a junção natural e a união definida) da seguinte maneira:

R ⟗ S = ( R ⟕ S ) ∪ ( R ⟖ S )

Operações para cálculos de domínio

Não há nada na álgebra relacional introduzida até agora que permitiria cálculos nos domínios de dados (além da avaliação de expressões proposicionais envolvendo igualdade). Por exemplo, não é possível usar apenas a álgebra introduzida até agora para escrever uma expressão que multiplicaria os números de duas colunas, por exemplo, um preço unitário com uma quantidade para obter um preço total. Linguagens de consulta práticos têm tais instalações, por exemplo, o SQL SELECT permite operações aritméticas para definir novas colunas no resultado e uma academia semelhante é fornecido de forma mais explícita por Tutorial D 's palavra-chave. Na teoria do banco de dados, isso é chamado de projeção estendida . SELECT unit_price * quantity AS total_price FROM tEXTEND

Agregação

Além disso, calcular várias funções em uma coluna, como a soma de seus elementos, também não é possível usando a álgebra relacional apresentada até agora. Existem cinco funções agregadas incluídas na maioria dos sistemas de banco de dados relacionais. Essas operações são Soma, Contagem, Média, Máximo e Mínimo. Na álgebra relacional, a operação de agregação sobre um esquema ( A ₁ , A ₂ , ... A _n ) é escrita da seguinte forma:

${\ displaystyle G_ {1}, G_ {2}, \ ldots, G_ {m} \ g_ {f_ {1} ({A_ {1}} '), f_ {2} ({A_ {2}}') , \ ldots, f_ {k} ({A_ {k}} ')} \ (r)}$

onde cada A _j ', 1 ≤ j ≤ k , é um dos atributos originais A _i , 1 ≤ i ≤ n .

Os atributos que precedem g são atributos de agrupamento, que funcionam como uma cláusula "group by" no SQL. Então, há um número arbitrário de funções de agregação aplicadas a atributos individuais. A operação é aplicada a uma relação arbitrária r . Os atributos de agrupamento são opcionais e, se não forem fornecidos, as funções de agregação serão aplicadas em toda a relação à qual a operação é aplicada.

Vamos supor que temos uma tabela chamada Conta com três colunas, a saber , Account_Number, Branch_Name e Balance . Queremos encontrar o equilíbrio máximo de cada ramo. Isso é realizado por _{Branch_Name} G _{Max ( Balance )} ( Account ). Para encontrar o maior saldo de todas as contas, independentemente do ramo, poderíamos simplesmente escrever G _{Max ( Saldo )} ( Conta ).

O agrupamento geralmente é escrito como _{Branch_Name} ɣ _{Max ( Balance )} ( Account ).

Fechamento transitivo

Embora a álgebra relacional pareça poderosa o suficiente para a maioria dos propósitos práticos, existem alguns operadores simples e naturais nas relações que não podem ser expressos pela álgebra relacional. Um deles é o fechamento transitivo de uma relação binária. Dado um domínio D , deixar binário relação R ser um subconjunto de D × D . O fechamento transitivo R ⁺ de R é o menor subconjunto de D × D que contém R e satisfaz a seguinte condição:

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

Não há expressão de álgebra relacional E ( R ) tomando R como um argumento variável que produz R ⁺ . Isso pode ser provado usando o fato de que, dada uma expressão relacional E para a qual é afirmado que E ( R ) = R ⁺ , onde R é uma variável, podemos sempre encontrar uma instância r de R (e um domínio correspondente d ) de modo que E ( r ) ≠ r ⁺ .

No entanto, o SQL oficialmente suporta tais consultas de fixpoint desde 1999, e tinha extensões específicas do fornecedor nessa direção muito antes disso.

Uso de propriedades algébricas para otimização de consulta

As consultas podem ser representadas como uma árvore , onde

• os nós internos são operadores,
• folhas são relações ,
• subárvores são subexpressões.

O objectivo primário é o de transformar em árvores de expressão equivalentes árvores de expressão , onde o tamanho médio das relações gerados pelo subexpress~oes na árvore é menor do que era antes da optimização . O objetivo secundário é tentar formar subexpressões comuns dentro de uma única consulta, ou se houver mais de uma consulta sendo avaliada ao mesmo tempo, em todas essas consultas. A lógica por trás do segundo objetivo é que é suficiente calcular subexpressões comuns uma vez, e os resultados podem ser usados ​​em todas as consultas que contêm essa subexpressão.

Aqui está um conjunto de regras que podem ser usadas em tais transformações.

Seleção

As regras sobre os operadores de seleção desempenham a função mais importante na otimização da consulta. A seleção é um operador que diminui muito efetivamente o número de linhas em seu operando, portanto, se as seleções em uma árvore de expressão forem movidas em direção às folhas, as relações internas (produzidas por subexpressões) provavelmente diminuirão.

Propriedades básicas de seleção

A seleção é idempotente (múltiplas aplicações da mesma seleção não têm efeito adicional além da primeira) e comutativa (as seleções de ordem aplicadas não têm efeito no resultado eventual).

1. ${\ displaystyle \ sigma _ {A} (R) = \ sigma _ {A} \ sigma _ {A} (R) \, \!}$
2. ${\ displaystyle \ 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 essas 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 ser avaliadas ou para dividi-las de forma que as seleções de componentes possam ser movidas ou otimizadas separadamente.

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

Seleção e produto cruzado

O produto cruzado é o operador mais caro de avaliar. Se as relações de entrada tiverem N e M linhas, o resultado conterá linhas. Portanto, é importante diminuir o tamanho de ambos os operandos antes de aplicar o operador de produto cruzado. ${\ displaystyle NM}$

Isso pode ser feito de forma eficaz se o produto vetorial for seguido por um operador de seleção, por exemplo . Considerando a definição de junção, esse é o caso mais provável. Se o produto vetorial não for seguido por um operador de seleção, podemos tentar empurrar para baixo uma seleção de níveis superiores da árvore de expressão usando as outras regras de seleção. ${\ displaystyle \ sigma _ {A} (R \ vezes P)}$

No caso acima, a condição A é dividida nas condições B , C e D usando as regras de divisão sobre condições de seleção complexas, de modo que e B contém atributos apenas de R , C contém atributos apenas de P e D contém a parte de Um que contém atributos de ambos R e P . Observe que B , C ou D estão possivelmente vazios. Então o seguinte é válido: ${\ displaystyle A = B \ wedge C \ wedge D}$

${\ displaystyle \ 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 conjunto de operadores

A seleção é distributiva sobre os operadores de diferença, interseção e união do conjunto. As três regras a seguir são usadas para empurrar a seleção abaixo das operações definidas na árvore de expressão. Para os operadores de diferença de conjunto e de interseção, é possível aplicar o operador de seleção a apenas um dos operandos após a transformação. Isso pode ser benéfico onde um dos operandos é pequeno e a sobrecarga de avaliar o operador de seleção supera os benefícios de usar uma relação menor como um operando.

1. ${\ displaystyle \ sigma _ {A} (R \ setminus P) = \ sigma _ {A} (R) \ setminus \ sigma _ {A} (P) = \ sigma _ {A} (R) \ setminus P}$
2. ${\ displaystyle \ sigma _ {A} (R \ xícara P) = \ sigma _ {A} (R) \ xícara \ sigma _ {A} (P)}$
3. ${\ displaystyle \ 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

A seleção comuta com a projeção se e somente se os campos referenciados na condição de seleção forem um subconjunto dos campos na projeção. Executar a seleção antes da projeção pode ser útil se o operando for um produto cruzado ou uma junção. Em outros casos, se a condição de seleção for relativamente cara para calcular, mover a seleção fora da projeção pode reduzir o número de tuplas que devem ser testadas (uma vez que a projeção pode produzir menos tuplas devido à eliminação de duplicatas resultantes de campos omitidos).

${\ displaystyle \ pi _ {a_ {1}, \ ldots, a_ {n}} (\ sigma _ {A} (R)) = \ sigma _ {A} (\ pi _ {a_ {1}, \ ldots , a_ {n}} (R)) {\ text {onde campos em}} A \ subseteq \ {a_ {1}, \ ldots, a_ {n} \}}$

Projeção

Propriedades básicas de projeção

A projeção é idempotente, de modo que uma série de projeções (válidas) é equivalente à projeção mais externa.

${\ displaystyle \ pi _ {a_ {1}, \ ldots, a_ {n}} (\ pi _ {b_ {1}, \ ldots, b_ {m}} (R)) = \ pi _ {a_ {1 }, \ ldots, a_ {n}} (R) {\ text {onde}} \ {a_ {1}, \ ldots, a_ {n} \} \ subseteq \ {b_ {1}, \ ldots, b_ { m} \}}$

Operadores de projeção e conjunto

A projeção é distributiva sobre a união do conjunto.

${\ displaystyle \ pi _ {a_ {1}, \ ldots, a_ {n}} (R \ xícara P) = \ pi _ {a_ {1}, \ ldots, a_ {n}} (R) \ xícara \ pi _ {a_ {1}, \ ldots, a_ {n}} (P). \,}$

A projeção não se distribui pela interseção e diferença definida. Contra-exemplos são dados por:

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

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

e

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

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

onde b é considerado distinto de b ' .

Renomear

Propriedades básicas de renomeação

Sucessivas renomeações de uma variável podem ser reduzidas em uma única renomeação. Operações de renomeação que não têm variáveis ​​em comum podem ser reordenadas arbitrariamente umas em relação às outras, o que pode ser explorado para tornar sucessivas renomeações adjacentes para que possam ser recolhidas.

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

Renomear e definir operadores

Renomear é distributivo em relação à diferença, união e interseção do conjunto.

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

Produto e união

O produto cartesiano é distributivo em relação ao sindicato.

1. ${\ displaystyle (A \ vezes B) \ xícara (A \ vezes C) = A \ vezes (B \ xícara C)}$

Implementações

A primeira linguagem de consulta baseada na álgebra de Codd foi a Alpha, desenvolvida pelo próprio Dr. Codd. Posteriormente, o ISBL foi criado, e este trabalho pioneiro foi aclamado por muitas autoridades por ter mostrado o caminho para transformar a ideia de Codd em uma linguagem útil. O Business System 12 foi um SGBD relacional de força da indústria de curta duração que seguiu o exemplo do ISBL.

Em 1998, Chris Date e Hugh Darwen propuseram uma linguagem chamada Tutorial D destinada ao uso no ensino de teoria de banco de dados relacional, e sua linguagem de consulta também se baseia nas ideias do ISBL. Rel é uma implementação do Tutorial D .

Mesmo a linguagem de consulta do SQL é vagamente baseada em uma álgebra relacional, embora os operandos em SQL ( tabelas ) não sejam exatamente relações e vários teoremas úteis sobre a álgebra relacional não sejam válidos na contraparte SQL (possivelmente em detrimento dos otimizadores e / ou usuários). O modelo de tabela SQL é um saco ( multiset ), em vez de um conjunto. Por exemplo, a expressão é um teorema para álgebra relacional em conjuntos, mas não para álgebra relacional em bolsas; para um tratamento da álgebra relacional em bolsas, consulte o capítulo 5 do livro "Completo" de Garcia-Molina , Ullman e Widom . ${\ displaystyle (R \ cup S) \ setminus T = (R \ setminus T) \ cup (S \ setminus T)}$

Veja também

Referências

Leitura adicional

Praticamente qualquer livro acadêmico sobre bancos de dados tem um tratamento detalhado da álgebra relacional clássica.

• Imieliński, T .; Lipski, W. (1984). "O modelo relacional de dados e álgebras cilíndricas" . Journal of Computer and System Sciences . 28 : 80–102. doi : 10.1016 / 0022-0000 (84) 90077-1 .(Para relacionamento com álgebras cilíndricas ).

links externos

• RATO. Software Relational Algebra Translator to SQL
• Vídeos da aula: Processamento de álgebra relacional - Uma introdução a como os sistemas de banco de dados processam álgebra relacional
• Notas da aula: Álgebra Relacional - Um tutorial rápido para adaptar consultas SQL à álgebra relacional
• Relacional - Uma implementação gráfica da álgebra relacional
• Otimização de consulta (página excluída; alternativas mais próximas : Otimização de consulta Standford 2 , Otimização de consulta de pesquisa da Microsoft em sistemas relacionais , artigo de Stanford: Otimização de consulta ) Este artigo é uma introdução ao uso da álgebra relacional na otimização de consultas e inclui várias citações para mais estudo aprofundado.
• Sistema de Álgebra Relacional para Oracle e Microsoft SQL Server
• Pireal - Uma ferramenta educacional experimental para trabalhar com Álgebra Relacional
• DES - Uma ferramenta educacional para trabalhar com Álgebra Relacional e outras linguagens formais
• RelaX - Calculadora de Álgebra Relacional (software de código aberto disponível como um serviço online sem registro)
• RA: um intérprete de álgebra relacional
• Traduzindo SQL para Álgebra Relacional