Marcação hierárquica em SQL

Question

Eu tenho um aplicativo da Web PHP que usa um banco de dados MySQL para marcação de objetos, na qual usei a estrutura de tags aceita como resposta para isso é tão pergunta.

Eu gostaria de implementar uma hierarquia de tags, onde cada tag pode ter uma tag pai exclusiva. As pesquisas por uma etiqueta pai t correspondem a todos os descendentes de t (ou seja, tags, quem é pai (filhos de t), netos de t, etc.).

A maneira mais fácil de fazer isso parece ser adicionar um campo parentid à tabela de tags, que contém o ID da tag pai de uma tag ou algum número mágico se a tag não tiver pai. A busca de descendentes, no entanto, requer pesquisas completas repetidas do banco de dados para encontrar as tags em cada 'geração', que eu gostaria de evitar.

Uma maneira (presumivelmente) mais rápida, mas menos normalizada, seria ter uma tabela contendo todos os filhos de cada etiqueta, ou mesmo todos os descendentes de cada etiqueta. No entanto, isso corre o risco de dados inconsistentes no banco de dados (por exemplo, uma tag sendo a criança de mais de um pai).

Existe uma boa maneira de fazer consultas para encontrar descendentes rapidamente, mantendo os dados o mais normalizados possível?

Answer 1

A resposta de Ali tem um link para As árvores e hierarquias de Joe Celko no SQL para Smarties, que confirma minha suspeita - não há uma estrutura simples de banco de dados que ofereça o melhor de todos os mundos. O melhor para o meu propósito parece ser a "árvore de inserção frequente" detalhada neste livro, que é como o "modelo de conjunto aninhado" do link de Ali, mas com indexação não consecutiva. Isso permite a (1) inserção (a la numeração básica de linha não estruturada), com reorganização ocasional do índice como e quando necessário.

Answer 2

Eu o implementei usando duas colunas. Eu simplico um pouco aqui, porque tive que manter o nome da tag em um campo/tabela separado, porque tive que localizá -lo para diferentes idiomas:

• marcação
• caminho

Olhe para essas linhas, por exemplo:

tag            path
---            ----
database       database/
mysql          database/mysql/
mysql4         database/mysql/mysql4/
mysql4-1       database/mysql/mysql4-1/
oracle         database/oracle/
sqlserver      database/sqlserver/
sqlserver2005  database/sqlserver/sqlserver2005/
sqlserver2005  database/sqlserver/sqlserver2008/

etc.

Usando o like Operador no campo do caminho Você pode facilmente obter todas as linhas de tags necessárias:

SELECT * FROM tags WHERE path LIKE 'database/%'

Existem alguns detalhes de implementação, como quando você move um nó na hierarquia, também precisa mudar todas as crianças etc., mas não é difícil.

Também verifique se o comprimento do seu caminho é longo o suficiente - no meu caso, não usei o nome da tag para o caminho, mas outro campo para garantir que eu não receba caminhos muito longos.

Answer 3

Algumas maneiras aqui

Answer 4

Você pode construir o que Kimball chama de mesa de auxiliar de hierarquia.

Diga que sua hierarquia se parece com isto: a -> b | B -> C | C -> D

você inseriria registros em uma tabela que se parece com isso

ParentID, ChildID, Depth, Highest Flag, Lowest Flag
A, A, 0, Y, N
A, B, 1, N, N
A, C, 2, N, N
A, D, 3, N, Y
B, B, 0, N, N
B, C, 1, N, N
B, D, 2, N, Y
C, C, 0, N, N
C, D, 1, N, Y
D, D, 0. N, Y

Eu acho que tenho isso correto .... De qualquer forma. O ponto é que você ainda armazena a hierarquia corretamente, basta construir esta tabela a partir da sua tabela adequada. Esta tabela consulta como um banshee. Digamos que você queira saber quais são todo o primeiro nível abaixo B.

WHERE parentID = 'B' and Depth = 1

Answer 5

Eu usaria algum tipo de matriz para armazenar as tags infantis, isso deve ser muito mais rápido do que ingressar em uma tabela em si (especialmente se você tiver um grande número de tags). Eu dei uma olhada e não sei dizer se o MySQL tem um tipo de dados de matriz nativo, mas você pode imitar isso usando uma coluna de texto e armazenando uma matriz serializada nele. Se você deseja acelerar as coisas ainda mais, poderá colocar um índice de pesquisa de texto nessa coluna para descobrir quais tags estão relacionadas.

Editar] Depois de ler o artigo de Ali, fiz mais um pouco de caça e encontrei isto Apresentação sobre várias abordagens para implementar hierarquias no Postgres. Ainda pode ser útil para fins explicativos.