0

假设存储在数据库(MS SQL Server)中的树具有以下结构

CREATE TABLE Nodes(
   NodeId int PRIMARY KEY, 
   NodeValue varchar(50));

CREATE TABLE Adjacencies(
   ParentId int REFERENCES Nodes(NodeId), 
   -- every adjacence is unique for specified child node
   ChildId int PRIMARY KEY REFERENCES Nodes(NodeId), 
   Weight int);

现在我们有一个表Foo,它使用了这棵树中的值(具有多对多关系)

CREATE TABLE Foo(FooId int PRIMARY KEY);
CREATE TABLE Foo_Nodes(
   FooId int REFERENCES Foo(FooId), 
   NodeId int REFERENCES Nodes(NodeId),
   CONSTRAINT PK_Foo_Nodes PRIMARY KEY (FooId,NodeId))

现在对于指定的FooId,我们有树节点的子集(在FooNodes表中),我们的任务是从这个子集中找到所有“根叶”路径(这个子集不需要仍然是树,而是子树的集合)。

有没有最好的方法使用 SQL 语法来做到这一点?

例如,路径的结果表{{1,2,3}, {1,4}, {5,6}, {9}}可以具有这样的结构

PathId    NodeId    Level
---------------------------
1         1         1       |
1         2         2       | first path
1         3         3       |
2         1         1           | second path
2         4         2           |
3         5         1                | third path
3         6         2                |
4         9         1                      | fourth path

PS 这个任务在命令式语言中相当明显:我们只需要枚举所有结果子树中的所有“根叶”路径并将这些路径集合并。

4

0 回答 0