Recursive CTE on tree with doubly linked items

classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

Recursive CTE on tree with doubly linked items

heribert
I've a tree with doubly linked items. I want to get all siblings of a
tree node (e.g. ID=2 or harder to implement ID=3).
I tried to solve this problem with CTE of SQLite by myself - but I can
not find the solution. I looked for any exemplary solution - but do not
find some.

DROP TABLE IF EXISTS "Tree";

CREATE TABLE "Tree" (
   "ID" INTEGER,
   "PrevIDX" INTEGER DEFAULT NULL,
   "NextIDX" INTEGER DEFAULT NULL,
   "ParentIDX" INTEGER DEFAULT NULL,
   PRIMARY KEY ("ID"),
   FOREIGN KEY ("PrevIDX") REFERENCES "Tree" ("ID"),
   FOREIGN KEY ("NextIDX") REFERENCES "Tree" ("ID"),
   FOREIGN KEY ("ParentIDX") REFERENCES "Tree" ("ID") ON DELETE CASCADE
);

INSERT INTO "Tree" VALUES (1, NULL, NULL, NULL);
INSERT INTO "Tree" VALUES (2, NULL, 3, 1);
INSERT INTO "Tree" VALUES (3, 2, 4, 1);
INSERT INTO "Tree" VALUES (4, 3, NULL, 1);

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Recursive CTE on tree with doubly linked items

Hick Gunter
You might like to consider writing the phrase INTEGER PRIMARY KEY to make ID an alias for the rowid, or adding the phrase WITHOUT ROWID to make ID the "true" primary key.

What is your definition of "sibling"? Is it not the set of nodes reachable via the PrevIdx and (respecitvely in the case of a circularyl linked list, or) NextIdx links? Or more simply, having hte same parent? Or maybe you are looking for "cousins" (same level but different parents) too?

Linking each node upwards, but none downwards makes traversal difficult. Also, I am not sure what ON DELETE CASCADE on the "parent" link is for, as it will orphan the siblings of a deleted node and CASCADE right up to the root of the tree.

SELECT ID FROM Tree WHERE ParentIDX = (SELECT ParentIDX FROM Tree WHERE ID=?);

-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von heribert
Gesendet: Montag, 11. März 2019 09:08
An: 'SQLite mailing list' <[hidden email]>
Betreff: [EXTERNAL] [sqlite] Recursive CTE on tree with doubly linked items

I've a tree with doubly linked items. I want to get all siblings of a tree node (e.g. ID=2 or harder to implement ID=3).
I tried to solve this problem with CTE of SQLite by myself - but I can not find the solution. I looked for any exemplary solution - but do not find some.

DROP TABLE IF EXISTS "Tree";

CREATE TABLE "Tree" (
   "ID" INTEGER,
   "PrevIDX" INTEGER DEFAULT NULL,
   "NextIDX" INTEGER DEFAULT NULL,
   "ParentIDX" INTEGER DEFAULT NULL,
   PRIMARY KEY ("ID"),
   FOREIGN KEY ("PrevIDX") REFERENCES "Tree" ("ID"),
   FOREIGN KEY ("NextIDX") REFERENCES "Tree" ("ID"),
   FOREIGN KEY ("ParentIDX") REFERENCES "Tree" ("ID") ON DELETE CASCADE );

INSERT INTO "Tree" VALUES (1, NULL, NULL, NULL); INSERT INTO "Tree" VALUES (2, NULL, 3, 1); INSERT INTO "Tree" VALUES (3, 2, 4, 1); INSERT INTO "Tree" VALUES (4, 3, NULL, 1);

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users


___________________________________________
 Gunter Hick | Software Engineer | Scientific Games International GmbH | Klitschgasse 2-4, A-1130 Vienna | FN 157284 a, HG Wien, DVR: 0430013 | (O) +43 1 80100 - 0

