Marquage hiérarchique en SQL

Question

J'ai une application Web PHP qui utilise une base de données MySQL pour le balisage d'objet, dans laquelle j'ai utilisé la structure de balise acceptée comme réponse à cette question SO .

J'aimerais implémenter une hiérarchie de balises, dans laquelle chaque balise peut avoir une balise parent unique. Les recherches pour une balise parent T correspondent alors à tous les descendants de T (c’est-à-dire T, les balises dont le parent est T (enfants de T), les petits-enfants de T, etc.).

Le moyen le plus simple de procéder semble être d’ajouter un champ ParentID à la table des balises, qui contient l’ID de la balise parent d’une balise, ou un nombre magique si la balise n’a pas de parent. Toutefois, la recherche de descendants nécessite ensuite des recherches complètes répétées dans la base de données pour rechercher les balises de chaque génération, ce que je souhaiterais éviter.

Un moyen (probablement) plus rapide, mais moins normalisé, serait d’avoir une table contenant tous les enfants de chaque balise, voire tous les descendants de chaque balise. Toutefois, cela risque de donner lieu à des données incohérentes dans la base de données (par exemple, une balise étant l’enfant de plusieurs parents).

Existe-t-il un moyen efficace de rechercher rapidement des descendants, tout en maintenant les données aussi normalisées que possible?

Answer 1

La réponse d'Ali a un lien vers Les arbres et les hiérarchies de Joe Celko dans SQL pour Smarties , ce qui confirme mes soupçons - il n’existe pas de structure de base de données simple offrant le meilleur des mondes. Le meilleur pour moi semble être "l'arborescence d'insertion fréquente". détaillé dans ce livre, qui ressemble au "Modèle de jeu imbriqué". du lien de Ali, mais avec une indexation non consécutive. Ceci permet l’insertion d’O (1) ( à la numérotation de lignes BASIC non structurée), avec une réorganisation occasionnelle de l’index selon les besoins.

Answer 2

Je l'ai implémenté en utilisant deux colonnes. Je simplifie un peu ici, car je devais conserver le nom de la balise dans un champ / une table séparé, car je devais le localiser pour différentes langues:

• balise
• chemin

Regardez ces lignes par exemple:

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.

En utilisant l'opérateur like dans le champ du chemin, vous pouvez facilement obtenir toutes les lignes de balises nécessaires:

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

Il existe certains détails d'implémentation, comme lorsque vous déplacez un nœud dans la hiérarchie, vous devez également modifier tous les enfants, etc., mais ce n'est pas difficile.

Assurez-vous également que la longueur de votre chemin est suffisamment longue. Dans mon cas, je n'ai pas utilisé le nom de la balise pour le chemin, mais un autre champ pour m'assurer que les chemins ne sont pas trop longs.

Answer 3

Quelques manières ici

Answer 4

Vous pouvez créer ce que Kimball appelle une table d’aide à la hiérarchie.

Disons que votre hiérarchie ressemble à ceci: A - > B | B - > C | C - > D

vous voudriez insérer des enregistrements dans une table qui ressemble à ceci

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

Je pense que j'ai ce correct .... de toute façon. Le fait est que vous stockez toujours correctement votre hiérarchie, vous venez de construire cette table à partir de votre table appropriée. CETTE table pose comme une banshee. Supposons que vous souhaitiez savoir ce que sont tous les premiers niveaux inférieurs à B.

WHERE parentID = 'B' and Depth = 1

Answer 5

J'utiliserais une sorte de tableau pour stocker les balises enfants. Cela devrait être beaucoup plus rapide que de rejoindre une table sur elle-même (surtout si vous avez un grand nombre de balises). J'ai jeté un coup d'œil et je ne sais pas si mysql a un type de données de tableau natif, mais vous pouvez l'imiter en utilisant une colonne de texte et en stockant un tableau sérialisé. Si vous souhaitez accélérer les choses, vous devriez pouvoir insérer un index de recherche de texte dans cette colonne pour déterminer les tags associés.

[Modifier] Après avoir lu l'article d'Ali, j'ai fait quelques recherches supplémentaires et j'ai trouvé cette présentation sur un tas de approches pour la mise en place de hiérarchies dans postgres. Cela pourrait encore être utile à des fins d’explication.