Các nguyên tắc cơ bản về biểu thức bảng, Phần 6 - CTE đệ quy

Điều gì làm cho một thành viên đệ quy là có một tham chiếu đến tên CTE. Tham chiếu này đại diện cho tập kết quả của lần thực thi cuối cùng. Trong lần thực thi đầu tiên của thành viên đệ quy, tham chiếu đến tên CTE đại diện cho tập kết quả của thành viên neo. Trong lần thực thi thứ N, trong đó N> 1, tham chiếu đến tên CTE đại diện cho tập kết quả của việc thực thi (N - 1) của thành viên đệ quy. Như đã đề cập, một khi thành viên đệ quy trả về một tập hợp rỗng, nó sẽ không được thực thi lại. Tham chiếu đến tên CTE trong truy vấn bên ngoài đại diện cho các tập kết quả hợp nhất của việc thực thi đơn lẻ của thành phần neo và tất cả các lần thực thi của thành viên đệ quy.

Đoạn mã sau thực hiện tác vụ nói trên là trả về cây con của các nhân viên cho một người quản lý đầu vào nhất định, chuyển ID nhân viên 3 làm nhân viên gốc trong ví dụ này:

 DECLARE @root AS INT =3; VỚI C AS (CHỌN empid, mgrid, empname FROM dbo. Nhân viên WHERE empid =@root UNION TẤT CẢ CHỌN S.empid, S.mgrid, S.empname FROM C AS M INNER JOIN dbo. Nhân viên AS S TRÊN S.mgrid =M .empid) CHỌN empid, mgrid, empnameFROM C; 

Truy vấn neo chỉ được thực thi một lần, trả về hàng cho nhân viên gốc đầu vào (trong trường hợp của chúng tôi là nhân viên 3).

Truy vấn đệ quy kết hợp tập hợp nhân viên từ cấp trước — được biểu thị bằng tham chiếu đến tên CTE, bí danh là M cho người quản lý — với cấp dưới trực tiếp của họ từ bảng Nhân viên, bí danh là S cho cấp dưới. Vị từ tham gia là S.mgrid =M.empid, nghĩa là giá trị mgrid của cấp dưới bằng với giá trị trống của người quản lý. Truy vấn đệ quy được thực thi bốn lần như sau:

1. Trả lại cấp dưới của nhân viên 3; đầu ra:nhân viên 7
2. Trả lại cấp dưới của nhân viên 7; đầu ra:nhân viên 9 và 11
3. Trả lại cấp dưới của nhân viên 9 và 11; đầu ra:12, 13 và 14
4. Trả lại cấp dưới của các nhân viên 12, 13 và 14; đầu ra:tập hợp rỗng; đệ quy dừng

Tham chiếu đến tên CTE trong truy vấn bên ngoài đại diện cho kết quả hợp nhất của việc thực thi một lần truy vấn neo (nhân viên 3) với kết quả của tất cả các lần thực thi truy vấn đệ quy (nhân viên 7, 9, 11, 12, 13 và 14). Mã này tạo ra kết quả sau:

 empid mgrid empname ------ ------ -------- 3 1 Ina7 3 Aaron9 7 Rita11 7 Gabriel12 9 Emilia13 9 Michael14 9 Didi 

Một vấn đề phổ biến trong các giải pháp lập trình là mã chạy như vòng lặp vô hạn thường do lỗi gây ra. Với CTE đệ quy, một lỗi có thể dẫn đến việc thực thi thành viên đệ quy trên đường băng. Ví dụ:giả sử rằng trong giải pháp của chúng tôi để trả lại cấp dưới của một nhân viên đầu vào, bạn đã gặp lỗi trong vị từ tham gia của thành viên đệ quy. Thay vì sử dụng ON S.mgrid =M.empid, bạn đã sử dụng ON S.mgrid =S.mgrid, như sau:

 DECLARE @root AS INT =3; VỚI C AS (CHỌN empid, mgrid, empname FROM dbo. Nhân viên WHERE empid =@root UNION TẤT CẢ CHỌN S.empid, S.mgrid, S.empname FROM C AS M INNER JOIN dbo. Nhân viên AS S TRÊN S.mgrid =S .mgrid) CHỌN empid, mgrid, empnameFROM C; 

