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

[Joshua Wise]

> On Mar 18, 2019, at 5:21 AM, Keith Medcalf  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 ))
WHERE id IN (SELECT id FROM _children);
DELETE FROM _children;
END;

___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

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

[Wout Mertens]

On Mon, Mar 18, 2019 at 10:21 AM Keith Medcalf  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
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] 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-
>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
>   

Re: [sqlite] 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
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

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

[James K. Lowden]

On Mon, 11 Mar 2019 10:39:06 +0100
Jean-Luc Hainaut  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
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

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

[Keith Medcalf]

On Monday, 11 March, 2019 09:42, heribert  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
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] 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
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

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

[Clemens Ladisch]

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

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

[Jean-Luc Hainaut]

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
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

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