Reputation: 1408
Sorting siblings in nested set
I have a nested set model in SQLite database. The siblings need to be sorted alphabetically. Below is the full set, but the siblings that need to be sorted is the second level. As you can see, they start in this order:
Kanval, Wafiyah, Qamar, Lamya, Chaman, Fadila
familyName | lft | rgt
----------------------+------+-----
Families | 1 | 62
-- Kanval | 2 | 9
---- Omera | 3 | 4
---- Dafiyah | 5 | 6
---- Daneen | 7 | 8
-- Qamar | 10 | 19
---- Deeba | 11 | 12
---- Pakeezah | 13 | 14
---- Rabiya | 15 | 16
---- Banafsha | 17 | 18
-- Lamya | 20 | 33
---- Banujah | 21 | 22
---- Buthaynah | 23 | 24
---- Vardah | 25 | 26
---- Kaneez | 27 | 28
---- Parveen | 29 | 30
---- Ghunyah | 31 | 32
-- Chaman | 34 | 45
---- Kanz | 35 | 36
---- Varisha | 37 | 38
---- Kunza | 39 | 40
---- Khusbakht | 41 | 42
---- Ermina | 43 | 44
-- Fadila | 46 | 53
---- Tahani | 47 | 48
---- Iffah | 49 | 50
---- Huwaydah | 51 | 52
-- Wafiyah | 54 | 61
---- Asheeyana | 55 | 56
---- Hutun | 57 | 58
---- Aakifah | 59 | 60
But the need to be sorted to this order:
Chaman, Fadila, Kanval, Lamya, Qamar, Wafiyah
familyName | lft | rgt
------------------+-----+-----
Families | 1 | 62
--Chaman | 2 | 13
----Kanz | 3 | 4
----Varisha | 5 | 6
----Kunza | 7 | 8
----Khusbakht | 9 | 10
----Ermina | 11 | 12
--Fadila | 14 | 21
----Tahani | 15 | 16
----Iffah | 17 | 18
----Huwaydah | 19 | 20
--Kanval | 22 | 29
----Omera | 23 | 24
----Dafiyah | 25 | 26
----Daneen | 27 | 28
--Lamya | 30 | 43
----Banujah | 31 | 32
----Buthaynah | 33 | 34
----Vardah | 35 | 36
----Kaneez | 37 | 38
----Parveen | 39 | 40
----Ghunyah | 41 | 42
--Qamar | 44 | 53
----Deeba | 45 | 46
----Pakeezah | 47 | 48
----Rabiya | 49 | 50
----Banafsha | 51 | 52
--Wafiyah | 54 | 61
----Asheeyana | 55 | 56
----Hutun | 57 | 58
----Aakifah | 59 | 60
I have Joe Celko's Trees and Hieracrchies in SQL for Smarties, it has examples of moving nodes around like moving Chaman to the front. I have also found similar examples on the web, but I cannot find any SQL examples that will sort all the siblings.
How might one go about sorting the siblings?
Details on how I created the above data...
I have a test app that will populate the nested set. So I simply created it twice, one time with the names out of order, the second time with the names in order to show the desired results. As far as actually getting this data out of the database, I used this query:
SELECT COUNT(e1.ObjectId) AS LEVEL, e2.name, e2.lft, e2.rgt
FROM EventNode AS e1, EventNode AS e2
WHERE e2.lft BETWEEN e1.lft AND e1.rgt
GROUP BY e2.ObjectId
ORDER BY e2.lft
The reason why ordering is important is because the order is going to be controlled by the end user. They will be able to sort either way and also move individual nodes around so the siblings are displayed in the order they desire. So it is important that the data in the tree be in the correct order.
(P.S. in the real data there is an ObjectID which is a unique identifier, it allows the names to be repeated within the nested set)
Upvotes: 3
Views: 569
Answers (1)
Reputation: 857
Considering your table has the following structure:
EventNode(objectID, familyName, lft, rgt)
I'd first get the parentObjectID of each Node and then re-generate the Nested Set with the needed lft and rgt values. I have also re-ordered alphabetically the children on level 3 and inserted the sample data into EventNode:
CREATE TABLE EventNode
(
objectID INT IDENTITY(1, 1) NOT NULL,
familyName VARCHAR(20) NOT NULL,
lft TINYINT NOT NULL,
rgt TINYINT NOT NULL
)
GO
INSERT INTO EventNode (familyName, lft, rgt)
VALUES
('Families' , 1 , 62),
('Kanval' , 2 , 9),
('Omera' , 3 , 4),
('Dafiyah' , 5 , 6),
('Daneen' , 7 , 8),
('Qamar' , 10 , 19),
('Deeba' , 11 , 12),
('Pakeezah' , 13 , 14),
('Rabiya' , 15 , 16),
('Banafsha' , 17 , 18),
('Lamya' , 20 , 33),
('Banujah' , 21 , 22),
('Buthaynah', 23 , 24),
('Vardah' , 25 , 26),
('Kaneez' , 27 , 28),
('Parveen' , 29 , 30),
('Ghunyah' , 31 , 32),
('Chaman' , 34 , 45),
('Kanz' , 35 , 36),
('Varisha' , 37 , 38),
('Kunza' , 39 , 40),
('Khusbakht', 41 , 42),
('Ermina' , 43 , 44),
('Fadila' , 46 , 53),
('Tahani' , 47 , 48),
('Iffah' , 49 , 50),
('Huwaydah' , 51 , 52),
('Wafiyah' , 54 , 61),
('Asheeyana', 55 , 56),
('Hutun' , 57 , 58),
('Aakifah' , 59 , 60)
;WITH familyHierarchy(familyName, objectID, parentObjectID)
AS
(
SELECT familyName, objectID,
(SELECT TOP 1 objectID
FROM EventNode e2
WHERE e2.lft < e1.lft AND e2.rgt > e1.rgt
ORDER BY e2.rgt-e1.rgt ASC) AS parentObjectID
FROM EventNode e1
)
, EventNodeRN
AS
(
SELECT familyName, objectID, parentObjectID,
ROW_NUMBER() OVER(PARTITION BY parentObjectID ORDER BY familyName, objectID) * 2 - 1 AS n
FROM familyHierarchy
)
, C1
AS
(
SELECT objectID, 1 AS arm, CAST(0x01 AS VARBINARY(8000)) AS sortpath
FROM familyHierarchy
WHERE parentObjectID is NULL
UNION ALL
SELECT objectID, 2 AS arm, CAST(0x02 AS VARBINARY(8000)) AS sortpath
FROM familyHierarchy
WHERE parentObjectID is NULL
UNION ALL
SELECT E.objectID, 1 AS arm,
CAST(M.sortpath + CAST(E.n AS BINARY(1)) AS VARBINARY(8000)) AS sortpath
FROM C1 AS M
INNER JOIN EventNodeRN AS E
ON E.parentObjectID = M.objectID
WHERE M.arm = 1
UNION ALL
SELECT E.objectID, 2 AS arm,
CAST(M.sortpath + CAST(E.n + 1 AS BINARY(1)) AS VARBINARY(8000)) AS sortpath
FROM C1 AS M
INNER JOIN EventNodeRN AS E
ON E.parentObjectID = M.objectID
WHERE M.arm = 1
)
, c2
AS
(
SELECT objectID, ROW_NUMBER() OVER(ORDER BY sortpath) AS sortval
FROM C1
)
UPDATE e
SET lft = reordered.lft, rgt = reordered.rgt
FROM EventNode e
INNER JOIN (
SELECT c2.objectID, e.familyName, MIN(sortval) AS lft, MAX(sortval) AS rgt
FROM c2
INNER JOIN familyHierarchy e ON c2.objectID = e.objectID
GROUP BY c2.objectID, e.familyName
) reordered ON e.objectID = reordered.objectID
Now, querying the initial table returns the following results:
familyName lft rgt
Families 1 62
Chaman 2 13
Ermina 3 4
Kanz 5 6
Khusbakht 7 8
Kunza 9 10
Varisha 11 12
Fadila 14 21
Huwaydah 15 16
Iffah 17 18
Tahani 19 20
Kanval 22 29
Dafiyah 23 24
Daneen 25 26
Omera 27 28
Lamya 30 43
Banujah 31 32
Buthaynah 33 34
Ghunyah 35 36
Kaneez 37 38
Parveen 39 40
Vardah 41 42
Qamar 44 53
Banafsha 45 46
Deeba 47 48
Pakeezah 49 50
Rabiya 51 52
Wafiyah 54 61
Aakifah 55 56
Asheeyana 57 58
Hutun 59 60
Upvotes: 0
Related Questions
- Mysql sorting Hierarchical data
- How to Order table records with parent followed by child using SQL Query
- order records by depth AND sibling order
- Sort a tree data structure
- How do you sort a tree stored using the nested set model?
- Sorting a subtree in a closure table hierarchical-data structure
- nested set model sorting
- SqlServer Hierarchical parent/child query with sort of children inside parent
- How can you order like items in a nested set hierarchical structure?
- Ordering siblings in nested set model