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.