Cho ít nhất một nhân viên có ID người quản lý không rỗng có trong bảng, việc thực thi thành viên đệ quy sẽ tiếp tục trả về kết quả không có giá trị nào. Hãy nhớ rằng điều kiện kết thúc ngầm định cho thành viên đệ quy là khi việc thực thi của nó trả về một tập kết quả trống. Nếu nó trả về một tập hợp kết quả khác, SQL Server sẽ thực thi lại nó. Bạn nhận ra rằng nếu SQL Server không có cơ chế để giới hạn các lần thực thi đệ quy, thì nó sẽ tiếp tục thực thi thành viên đệ quy lặp đi lặp lại mãi mãi. Như một biện pháp an toàn, T-SQL hỗ trợ tùy chọn truy vấn MAXRECURSION giới hạn số lần thực thi tối đa được phép của thành viên đệ quy. Theo mặc định, giới hạn này được đặt thành 100, nhưng bạn có thể thay đổi nó thành bất kỳ giá trị SMALLINT không âm nào, với 0 đại diện cho không giới hạn. Đặt giới hạn đệ quy tối đa thành giá trị dương N có nghĩa là N + 1 đã cố gắng thực hiện thành viên đệ quy bị hủy bỏ do lỗi. Ví dụ:chạy mã lỗi ở trên có nghĩa là bạn dựa vào giới hạn đệ quy tối đa mặc định là 100, vì vậy việc thực thi 101 thành viên đệ quy không thành công:

 empid mgrid empname ------ ------ -------- 3 1 Ina2 1 Eitan3 1 Ina ... 

Giả sử rằng trong tổ chức của bạn có thể an toàn khi giả định rằng hệ thống phân cấp nhân viên sẽ không vượt quá 6 cấp quản lý. Bạn có thể giảm giới hạn đệ quy tối đa từ 100 xuống một số nhỏ hơn nhiều, chẳng hạn như 10 ở mức an toàn, như vậy:

 DECLARE @root AS INT =3; VỚI C AS (CHỌN empid, mgrid, empname FROM dbo. Nhân viên WHERE empid =@root UNION TẤT CẢ CHỌN S.empid, S.mgrid, S.empname FROM C AS M INNER JOIN dbo. Nhân viên AS S TRÊN S.mgrid =S .mgrid) CHỌN empid, mgrid, empnameFROM COPTION (MAXRECURSION 10); 

Bây giờ, nếu có lỗi dẫn đến việc thực thi thành viên đệ quy đang chạy, nó sẽ được phát hiện ở lần thực thi thứ 11 của thành viên đệ quy thay vì ở lần thực thi 101:

 empid mgrid empname ------ ------ -------- 3 1 Ina2 1 Eitan3 1 Ina ... 

Điều quan trọng cần lưu ý là giới hạn đệ quy tối đa chủ yếu nên được sử dụng như một biện pháp an toàn để hủy bỏ việc thực thi mã chạy lỗi. Hãy nhớ rằng khi vượt quá giới hạn, việc thực thi mã sẽ bị hủy bỏ do có lỗi. Bạn không nên sử dụng tùy chọn này để giới hạn số lượng cấp độ cần truy cập cho mục đích lọc. Bạn không muốn lỗi được tạo ra khi không có vấn đề gì với mã.

Đối với mục đích lọc, bạn có thể giới hạn số lượng cấp độ truy cập theo chương trình. Bạn xác định một cột được gọi là lvl theo dõi số cấp của nhân viên hiện tại so với nhân viên gốc đầu vào. Trong truy vấn liên kết, bạn đặt cột lvl thành hằng số 0. Trong truy vấn đệ quy, bạn đặt nó thành giá trị lvl của người quản lý cộng với 1. Để lọc nhiều cấp bên dưới gốc đầu vào là @maxlevel, hãy thêm vị từ M.lvl <@ maxlevel cho mệnh đề ON của truy vấn đệ quy. Ví dụ:mã sau trả về nhân viên 3 và hai cấp độ cấp dưới của nhân viên 3:

 DECLARE @root AS INT =3, @maxlevel AS INT =2; VỚI C AS (CHỌN empid, mgrid, empname, 0 AS lvl TỪ dbo. Nhân viên WHERE empid =@root UNION TẤT CẢ CHỌN S.empid, S.mgrid, S.empname, M.lvl + 1 AS lvl TỪ C AS M INNER THAM GIA dbo. Nhân viên NHƯ S TRÊN S.mgrid =M.empid VÀ M.lvl <@maxlevel) CHỌN empid, mgrid, empname, lvlFROM C; 

Truy vấn này tạo ra kết quả sau:

 empid mgrid empname lvl ------ ------ -------- ---- 3 1 Ina 07 3 Aaron 19 7 Rita 211 7 Gabriel 2 

Điều khoản TÌM KIẾM và CYCLE tiêu chuẩn

Tiêu chuẩn ISO / IEC SQL xác định hai tùy chọn rất mạnh mẽ cho các CTE đệ quy. Một là mệnh đề có tên là TÌM KIẾM điều khiển thứ tự tìm kiếm đệ quy và mệnh đề khác là mệnh đề CYCLE xác định các chu trình trong các đường đi ngang. Đây là cú pháp tiêu chuẩn cho hai mệnh đề:

Chức năng

Chỉ định việc tạo thông tin phát hiện thứ tự và chu trình trong kết quả của biểu thức truy vấn đệ quy.

Định dạng