May be privileged. May be confidential. Please delete if not the addressee.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Recursive CTE on tree with doubly linked items

heribert
Siblings (in my case) are nodes have the same parent - the NextIDX and
PrevIDX are only used for ordering sibling nodes. Every node may be
parent of other nodes. The ParentIDX is the downward ID of the parent node.

Yes, you are right: If i delete a node (parent node) all childs of the
node will be deleted too and the prev-/next-sibling-node of  the deleted
"parent node" have to be relinked. I will do this with by updating the
NextIDX and PrevIDX of the sibling-nodes.

I'm looking for a solution to get a ordered ID list of the siblings (or
childs of a parent node).

e.g. ordered child list the parent node ID=1 -> 2, 5, 3

1...2
      .
      .
      5...4
       .   6
       .
      3


> You might like to consider writing the phrase INTEGER PRIMARY KEY to make ID an alias for the rowid, or adding the phrase WITHOUT ROWID to make ID the "true" primary key.
>
> What is your definition of "sibling"? Is it not the set of nodes reachable via the PrevIdx and (respecitvely in the case of a circularyl linked list, or) NextIdx links? Or more simply, having hte same parent? Or maybe you are looking for "cousins" (same level but different parents) too?
>
> Linking each node upwards, but none downwards makes traversal difficult. Also, I am not sure what ON DELETE CASCADE on the "parent" link is for, as it will orphan the siblings of a deleted node and CASCADE right up to the root of the tree.
>
> SELECT ID FROM Tree WHERE ParentIDX = (SELECT ParentIDX FROM Tree WHERE ID=?);
>
> -----Ursprüngliche Nachricht-----
> Von: sqlite-users [mailto:[hidden email]] Im Auftrag von heribert
> Gesendet: Montag, 11. März 2019 09:08
> An: 'SQLite mailing list' <[hidden email]>
> Betreff: [EXTERNAL] [sqlite] Recursive CTE on tree with doubly linked items
>
> I've a tree with doubly linked items. I want to get all siblings of a tree node (e.g. ID=2 or harder to implement ID=3).
> I tried to solve this problem with CTE of SQLite by myself - but I can not find the solution. I looked for any exemplary solution - but do not find some.
>
> DROP TABLE IF EXISTS "Tree";
>
> CREATE TABLE "Tree" (
>     "ID" INTEGER,
>     "PrevIDX" INTEGER DEFAULT NULL,
>     "NextIDX" INTEGER DEFAULT NULL,
>     "ParentIDX" INTEGER DEFAULT NULL,
>     PRIMARY KEY ("ID"),
>     FOREIGN KEY ("PrevIDX") REFERENCES "Tree" ("ID"),
>     FOREIGN KEY ("NextIDX") REFERENCES "Tree" ("ID"),
>     FOREIGN KEY ("ParentIDX") REFERENCES "Tree" ("ID") ON DELETE CASCADE );
>
> INSERT INTO "Tree" VALUES (1, NULL, NULL, NULL); INSERT INTO "Tree" VALUES (2, NULL, 3, 1); INSERT INTO "Tree" VALUES (3, 2, 4, 1); INSERT INTO "Tree" VALUES (4, 3, NULL, 1);
>
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
>
> ___________________________________________
>   Gunter Hick | Software Engineer | Scientific Games International GmbH | Klitschgasse 2-4, A-1130 Vienna | FN 157284 a, HG Wien, DVR: 0430013 | (O) +43 1 80100 - 0
>
> May be privileged. May be confidential. Please delete if not the addressee.
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Recursive CTE on tree with doubly linked items

Jean-Luc Hainaut
In reply to this post by heribert

Your implementation of trees is that of network databases at the
pointer-based physical level but definitely not relational. Try this:

create table TREE(
   ID integer not null primary key,
   Parent  integer references TREE on delete ... on update cascade); --
Notice the absence of "not null"
create index XTREE on TREE(Parent); -- Only useful for large sets of nodes

