3

Como montar query para comparar se um conjunto A de números é igual ao outro, de B, com os mesmo números do conjunto A, e assim sucessivamente.

Exemplo:

Dados da tabela

id  conjunto    numero      ordem
1   1           1           1
2   1           12          2
3   1           4           3
4   1           6           4
5   2           1           1
6   2           12          2
7   2           4           3
8   2           6           4
9   3           15          1
10  3           17          2
11  3           20          3
12  4           15          1
13  4           17          2

O resultado após comparação: conjuntos 1 e 2 duplicados

Possuo uma tabela com mais de um milhão de conjuntos e com vários números para cada conjunto e está demorando demais retornar resultado. Não achei um outro jeito de comparar a não ser usando o For XML e criando tabela temporária TEMP. Existe uma outra maneira de comparar de maneira eficiente e performático?

Segue abaixo um script que faz a comparação:

select
    t.*
INTO 
#TABELA
from
    (
        select 1 id, 1 conjunto, 1 numero, 1 ordem
        union all
        select 2 id, 1 conjunto, 12 numero, 2 ordem
        union all
        select 3 id, 1 conjunto, 4 numero, 3 ordem
        union all
        select 4 id, 1 conjunto, 6 numero, 4 ordem
        union all
        select 5 id, 2 conjunto, 1 numero, 1 ordem
        union all
        select 6 id, 2 conjunto, 12 numero, 2 ordem
        union all
        select 7 id, 2 conjunto, 4 numero, 3 ordem
        union all
        select 8 id, 2 conjunto, 6 numero, 4 ordem
        union all
        select 9 id, 3 conjunto, 15 numero, 1 ordem
        union all
        select 10 id, 3 conjunto, 17 numero, 2 ordem
        union all
        select 11 id, 3 conjunto, 20 numero, 3 ordem
        union all
        select 12 id, 4 conjunto, 15 numero, 1 ordem
        union all
        select 13 id, 4 conjunto, 17 numero, 2 ordem
    ) t   