::=
[ ]
AS []
::=
| |
::=
TÌM KIẾM ĐẶT
::=
DEPTH FIRST BY | BREADTH FIRST BY
::=
::=
CYCLE SET ĐẾN
DEFAULT SỬ DỤNG
::= [{ }… ]
::=
::=
::=
::=
::=

Tại thời điểm viết bài, T-SQL không hỗ trợ các tùy chọn này, nhưng trong các liên kết sau, bạn có thể tìm thấy các yêu cầu cải tiến tính năng yêu cầu đưa chúng vào T-SQL trong tương lai và bỏ phiếu cho chúng:

• Thêm hỗ trợ cho mệnh đề TÌM KIẾM SQL ISO / IEC cho các CTE đệ quy trong T-SQL
• Thêm hỗ trợ cho mệnh đề ISO / IEC SQL CYCLE cho các CTE đệ quy trong T-SQL

Trong các phần sau, tôi sẽ mô tả hai tùy chọn tiêu chuẩn và cũng cung cấp các giải pháp thay thế tương đương về mặt logic hiện có sẵn trong T-SQL.

Mệnh đề TÌM KIẾM

Mệnh đề TÌM KIẾM tiêu chuẩn xác định thứ tự tìm kiếm đệ quy là BREADTH FIRST hoặc DEPTH FIRST theo một số cột thứ tự được chỉ định và tạo một cột trình tự mới với các vị trí thứ tự của các nút đã truy cập. Bạn chỉ định BREADTH FIRST để tìm kiếm trước tiên trên mỗi cấp độ (bề rộng) và sau đó xuống các cấp độ (độ sâu). Bạn chỉ định DEPTH FIRST để tìm kiếm đầu tiên xuống dưới (độ sâu) và sau đó trên bề rộng (bề rộng).

Bạn chỉ định mệnh đề TÌM KIẾM ngay trước truy vấn bên ngoài.

Tôi sẽ bắt đầu với một ví dụ cho thứ tự tìm kiếm đệ quy đầu tiên theo chiều rộng. Chỉ cần nhớ rằng tính năng này không có sẵn trong T-SQL, vì vậy bạn sẽ không thể thực sự chạy các ví dụ sử dụng mệnh đề tiêu chuẩn trong SQL Server hoặc Azure SQL Database. Đoạn mã sau đây trả về cây con của nhân viên 1, yêu cầu thứ tự tìm kiếm đầu tiên theo chiều rộng bằng empid, tạo một cột trình tự được gọi là seqbreadth với các vị trí thứ tự của các nút đã truy cập:

 DECLARE @root AS INT =1; VỚI C AS (CHỌN empid, mgrid, empname FROM dbo. Nhân viên WHERE empid =@root UNION TẤT CẢ CHỌN S.empid, S.mgrid, S.empname FROM C AS M INNER JOIN dbo. Nhân viên AS S TRÊN S.mgrid =M .empid) TÌM KIẾM BÚP BÊ ĐẦU TIÊN BẰNG BỘ trống seqbreadth ---------------------------------------- ---- CHỌN empid, mgrid, empname, seqbreadthFROM CORDER BY seqbreadth; 

Đây là đầu ra mong muốn của mã này:

 empid mgrid empname seqbreadth ------------- ----------- 1 NULL David 12 1 Eitan 23 1 Ina 34 2 Seraph 45 2 Jiru 56 2 Steve 67 3 Aaron 78 5 Lilach 89 7 Rita 910 5 Sean 1011 7 Gabriel 1112 9 Emilia 1213 9 Michael 1314 9 Didi 14 

Đừng bối rối bởi thực tế là các giá trị seqbreadth dường như giống hệt với các giá trị rỗng. Đó chỉ là tình cờ do cách tôi chỉ định thủ công các giá trị trống trong dữ liệu mẫu mà tôi đã tạo.

Hình 2 mô tả bằng đồ họa về hệ thống phân cấp nhân viên, với một đường chấm chấm hiển thị thứ tự đầu tiên theo chiều rộng mà các nút được tìm kiếm. Các giá trị rỗng xuất hiện ngay bên dưới tên nhân viên và các giá trị seqbreadth được chỉ định xuất hiện ở góc dưới cùng bên trái của mỗi hộp.

Hình 2:Độ rộng tìm kiếm đầu tiên

Điều thú vị cần lưu ý ở đây là trong mỗi cấp, các nút được tìm kiếm dựa trên thứ tự cột được chỉ định (trong trường hợp của chúng tôi là trống) bất kể liên kết mẹ của nút. Ví dụ, lưu ý rằng ở cấp độ thứ tư, Lilach được truy cập đầu tiên, Rita thứ hai, Sean thứ ba và Gabriel cuối cùng. Đó là bởi vì trong số tất cả nhân viên ở cấp độ thứ tư, đó là thứ tự của họ dựa trên các giá trị trống rỗng của họ. Không giống như Lilach và Sean phải được khám xét liên tục vì họ là cấp dưới trực tiếp của cùng một người quản lý, Jiru.