That's all.

 From this, CTE and non-CTE queries just are easy, elegant and fast. For
instance extracting the siblings of a note is the translation of their
intuitive definition: "nodes with the same parent" :

select * from TREE where Parent = 2.

Regards

J-L Hainaut

On 11/03/2019 09:08, heribert wrote:

> I've a tree with doubly linked items. I want to get all siblings of a
> tree node (e.g. ID=2 or harder to implement ID=3).
> I tried to solve this problem with CTE of SQLite by myself - but I can
> not find the solution. I looked for any exemplary solution - but do
> not find some.
>
> DROP TABLE IF EXISTS "Tree";
>
> CREATE TABLE "Tree" (
>   "ID" INTEGER,
>   "PrevIDX" INTEGER DEFAULT NULL,
>   "NextIDX" INTEGER DEFAULT NULL,
>   "ParentIDX" INTEGER DEFAULT NULL,
>   PRIMARY KEY ("ID"),
>   FOREIGN KEY ("PrevIDX") REFERENCES "Tree" ("ID"),
>   FOREIGN KEY ("NextIDX") REFERENCES "Tree" ("ID"),
>   FOREIGN KEY ("ParentIDX") REFERENCES "Tree" ("ID") ON DELETE CASCADE
> );
>
> INSERT INTO "Tree" VALUES (1, NULL, NULL, NULL);
> INSERT INTO "Tree" VALUES (2, NULL, 3, 1);
> INSERT INTO "Tree" VALUES (3, 2, 4, 1);
> INSERT INTO "Tree" VALUES (4, 3, NULL, 1);
>
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Recursive CTE on tree with doubly linked items

Clemens Ladisch
In reply to this post by heribert
heribert wrote:
> I've a tree with doubly linked items. I want to get all siblings of a tree node.

If you want them in order, you have to walk through the linked list:

WITH SiblingsOf3 AS (
  SELECT *
  FROM Tree
  WHERE ParentIDX = (SELECT ParentIDX
                     FROM Tree
                     WHERE ID = 3)
    AND PrevIDX IS NULL

  UNION ALL

  SELECT Tree.*
  FROM Tree
  JOIN SiblingsOf3 ON SiblingsOf3.NextIDX = Tree.ID
)
SELECT * FROM SiblingsOf3;


Regards,
Clemens
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Recursive CTE on tree with doubly linked items

heribert
Thx clemens,

it works perfect - but i do not understand why.

The 'inital-select' results with the head node - only one result set.

SELECT *
   FROM Tree
   WHERE ParentIDX = (SELECT ParentIDX
                      FROM Tree
                      WHERE ID = 3)
     AND PrevIDX IS NULL

Points SiblingsOf3 after your 'initial-select' to this head node?

Why (and how) iterates your 'recursive-select'?

SELECT Tree.*
FROM Tree
JOIN SiblingsOf3 ON SiblingsOf3.NextIDX = Tree.ID

Best regards
heribert


> heribert wrote:
>> I've a tree with doubly linked items. I want to get all siblings of a tree node.
> If you want them in order, you have to walk through the linked list:
>
> WITH SiblingsOf3 AS (
>    SELECT *
>    FROM Tree
>    WHERE ParentIDX = (SELECT ParentIDX
>                       FROM Tree
>                       WHERE ID = 3)
>      AND PrevIDX IS NULL
>
>    UNION ALL
>
>    SELECT Tree.*
>    FROM Tree
>    JOIN SiblingsOf3 ON SiblingsOf3.NextIDX = Tree.ID
> )
> SELECT * FROM SiblingsOf3;
>
>
> Regards,
> Clemens
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Recursive CTE on tree with doubly linked items

Keith Medcalf

On Monday, 11 March, 2019 09:42, heribert <[hidden email]> wrote:

>it works perfect - but i do not understand why.

See https://sqlite.org/lang_with.html for a description of recursive queries ...


