Design de banco de dados para marcação

https://stackoverflow.com/questions/48475

09-06-2019
|

Pergunta

Como você projetaria um banco de dados para suportar os seguintes recursos de marcação:

os itens podem ter um grande número de tags
pesquisas por todos os itens marcados com um determinado conjunto de tags devem ser rápidas (os itens devem ter TODAS as tags, portanto é uma pesquisa AND, não uma pesquisa OR)
a criação/gravação de itens pode ser mais lenta para permitir pesquisa/leitura rápida

Idealmente, a pesquisa de todos os itens marcados com (pelo menos) um conjunto de n tags deve ser feita usando uma única instrução SQL.Como o número de tags a serem pesquisadas, bem como o número de tags em qualquer item, são desconhecidos e podem ser altos, o uso de JOINs é impraticável.

Alguma ideia?

Obrigado por todas as respostas até agora.

Se não me engano, entretanto, as respostas fornecidas mostram como fazer uma pesquisa OR nas tags.(Selecione todos os itens que possuem uma ou mais de n tags).Estou procurando uma pesquisa AND eficiente.(Selecione todos os itens que possuem TODAS as n tags - e possivelmente mais.)

Solução

Sobre AND:Parece que você está procurando a operação de "divisão relacional". Este artigo cobre a divisão relacional de forma concisa e ainda assim compreensível.

Sobre desempenho:Uma abordagem baseada em bitmap parece intuitivamente adequada à situação.No entanto, não estou convencido de que seja uma boa ideia implementar a indexação de bitmap "manualmente", como sugere o digiguru:Parece uma situação complicada sempre que novas tags são adicionadas (?) Mas alguns SGBDs (incluindo Oracle) oferecem índices de bitmap que podem de alguma forma ser úteis, porque um sistema de indexação integrado elimina a complexidade potencial da manutenção de índices;além disso, um SGBD que oferece índices de bitmap deve ser capaz de considerá-los adequadamente ao executar o plano de consulta.

Outras dicas

Aqui está um bom artigo sobre marcação de esquemas de banco de dados:

http://howto.philippkeller.com/2005/04/24/Tags-Database-schemas/

junto com testes de desempenho:

http://howto.philippkeller.com/2005/06/19/Tagsystems-performance-tests/

Observe que as conclusões são muito específicas do MySQL, que (pelo menos em 2005, na época em que este artigo foi escrito) tinha características de indexação de texto completo muito ruins.

Não vejo problema com uma solução direta:Tabela para itens, tabela para tags, tabela cruzada para "etiquetagem"

Os índices na tabela cruzada devem ser otimização suficiente.A seleção de itens apropriados seria

SELECT * FROM items WHERE id IN  
    (SELECT DISTINCT item_id FROM item_tag WHERE  
    tag_id = tag1 OR tag_id = tag2 OR ...)

E a marcação seria

SELECT * FROM items WHERE  
    EXISTS (SELECT 1 FROM item_tag WHERE id = item_id AND tag_id = tag1)  
    AND EXISTS (SELECT 1 FROM item_tag WHERE id = item_id AND tag_id = tag2)  
    AND ...

o que é reconhecidamente não tão eficiente para um grande número de tags de comparação.Se você quiser manter a contagem de tags na memória, poderá fazer a consulta começar com tags que não são frequentes, para que a sequência AND seja avaliada mais rapidamente.Dependendo do número esperado de tags a serem correspondidas e da expectativa de correspondência com qualquer uma delas, esta pode ser uma solução OK, se você quiser combinar 20 tags e esperar que algum item aleatório corresponda a 15 delas, então isso ainda seria pesado em um banco de dados.