Khá đơn giản để đưa ra một giải pháp T-SQL cung cấp sự tương đương logic của tùy chọn SAERCH DEPTH FIRST tiêu chuẩn. Bạn tạo một cột có tên lvl như tôi đã trình bày trước đó để theo dõi cấp của nút liên quan đến gốc (0 đối với cấp đầu tiên, 1 đối với cấp thứ hai, v.v.). Sau đó, bạn tính cột trình tự kết quả mong muốn trong truy vấn bên ngoài bằng cách sử dụng hàm ROW_NUMBER. Khi cửa sổ đặt hàng, bạn chỉ định lvl trước tiên, sau đó là cột đặt hàng mong muốn (trống trong trường hợp của chúng tôi). Đây là mã hoàn chỉnh của giải pháp:

 DECLARE @root AS INT =1; VỚI C AS (CHỌN empid, mgrid, empname, 0 AS lvl TỪ dbo. Nhân viên WHERE empid =@root UNION TẤT CẢ CHỌN S.empid, S.mgrid, S.empname, M.lvl + 1 AS lvl TỪ C AS M INNER THAM GIA dbo. Nhân viên NHƯ S TRÊN S.mgrid =M.empid) CHỌN empid, mgrid, empname, ROW_NUMBER () OVER (ORDER BY lvl, empid) AS seqbreadthFROM CORDER BY seqbreadth; 

Tiếp theo, hãy kiểm tra thứ tự tìm kiếm DEPTH FIRST. Theo tiêu chuẩn, đoạn mã sau sẽ trả về cây con của nhân viên 1, yêu cầu thứ tự tìm kiếm theo độ sâu đầu tiên theo trống, tạo một cột trình tự được gọi là seqdepth với các vị trí thứ tự của các nút được tìm kiếm:

 DECLARE @root AS INT =1; VỚI C AS (CHỌN empid, mgrid, empname FROM dbo. Nhân viên WHERE empid =@root UNION TẤT CẢ CHỌN S.empid, S.mgrid, S.empname FROM C AS M INNER JOIN dbo. Nhân viên AS S TRÊN S.mgrid =M .empid) TÌM KIẾM DEPTH ĐẦU TIÊN BẰNG BỘ trống seqdepth ---------------------------------------- CHỌN empid, mgrid, empname, seqdepthFROM CORDER BY seqdepth; 

Sau đây là kết quả mong muốn của mã này:

 empid mgrid empname seqdepth ------ ------ -------- --------- 1 NULL David 12 1 Eitan 24 2 Seraph 35 2 Jiru 48 5 Lilach 510 5 Sean 66 2 Steve 73 1 Ina 87 3 Aaron 99 7 Rita 1012 9 Emilia 1113 9 Michael 1214 9 Didi 1311 7 Gabriel 14 

Nhìn vào kết quả truy vấn mong muốn, có lẽ khó tìm ra lý do tại sao các giá trị trình tự lại được gán theo cách của chúng. Hình 3 sẽ hữu ích. Nó có một mô tả đồ họa về hệ thống phân cấp nhân viên, với một đường chấm phản ánh thứ tự tìm kiếm theo độ sâu đầu tiên, với các giá trị trình tự được chỉ định ở góc dưới cùng bên trái của mỗi hộp.

Hình 3:Độ sâu tìm kiếm đầu tiên

Việc đưa ra giải pháp T-SQL cung cấp tính hợp lý tương đương với tùy chọn TÌM KIẾM ĐẦU TIÊN tiêu chuẩn là một chút khó khăn, nhưng có thể thực hiện được. Tôi sẽ mô tả giải pháp trong hai bước.

Trong Bước 1, đối với mỗi nút, bạn tính toán một đường dẫn sắp xếp nhị phân được tạo từ một phân đoạn cho mỗi tổ tiên của nút, với mỗi phân đoạn phản ánh vị trí sắp xếp của tổ tiên trong số các anh chị em của nó. Bạn xây dựng đường dẫn này tương tự như cách bạn tính toán cột lvl. Đó là, bắt đầu với một chuỗi nhị phân trống cho nút gốc trong truy vấn neo. Sau đó, trong truy vấn đệ quy, bạn nối đường dẫn của cha với vị trí sắp xếp của nút giữa các anh chị em sau khi bạn chuyển đổi nó thành một phân đoạn nhị phân. Bạn sử dụng hàm ROW_NUMBER để tính toán vị trí, được phân vùng bởi cấp độ gốc (mgrid trong trường hợp của chúng tôi) và được sắp xếp theo cột thứ tự liên quan (trống trong trường hợp của chúng tôi). Bạn chuyển đổi số hàng thành giá trị nhị phân có kích thước đủ tùy thuộc vào số lượng con trực tiếp tối đa mà cha mẹ có thể có trong biểu đồ của bạn. BINARY (1) hỗ trợ tối đa 255 con cho mỗi phụ huynh, BINARY (2) hỗ trợ 65.535, BINARY (3):16.777.215, BINARY (4):4.294.967.295. Trong CTE đệ quy, các cột tương ứng trong các truy vấn liên kết và đệ quy phải cùng loại và cùng kích thước , vì vậy hãy đảm bảo chuyển đổi đường dẫn sắp xếp thành giá trị nhị phân có cùng kích thước trong cả hai.