>The 'inital-select' results with the head node - only one result set.

>SELECT *
>   FROM Tree
>   WHERE ParentIDX = (SELECT ParentIDX
>                      FROM Tree
>                      WHERE ID = 3)
>     AND PrevIDX IS NULL
>
>Points SiblingsOf3 after your 'initial-select' to this head node?
>
>Why (and how) iterates your 'recursive-select'?
>
>SELECT Tree.*
>FROM Tree
>JOIN SiblingsOf3 ON SiblingsOf3.NextIDX = Tree.ID

---
The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume.




_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Recursive CTE on tree with doubly linked items

James K. Lowden
In reply to this post by Jean-Luc Hainaut
On Mon, 11 Mar 2019 10:39:06 +0100
Jean-Luc Hainaut <[hidden email]> wrote:

> Your implementation of trees is that of network databases at the
> pointer-based physical level but definitely not relational. Try this:
>
> create table TREE(
>    ID integer not null primary key,
>    Parent  integer references TREE on delete ... on update cascade);
> -- Notice the absence of "not null"
> create index XTREE on TREE(Parent); -- Only useful for large sets of
> nodes
>
> That's all.

Bravo!  

To the OP: this is the answer you want, whether you want it or not.  

> > I've a tree with doubly linked items.

That's the root of your problem, as it were.  It's hard to solve in SQL
because you're trying to use SQL in a nonrelational way.  

--jkl
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Recursive CTE on tree with doubly linked items

Joshua Thomas Wise
Another way of implementing ordered siblings is to use a floating point “position” column instead of maintaining links to siblings via foreign keys. The advantage of a “position” column is that the data model maintains consistency automatically—you don’t need to painstakingly make sure all sibling pointers are correct. When using sibling pointers, there are many “invalid” states you could find yourself in. With a position column, all possible states are valid. This is a much more “relational” approach.

CREATE TABLE tree (
        id INTEGER PRIMARY KEY,
        parent INTEGER,
        position REAL,
        UNIQUE(parent, position),
        CHECK((parent IS NULL) = (position IS NULL)),
        FOREIGN KEY(parent) REFERENCES tree(id) ON DELETE CASCADE ON UPDATE SET NULL
);

Now, basic tree operations become simple:
Create root node:
INSERT INTO tree DEFAULT VALUES
Append child:
INSERT INTO tree (parent, position) VALUES (@parent, @position)
To insert a node between two existing nodes, set @position to be ((left.position + right.position) / 2).
Delete a node:
DELETE FROM tree WHERE id = @id
No need to maintain sibling links
Swap two sibling nodes:
Simply swap their positions (using some intermediate value to get around the UNIQUE constraint)

You can even create a view to dynamically expose sibling links, without having to manually maintain them:

CREATE VIEW doubly_linked_tree(id, parent, prev, next) AS
        SELECT id, parent, lag(id) OVER siblings, lead(id) OVER siblings
        FROM tree
        WINDOW siblings AS (PARTITION BY parent ORDER BY position);

One downside to “position” column approach is the finite precision of floating point values. For example, inserting a new node between two existing nodes implies finding the average of the two sibling positions. If those siblings have position values of 1 and 2, only 52 nodes can be inserted between them before we run out of floating point real-estate.

One solution is to use a view and trigger to implement a “normalize” function:

CREATE TEMP VIEW normalize_tree(parent) AS SELECT NULL;
CREATE TEMP TABLE _children(id INTEGER PRIMARY KEY, position REAL);
CREATE TEMP TRIGGER normalize_tree_impl INSTEAD OF UPDATE ON normalize_tree
BEGIN
        INSERT INTO _children
                SELECT id, row_number() OVER (ORDER BY position)
                FROM tree
                WHERE parent = new.parent
                ORDER BY position;
        UPDATE tree
                SET position = (SELECT position FROM _children WHERE id = tree.id)
                WHERE EXISTS(SELECT position FROM _children WHERE id = tree.id);
        DELETE FROM _children;
