maintaining nested sets - HOW?

[sneakyimp]

hello hello!

last week i spent 2 or 3 days writing a function to move tree branches within a data tree encoded using nested sets. actually, it's encoded with an adjacency list / nested set hybrid (it uses both).

the client was moving a tree branch and the data was suddenly corrupted! i had fortunately backed up the data and once i restored it to the backed up state, the problem didn't happen again.

a few questions:
1) can the user interacting with their browser cause scripts to halt or run twice? like if they click stop or refresh? anybody have strategies to avoid this?

2) the nested set data tree model seems especially vulnerable to corruption and problems because edits to the tree require a very large number of records to be changed (if you add a node at the root, EVERYTHING changes). Can anyone recommend steps to be put into a "sanity check" function? I can think of the following:

a) make sure there are no orphaned nodes
b) check for bad numbering...not sure how to do this logically
c) what else?

3) lastly, how about UNDO logic? i can imagine it would be quite easy to simply create a copy of the table every time you perform an operation that changes it, but this seems like a huge waste of disk space. can anyone recommend a good undo/rollback strategy?

thanks for reading.

[xblue]

Hi sneakyimp,

quite some time ago, are you still into this?

I thought about sanity-checking nested sets once, so maybe I can contribute concerning issue 2. some suggestions:

a) no gaps (probably difficult via sql only, might need to be done with php?)

b) no duplicates (should be possible with a self join)

c) if left value of an item is between left and right value of another item, right value must between these limit as well and vice versa (should be possible with a self join)

d) sum of left and right value of each element mustn't be even (probably easiest)

concerning #1: I don't think that the client hitting stop would stop script execution on the server (would the server actually notice at all?), but information being submitted twice may be a problem. I've seen attempts to prevent it with javascript - not bulletproof for sure, but may help to prevent accidently re-submitted data.

no good suggestions for #3, sorry.

[sneakyimp]

yes i'm still into this. i consider my nested set code part of my code library--useful stuff to use in the future.

for the record, i think i'll just use adjacency list in the future...it's fine for my average use. i found out that downloading the javascript i've written to display a hierachical tree takes longer than any processing i'd have to do for as many as 1000 nodes. interesting that.

as for user tinkering with their client before code execution complate, shryku had a tip here:

http://www.phpbuilder.com/board/showthread.php?s=&threadid=10284616&highlight=ignoreuserabort

thanks for your advice on sanity check...i'm wondering a few things

a) no gaps - what do you mean exactly? a parent item's RGT value will be only 1 greater than the last child item's RGT value? logic / coding here seems like it might be pretty elaborate.

b) no two records with same LFT and RGT values? or no two records with same LFT or RGT values? seems to me the latter. joins are new to me. any suggestions?

c) ok...i get that. again, new to joins over here. any sql suggestions?

d) got it!

THANKS! this is no longer urgent really. i'm currently trying to pay the overdue rent with some other work.

[xblue]

hi again,

a) it's something like for each element's lft value (unless it is the root element) there must be another element with either lft or rgt 1 smaller and for each element's rgt value (unless it is the root element) there must be another element with either lft or rgt 1 greater. EDIT: this may be expressed more complicated than it actually is. don't post before you finished thinking, xblue.

putting it this way, it might be possible to get it done with sql. still may be easier to put all lft and rgt values into 1 array, sort it and see if the values are sequentially.

b) ok, to keep it simple: let's assume you have designed both lft and rgt columns as unique, you only need to check that the lft value of one element does not equal the rgt value of any other element including itself. something like that should bring up invalid items

SELECT * FROM tablename AS a, tablename AS b WHERE a.lft=b.rgt

c) left for tomorrow

[xblue]

c) should be something like

SELECT * FROM tablename AS a, tablename AS b WHERE a.lft BETWEEN b.lft AND b.rgt AND a.rgt > b.rgt