PostgreSQL – How to Convert ltree Structure to Nested Set Using VIEW

hierarchypostgresqlpostgresql-9.4

I would like to ask a question about a way for transforming a PostgreSQL ltree structure to a nested set structure with only one query by using only VIEWs.

For example, I have a table which has data with relation to each other as on the picture below:

Table structure

So, the table daclaration is

KeywordLtree(id INT PRIMARY KEY, value TEXT, path ltree);

-- And the data is:

pk |  value  |  path  |
0  |   'A'   |   ''   |
0  |   'B'   |   '1'  |
0  |   'C'   |   '2'  |
0  |   'D'   |  '1.3' |
0  |   'E'   |  '1.4' |
0  |   'F'   |  '1.5' |
0  |   'G'   |  '2.6' |
0  |   'H'   |  '2.7' |

And I have to convert this table to such table:

KeywordSets(id INT PRIMARY KEY, value TEXT, lft INT, rgt INT);

where the rules for the left and the right borders are done according to a nested sets rules.
I found the way how to obtain vertices on each level

CREATE OR REPLACE RECURSIVE VIEW bfs (id, value, path, num_on_level, level) AS
    SELECT id, value, path, row_number() OVER (), 0 as level
    FROM KeywordLtreeSandbox WHERE path ~ '*{0}'

    UNION ALL

    SELECT C.id, C.value, C.path, row_number() OVER (PARTITION BY P.path), level + 1 
    FROM KeywordLtreeSandbox C JOIN bfs P ON P.path @> C.path 
    WHERE nlevel(C.path) = level + 1;

-- Data would be like below
id | value | path | num_on_level | level |
0  |  "A"  |  ""  |      1       |   0   |
1  |  "B"  | "1"  |      1       |   1   |
2  |  "C"  | "2"  |      2       |   1   |
3  |  "D"  |"1.3" |      1       |   2   |
4  |  "E"  |"1.4" |      2       |   2   |
5  |  "F"  |"1.5" |      3       |   2   |
6  |  "G"  |"2.6" |      1       |   2   |
7  |  "H"  |"2.7" |      2       |   2   |

But I have no idea how to enumerate them correctly then (So "A" left = 1, right = 16, "B" left = 2, right = 9 and so on…)

If I need to be more clear please let me know.

Could anyone give me an idea how it is possible to do?

Best Answer

I think there is a way around this without using a recursive query:

WITH cte AS
  ( SELECT 
        m.*, 
        ( SELECT COUNT(*) 
          FROM KeywordLtree AS d
          WHERE m.path @> d.path
        ) AS descendants,
        ( SELECT COUNT(*) 
          FROM KeywordLtree AS a
          WHERE a.path @> m.path
        ) AS ancestors,
        ROW_NUMBER() OVER (ORDER BY m.path) AS rn
    FROM KeywordLtree AS m
  ) 
SELECT cte.*, 
       2 * rn - ancestors AS lft,
       2 * rn - ancestors + 2 * descendants - 1 AS rgt
FROM cte
ORDER BY path ;
Related Question