Eu só queria destacar que o artigo ao qual @Jeff Atwood vincula (http://howto.philippkeller.com/2005/04/24/Tags-Database-schemas/) é muito completo (discute os méritos de três abordagens de esquema diferentes) e tem uma boa solução para as consultas AND que geralmente terão um desempenho melhor do que o que foi mencionado aqui até agora (ou seja,não usa uma subconsulta correlacionada para cada termo).Também muitas coisas boas nos comentários.

ps - A abordagem que todos estão falando aqui é chamada de solução "Toxi" no artigo.

Você pode querer experimentar uma solução não estritamente de banco de dados, como um Repositório de conteúdo Java implementação (por ex. Coelho Apache) e use um mecanismo de pesquisa baseado nele, como Apache Lucene.

Esta solução com os mecanismos de cache apropriados possivelmente produziria um desempenho melhor do que uma solução desenvolvida internamente.

No entanto, eu realmente não acho que em um aplicativo de pequeno ou médio porte você precisaria de uma implementação mais sofisticada do que o banco de dados normalizado mencionado em postagens anteriores.

EDITAR:com o seu esclarecimento, parece mais atraente usar uma solução semelhante ao JCR com um mecanismo de pesquisa.Isso simplificaria muito seus programas no longo prazo.

O método mais fácil é criar um Tag mesa.
Target_Type -- caso você esteja marcando várias tabelas
Target -- A chave para o registro que está sendo marcado
Tag -- O texto de uma tag

Consultar os dados seria algo como:

Select distinct target from tags   
where tag in ([your list of tags to search for here])  
and target_type = [the table you're searching]

ATUALIZAR
Com base na sua exigência de AND nas condições, a consulta acima se transformaria em algo assim

select target
from (
  select target, count(*) cnt 
  from tags   
  where tag in ([your list of tags to search for here])
    and target_type = [the table you're searching]
)
where cnt = [number of tags being searched]

Eu apoiaria a sugestão do @Zizzencs de que você pode querer algo que não seja totalmente centrado em (R)DB

De alguma forma, acredito que o uso de campos nvarchar simples para armazenar essas tags com algum cache/indexação adequado pode produzir resultados mais rápidos.Mas isso sou só eu.

Eu implementei sistemas de marcação usando 3 tabelas para representar um relacionamento muitos-para-muitos antes (Item Tags ItemTags), mas suponho que você lidará com tags em muitos lugares, posso dizer que com 3 tabelas tendo que ser manipulado/consultado simultaneamente o tempo todo certamente tornará seu código mais complexo.

Você pode considerar se a complexidade adicional vale a pena.

Você não poderá evitar junções e ainda assim estar um pouco normalizado.

Minha abordagem é ter uma tabela de tags.

 TagId (PK)| TagName (Indexed)

Então, você tem uma coluna TagXREFID na sua tabela de itens.

Esta coluna TagXREFID é um FK para uma terceira tabela, vou chamá-la de TagXREF:

 TagXrefID | ItemID | TagId

Então, para obter todas as tags de um item seria algo como:

SELECT Tags.TagId,Tags.TagName 
     FROM Tags,TagXref 
     WHERE TagXref.TagId = Tags.TagId 
         AND TagXref.ItemID = @ItemID

E para obter todos os itens de uma tag, eu usaria algo assim:

SELECT * FROM Items, TagXref
     WHERE TagXref.TagId IN 
          ( SELECT Tags.TagId FROM Tags
                WHERE Tags.TagName = @TagName; )
     AND Items.ItemId = TagXref.ItemId;

Para AND um monte de tags juntas, você modificaria ligeiramente a instrução acima para adicionar AND Tags.TagName = @TagName1 AND Tags.TagName = @TagName2 etc...e construir dinamicamente a consulta.

O que eu gosto de fazer é ter várias tabelas que representam os dados brutos, então neste caso você teria

Items (ID pk, Name, <properties>)
Tags (ID pk, Name)
TagItems (TagID fk, ItemID fk)

Isso funciona rápido para os tempos de gravação e mantém tudo normalizado, mas você também pode observar que, para cada tag, você precisará juntar tabelas duas vezes para cada tag adicional que desejar E, portanto, a leitura é lenta.

Uma solução para melhorar a leitura é criar uma tabela de cache sob comando, configurando um procedimento armazenado que essencialmente cria uma nova tabela que representa os dados em um formato nivelado...

CachedTagItems(ID, Name, <properties>, tag1, tag2, ... tagN)

Então você pode considerar com que frequência a tabela Tagged Item precisa ser mantida atualizada, se estiver em cada inserção, e então chamar o procedimento armazenado em um evento de inserção de cursor.Se for uma tarefa por hora, configure um trabalho por hora para executá-la.

Agora, para ser realmente inteligente na recuperação de dados, você desejará criar um procedimento armazenado para obter dados das tags.Em vez de usar consultas aninhadas em uma instrução case massiva, você deseja passar um único parâmetro contendo uma lista de tags que deseja selecionar no banco de dados e retornar um conjunto de registros de itens.Isso seria melhor em formato binário, usando operadores bit a bit.

Em formato binário, é fácil de explicar.Digamos que existem quatro tags a serem atribuídas a um item, em binário poderíamos representar isso

Se todas as quatro tags forem atribuídas a um objeto, o objeto ficaria assim...

Se apenas os dois primeiros...

Depois é só encontrar os valores binários com 1s e zeros na coluna desejada.Usando os operadores Bitwise do SQL Server, você pode verificar se há 1 na primeira das colunas usando consultas muito simples.

Verifique este link para descobrir mais.

Parafraseando o que outros disseram:o truque não está no esquema, está no consulta.

O esquema ingênuo de Entidades/Rótulos/Tags é o caminho certo a seguir.Mas, como você viu, não está imediatamente claro como realizar uma consulta AND com muitas tags.

A melhor maneira de otimizar essa consulta dependerá da plataforma, portanto, recomendo remarcar sua pergunta com seu RDBS e alterar o título para algo como "Maneira ideal de executar uma consulta AND em um banco de dados de marcação".

Tenho algumas sugestões para MS SQL, mas me absterei caso essa não seja a plataforma que você está usando.

Uma variação da resposta acima é pegar os IDs das tags, classificá-los, combiná-los como uma string separada por ^ e hash-los.Depois basta associar o hash ao item.Cada combinação de tags produz uma nova chave.Para fazer uma pesquisa AND, basta recriar o hash com os IDs de tag fornecidos e pesquisar.Alterar tags em um item fará com que o hash seja recriado.Itens com o mesmo conjunto de tags compartilham a mesma chave hash.

Se você tiver um tipo de matriz, poderá pré-agregar os dados necessários.Veja esta resposta em um tópico separado:

qual é a utilidade do tipo array?

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow