Divisão Relacional, parte II

por Marcelino em 26/02/2013
Divisão Relacional, parte II

No artigo anterior, vimos qual o uso da divisão relacional e uma solução utilizando NOT EXISTS de dois níveis.
Antes de apresentarmos outras formas de se resolver esse problema, é importante citarmos algumas desvantagens que o uso do duplo NOT EXISTS acarreta:

Repetição de tuplas
A consulta realiza o teste para cada tupla do dividendo (relação R), e retorna o atributo da projeção para todas as tuplas que retornarem TRUE no teste do NOT EXISTS mais externo. Assim, para que a divisão relacional seja representada corretamente é necessário o uso da cláusula DISTINCT. Portanto, não se esqueçam dela, caso optem por implementar essa solução na hora da prova.

Divisão por zero
Em uma situação hipotética, na qual o divisor (relação S) é um conjunto vazio (não há tuplas), a consulta retornará todas as tuplas existentes no dividendo (relação R). Essa característica ainda não foi cobrada em prova, mas cuidado, para que não sejam surpreendidos.
A combinação dos dois problemas acima descritos, explica a impressão de quatro valores “b1” no resultado da consulta sem a cláusula DISTINCT. Como na relação divisor (select intermediário) não há o valor “a4” para o atributo A na relação S, o divisor será um conjunto vazio, retornando, por isso, mais uma linha para o valor “b1”.


Apresentemos, agora, outras implementações para a divisão relacional.

2. HAVING COUNT
Esta solução apresenta como vantagem a simplicidade. Nela não são utilizadas consultas aninhadas correlacionadas, o que facilita a avaliação da sentença. Além disso, ela não apresenta o comportamento anômalo descrito no duplo NOT EXISTS ao lidar com conjuntos vazios no divisor nem o de repetição de tuplas, eliminando a necessidade da cláusula DISTINCT.
A sentença possui o seguinte formato (utilizando as relações R e S):
Entendendo a sentença:

Nesta sentença, não estão presentes os elementos da divisão (dividendo, divisor, quociente). Avaliemos cada parte da sentença:

SELECT B FROM R, S: cross join (R x S) que imprime uma projeção com 36 linhas

WHERE R.A = S.A: retorna uma seleção contendo 10 linhas, ou seja, apenas tuplas da projeção (cross join) em que os atributos A das duas relações sejam iguais. A figura abaixo mostra a seleção, considerando os atributos de ambas as relações.

GROUP BY R.B: apenas agrupa a seleção anterior pelo atributo B (R_B), apresentando o seguinte resultado:

HAVING COUNT(R.A) = (SELECT COUNT(A) FROM S): faz uma comparação entre a quantidade de tuplas da relação S e o agrupamento acima apresentado.
Como visto, esta solução, apesar de não utilizar os conceitos da divisão, apresenta uma resposta para consultas que necessitam retornar tuplas de uma relação que possuam correspondência com todas as tuplas de outra. Por exemplo, empregados que tenham trabalhado em todos os projetos.


3. NOT EXISTS + NOT IN
Essa solução é uma variante do duplo NOT EXISTS. Ela possui o mesmo custo e as mesmas desvantagens citadas anteriormente.

Abaixo, apresentamos a sentença:

Como dito, por possuir as mesmas desvantagens, há também a necessidade de se atentar para a cláusula DISTINCT, para que a divisão relacional seja corretamente representada. Por fim, lembre-se do problema do conjunto vazio, que faria a consulta retornar todas as ocorrências da relação dividendo.


4. EXCEPT
Outra forma de implementar a divisão relacional é utilizando o operador de diferença de conjuntos em uma consulta aninhada correlacionada.
A operação de diferença resulta em uma relação que inclui as tuplas da primeira relação (minuendo) que não possuam correspondentes na segunda (subtraendo). Essa operação possui a propriedade de não comutatividade (a ordem dos conjuntos altera o resultado) e a necessidade de os conjuntos serem união-compatíveis, ou seja, o domínio dos atributos componentes da subtração deve ser equivalente.

No padrão SQL ANSI 99 essa operação é representada pelo operador EXCEPT (MINUS no Oracle).

A sentença para esta implementação é apresentada abaixo:
Entendendo a sentença:

Primeiramente, vamos classificar as sentenças nos elementos da subtração:
minuendo: SELECT S.A FROM S
subtraendo: SELECT R2.A FROM R AS R2 WHERE R2.B=R1.B

Como temos uma consulta correlacionada o teste é feito para cada tupla da consulta mais externa, e se o resultado da subtração for um conjunto vazio o NOT EXISTS retorna TRUE, e consequentemente teremos uma correspondência. Verifiquemos esse comportamento no teste de mesa abaixo.

A avaliação será feita para cada uma das doze tuplas da relação R. Contudo, optamos por apresentar apenas quatro linhas de análise, pois a avaliação é equivalente para valores de B iguais.

Essa implementação apresenta os mesmos problemas do NOT EXISTS de dois níveis. Portanto, é necessário ficar atento ao conjunto vazio para a relação-minuendo, pois caso ocorra, o resultado será todas as tuplas da relação-subtraendo. Da mesma forma, é preciso utilizar a cláusula DISTINCT devido à repetição de tuplas.


Comparação entre as implementações

 
 
* Valores apurados com a ferramenta Explain Plan do Oracle 10G XE.
** Quando a consulta intermediária (divisor ou minuendo) retorna um conjunto vazio a consulta externa retorna todas as tuplas existentes na relação.
 
 


No próximo e último artigo, analisaremos uma coletânea de questões sobre o assunto.
 
Até lá.
 
 

Referências Bibliográficas
1. CELKO’S, Joe. SQL for Smarties: Advanced SQL Programming.
2. NAVATHE, Shamkant B. e ELMASRI, Ramez. Sistema de Banco de Dados.
3. SILBERSCHATZ, Abraham, KORTH, Henry F. e SUDARSHAN S. Sistema de Banco de Dados.
Deixe seu comentário:
Ocorreu um erro na requisição, tente executar a operação novamente.