代码之家 › 专栏 › 技术社区 › Ocelot20

存储和查询具有多个父节点的体系结构数据

data-structures database-design database sql

Ocelot20 · 技术社区 · 14 年前

我已经做了相当多的搜索,但还没有找到很多关于这个主题的资源。我的目标是像在甘特图中一样存储计划数据。因此,存储数据的一个示例可能是:

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 回复 | 直到 14 年前

Charles Bretana 14 年前

您的问题与关系基数的概念有关。所有关系都有一些基数,它们表示关系每一端作为其成员或可以参与关系的单个实例的潜在实例数。作为一个例子,对于人来说(我猜,对于大多数生物,除了极少数例外),亲子关系的基数是 2 to zero or many 也就是说,这需要父母两个在一起,并且可以有零个或多个孩子(也许应该是 2 to 1 or many )

在数据库设计中,通常情况下,任何一侧具有1(一)、(或0或1)的表都可以很容易地用两个表来表示,每个实体一个表(有时只需要一个表,请参见注释**)和表中表示“多”侧的外键列来表示,这些表指向另一个将实体保存在“一”侧的表。

在你的情况下,你有一个 many to many 关系。(一个任务可以有多个前置任务,每个前置任务当然可以是多个任务的前置任务)在这种情况下,需要第三个表,其中每一行有效地表示两个任务之间的关联,表示一个任务是另一个任务的前置任务。通常,此表被设计为只包含两个父表的主键的所有列,它自己的主键是两个父主键中所有列的组合。在您的例子中,它只是有两列,taskid和predestortaskid,这对id在表中应该是唯一的,所以它们一起构成了复合pk。

查询时,为了避免在有多个联接时对父表中的数据列进行重复计数,只需将查询基于父表…例如,要查找最长父级的持续时间, 假设您的关联表名为taskprevious

  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)示例是一个雇员表,其中包含工人与主管之间的多对一关系…由于主管也是雇员,因此工人和主管都可以在同一个[雇员]表中,并且关系可以使用指向同一表中另一行并包含该雇员主管的雇员记录ID的外键(称为supervisor id)建模。

Quassnoi 14 年前

使用邻接列表模型:

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

Tegiri Nenashi 14 年前

检查“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