Using Recursive Common table expressions to represent Tree structures
to Table Using Tree Common Expressions recursive
2023-09-27 14:26:39 时间
http://www.postgresonline.com/journal/archives/131-Using-Recursive-Common-table-expressions-to-represent-Tree-structures.html
Tree Problem and was based on PostgreSQL 7.4 technology.
We'll repeat the text here for completeness and demonstrate the PostgreSQL 8.4 that solves this and more efficiently.
The Problem
Below is what the structure of your table looks like.
si_id int, si_parentid int, si_item. In your table are the following entries
Solution
Suppose you are tracking supplies and have a field called si_item and another called si_parentid. The parent keeps track of what subclass a supply item belongs to. E.g. you have paper parent that has subclasses such as recycled, non-recycled. When someone takes supplies, you want to return the fully qualified name e.g. Paper->Recycled->20 Lb
Below is what the structure of your table looks like.
si_id int, si_parentid int, si_item. In your table are the following entries
si_id | si_parentid | si_item |
---|---|---|
1 | Paper | |
2 | 1 | Recycled |
3 | 2 | 20 lb |
4 | 2 | 40 lb |
5 | 1 | Non-Recycled |
6 | 5 | 20 lb |
7 | 5 | 40 lb |
8 | 5 | Scraps |
Solution
CREATE TABLE supplyitem(si_id integer PRIMARY KEY, si_parentid integer, si_item varchar(100));
--load up the table (multirow constructor introduced in 8.2)
INSERT INTO supplyitem(si_id,si_parentid, si_item)
VALUES (1, NULL, 'Paper'),
(2,1, 'Recycled'),
(3,2, '20 lb'),
(4,2, '40 lb'),
(5,1, 'Non-Recycled'),
(6,5, '20 lb'),
(7,5, '40 lb'),
(8,5, 'Scraps');
--Recursive query (introduced in 8.4 returns fully qualified name)
WITH RECURSIVE supplytree AS
(SELECT si_id, si_item, si_parentid, CAST(si_item As varchar(1000)) As si_item_fullname
FROM supplyitem
WHERE si_parentid IS NULL
UNION ALL
SELECT si.si_id,si.si_item,
si.si_parentid,
CAST(sp.si_item_fullname || '->' || si.si_item As varchar(1000)) As si_item_fullname
FROM supplyitem As si
INNER JOIN supplytree AS sp
ON (si.si_parentid = sp.si_id)
)
SELECT si_id, si_item_fullname
FROM supplytree
ORDER BY si_item_fullname;
Result looks like
si_id | si_item_fullname ------+----------------------------- 1 | Paper 5 | Paper->Non-Recycled 6 | Paper->Non-Recycled->20 lb 7 | Paper->Non-Recycled->40 lb 8 | Paper->Non-Recycled->Scraps 2 | Paper->Recycled 3 | Paper->Recycled->20 lb 4 | Paper->Recycled->40 lb
Comments
Display comments as
(Linear | Threaded)
Great topic!
A couple of observations:
* Unless the length 1000 has some significance, use TEXT instead of
VARCHAR(1000).
* It might well be both faster and more correct to push items into an array
and use array_to_string() in the outer SELECT, and it won't be subject to
sorting anomalies.
WITH RECURSIVE supplytree AS
(
SELECT
si_id,
si_item,
si_parentid,
ARRAY[si_item] AS si_item_array
FROM supplyitem
WHERE si_parentid IS NULL
UNION ALL
SELECT
si.si_id,si.si_item,
si.si_parentid,
sp.si_item_array || si.si_item As si_item_array
FROM
supplyitem As si
JOIN
supplytree AS sp
ON (si.si_parentid = sp.si_id)
)
SELECT
si_id,
array_to_string(si_item_array, '->') AS si_item_fullname
FROM supplytree
ORDER BY si_item_array;
A couple of observations:
* Unless the length 1000 has some significance, use TEXT instead of
VARCHAR(1000).
* It might well be both faster and more correct to push items into an array
and use array_to_string() in the outer SELECT, and it won't be subject to
sorting anomalies.
WITH RECURSIVE supplytree AS
(
SELECT
si_id,
si_item,
si_parentid,
ARRAY[si_item] AS si_item_array
FROM supplyitem
WHERE si_parentid IS NULL
UNION ALL
SELECT
si.si_id,si.si_item,
si.si_parentid,
sp.si_item_array || si.si_item As si_item_array
FROM
supplyitem As si
JOIN
supplytree AS sp
ON (si.si_parentid = sp.si_id)
)
SELECT
si_id,
array_to_string(si_item_array, '->') AS si_item_fullname
FROM supplytree
ORDER BY si_item_array;
Have thought about using ltree ?
http://www.postgresql.org/docs/current/static/ltree.html
I'am not saying than WITH RECURSIVE is bad .. just that, there are simpler solution sometimes ;-)
http://www.postgresql.org/docs/current/static/ltree.html
I'am not saying than WITH RECURSIVE is bad .. just that, there are simpler solution sometimes ;-)
Good point. We haven't explored the use of ltree so
will have to give it a test drive sometime. I think the only thing
against it is that its a PostgreSQL specific feature where as the CTE is
more ANSI portable (except for possiblyt the word RECURSIVE)
How do you use it to find the parent path for just a single item?
Sabra,
Couple of ways -- you could write a function as we demonstrated in linked article, but that is not as suitable for multiple sets since it would probably do a subquery for each record.
You coulde also take our example and limit with a WHERE clause but that is much slower than it could be.
The other way would be to recurse backward from the child to the parent. So instead of starting at parent nodes -- you start at the child node and keep on unioning until you hit a parent with no parent. Will have to write that up sometime.
Couple of ways -- you could write a function as we demonstrated in linked article, but that is not as suitable for multiple sets since it would probably do a subquery for each record.
You coulde also take our example and limit with a WHERE clause but that is much slower than it could be.
The other way would be to recurse backward from the child to the parent. So instead of starting at parent nodes -- you start at the child node and keep on unioning until you hit a parent with no parent. Will have to write that up sometime.
many thanks for this great example.i implemented the child to parent recursion in case someone needs it:
--Recursive query (introduced in 8.4 returns fully qualified name)
WITH RECURSIVE supplytree AS
(SELECT si_id, si_item, si_parentid, CAST(si_item As varchar(1000)) As si_item_fullname
FROM supplyitem
WHERE si_item in( '40 lb')
UNION ALL
SELECT si.si_id,si.si_item,
si.si_parentid,
CAST(si.si_item || '->' || sp.si_item_fullname As varchar(1000)) As si_item_fullname
FROM supplyitem As si
INNER JOIN supplytree AS sp
ON (si.si_id = sp.si_parentid)
)
SELECT si_id, si_item_fullname
FROM supplytree where si_parentid is null
ORDER BY si_item_fullname;
--Recursive query (introduced in 8.4 returns fully qualified name)
WITH RECURSIVE supplytree AS
(SELECT si_id, si_item, si_parentid, CAST(si_item As varchar(1000)) As si_item_fullname
FROM supplyitem
WHERE si_item in( '40 lb')
UNION ALL
SELECT si.si_id,si.si_item,
si.si_parentid,
CAST(si.si_item || '->' || sp.si_item_fullname As varchar(1000)) As si_item_fullname
FROM supplyitem As si
INNER JOIN supplytree AS sp
ON (si.si_id = sp.si_parentid)
)
SELECT si_id, si_item_fullname
FROM supplytree where si_parentid is null
ORDER BY si_item_fullname;
Great example for recursive CTE. Very useful. Thanks!
this is most easy
table tema
-field tema_id (is the identificator)
-field nombre (is the name)
-field padre_id (is the parent id)
WITH RECURSIVE tema_tree AS (
SELECT tema_id, nombre, padre_id, nombre||'' full_name
FROM tema
WHERE padre_id IS NULL
UNION ALL
SELECT t.tema_id, t.nombre, t.padre_id, tt.full_name||' -> '||t.nombre full_name
FROM tema t
JOIN tema_tree tt ON t.padre_id = tt.tema_id
)
SELECT tema_id, full_name
FROM tema_tree
ORDER BY 2
table tema
-field tema_id (is the identificator)
-field nombre (is the name)
-field padre_id (is the parent id)
WITH RECURSIVE tema_tree AS (
SELECT tema_id, nombre, padre_id, nombre||'' full_name
FROM tema
WHERE padre_id IS NULL
UNION ALL
SELECT t.tema_id, t.nombre, t.padre_id, tt.full_name||' -> '||t.nombre full_name
FROM tema t
JOIN tema_tree tt ON t.padre_id = tt.tema_id
)
SELECT tema_id, full_name
FROM tema_tree
ORDER BY 2
相关文章
- vcenter提示连不上cannot connect to vcenter single sign-on server 7444/sts/stsservice/vsphere.local
- nginx的buffered to a temporary警告
- Mysql-报错:1130-host ... is not allowed to connect to this MySql server 开放mysql远程连接 不使用localhost
- Each record in table should have a unique `key` prop,or set `rowKey` to an unique primary key.
- migration to end point routing
- elasticsearch配置文件里的一些坑 [Failed to load settings from [elasticsearch.yml]]
- How to apply Local Group Policy settings silently using the ImportRegPol.exe and Apply_LGPO_Delta.exe utilities.
- SELECT command denied to user 'username'@'ip' for table 'user'错误处理
- mysqlworkbench 执行update语句报错:You are using safe update mode and you tried to update a table without a WHERE that uses a KEY column
- The Definitive Guide To Django 2 学习笔记(三) URLconfs 和松耦合
- 解决 spring-test 出现 Failed to load ApplicationContext 的异常
- ORA-01779: cannot modify a column which maps to a non-key-preserved table
- 已解决TypeError: only integer scalar arrays can be converted to a scalar index
- How to Plan and Configure YARN and MapReduce 2 in HDP 2.0
- How to add a button in the seletions "More"
- Eclipse项目修改编译jdk版本(Failed to read candidate component class: file 处理)
- How To Run Docker in Docker Container [3 Easy Methods]
- [LeetCode] 13. Roman to Integer 罗马数字转为整数
- 我的Android进阶之旅------>解决Error:Unable to find method 'org.gradle.api.internal.project.ProjectInternal.g
This post was mentioned on Twitter by roblb: Using Recursive Common table expressions to represent Tree structures: A very long time ago, we wrote .. http://bit.ly/Flne3 #postgres
Tracked: Jan 04, 21:19
Tracked: Aug 20, 00:58