Stockage et interrogation de données hiérarchiques avec plusieurs nœuds parents

Question

J'ai effectué pas mal de recherches, mais je n'ai pas trouvé beaucoup de ressources sur le sujet. Mon but est de stocker les données de planification comme vous le feriez dans un diagramme de Gantt. Ainsi, un exemple de stockage des données pourrait être:

Task Id | Name | Duration 
1   Task A 1 
2   Task B 3 
3   Task C 2 

Task Id | Predecessors 
1   Null 
2   Null 
3   1 
3   2 

qui aurait la tâche C attente pour les tâches A et B pour terminer la tâche. Donc, ma question est: Quelle est la meilleure façon de stocker ce type de données et efficacement l'interroger? De bonnes ressources pour ce genre de chose? Il y a une tonne d'informations sur les structures arborescentes, mais une fois que vous ajoutez plusieurs parents, il devient difficile de trouver des informations. En passant, je travaille avec SQL Server et .NET pour cette tâche.

Answer 1

Votre problème est lié au concept de cardinalité des relations. Toutes les relations ont une certaine cardinalité, qui exprime le nombre potentiel d'instances de chaque côté de la relation qui en sont membres, ou peut participer à une instance unique de la relation. Par exemple, pour les personnes, (à part de rares exceptions), la relation Parent-Enfant a une cardinalité de 2 to zero or many, ce qui signifie qu'il faut deux parents du côté parent, et qu'il peut y avoir zéro ou plusieurs enfants (En général, tout ce qui a un 1 (un), (ou un zéro ou un) d'un côté peut être facilement représenté avec seulement deux tables, une pour chaque entité (en général, 2 to 1 or many)

, (parfois seule une table est nécessaire voir note **) et une colonne de clé étrangère dans la table représentant le côté "many", qui pointe vers l'autre table contenant l'entité du côté "un". Dans votre cas, vous avez une relation many to many. (Une tâche peut avoir plusieurs prédécesseurs, et chaque prédécesseur peut certainement être le prédécesseur de plusieurs tâches) Dans ce cas, une troisième table est nécessaire, où chaque ligne représente effectivement une association entre deux tâches, représentant celle qui est le prédécesseur de la tâche. autre. Généralement, cette table est conçue pour contenir uniquement toutes les colonnes des clés primaires des deux tables parentes et sa propre clé primaire est un composite de toutes les colonnes dans les deux clés primaires parentes. Dans votre cas, il a simplement deux colonnes, le taskId, et le PredecessorTaskId, et cette paire d'identifiants doit être unique dans la table afin qu'ils forment ensemble le PK composite. Lors de l'interrogation, pour éviter le double comptage des colonnes de données dans les tables parentes lorsqu'il existe plusieurs jointures, basez simplement la requête sur la table parente ... par exemple, pour trouver la durée du parent le plus long, En supposant votre table d'association est nommé TaskPredecessor

Select TaskId, Max(P.Duration) 
    From Task T Join Task P 
    On P.TaskId In (Select PredecessorId 
        From TaskPredecessor 
        Where TaskId = T.TaskId) 

** REMARQUE. Dans les cas où les deux entités de la relation appartiennent au même type d'entité, elles peuvent toutes deux être dans la même table. L'exemple canonique (luv ce mot) est une table d'employés avec la relation plusieurs à un de travailleur à superviseur ...Puisque le superviseur est également un employé, les employés et les superviseurs peuvent être dans la même table [Employee], et la realtionship peut être modélisée avec une clé étrangère (appelée par exemple SupervisorId) qui pointe vers une autre ligne dans la même table et contient l'ID du dossier de l'employé pour le superviseur de cet employé.

Answer 2

Utiliser le modèle de liste contiguïté:

chain 

task_id predecessor 
3  1 
3  2 

et cette requête pour trouver tous les prédécesseurs de la tâche donnée:

WITH q AS 
     (
     SELECT predecessor 
     FROM chain 
     WHERE task_id = 3 
     UNION ALL 
     SELECT c.predecessor 
     FROM q 
     JOIN chain c 
     ON  c.task_id = q.predecessor 
     ) 
SELECT * 
FROM q 

Pour obtenir la durée de la plus longue parent pour chaque tâche:

WITH q AS 
     (
     SELECT task_id, duration 
     FROM tasks 
     UNION ALL 
     SELECT t.task_id, t.duration 
     FROM q 
     JOIN chain с 
     ON  c.task_id = q.task_id 
     JOIN tasks t 
     ON  t.task_id = c.predecessor 
     ) 
SELECT task_id, MAX(duration) 
FROM q 

Answer 3

Cochez la case "Total hiérarchique pondéré" dans le livre "Modèles de conception SQL" ou la section "Nomenclature" dans "Arbres et hiérarchies dans SQL".

En un mot, les graphiques comportent une double agrégation. Vous faites une sorte d'agrégation le long des nœuds dans chaque chemin, et une autre à travers les chemins alternatifs. Par exemple, trouver une distance minimale entre les deux nœuds est minimum sur sommation. La requête totale pondérée hiérarchique (alias Bill of Materials) est la multiplication des quantités le long de chaque chemin et la sommation le long de chaque chemin alternatif:

  
     with TCAssembly as (
      select Part, SubPart, Quantity AS factoredQuantity 
      from AssemblyEdges 
      where Part = ‘Bicycle’ 
      union all 
      select te.Part, e.SubPart, e.Quantity * te.factoredQuantity 
      from TCAssembly te, AssemblyEdges e 
      where te.SubPart = e.Part 
     ) select SubPart, sum(Quantity) from TCAssembly 
     group by SubPart