Хранение и запрос иерархических данных с несколькими родительскими узлами - PullRequest
Новая
       26

Хранение и запрос иерархических данных с несколькими родительскими узлами

5 голосов
/ 27 августа 2010

Я довольно много искал, но не смог найти много ресурсов по этой теме. Моя цель состоит в том, чтобы хранить данные планирования, как вы бы нашли на диаграмме Ганта. Так что одним из примеров хранения данных может быть: 

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

Который должен был бы выполнить задачу C, ожидающую выполнения задачи A и B.

Итак, мой вопрос: как лучше всего хранить данные такого рода и эффективно запрашивать их? Какие-нибудь хорошие ресурсы для такого рода вещей? Существует масса информации о древовидных структурах, но как только вы добавляете несколько родителей, становится трудно найти информацию. Кстати, я работаю с SQL Server и .NET для этой задачи.

Ответы [ 3 ]

2 голосов
/ 27 августа 2010

Ваша проблема связана с понятием кардинальности отношений.Все отношения имеют некоторую мощность, которая выражает потенциальное число экземпляров на каждой стороне отношения, которые являются его членами или могут участвовать в одном экземпляре отношения.Например, для людей (для большинства живых существ, я полагаю, за редкими исключениями) отношение родителей и детей имеет кардинальное значение 2 to zero or many, что означает, что для родительской стороны требуется два родителя, и может быть ноль илимногие дети (возможно, это должно быть 2 to 1 or many)

В дизайне базы данных, как правило, все, что имеет 1 (один), (или ноль или один) на одной стороне, может быть легко представлено только двумятаблицы, по одной для каждой сущности (иногда требуется только одна таблица, см. примечание **) и столбец внешнего ключа в таблице, представляющий сторону «многие», который указывает на другую таблицу, содержащую сущность на стороне «один».

В вашем случае у вас есть many to many отношения.(Задача может иметь несколько предшественников, и каждый предшественник, безусловно, может быть предшественником для нескольких задач). В этом случае требуется третья таблица, где каждая строка, по сути, представляет связь между двумя задачами, представляя, что одна является предшественницейДругой.Как правило, эта таблица предназначена для того, чтобы содержать только все столбцы первичных ключей двух родительских таблиц, а ее собственный первичный ключ представляет собой совокупность всех столбцов в обоих родительских первичных ключах.В вашем случае он просто имеет два столбца, taskId и PredecessorTaskId, и эта пара идентификаторов должна быть уникальной в таблице, чтобы вместе они образовывали составной PK.

При запросах, чтобы избежать двойного подсчета столбцов данныхв родительских таблицах, когда есть несколько объединений, просто основывайте запрос на родительской таблице ... например, чтобы найти продолжительность самого длинного родителя, предполагая, что ваша таблица ассоциации называется TaskPredecessor 

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

**НОТА.В тех случаях, когда оба объекта в отношении имеют один и тот же тип объекта, они оба могут находиться в одной и той же таблице.Каноническим примером (luv that word) является таблица сотрудников с отношением «многие к одному» между работником и руководителем ... Поскольку руководитель также является сотрудником, как работники, так и руководители могут быть в одной таблице [Сотрудник] и в сфере отношенийМожно смоделировать с помощью внешнего ключа (называемого, скажем, SupervisorId), который указывает на другую строку в той же таблице и содержит идентификатор записи сотрудника для руководителя этого сотрудника.

2 голосов
/ 27 августа 2010

Использовать модель списка смежностей: 

chain

task_id  predecessor
3        1
3        2

и этот запрос, чтобы найти всех предшественников данной задачи: 

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

Чтобы получить продолжительность самого длинного родителя для каждой задачи:

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
1 голос
/ 27 августа 2010

Проверьте шаблон «Иерархический взвешенный итог» в книге «Шаблоны проектирования SQL» или раздел «Спецификация» в «Деревья и иерархии в SQL».

Одним словом, графики характеризуются двойной агрегацией. Вы выполняете один вид агрегации по узлам в каждом пути, а другой - по альтернативным путям. Например, найти минимальное расстояние между двумя узлами является минимальным по суммированию. Иерархический взвешенный суммарный запрос (он же спецификация) представляет собой умножение величин по каждому пути и суммирование по каждому альтернативному пути: 

     
       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
...