Đây là mã triển khai Bước 1 trong giải pháp của chúng tôi (giả sử BINARY (1) là đủ cho mỗi phân đoạn nghĩa là bạn có không quá 255 cấp dưới trực tiếp cho mỗi người quản lý):

 DECLARE @root AS INT =1; VỚI C AS (SELECT empid, mgrid, empname, CAST (0x AS VARBINARY (900)) AS sortpath FROM dbo. đường dẫn sắp xếp + CAST (ROW_NUMBER () HẾT (PHẦN THEO ĐƠN HÀNG CỦA S.mgrid BỞI S.empid) NHƯ BINARY (1)) NHƯ BIẾN (900)) NHƯ đường dẫn sắp xếp TỪ C NHƯ M BÊN TRONG THAM GIA dbo. Nhân viên NHƯ S TRÊN S.mgrid =M.empid) CHỌN empid, mgrid, empname, sortpathFROM C; 

Mã này tạo ra kết quả sau:

 empid mgrid empname sortpath ------ --------- ----------- 1 NULL David 0x2 1 Eitan 0x013 1 Ina 0x027 3 Aaron 0x02019 7 Rita 0x02010111 7 Gabriel 0x02010212 9 Emilia 0x0201010113 9 Michael 0x0201010214 9 Didi 0x020101034 2 Seraph 0x01015 2 Jiru 0x01026 2 Steve 0x01038 5 Lilach 0x01020110 5 Sean 0x01020 

 Lưu ý rằng tôi đã sử dụng một chuỗi nhị phân trống làm đường dẫn sắp xếp cho nút gốc của cây con duy nhất mà chúng tôi đang truy vấn ở đây. Trong trường hợp thành phần liên kết có thể trả về nhiều gốc cây con, chỉ cần bắt đầu với một phân đoạn dựa trên tính toán ROW_NUMBER trong truy vấn liên kết, tương tự như cách bạn tính toán nó trong truy vấn đệ quy. Trong trường hợp như vậy, đường dẫn sắp xếp của bạn sẽ dài hơn một đoạn. 
 

 Việc còn lại phải làm trong Bước 2, là tạo cột seqdepth kết quả mong muốn bằng cách tính toán các số hàng được sắp xếp theo đường sắp xếp trong truy vấn bên ngoài, tương tự như vậy 
 
 DECLARE @root AS INT =1; VỚI C AS (SELECT empid, mgrid, empname, CAST (0x AS VARBINARY (900)) AS sortpath FROM dbo. đường dẫn sắp xếp + CAST (ROW_NUMBER () HẾT (PHẦN THEO ĐƠN HÀNG CỦA S.mgrid BỞI S.empid) NHƯ BINARY (1)) NHƯ BIẾN (900)) NHƯ đường dẫn sắp xếp TỪ C NHƯ M BÊN TRONG THAM GIA dbo. Nhân viên NHƯ S TRÊN S.mgrid =M.empid) CHỌN empid, mgrid, empname, ROW_NUMBER () HẾT (ĐẶT HÀNG THEO đường sắp xếp) NHƯ seqdepthFROM CORDER THEO seqdepth; 
 

 Giải pháp này tương đương hợp lý với việc sử dụng tùy chọn TÌM KIẾM DEPTH FIRST tiêu chuẩn được hiển thị trước đó cùng với đầu ra mong muốn của nó. 
 

 Khi bạn có một cột trình tự phản ánh độ sâu thứ tự tìm kiếm đầu tiên (trong trường hợp của chúng tôi là seqdepth), chỉ với một chút nỗ lực nữa, bạn có thể tạo ra một mô tả trực quan rất đẹp về hệ thống phân cấp. Bạn cũng sẽ cần cột lvl nói trên. Bạn sắp xếp truy vấn bên ngoài theo cột trình tự. Bạn trả về một số thuộc tính mà bạn muốn sử dụng để đại diện cho nút (giả sử là empname trong trường hợp của chúng tôi), có tiền tố là một số chuỗi (ví dụ '|') được sao chép lần lvl. Đây là mã hoàn chỉnh để đạt được mô tả trực quan như vậy:
 
 DECLARE @root AS INT =1; VỚI C AS (SELECT empid, empname, 0 AS lvl, CAST (0x AS VARBINARY (900)) AS sortpath FROM dbo. lvl, CAST (M.sortpath + CAST (ROW_NUMBER () OVER (PARTITION BY S.mgrid ORDER BY S.empid) AS BINARY (1)) AS VARBINARY (900)) AS sortpath TỪ C AS M INNER JOIN dbo. Nhân viên AS S ON S.mgrid =M.empid) SELECT empid, ROW_NUMBER () OVER (ORDER BY sắp xếp) AS seqdepth, REPLICATE ('|', lvl) + empname AS empFROM CORDER BY seqdepth; 
 

 Mã này tạo ra kết quả sau:
 
 empid seqdepth emp -------------------------------- 1 1 David2 2 | Eitan4 3 | | Seraph5 4 | | Jiru8 5 | | | Lilach10 6 | | | Sean6 7 | | Steve3 8 | Ina7 9 | | Aaron9 10 | | | Rita12 11 | | | | Emilia13 12 | | | | Michael14 13 | | | | Didi11 14 | | | Gabriel 
 

 Điều đó khá tuyệt! 
 
 Điều khoản CYCLE 
 

 Cấu trúc đồ thị có thể có chu kỳ. Các chu kỳ đó có thể hợp lệ hoặc không hợp lệ. Ví dụ cho các chu kỳ hợp lệ là biểu đồ đại diện cho các đường cao tốc và đường nối các thành phố và thị trấn. Đó là những gì được gọi là  đồ thị theo chu kỳ  . Ngược lại, một biểu đồ đại diện cho hệ thống phân cấp nhân viên như trong trường hợp của chúng tôi không được cho là có chu kỳ. Đó là thứ được gọi là  acyclic  đồ thị. Tuy nhiên, giả sử rằng do một số cập nhật sai, bạn kết thúc một chu kỳ ngoài ý muốn. Ví dụ:giả sử do nhầm lẫn bạn cập nhật ID người quản lý của Giám đốc điều hành (nhân viên 1) thành nhân viên 14 bằng cách chạy mã sau:
 
 CẬP NHẬT Nhân viên SET mgrid =14WHERE empid =1; 
 

 Bây giờ bạn có một chu kỳ không hợp lệ trong hệ thống phân cấp nhân viên. 
 

 Cho dù chu kỳ hợp lệ hay không hợp lệ, khi bạn duyệt qua cấu trúc biểu đồ, bạn chắc chắn không muốn tiếp tục theo đuổi một con đường tuần hoàn lặp đi lặp lại. Trong cả hai trường hợp, bạn muốn ngừng theo đuổi một đường dẫn khi tìm thấy sự xuất hiện không đầu tiên của cùng một nút và đánh dấu đường dẫn đó là theo chu kỳ. 
 

 Vì vậy, điều gì sẽ xảy ra khi bạn truy vấn một biểu đồ có các chu kỳ bằng cách sử dụng truy vấn đệ quy, không có cơ chế để phát hiện những chu kỳ đó? Điều này phụ thuộc vào việc thực hiện. Trong SQL Server, tại một số điểm, bạn sẽ đạt đến giới hạn đệ quy tối đa và truy vấn của bạn sẽ bị hủy bỏ. Ví dụ:giả sử bạn chạy bản cập nhật ở trên đã giới thiệu chu trình, hãy thử chạy truy vấn đệ quy sau để xác định cây con của nhân viên 1:
 
 DECLARE @root AS INT =1; VỚI C AS (CHỌN empid, mgrid, empname FROM dbo. Nhân viên WHERE empid =@root UNION TẤT CẢ CHỌN S.empid, S.mgrid, S.empname FROM C AS M INNER JOIN dbo. Nhân viên AS S TRÊN S.mgrid =M .empid) CHỌN empid, mgrid, empnameFROM C; 
 

 Vì mã này không đặt giới hạn đệ quy tối đa rõ ràng nên giới hạn mặc định là 100 được giả định. SQL Server hủy bỏ việc thực thi mã này trước khi hoàn thành và tạo ra lỗi:
 
 empid mgrid empname ------ ------ -------- 1 14 David2 1 Eitan3 1 Ina7 3 Aaron9 7 Rita11 7 Gabriel12 9 Emilia13 9 Michael14 9 Didi1 14 David2 1 Eitan3 1 Ina7 3 Aaron ... 
 Msg 530, Mức 16, Trạng thái 1, Dòng 432 
 Tuyên bố đã chấm dứt. Đệ quy tối đa 100 đã hết trước khi hoàn thành câu lệnh. 

 Tiêu chuẩn SQL định nghĩa một mệnh đề gọi là CYCLE cho các CTE đệ quy, cho phép bạn xử lý các chu trình trong đồ thị của mình. Bạn chỉ định mệnh đề này ngay trước truy vấn bên ngoài. Nếu mệnh đề TÌM KIẾM cũng có, bạn chỉ định nó trước rồi đến mệnh đề CYCLE. Đây là cú pháp của mệnh đề CYCLE:
 CYCLE  
 ĐẶT  ĐẾN  DEFAULT  
 SỬ DỤNG  

 Việc phát hiện chu kỳ dựa trên  danh sách cột chu kỳ  được chỉ định . Ví dụ:trong hệ thống phân cấp nhân viên của chúng tôi, bạn có thể muốn sử dụng cột trống cho mục đích này. Khi cùng một giá trị trống xuất hiện lần thứ hai, một chu kỳ được phát hiện và truy vấn không theo đuổi đường dẫn như vậy nữa. Bạn chỉ định một  cột đánh dấu chu kỳ  mới điều đó sẽ cho biết liệu một chu kỳ có được tìm thấy hay không và các giá trị của riêng bạn dưới dạng  dấu chu kỳ  và  dấu không theo chu kỳ  các giá trị. Ví dụ:những giá trị đó có thể là 1 và 0 hoặc 'Có' và 'Không', hoặc bất kỳ giá trị nào khác mà bạn chọn. Trong mệnh đề SỬ DỤNG, bạn chỉ định một tên cột mảng mới sẽ giữ đường dẫn của các nút được tìm thấy cho đến nay. 
 

 Dưới đây là cách bạn xử lý yêu cầu cấp dưới của một số nhân viên gốc đầu vào, với khả năng phát hiện các chu kỳ dựa trên cột trống, chỉ ra 1 trong cột đánh dấu chu kỳ khi một chu kỳ được phát hiện và 0 nếu không:
 
 DECLARE @root AS INT =1; VỚI C AS (CHỌN empid, mgrid, empname FROM dbo. Nhân viên WHERE empid =@root UNION TẤT CẢ CHỌN S.empid, S.mgrid, S.empname FROM C AS M INNER JOIN dbo. Nhân viên AS S TRÊN S.mgrid =M .empid) CYCLE trống ĐẶT chu kỳ ĐẾN 1 MẶC ĐỊNH 0 ------------------------------------ CHỌN trống, mgrid, empnameFROM C; 
 

 Đây là đầu ra mong muốn của mã này:
 
 empid mgrid empname cycle ------ ------ -------- ------ 1 14 David 02 1 Eitan 03 1 Ina 07 3 Aaron 09 7 Rita 011 7 Gabriel 012 9 Emilia 013 9 Michael 014 9 Didi 01 14 David 14 2 Seraph 05 2 Jiru 06 2 Steve 08 5 Lilach 010 5 Sean 0 
 

 T-SQL hiện không hỗ trợ mệnh đề CYCLE, nhưng có một giải pháp cung cấp một cách tương đương logic. Nó bao gồm ba bước. Nhớ lại rằng trước đó bạn đã xây dựng một đường dẫn sắp xếp nhị phân để xử lý thứ tự tìm kiếm đệ quy. Theo cách tương tự, là bước đầu tiên trong giải pháp, bạn xây dựng một đường dẫn tổ tiên dựa trên chuỗi ký tự được tạo bằng các ID nút (ID nhân viên trong trường hợp của chúng tôi) của tổ tiên dẫn đến nút hiện tại, bao gồm cả nút hiện tại. Bạn muốn có dấu phân cách giữa các ID nút, bao gồm một ở đầu và một ở cuối. 
 

 Đây là mã để xây dựng đường dẫn tổ tiên như vậy:
 
 DECLARE @root AS INT =1; VỚI C AS (SELECT empid, mgrid, empname, CAST ('.' + CAST (empid AS VARCHAR (4)) + '.' AS VARCHAR (900)) AS ancpath FROM dbo. S.empid, S.mgrid, S.empname, CAST (M.ancpath + CAST (S.empid AS VARCHAR (4)) + '.' AS VARCHAR (900)) AS ancpath FROM C AS M INNER JOIN dbo. AS S ON S.mgrid =M.empid) CHỌN empid, mgrid, empname, ancpathFROM C; 
 

 Mã này tạo ra kết quả sau, vẫn theo đuổi các đường dẫn tuần hoàn và do đó sẽ hủy bỏ trước khi hoàn thành khi vượt quá giới hạn đệ quy tối đa:
 
 empid mgrid empname ancpath ------ ------------------------------- 1 14 David. 1.2 1 Eitan .1.2.3 1 Ina .1.3.7 3 Aaron .1.3.7.9 7 Rita .1.3.7.9.11 7 Gabriel .1.3.7.11.12 9 Emilia .1.3.7.9.12.13 9 Michael .1.3.7.9. 13.14 9 Didi .1.3.7.9.14.1 14 David .1.3.7.9.14.1.2 1 Eitan .1.3.7.9.14.1.2.3 1 Ina .1.3.7.9.14.1.3.7 3 Aaron .1.3.7.9.14.1.3.7. ... 
 Msg 530, Mức 16, Trạng thái 1, Dòng 492 
 Tuyên bố đã chấm dứt. Đệ quy tối đa 100 đã hết trước khi hoàn thành câu lệnh. 

 Eyeballing the output, you can identify a cyclic path when the current node appears in the path for the nonfirst time, such as in the path '.1.3.7.9.14.1.' . 
 

 In the second step of the solution you produce the cycle mark column. In the anchor query you simply set it to 0 since clearly a cycle cannot be found in the first node. In the recursive member you use a CASE expression that checks with a LIKE-based predicate whether the current node ID already appears in the parent’s path, in which case it returns the value 1, or not, in which case it returns the value 0. 
 

 Here’s the code implementing Step 2:
 
