Re: [sqlite] CTE to Get Path In a Tree
Thanks, that works perfect indeed. RBS On Tue, May 14, 2019 at 3:23 AM Keith Medcalf wrote: > > That should of course be: > > with folderpath(id, rightmost_folder_id, parent_id, path, rank) > as ( > select id, id, parent_id, name, rank > from folders > union all > select f.id, fp.rightmost_folder_id, f.parent_id, f.name || '/' || > fp.path, fp.rank > from folders f > join folderpath fp > on f.id == fp.parent_id > ) > select rightmost_folder_id, path > from folderpath >where id == 1 > order by rank; > > to propogate the rightmost_folder_id from the rightmost (first) folders > tuple ... > > --- > The fact that there's a Highway to Hell but only a Stairway to Heaven says > a lot about anticipated traffic volume. > > > >-Original Message- > >From: sqlite-users [mailto:sqlite-users- > >boun...@mailinglists.sqlite.org] On Behalf Of Keith Medcalf > >Sent: Monday, 13 May, 2019 19:46 > >To: SQLite mailing list > >Subject: Re: [sqlite] CTE to Get Path In a Tree > > > > > >Assuming "right folder id" is short-hand for "the id of the rightmost > >folder" ... > > > >with folderpath(id, rightmost_folder_id, parent_id, path, rank) > > as ( > > select id, rightmost_folder_id, parent_id, name, rank > >from folders > > union all > > select f.id, rightmost_folder_id, f.parent_id, f.name || '/' || > >fp.path, fp.rank > >from folders f > >join folderpath fp > > on (f.id == fp.parent_id) > > ) > > select rightmost_folder_id, path > >from folderpath > > where id == 1 > >order by rank; > > > >--- > >The fact that there's a Highway to Hell but only a Stairway to Heaven > >says a lot about anticipated traffic volume. > > > >>-Original Message- > >>From: sqlite-users [mailto:sqlite-users- > >>boun...@mailinglists.sqlite.org] On Behalf Of Bart Smissaert > >>Sent: Monday, 13 May, 2019 15:22 > >>To: SQLite mailing list > >>Subject: Re: [sqlite] CTE to Get Path In a Tree > >> > >>Have the same table structure to represent a folder tree: > >> > >>CREATE TABLE FOLDERS([ID] INTEGER PRIMARY KEY, [PARENT_ID] INTEGER, > >>[NAME] > >>TEXT, [LEVEL] INTEGER, [RANK] TEXT) > >> > >>Data is as follows: > >> > >>ID PARENT_ID NAME LEVEL RANK > >> > >- > >>-- > >>1 0 Main 0 0 > >>2 1 Diabetic audit 1 01-02 > >>3 1 GROUP BY 1 01-03 > >>4 1 x 1 01-04 > >>8 1 Common 1 01-08 > >>9 3 zzz 2 01-03-09 > >>10 9 yyy 3 01-03-09-10 > >> > >>Now I would like the following output: > >>In first column the ID of the folder and in the second column the > >>full path > >>of that folder. > >> > >>This will give the right ID's and the right folders in the right > >>order by > >>doesn't give the full path: > >> > >>select f.id, f.name as name from folders f where f.id in > >>(with recursive branch(id) as (select id from folders where id = 1 > >>union all > >>select f.id from folders f inner join branch b on(f.parent_id = > >>b.id)) > >>select id from branch) > >>order by rank > >> > >>This will give the right full paths in the right order but doesn't > >>give me > >>the right folder ID (1 for all rows): > >> > >>with recursive folderpath(id, parent_id, path, rank) as > >>(select id, parent_id, name, rank from folders > >>union all > >>select f.id, f.parent_id, f.name || '/' || fp.path, fp.rank from > >>folders f > >>inner join folderpath fp on (f.id = fp.parent_id)) > >>select id, path from folderpath where id = 1 order by rank > >> > >>How do I get the right folder ID and the full paths? > >> > >>RBS > >> > >>On Sun, May 12, 2019 at 1:15 PM Igor Tandetnik > >>wrote: > >> > >>> On 5/12/2019 6:19 AM, Philip Bennefall wrote: > >>> > Hi everyone, > >>> > > >>> > I have a tree of folders and I want to find the complete path > >>from any > >>
Re: [sqlite] CTE to Get Path In a Tree
That should of course be: with folderpath(id, rightmost_folder_id, parent_id, path, rank) as ( select id, id, parent_id, name, rank from folders union all select f.id, fp.rightmost_folder_id, f.parent_id, f.name || '/' || fp.path, fp.rank from folders f join folderpath fp on f.id == fp.parent_id ) select rightmost_folder_id, path from folderpath where id == 1 order by rank; to propogate the rightmost_folder_id from the rightmost (first) folders tuple ... --- The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume. >-Original Message- >From: sqlite-users [mailto:sqlite-users- >boun...@mailinglists.sqlite.org] On Behalf Of Keith Medcalf >Sent: Monday, 13 May, 2019 19:46 >To: SQLite mailing list >Subject: Re: [sqlite] CTE to Get Path In a Tree > > >Assuming "right folder id" is short-hand for "the id of the rightmost >folder" ... > >with folderpath(id, rightmost_folder_id, parent_id, path, rank) > as ( > select id, rightmost_folder_id, parent_id, name, rank >from folders > union all > select f.id, rightmost_folder_id, f.parent_id, f.name || '/' || >fp.path, fp.rank >from folders f >join folderpath fp > on (f.id == fp.parent_id) > ) > select rightmost_folder_id, path >from folderpath > where id == 1 >order by rank; > >--- >The fact that there's a Highway to Hell but only a Stairway to Heaven >says a lot about anticipated traffic volume. > >>-Original Message- >>From: sqlite-users [mailto:sqlite-users- >>boun...@mailinglists.sqlite.org] On Behalf Of Bart Smissaert >>Sent: Monday, 13 May, 2019 15:22 >>To: SQLite mailing list >>Subject: Re: [sqlite] CTE to Get Path In a Tree >> >>Have the same table structure to represent a folder tree: >> >>CREATE TABLE FOLDERS([ID] INTEGER PRIMARY KEY, [PARENT_ID] INTEGER, >>[NAME] >>TEXT, [LEVEL] INTEGER, [RANK] TEXT) >> >>Data is as follows: >> >>ID PARENT_ID NAME LEVEL RANK >> >- >>-- >>1 0 Main 0 0 >>2 1 Diabetic audit 1 01-02 >>3 1 GROUP BY 1 01-03 >>4 1 x 1 01-04 >>8 1 Common 1 01-08 >>9 3 zzz 2 01-03-09 >>10 9 yyy 3 01-03-09-10 >> >>Now I would like the following output: >>In first column the ID of the folder and in the second column the >>full path >>of that folder. >> >>This will give the right ID's and the right folders in the right >>order by >>doesn't give the full path: >> >>select f.id, f.name as name from folders f where f.id in >>(with recursive branch(id) as (select id from folders where id = 1 >>union all >>select f.id from folders f inner join branch b on(f.parent_id = >>b.id)) >>select id from branch) >>order by rank >> >>This will give the right full paths in the right order but doesn't >>give me >>the right folder ID (1 for all rows): >> >>with recursive folderpath(id, parent_id, path, rank) as >>(select id, parent_id, name, rank from folders >>union all >>select f.id, f.parent_id, f.name || '/' || fp.path, fp.rank from >>folders f >>inner join folderpath fp on (f.id = fp.parent_id)) >>select id, path from folderpath where id = 1 order by rank >> >>How do I get the right folder ID and the full paths? >> >>RBS >> >>On Sun, May 12, 2019 at 1:15 PM Igor Tandetnik >>wrote: >> >>> On 5/12/2019 6:19 AM, Philip Bennefall wrote: >>> > Hi everyone, >>> > >>> > I have a tree of folders and I want to find the complete path >>from any >>> arbitrary point back to the top level directory. The schema is: >>> > >>> > CREATE TABLE IF NOT EXISTS folders( >>> > id INTEGER PRIMARY KEY, >>> > parentFolderId INTEGER REFERENCES folders(id) ON DELETE >>CASCADE ON >>> UPDATE CASCADE, >>> > name TEXT NOT NULL); >>> > >>> > I made the following CTE: >>> > >>> > WITH RECURSIVE folderTree (id, path) >>> > AS(SELECT id, name FROM folders WHERE parentFolderId IS NULL >>> > UNION ALL >>> > SELECT folders.id, folderTree.path || '/' || folders.name >>> > FROM folders
Re: [sqlite] CTE to Get Path In a Tree
Assuming "right folder id" is short-hand for "the id of the rightmost folder" ... with folderpath(id, rightmost_folder_id, parent_id, path, rank) as ( select id, rightmost_folder_id, parent_id, name, rank from folders union all select f.id, rightmost_folder_id, f.parent_id, f.name || '/' || fp.path, fp.rank from folders f join folderpath fp on (f.id == fp.parent_id) ) select rightmost_folder_id, path from folderpath where id == 1 order by rank; --- The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume. >-Original Message- >From: sqlite-users [mailto:sqlite-users- >boun...@mailinglists.sqlite.org] On Behalf Of Bart Smissaert >Sent: Monday, 13 May, 2019 15:22 >To: SQLite mailing list >Subject: Re: [sqlite] CTE to Get Path In a Tree > >Have the same table structure to represent a folder tree: > >CREATE TABLE FOLDERS([ID] INTEGER PRIMARY KEY, [PARENT_ID] INTEGER, >[NAME] >TEXT, [LEVEL] INTEGER, [RANK] TEXT) > >Data is as follows: > >ID PARENT_ID NAME LEVEL RANK >- >-- >1 0 Main 0 0 >2 1 Diabetic audit 1 01-02 >3 1 GROUP BY 1 01-03 >4 1 x 1 01-04 >8 1 Common 1 01-08 >9 3 zzz 2 01-03-09 >10 9 yyy 3 01-03-09-10 > >Now I would like the following output: >In first column the ID of the folder and in the second column the >full path >of that folder. > >This will give the right ID's and the right folders in the right >order by >doesn't give the full path: > >select f.id, f.name as name from folders f where f.id in >(with recursive branch(id) as (select id from folders where id = 1 >union all >select f.id from folders f inner join branch b on(f.parent_id = >b.id)) >select id from branch) >order by rank > >This will give the right full paths in the right order but doesn't >give me >the right folder ID (1 for all rows): > >with recursive folderpath(id, parent_id, path, rank) as >(select id, parent_id, name, rank from folders >union all >select f.id, f.parent_id, f.name || '/' || fp.path, fp.rank from >folders f >inner join folderpath fp on (f.id = fp.parent_id)) >select id, path from folderpath where id = 1 order by rank > >How do I get the right folder ID and the full paths? > >RBS > >On Sun, May 12, 2019 at 1:15 PM Igor Tandetnik >wrote: > >> On 5/12/2019 6:19 AM, Philip Bennefall wrote: >> > Hi everyone, >> > >> > I have a tree of folders and I want to find the complete path >from any >> arbitrary point back to the top level directory. The schema is: >> > >> > CREATE TABLE IF NOT EXISTS folders( >> > id INTEGER PRIMARY KEY, >> > parentFolderId INTEGER REFERENCES folders(id) ON DELETE >CASCADE ON >> UPDATE CASCADE, >> > name TEXT NOT NULL); >> > >> > I made the following CTE: >> > >> > WITH RECURSIVE folderTree (id, path) >> > AS(SELECT id, name FROM folders WHERE parentFolderId IS NULL >> > UNION ALL >> > SELECT folders.id, folderTree.path || '/' || folders.name >> > FROM folders, folderTree WHERE folders.parentFolderId = >folderTree.id) >> > SELECT path FROM folderTree WHERE id=?1; >> > >> > This produces the correct result, but I am wondering if there is >a more >> efficient way? This query seems to generate the entire tree and >then do a >> table scan to find just the one row I am looking for. Can I start >from the >> given row and *only* traverse upwards through the levels until I >find a >> node with no parent? >> >> Just reverse the conditions. Something like this (not tested): >> >> WITH RECURSIVE folderPath(id, parentId, path) >> AS(SELECT id, parentFolderId, name FROM folders WHERE id=?1) >> UNION ALL >> SELECT f.id, f.parentFolderId, f.name || '/' || fp.path >> FROM folders f join folderPath fp on (f.id = fp.parentId)) >> SELECT path FROM folderPath WHERE parentId is null; >> >> -- >> Igor Tandetnik >> >> >> ___ >> sqlite-users mailing list >> sqlite-users@mailinglists.sqlite.org >> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite- >users >> >___ >sqlite-users mailing list >sqlite-users@mailinglists.sqlite.org >http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] CTE to Get Path In a Tree
Have the same table structure to represent a folder tree: CREATE TABLE FOLDERS([ID] INTEGER PRIMARY KEY, [PARENT_ID] INTEGER, [NAME] TEXT, [LEVEL] INTEGER, [RANK] TEXT) Data is as follows: ID PARENT_ID NAME LEVEL RANK --- 1 0 Main 0 0 2 1 Diabetic audit 1 01-02 3 1 GROUP BY 1 01-03 4 1 x 1 01-04 8 1 Common 1 01-08 9 3 zzz 2 01-03-09 10 9 yyy 3 01-03-09-10 Now I would like the following output: In first column the ID of the folder and in the second column the full path of that folder. This will give the right ID's and the right folders in the right order by doesn't give the full path: select f.id, f.name as name from folders f where f.id in (with recursive branch(id) as (select id from folders where id = 1 union all select f.id from folders f inner join branch b on(f.parent_id = b.id)) select id from branch) order by rank This will give the right full paths in the right order but doesn't give me the right folder ID (1 for all rows): with recursive folderpath(id, parent_id, path, rank) as (select id, parent_id, name, rank from folders union all select f.id, f.parent_id, f.name || '/' || fp.path, fp.rank from folders f inner join folderpath fp on (f.id = fp.parent_id)) select id, path from folderpath where id = 1 order by rank How do I get the right folder ID and the full paths? RBS On Sun, May 12, 2019 at 1:15 PM Igor Tandetnik wrote: > On 5/12/2019 6:19 AM, Philip Bennefall wrote: > > Hi everyone, > > > > I have a tree of folders and I want to find the complete path from any > arbitrary point back to the top level directory. The schema is: > > > > CREATE TABLE IF NOT EXISTS folders( > > id INTEGER PRIMARY KEY, > > parentFolderId INTEGER REFERENCES folders(id) ON DELETE CASCADE ON > UPDATE CASCADE, > > name TEXT NOT NULL); > > > > I made the following CTE: > > > > WITH RECURSIVE folderTree (id, path) > > AS(SELECT id, name FROM folders WHERE parentFolderId IS NULL > > UNION ALL > > SELECT folders.id, folderTree.path || '/' || folders.name > > FROM folders, folderTree WHERE folders.parentFolderId = folderTree.id) > > SELECT path FROM folderTree WHERE id=?1; > > > > This produces the correct result, but I am wondering if there is a more > efficient way? This query seems to generate the entire tree and then do a > table scan to find just the one row I am looking for. Can I start from the > given row and *only* traverse upwards through the levels until I find a > node with no parent? > > Just reverse the conditions. Something like this (not tested): > > WITH RECURSIVE folderPath(id, parentId, path) > AS(SELECT id, parentFolderId, name FROM folders WHERE id=?1) > UNION ALL > SELECT f.id, f.parentFolderId, f.name || '/' || fp.path > FROM folders f join folderPath fp on (f.id = fp.parentId)) > SELECT path FROM folderPath WHERE parentId is null; > > -- > Igor Tandetnik > > > ___ > sqlite-users mailing list > sqlite-users@mailinglists.sqlite.org > http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users > ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] CTE to Get Path In a Tree
On 5/12/2019 2:14 PM, Igor Tandetnik wrote: On 5/12/2019 6:19 AM, Philip Bennefall wrote: Hi everyone, I have a tree of folders and I want to find the complete path from any arbitrary point back to the top level directory. The schema is: CREATE TABLE IF NOT EXISTS folders( id INTEGER PRIMARY KEY, parentFolderId INTEGER REFERENCES folders(id) ON DELETE CASCADE ON UPDATE CASCADE, name TEXT NOT NULL); I made the following CTE: WITH RECURSIVE folderTree (id, path) AS(SELECT id, name FROM folders WHERE parentFolderId IS NULL UNION ALL SELECT folders.id, folderTree.path || '/' || folders.name FROM folders, folderTree WHERE folders.parentFolderId = folderTree.id) SELECT path FROM folderTree WHERE id=?1; This produces the correct result, but I am wondering if there is a more efficient way? This query seems to generate the entire tree and then do a table scan to find just the one row I am looking for. Can I start from the given row and *only* traverse upwards through the levels until I find a node with no parent? Just reverse the conditions. Something like this (not tested): WITH RECURSIVE folderPath(id, parentId, path) AS(SELECT id, parentFolderId, name FROM folders WHERE id=?1) UNION ALL SELECT f.id, f.parentFolderId, f.name || '/' || fp.path FROM folders f join folderPath fp on (f.id = fp.parentId)) SELECT path FROM folderPath WHERE parentId is null; Thanks, that seems to work with a couple of very minor tweaks. The query plans are somewhat different and my gut feeling is that the one you wrote is better, but I will measure against some larger datasets just to be sure. Thanks for the quick response! Kind regards, Philip Bennefall ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] CTE to Get Path In a Tree
On 5/12/2019 6:19 AM, Philip Bennefall wrote: Hi everyone, I have a tree of folders and I want to find the complete path from any arbitrary point back to the top level directory. The schema is: CREATE TABLE IF NOT EXISTS folders( id INTEGER PRIMARY KEY, parentFolderId INTEGER REFERENCES folders(id) ON DELETE CASCADE ON UPDATE CASCADE, name TEXT NOT NULL); I made the following CTE: WITH RECURSIVE folderTree (id, path) AS(SELECT id, name FROM folders WHERE parentFolderId IS NULL UNION ALL SELECT folders.id, folderTree.path || '/' || folders.name FROM folders, folderTree WHERE folders.parentFolderId = folderTree.id) SELECT path FROM folderTree WHERE id=?1; This produces the correct result, but I am wondering if there is a more efficient way? This query seems to generate the entire tree and then do a table scan to find just the one row I am looking for. Can I start from the given row and *only* traverse upwards through the levels until I find a node with no parent? Just reverse the conditions. Something like this (not tested): WITH RECURSIVE folderPath(id, parentId, path) AS(SELECT id, parentFolderId, name FROM folders WHERE id=?1) UNION ALL SELECT f.id, f.parentFolderId, f.name || '/' || fp.path FROM folders f join folderPath fp on (f.id = fp.parentId)) SELECT path FROM folderPath WHERE parentId is null; -- Igor Tandetnik ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
[sqlite] CTE to Get Path In a Tree
Hi everyone, I have a tree of folders and I want to find the complete path from any arbitrary point back to the top level directory. The schema is: CREATE TABLE IF NOT EXISTS folders( id INTEGER PRIMARY KEY, parentFolderId INTEGER REFERENCES folders(id) ON DELETE CASCADE ON UPDATE CASCADE, name TEXT NOT NULL); I made the following CTE: WITH RECURSIVE folderTree (id, path) AS(SELECT id, name FROM folders WHERE parentFolderId IS NULL UNION ALL SELECT folders.id, folderTree.path || '/' || folders.name FROM folders, folderTree WHERE folders.parentFolderId = folderTree.id) SELECT path FROM folderTree WHERE id=?1; This produces the correct result, but I am wondering if there is a more efficient way? This query seems to generate the entire tree and then do a table scan to find just the one row I am looking for. Can I start from the given row and *only* traverse upwards through the levels until I find a node with no parent? Thanks in advance for any pointers. Kind regards, Philip Bennefall ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
