将邻接列表层次结构展平为所有路径的列表 [英] Flatten Adjacency List Hierarchy To A List Of All Paths
问题描述
我有一个表，该表使用邻接表模型存储层次结构信息. (使用以下示例中的自引用密钥.此表可能看起来熟悉):
I have a Table that stores Hierarchical information using the Adjacency List model. (uses a self referential key - example below. This Table may look familiar):
category_id name parent
----------- -------------------- -----------
1 ELECTRONICS NULL
2 TELEVISIONS 1
3 TUBE 2
4 LCD 2
5 PLASMA 2
6 PORTABLE ELECTRONICS 1
7 MP3 PLAYERS 6
8 FLASH 7
9 CD PLAYERS 6
10 2 WAY RADIOS 6
将上述数据平整"为类似内容的最佳方法是什么?
category_id lvl1 lvl2 lvl3 lvl4
----------- ----------- ----------- ----------- -----------
1 1 NULL NULL NULL
2 1 2 NULL NULL
6 1 6 NULL NULL
3 1 2 3 NULL
4 1 2 4 NULL
5 1 2 5 NULL
7 1 6 7 NULL
9 1 6 9 NULL
10 1 6 10 NULL
8 1 6 7 8
每行是通过层次结构的一个路径"，除了每个每个节点(不仅仅是每个叶节点)的行. category_id列表示当前节点，而"lvl"列是其祖先.当前节点的值也必须在最右边的lvl列中. lvl1列中的值将始终代表根节点，lvl2中的值将始终代表lvl1的直接后代，依此类推.
Each row is one "Path" through the Hierarchy, except there is a row for each node (not just each leaf node). The category_id column represents the current node and the "lvl" columns are its ancestors. The value for the current node must also be in the farthest right lvl column. The value in the lvl1 column will always represent the root node, values in lvl2 will always represent direct descendants of lvl1, and so on.
如果可能的话，生成此输出的方法将是SQL，并且适用于n层层次结构.
If possible the method to generate this output would be in SQL, and would work for n-tier hierarchies.
推荐答案
要在一个简单的邻接表中进行多级查询，总是涉及到自左联接.制作右对齐表很容易:
To do multi-level queries across a simple adjacency-list invariably involves self-left-joins. It's easy to make a right-aligned table:
SELECT category.category_id,
ancestor4.category_id AS lvl4,
ancestor3.category_id AS lvl3,
ancestor2.category_id AS lvl2,
ancestor1.category_id AS lvl1
FROM categories AS category
LEFT JOIN categories AS ancestor1 ON ancestor1.category_id=category.category_id
LEFT JOIN categories AS ancestor2 ON ancestor2.category_id=ancestor1.parent
LEFT JOIN categories AS ancestor3 ON ancestor3.category_id=ancestor2.parent
LEFT JOIN categories AS ancestor4 ON ancestor4.category_id=ancestor3.parent;
像您的示例一样将其左对齐比较棘手.这想到了:
To left-align it like your example is a bit more tricky. This comes to mind:
SELECT category.category_id,
ancestor1.category_id AS lvl1,
ancestor2.category_id AS lvl2,
ancestor3.category_id AS lvl3,
ancestor4.category_id AS lvl4
FROM categories AS category
LEFT JOIN categories AS ancestor1 ON ancestor1.parent IS NULL
LEFT JOIN categories AS ancestor2 ON ancestor1.category_id<>category.category_id AND ancestor2.parent=ancestor1.category_id
LEFT JOIN categories AS ancestor3 ON ancestor2.category_id<>category.category_id AND ancestor3.parent=ancestor2.category_id
LEFT JOIN categories AS ancestor4 ON ancestor3.category_id<>category.category_id AND ancestor4.parent=ancestor3.category_id
WHERE
ancestor1.category_id=category.category_id OR
ancestor2.category_id=category.category_id OR
ancestor3.category_id=category.category_id OR
ancestor4.category_id=category.category_id;
适用于n层层次结构.
would work for n-tier hierarchies.
抱歉，在邻接表模型中无法进行任意深度的查询.如果您经常执行这种查询，则应将架构更改为
Sorry, arbitrary-depth queries are not possible in the adjacency-list model. If you are doing this kind of query a lot, you should change your schema to one of the other models of storing hierarchical information: full adjacency relation (storing all ancestor-descendent relationships), materialised path, or nested sets.
如果类别变化不大(通常是像您的示例那样的商店)，那么我倾向于使用嵌套集.
If the categories don't move around a lot (which is usually the case for a store like your example), I would tend towards nested sets.
这篇关于将邻接列表层次结构展平为所有路径的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
