Sorting siblings in nested set

Question

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)

Answer 1

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