Design de banco de dados para marcação

171

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

  • itens podem ter um grande número de tags
  • as pesquisas de 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 e 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, no entanto, as respostas fornecidas mostram como fazer uma pesquisa em OR nas tags. (Selecione todos os itens que possuem uma ou mais de n tags). Estou à procura de uma eficiente E-pesquisa. (Selecione todos os itens que possuem TODAS tags n - e possivelmente mais.)

Christian Berg
fonte

Respostas:

22

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

Sobre o desempenho: uma abordagem baseada em bitmap parece intuitivamente adequada à situação. No entanto, não estou convencido de que seja uma boa idéia 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 DBMSes (incluindo Oracle) oferecem índices de bitmap que, de alguma forma, podem ser útil, porque um sistema de indexação interno elimina a complexidade potencial da manutenção de índices; além disso, um DBMS que ofereça índices de bitmap deve poder considerá-los adequadamente ao executar o plano de consulta.

Troels Arvin
fonte
4
Devo dizer que a resposta é um pouco míope, porque o uso de um tipo de campo de bit do banco de dados limita você a um número específico de bits. Isso não significa que cada item esteja limitado a um determinado número de tags, mas que só pode haver um certo número de tags exclusivas em todo o sistema (geralmente até 32 ou 64).
21410 Mark Renouf
1
Supondo uma implementação 3nf (Pergunta, Tag, Question_has_Tag) e um índice de bitmap no Tag_id em Question_has_Tag, o índice de bitmap deve ser reconstruído sempre que uma pergunta tiver uma tag adicionada ou removida. A consulta como select * from question q inner join question_has_tag qt where tag_id in (select tag_id from tags where (what we want) minus select tag_id from tags where (what we don't)deve ser fina e escalar assumindo existem os índices b-árvore certa no meio mesa
Adam Musch
O link "Este artigo" está morto. Gostaria de ler que :(
mpen 21/10/10
3
Mark: Este parece ser bom: simple-talk.com/sql/t-sql-programming/… Provavelmente é uma versão re-publicada daquela a que me referi.
Troels Arvin
a URL do artigo não é mais válida #
Sebastien H.
77

Aqui está um bom artigo sobre como marcar esquemas de banco de dados:

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

junto com os testes de desempenho:

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

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

Jeff Atwood
fonte
1
Também gostaria de ter uma visão técnica mais detalhada sobre como você implementou o sistema de marcação com SO? Eu acho que em um podcast você disse que mantém todas as tags em uma coluna com todas as perguntas e depois as serializa / desserializa rapidamente. Gostaria muito de saber mais sobre isso e talvez ver alguns trechos de código. Eu estive olhando e encontrando detalhes, existe um link em que você já fez isso antes de eu fazer a pergunta no META?
Marston A.
5
Esta pergunta sobre Meta tem algumas informações sobre o esquema SO: meta.stackexchange.com/questions/1863/so-database-schema
Barrett
Os links originais estavam mortos, mas acho que encontrei o novo local. Convém verificar se esses eram os artigos aos quais você estava se referindo.
Brad Larson
12
Apesar de ter sido escrito por @Jeff, isso ainda é essencialmente uma resposta apenas de link.
curiousdannii
13

Não vejo problema com uma solução simples: tabela para itens, tabela para tags, cruzável para "marcação"

Os índices na tabela cruzada devem ter 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 ...

que é reconhecidamente não tão eficiente para um grande número de tags de comparação. Se você deseja manter a contagem de tags na memória, é possível fazer uma consulta para 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 comparadas e da expectativa de corresponder a qualquer uma delas, isso pode ser uma solução OK. Se você quiser combinar 20 tags e esperar que algum item aleatório corresponda a 15 delas, isso ainda será pesado em um banco de dados.

Slartibartfast
fonte
13

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

ps - A abordagem que todo mundo está falando aqui é referida como a solução "Toxi" no artigo.

Winston Fassett
fonte
3
Lembro-me de ler esse ótimo artigo, mas infelizmente o link está morto agora. :( Alguém sabe de um espelho disso? #
Localhost
5
o link estava morto: <
Aaron
6

Você pode experimentar uma solução não estritamente de banco de dados como uma implementação do Java Content Repository (por exemplo, Apache Jackrabbit ) e usar um mecanismo de pesquisa construído sobre ele como o Apache Lucene .

Essa solução com os mecanismos de armazenamento em cache apropriados possivelmente produziria melhor desempenho do que uma solução doméstica.

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

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

Zizzencs
fonte
5

O método mais fácil é criar uma tabela de tags .
Target_Type- no caso de você estar marcando várias tabelas
Target- A chave do registro que está sendo marcado
Tag - O texto de uma marca

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]

ATUALIZAÇÃO
Com base em sua exigência de AND nas condições, a consulta acima se tornaria algo como isto

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]
Brad Bruce
fonte
1

Gostaria da segunda sugestão do @Zizzencs de que você pode querer algo que não seja totalmente centralizado no DB

De alguma forma, acredito que o uso de campos nvarchar simples para armazenar essas tags com algum cache / indexação adequado pode gerar resultados mais rápidos. Mas 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ê esteja lidando com tags em muitos lugares, posso dizer que com 3 tabelas ser manipulado / consultado simultaneamente o tempo todo definitivamente tornará seu código mais complexo.

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

chakrit
fonte
0

Você não poderá evitar junções e ainda será 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 3ª tabela, chamarei de TagXREF:

 TagXrefID | ItemID | TagId

Portanto, 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 para uma tag, eu usaria algo como isto:

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 juntos, você deve modificar ligeiramente a instrução acima para adicionar AND Tags.TagName = @ TagName1 AND Tags.TagName = @ TagName2 etc ... e criar dinamicamente a consulta.

FlySwat
fonte
0

O que eu gosto de fazer é ter um número de tabelas que representam os dados brutos, portanto, nesse 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á ingressar nas tabelas duas vezes para cada tag adicional que desejar AND, para uma 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)

Em seguida, considere com que frequência a tabela Item marcado precisa ser atualizada, se estiver em todas as inserções, e chame o procedimento armazenado em um evento de inserção do cursor. Se for uma tarefa horária, configure um trabalho por hora para executá-lo.

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 declaração de caso maciça, você deseja passar um único parâmetro que contém uma lista de tags que deseja selecionar no banco de dados e retornar um conjunto de itens de registro. Isso seria melhor em formato binário, usando operadores bit a bit.

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

0000

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

1111

Se apenas os dois primeiros ...

1100

Então é apenas um caso de encontrar os valores binários com os 1s e zeros na coluna desejada. Usando os operadores Bitwise do SQL Server, você pode verificar se existe um 1 na primeira das colunas usando consultas muito simples.

Verifique este link para saber mais .

digiguru
fonte
0

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

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

A melhor maneira de otimizar essa consulta dependerá da plataforma, portanto, recomendo que você remarque sua pergunta com seu RDBS e altere o título para algo como "Maneira ideal de executar E consultar em um banco de dados de marcação".

Tenho algumas sugestões para o MS SQL, mas evitarei se essa não for a plataforma que você está usando.

Portman
fonte
6
Você provavelmente não deve deixar de falar sobre uma determinada tecnologia, porque outras pessoas que tentam trabalhar nesse domínio de problema podem realmente estar usando essa tecnologia e se beneficiariam.
Bryan Rehbein
0

Uma variação da resposta acima é pegar os IDs das tags, classificá-los, combinar como uma sequência ^ separada e hash-los. Em seguida, basta associar o hash ao item. Cada combinação de tags produz uma nova chave. Para fazer uma pesquisa AND, simplesmente recrie o hash com os IDs de tags e a pesquisa fornecidos. A alteração de tags em um item fará com que o hash seja recriado. Itens com o mesmo conjunto de tags compartilham a mesma chave de hash.

nitinahuja
fonte
4
Com essa abordagem, você pode procurar apenas entradas com exatamente o mesmo conjunto de tags - isso é sempre trivial. Na minha pergunta original, quero encontrar entradas que tenham todas as tags que eu consultar e possivelmente mais.
Christian Berg
0

Se você possui um tipo de matriz, pode agregar previamente os dados necessários. Veja esta resposta em um tópico separado:

qual é a utilidade do tipo de matriz?

Denis de Bernardy
fonte