DECLARE @root AS INT =1; WITH C AS( SELECT empid, mgrid, empname, CAST('.' + CAST(empid AS VARCHAR(4)) + '.' AS VARCHAR(900)) AS ancpath, 0 AS cycle FROM dbo.Employees WHERE empid =@root UNION ALL SELECT S.empid, S.mgrid, S.empname, CAST(M.ancpath + CAST(S.empid AS VARCHAR(4)) + '.' AS VARCHAR(900)) AS ancpath, CASE WHEN M.ancpath LIKE '%.' + CAST(S.empid AS VARCHAR(4)) + '.%' THEN 1 ELSE 0 END AS cycle FROM C AS M INNER JOIN dbo.Employees AS S ON S.mgrid =M.empid)SELECT empid, mgrid, empname, ancpath, cycleFROM C;
 

 This code generates the following output, again, still pursuing cyclic paths and failing once the max recursion limit is reached:
 
empid mgrid empname ancpath cycle------ ------ -------- ------------------- ------1 14 David .1. 02 1 Eitan .1.2. 03 1 Ina .1.3. 07 3 Aaron .1.3.7. 09 7 Rita .1.3.7.9. 011 7 Gabriel .1.3.7.11. 012 9 Emilia .1.3.7.9.12. 013 9 Michael .1.3.7.9.13. 014 9 Didi .1.3.7.9.14. 01 14 David .1.3.7.9.14.1. 12 1 Eitan .1.3.7.9.14.1.2. 03 1 Ina .1.3.7.9.14.1.3. 17 3 Aaron .1.3.7.9.14.1.3.7. 1...
 Msg 530, Level 16, State 1, Line 532
