I'm developing an Android application that stores some of its data as a tree like structure in an SQLite table.
As an example, the relevant part of the table has the following structure:
id | name | type | depth | parentId |
---|---|---|---|---|
1 | 1 | node | 0 | |
2 | 2 | node | 1 | 1 |
3 | 3 | node | 1 | 1 |
4 | 4 | node | 2 | 2 |
5 | 5 | node | 2 | 3 |
6 | 6 | node | 2 | 3 |
7 | 7 | node | 3 | 4 |
8 | 8 | node | 3 | 6 |
9 | ** | data | 2 | 2 |
10 | ** | data | 2 | 2 |
11 | ** | data | 3 | 4 |
12 | ** | data | 3 | 5 |
The following image represents the same data of the table:
The question is: How can I get all the nodes (type = node
) that have no data
structures below them? In the example the result would be nodes 6, 7 and 8 which are colored green in the tree.
For now, I'm only able to get empty nodes on the deepest part of the tree with the following query:
SELECT id
FROM treeTable
WHERE type = 'node'
AND id NOT IN
(SELECT DISTINCT parentId
FROM treeTable
WHERE parentId IS NOT NULL)
My problem is with that node number 6. It should be returned in the query but, as it appears as a parent of another node I don't know how to filter it out. Any ideas are welcome.
CodePudding user response:
After some research based on the @tinazmu's answer, I finally came up with a query that seems to be working fine for my case in SQLite.
WITH AncestryTree AS (
SELECT id, parentId, type
FROM Tree
WHERE parentId IS NOT NULL
UNION ALL
SELECT T.id, AT.parentId, T.type
FROM AncestryTree AT
JOIN Tree T ON AT.id = T.parentId
)
SELECT id
FROM Tree
WHERE type = 'node'
AND id NOT IN (
SELECT DISTINCT parentId
FROM AncestryTree
WHERE type = 'data'
)
The query can be tested in db-fiddle, but it'd be great if someone pointed out any flaws or optimizations to this query.
CodePudding user response:
I could use recursion to find the data nodes within each 'node' node.
with treeTable as (
select *
from (values
(1,'1','node',0,null)
,(2,'2','node',1,1)
,(3,'3','node',1,1)
,(4,'4','node',2,2)
,(5,'5','node',2,3)
,(6,'6','node',2,3)
,(7,'7','node',3,4)
,(8,'8','node',3,6)
,(9,'**','data',2,2)
,(10,'**','data',2,2)
,(11,'**','data',3,4)
,(12,'**','data',3,5)
) T(id, name, type, depth, parentId)
),
Hry as (
SELECT StartNode=TN.id, ThisNode=TN.id, TN.name, tn.type, tn.depth, L=0
FROM treeTable TN
union all
SELECT StartNode=H.StartNode, ThisNode=TN.id, TN.name, TN.type, TN.depth, L=L 1
FROM treeTable TN
inner join
Hry H
on H.ThisNode=TN.ParentId
)
/* Now repeat for each 'node' node: recursively traverse each sub-tree and see if there are data nodes underneath */
select T.id
from treeTable T
left join
Hry H
on T.id=H.StartNode
and H.type='data'
where T.type='node'
and H.StartNode is null