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 firstname.lastname@example.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users