The statement terminated. The maximum recursion 100 has been exhausted before statement completion. 

 The third and last step is to add a predicate to the ON clause of the recursive member that pursues a path only if a cycle was not detected in the parent’s path.
 

 Here’s the code implementing Step 3, which is also the complete solution:
 
DECLARE @root AS INT =1; WITH C AS( SELECT empid, mgrid, empname, CAST('.' + CAST(empid AS VARCHAR(4)) + '.' AS VARCHAR(900)) AS ancpath, 0 AS cycle FROM dbo.Employees WHERE empid =@root UNION ALL SELECT S.empid, S.mgrid, S.empname, CAST(M.ancpath + CAST(S.empid AS VARCHAR(4)) + '.' AS VARCHAR(900)) AS ancpath, CASE WHEN M.ancpath LIKE '%.' + CAST(S.empid AS VARCHAR(4)) + '.%' THEN 1 ELSE 0 END AS cycle FROM C AS M INNER JOIN dbo.Employees AS S ON S.mgrid =M.empid AND M.cycle =0)SELECT empid, mgrid, empname, cycleFROM C;
 

 This code runs to completion, and generates the following output:
 
empid mgrid empname cycle------ ------ -------- -----------1 14 David 02 1 Eitan 03 1 Ina 07 3 Aaron 09 7 Rita 011 7 Gabriel 012 9 Emilia 013 9 Michael 014 9 Didi 01 14 David 14 2 Seraph 05 2 Jiru 06 2 Steve 08 5 Lilach 010 5 Sean 0
 

 You identify the erroneous data easily here, and fix the problem by setting the manager ID of the CEO to NULL, like so:
 
