Repair Broken Nested Set

Question

Hi, I have to repair broken nested set chains via script or sql. The table contains a left and a right value column, but no parent id column. I am able to compute the level of each node within the nested set. There are gaps in left and right values. The structure of computed levels is valid. Does someone know a solution to close the gaps via SQL? (MySQL)

None of the suggestions fit to my problem, but thanks for your engagement.

I worked out a solution for me: 1. first step compute parent ids and transform to adjacency list 2. use Joe Celko's approach to convert adjacency lists to nested sets 3. update old left and right values

Answer 1

i would just generate a parent_id column from the left and right values you have, then regenerate the left and right values.

if you don't want to modify your current table, you could even do this in a temporary table.

Answer 2

Each ancestor of a node (c) has a smaller left and bigger right value. And the immediate parent (p) is the one in that set (of ancestors) with the biggest left value.

E.g.

CREATE TABLE nested (
  id int AUTO_INCREMENT,
  name varchar(16),
  parentid int DEFAULT 0,
  lft int(11),
  rgt int(11),
  PRIMARY KEY (id)
)

INSERT INTO
    nested (name, parentid, lft, rgt)
VALUES
    ('1'      ,0,1,20),
    ('1.1'    ,0,2,9),
    ('1.1.1'  ,0,3,4),
    ('1.1.2'  ,0,5,6),
    ('1.1.3'  ,0,7,8),
    ('1.2'    ,0,10,19),
    ('1.2.1'  ,0,11,14),
    ('1.2.1.1',0,12,13),
    ('1.2.2'  ,0,15,16),
    ('1.2.3'  ,0,17,18)

SELECT
  p.id as pid, p.name as pname,
  c.id as cid, c.name as cname  
FROM
  nested as c
LEFT JOIN
  nested as p
ON
  p.lft=(
    SELECT
      MAX(lft)
    FROM
      nested AS l
    WHERE
      c.lft > l.lft
      AND c.lft < l.rgt
  )

returns

pid    pname    cid    cname
NULL   NULL     1      1
1      1        2      1.1
2      1.1      3      1.1.1
2      1.1      4      1.1.2
2      1.1      5      1.1.3
1      1        6      1.2
6      1.2      7      1.2.1
7      1.2.1    8      1.2.1.1
6      1.2      9      1.2.2
6      1.2      10     1.2.3