END;

You can then normalize the positions of all direct children of a given node, so that those children all have integral positions ascending from 1:

        UPDATE normalize_tree SET parent = @parent

Hopefully these ideas are helpful to you.

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Recursive CTE on tree with doubly linked items

Keith Medcalf

The trigger program will have update anomalies (violation of the UNIQUE constraint for example) as well as performance issues unless the data in the tree is tiny (since it must visit every row in the tree even if it is not being updated).  This will fix those issues (and also requires a "gentlemen's agreement" to only put positive values in the position column (meaning the database cannot enforce this, you need to do it at the application level) but the trigger can check to make sure before running):

CREATE TEMP TRIGGER normalize_tree_impl INSTEAD OF UPDATE ON normalize_tree
BEGIN
  SELECT RAISE(ABORT, 'Negative position value detected')
    FROM tree
   WHERE parent = new.parent
     AND position < 0;
  INSERT INTO _children
       SELECT id,
              row_number() OVER (ORDER BY position)
         FROM tree
        WHERE parent = new.parent
     ORDER BY position;
  UPDATE tree
     SET position = -position
   WHERE id IN (SELECT id FROM _children);
  UPDATE tree
     SET position = (SELECT position FROM _children WHERE id = tree.id) -- Multiply by x to number by x
   WHERE id IN (SELECT id FROM _children);
  DELETE FROM _children;
END;

You can also get rid of the window function entirely if you do this (which will presumably run even faster):

CREATE TEMP TABLE _children(position INTEGER PRIMARY KEY, id INTEGER NOT NULL UNIQUE);

CREATE TEMP TRIGGER normalize_tree_impl INSTEAD OF UPDATE ON normalize_tree
BEGIN
  SELECT RAISE(ABORT, 'Negative position value detected')
    FROM tree
   WHERE parent = new.parent
     AND position < 0;
  INSERT INTO _children (id)
       SELECT id
         FROM tree
        WHERE parent = new.parent
     ORDER BY position;
  UPDATE tree
     SET position = -position
   WHERE id IN (SELECT id FROM _children);
  UPDATE tree
     SET position = (SELECT position FROM _children WHERE id = tree.id) -- Multiply by x to number by x
   WHERE id IN (SELECT id FROM _children);
  DELETE FROM _children;
END;

---
The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume.