UPDATE Employees SET mgrid =NULLWHERE empid =1;
 

 Run the recursive query and you will find that there are no cycles present.
 
 Kết luận 
 

 Recursive CTEs enable you to write concise declarative solutions for purposes such as traversing graph structures. A recursive CTE has at least one anchor member, which gets executed once, and at least one recursive member, which gets executed repeatedly until it returns an empty result set. Using a query option called MAXRECURSION you can control the maximum number of allowed executions of the recursive member as a safety measure. To limit the executions of the recursive member programmatically for filtering purposes you can maintain a column that tracks the level of the current node with respect to the root node.
 

 The SQL standard supports two very powerful options for recursive CTEs that are currently not available in T-SQL. One is a clause called SEARCH that controls the recursive search order, and another is a clause called CYCLE that detects cycles in the traversed paths. I provided logically equivalent solutions that are currently available in T-SQL. If you find that the unavailable standard features could be important future additions to T-SQL, make sure to vote for them here:
 
 
Add support for ISO/IEC SQL SEARCH clause to recursive CTEs in T-SQL 
Add support for ISO/IEC SQL CYCLE clause to recursive CTEs in T-SQL
 

 This article concludes the coverage of the logical aspects of CTEs. Next month I’ll turn my attention to physical/performance considerations of CTEs.