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-
>boun...@mailinglists.sqlite.org] 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
>sqlite-users@mailinglists.sqlite.org
>http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
