CODEWITHSUNDEEP
phpmysql
Tom Schaefer
Tom Schaefer

Reputation: 897

Repair Broken Nested Set

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

Upvotes: 0

Views: 1846

Answers (3)

aj.toulan
aj.toulan

Reputation: 1431

There are 4 or 5 different cases for corruption in a nested set that are completely fixable (if done in the right order). Snaggle is easy to prevent with a simple trigger the checks to see if the Left is not >= the Right. I have gotten the best results from repairing a nested set in this order. The SQL itself is not difficult once the problem is broken down as follows.

  • Cross (1:4 3:6) or (1:2 2:3)
  • Under/Over (1:4 1:3) OR (1:4 2:4)
  • Gap (2:3 5:6 1:7) or (2:4 5:6 1:7)
  • Snaggle (2:1 4:2) OR (1:1)

Upvotes: 0

VolkerK
VolkerK

Reputation: 96159

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

Upvotes: 1

longneck
longneck

Reputation: 12226

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.

Upvotes: 1

Related Questions