select DISTINCT
T1.conjunto,
(SELECT RIGHT('' + CONVERT(varchar, numero), 2) as [text()] from #TABELA i where i.conjunto=t1.conjunto order by i.conjunto, i.ordem for xml path('')) numeros
INTO
#TEMP
from 
#TABELA T1



SELECT
t1.conjunto
FROM
(
    select
    t1.numeros numeros
    from 
    #TEMP t1
    group by
    t1.numeros
    having
    count(*) > 1
) t2
inner join #TEMP t1 on t2.numeros = t1.numeros
5
  • A ordem dos elementos no conjunto importa na comparação? Isto é, o conjunto {1, 12, 4, 6} é igual ou diferente de {1, 4, 6, 12} ?
    – José Dız
    Commented 27/10/2016 às 18:21
  • Os conjuntos a serem comparados devem ter o mesmo número de elementos ou a comparação considera o conjunto de menor número de elementos? Isto é, {1, 12, 4} é igual a {1, 12, 4, 6}?
    – José Dız
    Commented 27/10/2016 às 18:24
  • Um conjunto deve ser igual ao outro não importa a ordem e devem ter a mesma quantidade de números, ou seja o conjunto A {6, 12, 4, 1} é igual ao outro B {1, 12, 4, 6}.
    – Leandro
    Commented 27/10/2016 às 19:21
  • se, para a comparação de conjuntos, a ordem em que os elementos estão não importa, para que serve a coluna "ordem"? Os valores numéricos são sempre pequenos? Por exemplo, variam de 1 a 50.
    – José Dız
    Commented 28/10/2016 às 9:20
  • é um meio que eu achei como solução para conseguir comparar usando a query acima, mas de fato a ordem não importa. Os números variam de 0 a 99.
    – Leandro
    Commented 28/10/2016 às 11:20

2 Respostas 2

2

Considerando-se que:

  • a ordem dos elementos (números) no conjunto não importa;
  • não há elementos repetidos (isto é, um mesmo número não pode ocorrer mais de uma vez em um mesmo conjunto); e
  • os valores dos números variam de 0 a 99,

sugiro que armazene os conjuntos na forma de mapa de bits. Para cada conjunto cria-se um vetor de 100 posições, onde cada posição representa um número; se o número estiver presente no conjunto, a posição está com o valor 1, mas se o número não fizer parte do conjunto, a posição está 0.

Supondo que cada conjunto possa ter elementos que variam de 1 a 10, para representar o conjunto {4, 1, 9} teríamos 1001000010, onde o primeiro bit representa o número 1, o segundo bit representa o número 2 e assim em diante, até 10.

Considerando-se ainda que podem existir conjuntos repetidos, o mapa de bits fica em uma tabela. Ou seja, cada combinação de elementos existente ocupa um único mapa de bits. Em outra tabela, uma relação indicando qual mapa de bits cada conjunto utiliza.

A ideia inicial era implementar o mapa de bits com uma coluna declarada como bit(100). Ou seja, uma cadeia de bits. Mas, infelizmente, isto não é permitido em T-SQL. Para contornar essa restrição, a primeira versão utiliza então uma cadeia de bytes: char(100).

CREATE TABLE Tab_Bloco (
  ID int identity,
  Bloco char(100) not null default replicate('0', 100)
);

A outra tabela contém, para cada conjunto, qual é o mapa de bits que ela utiliza.

CREATE TABLE Conjunto_Bloco (
  ID_Conjunto int not null,
  ID_Bloco int not null 
           references Tab_Bloco(ID)
);

Por exemplo, os conjuntos 1:{4, 1, 9}, 2:{1, 2, 3, 5, 7} e 3:{1, 4, 9} seriam representados assim:

Tab_Bloco
1 1001000010
2 1110101000

Conjunto_Bloco
1 1
2 2
3 1

Observe que os conjuntos 1 e 3 compartilham o mesmo mapa de bits.

A princípio, se fosse possível utilizar a cadeia de bits, cada conjunto ocuparia somente 21 bytes (4 de ID_Conjunto, 4 do ID de Tab_Bloco, 13 de Bloco em Tab_Bloco). É óbvio que esta conta não engloba índices e outros controles. Mas, por enquanto, a solução proposta gasta 108 bytes (4 de ID_Conjunto, 4 do ID de Tab_Bloco, 100 de Bloco em Tab_Bloco).

Há como implementar o mapa de bits em 4 variáveis do tipo int, pois cada uma ocupa 32 bits. Ou talvez binary(13). Mas é necessário utilizar operações bitwise.

Como o objetivo inicial é performance, a nova estrutura de armazenamento garantirá rapidez para encontrar conjuntos repetidos como também pesquisas do tipo "tal conjunto existe?".

Para validar a nova estrutura é necessário saber quais são as principais manipulações com os dados. A princípio, não será necessário armazenar os conjuntos na forma antiga, mas somente como mapa de bits. Ou seja, cada novo conjunto a ser acrescentado é armazenado diretamente como mapa de bits. A partir de cada vetor é possível retornar os números que compõem cada elemento. Mas, se for necessário manter os conjuntos nas duas representações (números e mapa de bits), então recomenda-se o uso de procedimento trigger para garantir a consistência entre as duas tabelas.


Para verificar se há conjuntos repetidos, é um processo bem simples.

-- código #2
with Repetidos as (
SELECT ID_Bloco, Count(*) as Qtd
  from Conjunto_Bloco
  group by ID_Bloco
  having Count(*) > 1
)
SELECT T1.ID_Conjunto, T1.ID_Bloco
  from Conjunto_Bloco as T1
       inner join Repetidos as T2 on T1.ID_Bloco = T2.ID_Bloco
  order by ID_Bloco;

O código #1 a seguir converte a tabela atual para as duas novas tabelas. Optou-se pela utilização de cursor, para a leitura dos dados, pois me pareceu, neste caso, mais eficiente do que o uso de código set based.

-- código #1
-- cria as duas novas estruturas de dados
CREATE TABLE Tab_Bloco (
  ID int identity,
  Bloco char(100) not null default replicate('0', 100)
);
CREATE clustered index I1_Tab_Bloco on Tab_Bloco (Bloco);
CREATE unique nonclustered index I2_Tab_Bloco on Tab_Bloco (ID);


CREATE TABLE Conjunto_Bloco (
  ID_Conjunto int not null,
  ID_Bloco int not null
               references Tab_Bloco (ID)
);
CREATE clustered index I1_Conjunto_Bloco on Conjunto_Bloco (ID_Conjunto, ID_Bloco);
CREATE unique nonclustered index I2_Conjunto_Bloco on Conjunto_Bloco (ID_Bloco, ID_Conjunto);
go

--
DECLARE Lê_Número CURSOR 
   forward_only
   for SELECT Conjunto, Numero
         from Conjunto order by Conjunto;
declare @ID_Conjunto int, @Número int;
declare @ID_atual int;

declare @ID_Bloco int, @Bloco char(100);

OPEN Lê_Número;

-- obtém primeiro número do primeiro conjunto
FETCH NEXT
  from Lê_Número 
  into @ID_Conjunto, @Número;

while @@fetch_status = 0
   begin
   -- novo conjunto
   set @ID_atual= @ID_conjunto;
   set @Bloco= replicate('0', 100);

   -- coleciona números do conjunto atual
   while @@fetch_status = 0 and @ID_Conjunto = @ID_atual
      begin
      -- liga bit respectivo do número
      set @Bloco= Stuff(@Bloco, @Número+1, 1, '1');

      -- obtém próximo número 
      FETCH NEXT
        from Lê_Número 
        into @ID_Conjunto, @Número;
      end;
      -- fim números do conjunto atual

   -- registra bloco
   set @ID_Bloco= (SELECT ID from Tab_Bloco where Bloco = @Bloco);
   IF @ID_Bloco is null
      begin
      -- novo bloco
      INSERT into Tab_Bloco (Bloco) values (@Bloco);
      set @ID_Bloco= scope_identity();
      end;

   -- estabele ligação de conjunto e bloco
   INSERT into Conjunto_Bloco (ID_Conjunto, ID_Bloco)
     values (@ID_atual, @ID_Bloco);

   end;
   -- fim conjunto

CLOSE Lê_Número;

DEALLOCATE Lê_Número;
go

Falta validar esse modelo com um grande volume de dados.

2
  • Utilizando mapa de bits ficou consideravelmente mais rápido se comparado com outras formas de comparação usando números.
    – Leandro
    Commented 4/11/2016 às 13:41
  • @Leandro, boas notícias. Como T-SQL não aceita bit(n), tivemos que utilizar char(n). Ou seja, ficou mapa de bytes. Mas vou refinar o código #1, de modo a implementar mapa de bits usando operador bitwise. Espero que dê certo!
    – José Dız
    Commented 4/11/2016 às 22:50
2

Apesar de ter dúvidas se a performance terá melhorias, uma outra forma de comparar os registos é usando o INTERSECT. Exemplo:

declare @conjunto int, @conjMin int

select  @conjunto = max(conjunto),
        @conjMin = min(conjunto)
from #TABELA

select  *, num_rows = (select count(*) from #TABELA where conjunto = t.conjunto),
        is_duplicated = 0
into #tempTable
from #TABELA t

while @conjunto >= @conjMin begin
    if((select top 1 1
        from(   SELECT numero, ordem, num_rows
                FROM #tempTable t1
                where t1.conjunto = @conjunto
                INTERSECT
                SELECT numero, ordem, num_rows
                FROM #tempTable t2
                where t2.conjunto <> @conjunto)
            t))>0 begin

            update #tempTable
            set is_duplicated = 1
            where conjunto = @conjunto 
        end

    set @conjunto = @conjunto-1
end

select distinct conjunto from #tempTable where is_duplicated = 1

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .