Thread: celko nested set functions

celko nested set functions

From
Robert Treat
Date:
I'm wondering if anyone has written code that enables you to move
entities between parents in a nested set model. Specifically something
that can do it without deleting any of the children involved in the
process.  I looked in the postgresql cookbook which had adding and
building tree's, but not moving.  I'm hoping to find something
postgresql specific but if not that's ok. Thanks in advance,

Robert Treat





Re: celko nested set functions

From
Josh Berkus
Date:
Robert,

> I'm wondering if anyone has written code that enables you to move
> entities between parents in a nested set model. Specifically something
> that can do it without deleting any of the children involved in the
> process.  I looked in the postgresql cookbook which had adding and
> building tree's, but not moving.  I'm hoping to find something
> postgresql specific but if not that's ok. Thanks in advance,

I've been planning on doing this as an article for a while.   I'll send you an
answer off-list because I don't want to publicize it until I can add some
commentary.


--
-Josh BerkusAglio Database SolutionsSan Francisco



Re: celko nested set functions

From
greg@turnstep.com
Date:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message


The major thing you can do, besides using a prepare, is to not bother
splitting 502 times, but only enough times so that the last field you
are going to use is included. In this case, the highest element you are
using is [25], which is actually the 26th element to be split. Add one
more and 0-25 will be split, while 26 will be one giant field:

  my @line = split(/\|/, $_, 27);

Since you already know exactly which fields you want from the split
result, we can specify those directly like this:

  my @line = (split(/\|/, $_, 27))[0,4,5,6,10,11,14,18,22,25];

The parenthesis around the split call force it to be evaluated first,
and then we slice out the values we need. Now @line holds exactly the
elements you want to add in. Just pass that in to a prepared statement.

You can also remove the chomp and the chop, as the ends of the line are
being discarded anyways. Moving the commit outside of the loop should
help too. Here's the final result:


my $SQL = "INSERT INTO cdl_16master VALUES(nextval('cdl_16_seq'),?,?,?,?,?,?,?,?,?,?";
my $sth = $dbh->prepare($SQL);

while(<FHD>) {
  my @line = (split(/\|/, $_, 27))[0,4,5,6,10,11,14,18,22,25];
  $sth->execute(@line);
}
$dbh->commit();


On a final note, you may want to create tables in the future that
automagically populate columns with sequences like this:

CREATE TABLE cdl_16master (
  myid INTEGER NOT NULL DEFAULT nextval('cd_16_seq'),
  ...
);

The drawback is that you will need to specify the exact columns to be
filled in the INSERT command, but this is really a good practice to
get into anyway.

Greg Sabino Mullane greg@turnstep.com
PGP Key: 0x14964AC8 200210291455

-----BEGIN PGP SIGNATURE-----
Comment: http://www.turnstep.com/pgp.html

iD8DBQE9vunyvJuQZxSWSsgRAnFKAKD5Fkyl9TzEaRwrNTuX8dqvRa6SCACg3Bzd
pgaJNkoGC2hXvpE23Ko9CaE=
=wtsO
-----END PGP SIGNATURE-----



Re: celko nested set functions

From
greg@turnstep.com
Date:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message


Robert Treat and I came up with a better way to move 
nodes from one branch to another inside of a nested tree:



CREATE or REPLACE FUNCTION move_tree (integer, integer) RETURNS text
AS '

-- Moves part of a nested set tree to another part.
-- Pass in the left of the child (from) and the left of the parent (to)

DECLARE

cleft INTEGER;     cright INTEGER;
pleft INTEGER;     pright INTEGER;
leftbound INTEGER; rightbound INTEGER;
treeshift INTEGER; cwidth INTEGER;
leftrange INTEGER; rightrange INTEGER;

BEGIN

-- Self-move makes no sense
IF $1 = $2 THEN RETURN ''Cannot move: entries are identical'';
END IF;

SELECT lft, rgt FROM tree WHERE lft = $1 INTO cleft, cright;
SELECT lft, rgt FROM tree WHERE lft = $2 INTO pleft, pright;

-- Make sure the child exists
IF cleft IS NULL THEN RETURN ''No entry found with an left of ''||$1;
END IF;

-- Make sure the parent exists
IF pleft IS NULL THEN RETURN ''No entry found with a left of ''||$2;
END IF;

-- Parent cannot be underneath the child
IF pleft BETWEEN cleft AND cright THEN RETURN ''Cannot move: first entry contains second'';
END IF;

-- Child may already be in the proper place
IF cleft = pleft+1 THEN RETURN ''No changes need to be made'';
END IF;

IF cleft > pleft THEN  treeshift  := pleft - cleft + 1; leftbound  := pleft+1; rightbound := cleft-1; cwidth     :=
cright-cleft+1;leftrange := cright; rightrange  := pleft;
 
ELSE treeshift  := pleft - cright; leftbound  := cright + 1; rightbound := pleft; cwidth     := cleft-cright-1;
leftrange := pleft+1; rightrange := cleft;
 
END IF;


UPDATE tree SET lft = CASE           WHEN lft BETWEEN leftbound AND rightbound THEN lft + cwidth           WHEN lft
BETWEENcleft AND cright THEN lft + treeshift           ELSE lft END,     rgt = CASE           WHEN rgt BETWEEN
leftboundAND rightbound THEN rgt + cwidth           WHEN rgt BETWEEN cleft AND cright THEN rgt + treeshift
ELSErgt END
 
WHERE lft < leftrange OR rgt > rightrange;

RETURN ''Tree has been moved'';

END;
'
LANGUAGE 'plpgsql';




Greg Sabino Mullane greg@turnstep.com
PGP Key: 0x14964AC8 200211251526

-----BEGIN PGP SIGNATURE-----
Comment: http://www.turnstep.com/pgp.html

iD8DBQE94ojRvJuQZxSWSsgRAkkUAJ0eX9VJtXYajAo60UeKYaXH1xxmkwCeJDtX
qrX7tgXmUCJNd/fphjGi7tI=
=+ADv
-----END PGP SIGNATURE-----