Análise Combinatória com SQL: Combinações

Você precisa estar logado para dar um feedback. Clique aqui para efetuar o login
Para efetuar o download você precisa estar logado. Clique aqui para efetuar o login
Confirmar voto
0
 (0)  (0)

Veja neste artigo uma abordagem à Análise Combinatória utilizando SQL, enfatizando as Combinações.

Dando continuidade à série sobre análise combinatória com SQL, este artigo aborda a combinação de elementos.

Introdução

“Considerando quatro funcionários de uma empresa (André, Bianca, Carlos e Dayse), quantas e quais são as equipes contendo 2 pessoas que podem ser formadas?”

Acima descrevemos um típico problema de análise combinatória envolvendo combinações de elementos de um conjunto. O conjunto em questão é formado por 4 elementos: os funcionários ‘André’, ‘Bianca’, ‘Carlos’ e ‘Dayse’, que, daqui em diante, representaremos pelas letras A, B, C e D, respectivamente. Para resolver o problema, devemos determinar todas as equipes possíveis, mas sem considerar as diferentes ordens dos elementos. Isso que dizer que quando trabalhamos com combinação {A, B} e {B, A} são considerados o mesmo conjunto, ao contrário do que ocorre quando trabalhamos com arranjos.

A resposta para a questão proposta no primeiro parágrafo é a seguinte: “AB”, “AC”, “AD”, “BC”, “BD”, “CD”

Neste exemplo, realizamos uma combinação de 4 elementos tomados 2 a 2. O total de equipes é 6. De uma maneira geral, uma combinação de n elementos r a r, representado por C(n,r) produz um total de n! / (r! x (n-r)!) subconjuntos. Em nosso exemplo: 4! / (2! (4-2)!) = 6.

Combinações com SQL

No artigo anterior, introduzimos um modelo composto por três regras para a construção de consultas SQL para a geração de arranjos em grupos de 2 elementos. Para gerarmos combinações via SQL, o modelo é bem parecido. As duas primeiras regras continuam iguais e a terceira é levemente modificada para evitar a geração de conjuntos com elementos iguais em ordens diferentes. O modelo do SQL para combinações é apresentado a seguir:

  • Fazer o “self-join” da tabela-alvo (ou seja, instancia-la duas vezes), porém sem utilizar nenhuma condição de junção (sem ligar as duas instâncias da tabela por nenhum campo).
  • Dar apelidos diferentes para cada uma das duas instâncias da tabela.
  • Aplicar restrições na cláusula WHERE para evitar a produção de linhas contendo elementos iguais e ordens diferentes.

Como exemplo, considere a tabela T_CONJUNTO, cujo conteúdo é apresentado na Figura 1. Esta tabela possui apenas um campo, denominado ELEMENTO.

Tabela T_CONJUNTO

Figura 1: Tabela T_CONJUNTO

O SQL para realizar a combinação destes elementos 2 a 2 é apresentado abaixo. Veja que o “pulo do gato” - e a diferença em relação aos arranjos - consiste na utilização do operador “ < “ (“menor que”) na cláusula WHERE. Ele força com que em todas as tuplas retornadas, o elemento de T1 seja menor (tenha menor valor lexicográfico) do que o elemento de T2.

Listagem 1: Combinação de Elementos 2 a 2

SELECT * FROM T_CONJUNTO C1, T_CONJUNTO C2
WHERE C1.ELEMENTO < C2.ELEMENTO

O resultado é dado a seguir:

Resultado da Consulta - Combinação de elementos 2 a 2

Figura 2: Resultado da Consulta - Combinação de elementos 2 a 2

Ordenando os Resultados

Assim como no caso dos arranjos, a cláusula ORDER BY pode ser utilizada para ordenar os resultados pelo (primeiro elemento prioritariamente, depois segundo elemento dos conjuntos).

Listagem 2: Arranjo dos Elementos 2 a 2 - Ordenando pelo Primeiro Elemento

SELECT * FROM T_CONJUNTO C1, T_CONJUNTO C2
WHERE C1.ELEMENTO < C2.ELEMENTO
ORDER BY C1.ELEMENTO, C2.ELEMENTO
Resultado da Consulta com ORDER BY

Figura 3 Resultado da Consulta com ORDER BY

No próximo artigo, mostraremos que com SQL também podemos produzir arranjos e combinações 3 a 3, 4 a 4, etc. Até lá!

 
Você precisa estar logado para dar um feedback. Clique aqui para efetuar o login
Receba nossas novidades
Ficou com alguma dúvida?