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
