Sorting based on next and previous records in SQL

Question

I am trying to order a specific query by taking the next and previous records into account, but I can't seem to get it done. I would like to order by a number and a letter, but if, for example, the last letter of number 1 is equal to one of the letters of number 2, I want to change the ordering, so that the letter matches with the following record.

Create script and SQL fiddle demo

create table Parent (
id [bigint] IDENTITY(1,1), 
number bigint NOT NULL,
PRIMARY KEY (id)
)
GO

create table Child (
id [bigint] IDENTITY(1,1), 
parentId BIGINT, 
letter VARCHAR(1) NOT NULL,
PRIMARY KEY (id),
UNIQUE (parentId, Letter),
FOREIGN KEY (parentId) REFERENCES Parent(id)
)
GO

INSERT Parent (number) VALUES (1)
INSERT Parent (number) VALUES (2)
INSERT Parent (number) VALUES (3)

INSERT Child (parentId, letter) VALUES (1, 'A')
INSERT Child (parentId, letter) VALUES (1, 'C')
INSERT Child (parentId, letter) VALUES (2, 'B')
INSERT Child (parentId, letter) VALUES (2, 'C')
INSERT Child (parentId, letter) VALUES (3, 'B')
INSERT Child (parentId, letter) VALUES (3, 'D')

Current query

Currently I am sorting with this query:

SELECT P.number, C.letter 
FROM Child C
JOIN Parent P ON C.parentId = P.id
ORDER BY P.number, C.letter

Current result set

number               letter
-------------------- ------
1                    A
1                    C
2                    B
2                    C
3                    B
3                    D

Expected result set

To clarify what I actually want to do, here is the expected result set (with C and B of number 2 switched).

number               letter
-------------------- ------
1                    A
1                    C
2                    C --switched
2                    B --switched
3                    B
3                    D

Other requirements and question

• It has to work in SQL SERVER 2005.
• There is a scenario where 3 letters per number are used, I am happy if it just uses the best match.
• I am actually also interested in solutions for later versions of SQL Server (for learning), but those do not answer my question.

Can anyone point me in the right direction on how to do this?

Answer 1

You can do something like this.

1. Identify first and last letter of each parent by using ROW_NUMBER() and PARTITION BY
2. Match the last record of the preceding id with the first record of the next id.
3. Check if the second parent id has any letter which matches with the letter selected above
4. Use a LEFT JOIN and use CASE or ISNULL to set a higher priority for such an id record in which the letter had matched

Query

;WITH CTE AS 
(
SELECT id,ParentID,letter,
ROW_NUMBER()OVER(PARTITION BY parentId ORDER BY ID) first_element,
ROW_NUMBER()OVER(PARTITION BY parentId ORDER BY ID DESC) Last_element
FROM Child
), CTE2 AS 
(
SELECT c1.id,c1.parentid,c1.letter,c2.parentid as c2parentid
FROM CTE c1
INNER JOIN CTE c2
ON c1.last_element = 1
AND c2.first_element = 1
AND c1.id +1 = c2.id
), CTE3 AS 
(
SELECT C.parentid,C.id
FROM CTE2
INNER JOIN child C ON CTE2.c2parentid = C.parentid
AND C.letter = CTE2.letter
)
SELECT P.number, C.letter
FROM Child C
JOIN Parent P ON C.parentId = P.id
LEFT JOIN CTE3 ON CTE3.id = C.id
ORDER BY P.number, ISNULL(CTE3.id,0) DESC, C.letter 

Output

number  letter
1   A
1   C
2   C
2   B
3   B
3   D

SQL Fiddle

EDIT

If your ids are not sequential, you can change CTE1 and CTE2 like this to utilize ROW_NUMBER()OVER(ORDER BY ID) seq_id.

;WITH CTE AS 
(
SELECT id,ParentID,letter,
ROW_NUMBER()OVER(ORDER BY ID) seq_id,
ROW_NUMBER()OVER(PARTITION BY parentId ORDER BY ID) first_element,
ROW_NUMBER()OVER(PARTITION BY parentId ORDER BY ID DESC) Last_element
FROM Child
), CTE2 AS 
(
SELECT c1.id,c1.parentid,c1.letter,c2.parentid as c2parentid
FROM CTE c1
INNER JOIN CTE c2
ON c1.last_element = 1
AND c2.first_element = 1
AND c1.seq_id + 1 = c2.seq_id
)

Rest of the code remains same.

SQL Fiddle