De combien de requêtes SQL ai-je besoin?

Question

J'ai une table de base de données (sqlite) contenant des éléments qui forment une arborescence. Chaque élément a un champ id (pour lui-même) et un parentId pour son parent. Maintenant donné un article, je dois récupérer la chaîne entière de la racine à l'article.

Fondamentalement, l'algorithme pseudo-code ressemble à:

1. curseur élément
2. pour récupérer parentItem curseur par parentId
3. si parentItem n'est pas rootItem, puis curseur = parentItem et goto 2.

Je dois donc exécuter une requête SQL SELECT pour chaque élément.

Est-il possible de récupérer l'ensemble de la chaîne rootItem -> ... -> en exécutant une seule requête SQL?

Answer 1

Pas avec SQL standard ANSI ce n'est pas, non. Eh bien, ce n'est pas strictement vrai. Vous pouvez faire des jointures externes à gauche et les mettre suffisamment pour couvrir la profondeur maximale probable, mais à moins de restreindre la profondeur maximale et d'inclure autant de jointures, cela ne fonctionnera pas toujours.

Si votre jeu de lignes est suffisamment petit (disons moins de 1000), récupérez-les toutes et trouvez-les. Ce sera plus rapide que les parcours de lecture unique selon toute vraisemblance.

Vous pouvez effectuer le lot de la traversée parente. Avoir une requête comme:

SELECT t1.id id1, t1.parent parent1, 
     t2.id id2, t2.parent parent2, 
     t3.id id3, t3.parent parent3, 
     t4.id id4, t4.parent parent4, 
     t5.id id5, t5.parent parent5 
FROM mytable t1 
LEFT OUTER JOIN mytable t2 ON t1.parent = t2.id 
LEFT OUTER JOIN mytable t3 ON t2.parent = t3.id 
LEFT OUTER JOIN mytable t4 ON t3.parent = t4.id 
LEFT OUTER JOIN mytable t5 ON t4.parent = t5.id 
WHERE t1.id = 1234 

et l'étendre au nombre que vous voulez. Si le dernier parent récupéré n'est pas nul, vous n'êtes pas encore en haut de l'arbre, alors réexécutez la requête. De cette façon, vous devriez le réduire à 1-2 allers-retours. En plus de cela, vous pouvez chercher des moyens de coder ces données dans l'ID. Ce n'est pas recommandé mais si vous limitez, disons, chaque nœud à 100 enfants, vous pourriez dire que le nœud avec un ID 10030711 a un chemin de 10 -> 03 -> 07 -> 11. Cela a bien sûr d'autres problèmes (comme max ID longueur) et bien sûr, c'est hacky.

Il convient également de noter qu'il existe deux modèles de base pour les données hiérarchiques dans SQL. Listes d'adjacence et ensembles imbriqués. Votre chemin (qui est assez commun) est un ensemble d'adjacence. Les ensembles imbriqués ne seraient pas vraiment utiles avec cette situation et ils sont compliqués à faire des insertions sur.

Answer 2

Il existe de nombreuses façons créatives d'organiser des données hiérarchiques dans une base de données, mais je trouve toujours plus facile de ramener les données au format non hiérarchique, puis de faire correspondre les enregistrements parent et enfant par programme.

Montant total de l'effort: 1 requête + 1 passe programmatique dans votre jeu de données pour créer la hiérarchie.

---

approche alternative:

Je l'ai utilisé cette méthode dans le passé avec un succès limité.Vous pouvez stocker le chemin de chaque élément dans votre arbre en utilisant une colonne varchar (max) comme suit:

ID ParentID Path 
-- -------- ---- 
1  null  1/ 
2  1   1/2/ 
3  null  3/ 
4  2   1/2/4/ 
5  4   1/2/4/5/ 
6  null  6/ 
7  5   1/2/4/5/7/ 
9  5   1/2/4/5/9/ 

A partir de ce moment-là, obtenir tous les nœuds sous ID = 5 est très simple:

SELECT * 
FROM table 
WHERE Path like (SELECT Path FROM Table WHERE ID = 5) + '%' 

Answer 3

êtes-vous en mesure de changer la structure de la table? Il semblerait que le stockage des nœuds gauche et droit soit plus facile à travailler que le stockage d'un parent, car une seule sélection est possible. Voir les liens suivants:

http://www.mail-archive.com/sqlite-users@sqlite.org/msg23867.html

http://weblogs.asp.net/aghausman/archive/2009/03/16/storing-retrieving-hierarchical-data-in-sql-server-database.aspx (c'est SQLServer, mais ils ont un diagramme qui pourrait aider.)