>-----Original Message-----
>From: sqlite-users [mailto:sqlite-users-
>[hidden email]] On Behalf Of Joshua Thomas Wise
>Sent: Monday, 18 March, 2019 01:09
>To: SQLite mailing list
>Subject: Re: [sqlite] Recursive CTE on tree with doubly linked items
>
>Another way of implementing ordered siblings is to use a floating
>point “position” column instead of maintaining links to siblings via
>foreign keys. The advantage of a “position” column is that the data
>model maintains consistency automatically—you don’t need to
>painstakingly make sure all sibling pointers are correct. When using
>sibling pointers, there are many “invalid” states you could find
>yourself in. With a position column, all possible states are valid.
>This is a much more “relational” approach.
>
>CREATE TABLE tree (
> id INTEGER PRIMARY KEY,
> parent INTEGER,
> position REAL,
> UNIQUE(parent, position),
> CHECK((parent IS NULL) = (position IS NULL)),
> FOREIGN KEY(parent) REFERENCES tree(id) ON DELETE CASCADE ON
>UPDATE SET NULL
>);
>
>Now, basic tree operations become simple:
>Create root node:
>INSERT INTO tree DEFAULT VALUES
>Append child:
>INSERT INTO tree (parent, position) VALUES (@parent, @position)
>To insert a node between two existing nodes, set @position to be
>((left.position + right.position) / 2).
>Delete a node:
>DELETE FROM tree WHERE id = @id
>No need to maintain sibling links
>Swap two sibling nodes:
>Simply swap their positions (using some intermediate value to get
>around the UNIQUE constraint)
>
>You can even create a view to dynamically expose sibling links,
>without having to manually maintain them:
>
>CREATE VIEW doubly_linked_tree(id, parent, prev, next) AS
> SELECT id, parent, lag(id) OVER siblings, lead(id) OVER siblings
> FROM tree
> WINDOW siblings AS (PARTITION BY parent ORDER BY position);
>
>One downside to “position” column approach is the finite precision of
>floating point values. For example, inserting a new node between two
>existing nodes implies finding the average of the two sibling
>positions. If those siblings have position values of 1 and 2, only 52
>nodes can be inserted between them before we run out of floating
>point real-estate.
>
>One solution is to use a view and trigger to implement a “normalize”
>function:
>
>CREATE TEMP VIEW normalize_tree(parent) AS SELECT NULL;
>CREATE TEMP TABLE _children(id INTEGER PRIMARY KEY, position REAL);
>CREATE TEMP TRIGGER normalize_tree_impl INSTEAD OF UPDATE ON
>normalize_tree
>BEGIN
> INSERT INTO _children
> SELECT id, row_number() OVER (ORDER BY position)
> FROM tree
> WHERE parent = new.parent
> ORDER BY position;
> UPDATE tree
> SET position = (SELECT position FROM _children WHERE id =
>tree.id)
> WHERE EXISTS(SELECT position FROM _children WHERE id =
>tree.id);
> DELETE FROM _children;
>END;
>
>You can then normalize the positions of all direct children of a
>given node, so that those children all have integral positions
>ascending from 1:
>
> UPDATE normalize_tree SET parent = @parent
>
>Hopefully these ideas are helpful to you.
>
>_______________________________________________
>sqlite-users mailing list
>[hidden email]
>http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users



_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Recursive CTE on tree with doubly linked items

wmertens
On Mon, Mar 18, 2019 at 10:21 AM Keith Medcalf <[hidden email]> wrote:

> requires a "gentlemen's agreement" to only put positive values in the
> position column (meaning the database cannot enforce this, you need to do
> it at the application level)
>

Can't this be done with a before insert trigger?

sqlite> create table f(t);
sqlite> create trigger foo before insert on f begin select raise(ABORT, 'be
positive') where new.t<=0; end;
sqlite> insert into f values(5.5);
sqlite> insert into f values(0);
Error: be positive

Wout.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Recursive CTE on tree with doubly linked items

Joshua Thomas Wise
In reply to this post by Keith Medcalf

> On Mar 18, 2019, at 5:21 AM, Keith Medcalf <[hidden email]> wrote:
>
>  UPDATE tree
>     SET position = (SELECT position FROM _children WHERE id = tree.id) -- Multiply by x to number by x
>   WHERE id IN (SELECT id FROM _children);
>  DELETE FROM _children;
> END;

I don’t see the window function causing a significant performance loss, but your UPDATE statement is much better. You could also get rid of the gentleman’s agreement by temporarily setting both parent and position to NULL.

CREATE TEMP VIEW normalize_tree(parent) AS SELECT NULL;
CREATE TEMP TABLE _children(id INTEGER PRIMARY KEY, position REAL);
CREATE TEMP TRIGGER normalize_tree_impl INSTEAD OF UPDATE ON normalize_tree
BEGIN
        INSERT INTO _children
                SELECT id, row_number() OVER (ORDER BY position)
                FROM tree
                WHERE parent = new.parent
                ORDER BY position;
        UPDATE tree
                SET (parent, position) = (NULL, NULL)
                WHERE id IN (SELECT id FROM _children);
        UPDATE tree
                SET (parent, position) = (new.parent, (SELECT position FROM _children WHERE id = tree.id <http://tree.id/>))
                WHERE id IN (SELECT id FROM _children);
        DELETE FROM _children;
END;

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users