假设存储在数据库(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 这个任务在命令式语言中相当明显:我们只需要枚举所有结果子树中的所有“根叶”路径并将这些路径集合并。