Trước hết, chúng ta hãy cố gắng đơn giản hóa và làm rõ mô tả thuật toán được đưa ra trên trang hướng dẫn sử dụng. Để đơn giản hóa nó, hãy chỉ xem xét union all trong with recursive đệ quy mệnh đề bây giờ (và union sau):
WITH RECURSIVE pseudo-entity-name(column-names) AS (
Initial-SELECT
UNION ALL
Recursive-SELECT using pseudo-entity-name
)
Outer-SELECT using pseudo-entity-name
Để làm rõ nó, chúng ta hãy mô tả quá trình thực thi truy vấn bằng mã giả:
working-recordset = result of Initial-SELECT
append working-recordset to empty outer-recordset
while( working-recordset is not empty ) begin
new working-recordset = result of Recursive-SELECT
taking previous working-recordset as pseudo-entity-name
append working-recordset to outer-recordset
end
overall-result = result of Outer-SELECT
taking outer-recordset as pseudo-entity-name
Hoặc thậm chí ngắn hơn - Công cụ cơ sở dữ liệu thực hiện lựa chọn ban đầu, lấy các hàng kết quả của nó làm tập hợp làm việc. Sau đó, nó lặp lại thực hiện lựa chọn đệ quy trên nhóm làm việc, mỗi lần thay thế nội dung của nhóm làm việc bằng kết quả truy vấn thu được. Quá trình này kết thúc khi tập hợp trống được trả về bằng cách chọn đệ quy. Và tất cả các hàng kết quả được cung cấp trước tiên bởi lựa chọn ban đầu và sau đó bởi lựa chọn đệ quy được thu thập và cung cấp cho lựa chọn bên ngoài, kết quả này sẽ trở thành kết quả truy vấn tổng thể.
Truy vấn này đang tính toán giai thừa của 3:
WITH RECURSIVE factorial(F,n) AS (
SELECT 1 F, 3 n
UNION ALL
SELECT F*n F, n-1 n from factorial where n>1
)
SELECT F from factorial where n=1
Chọn ban đầu SELECT 1 F, 3 n cung cấp cho chúng ta các giá trị ban đầu:3 cho đối số và 1 cho giá trị hàm.
Chọn đệ quy SELECT F*n F, n-1 n from factorial where n>1 nói rằng mỗi khi chúng ta cần nhân giá trị chức năng cuối cùng với giá trị đối số cuối cùng và giá trị đối số giảm dần.
Công cụ cơ sở dữ liệu thực thi nó như sau:
Trước hết, nó thực thi initail select, cung cấp trạng thái ban đầu của tập bản ghi làm việc:
F | n
--+--
1 | 3
Sau đó, nó biến đổi tập bản ghi đang hoạt động với truy vấn đệ quy và có được trạng thái thứ hai:
F | n
--+--
3 | 2
Sau đó, trạng thái thứ ba:
F | n
--+--
6 | 1
Ở trạng thái thứ ba không có hàng nào theo sau n>1 điều kiện trong lựa chọn đệ quy, do đó, tập hợp làm việc tương tự là các lần thoát khỏi vòng lặp.
Tập bản ghi bên ngoài hiện giữ tất cả các hàng, được trả về bởi lựa chọn ban đầu và đệ quy:
F | n
--+--
1 | 3
3 | 2
6 | 1
Outer select lọc ra tất cả các kết quả trung gian từ tập bản ghi bên ngoài, chỉ hiển thị giá trị giai thừa cuối cùng trở thành kết quả truy vấn tổng thể:
F
--
6
Và bây giờ chúng ta hãy xem xét bảng forest(id,parent_id,name) :
id | parent_id | name
---+-----------+-----------------
1 | | item 1
2 | 1 | subitem 1.1
3 | 1 | subitem 1.2
4 | 1 | subitem 1.3
5 | 3 | subsubitem 1.2.1
6 | | item 2
7 | 6 | subitem 2.1
8 | | item 3
' Mở rộng toàn bộ cây 'ở đây có nghĩa là sắp xếp các mục cây theo thứ tự độ sâu đầu tiên có thể đọc được của con người trong khi tính toán các cấp độ và (có thể) đường dẫn của chúng. Cả hai tác vụ (về mức độ hoặc đường dẫn sắp xếp và tính toán chính xác) đều không thể giải quyết được trong một (hoặc thậm chí bất kỳ số lượng không đổi nào của) SELECT mà không sử dụng mệnh đề WITH RECURSIVE (hoặc mệnh đề Oracle CONNECT BY, không được PostgreSQL hỗ trợ). Nhưng truy vấn đệ quy này thực hiện công việc (tốt, gần như vậy, hãy xem ghi chú bên dưới):
WITH RECURSIVE fulltree(id,parent_id,level,name,path) AS (
SELECT id, parent_id, 1 as level, name, name||'' as path from forest where parent_id is null
UNION ALL
SELECT t.id, t.parent_id, ft.level+1 as level, t.name, ft.path||' / '||t.name as path
from forest t, fulltree ft where t.parent_id = ft.id
)
SELECT * from fulltree order by path
Công cụ cơ sở dữ liệu thực thi nó như thế này:
Đầu tiên, nó thực hiện chọn initail, cung cấp tất cả các mục cấp cao nhất (gốc) từ forest bảng:
id | parent_id | level | name | path
---+-----------+-------+------------------+----------------------------------------
1 | | 1 | item 1 | item 1
8 | | 1 | item 3 | item 3
6 | | 1 | item 2 | item 2
Sau đó, nó thực hiện lựa chọn đệ quy, cung cấp tất cả các mục cấp 2 từ forest bảng:
id | parent_id | level | name | path
---+-----------+-------+------------------+----------------------------------------
2 | 1 | 2 | subitem 1.1 | item 1 / subitem 1.1
3 | 1 | 2 | subitem 1.2 | item 1 / subitem 1.2
4 | 1 | 2 | subitem 1.3 | item 1 / subitem 1.3
7 | 6 | 2 | subitem 2.1 | item 2 / subitem 2.1
Sau đó, nó thực hiện lựa chọn đệ quy một lần nữa, truy xuất các mục cấp độ 3d:
id | parent_id | level | name | path
---+-----------+-------+------------------+----------------------------------------
5 | 3 | 3 | subsubitem 1.2.1 | item 1 / subitem 1.2 / subsubitem 1.2.1
Và bây giờ nó thực thi lựa chọn đệ quy một lần nữa, cố gắng truy xuất các mục cấp 4, nhưng không có mục nào trong số chúng, vì vậy vòng lặp sẽ thoát ra.
SELECT bên ngoài đặt thứ tự hàng chính xác mà con người có thể đọc được, sắp xếp trên cột đường dẫn:
id | parent_id | level | name | path
---+-----------+-------+------------------+----------------------------------------
1 | | 1 | item 1 | item 1
2 | 1 | 2 | subitem 1.1 | item 1 / subitem 1.1
3 | 1 | 2 | subitem 1.2 | item 1 / subitem 1.2
5 | 3 | 3 | subsubitem 1.2.1 | item 1 / subitem 1.2 / subsubitem 1.2.1
4 | 1 | 2 | subitem 1.3 | item 1 / subitem 1.3
6 | | 1 | item 2 | item 2
7 | 6 | 2 | subitem 2.1 | item 2 / subitem 2.1
8 | | 1 | item 3 | item 3
LƯU Ý :Thứ tự hàng kết quả sẽ chỉ đúng khi không có ký tự dấu câu đối chiếu trước / trong tên mục. Nếu chúng ta đổi tên Item 2 trong Item 1 * , nó sẽ phá vỡ thứ tự hàng, đứng giữa Item 1 và con cháu của nó.
Giải pháp ổn định hơn là sử dụng ký tự tab (E'\t' ) làm dấu phân tách đường dẫn trong truy vấn (có thể được thay thế bằng dấu phân tách đường dẫn dễ đọc hơn sau này:trong lựa chọn bên ngoài, trước khi bác bỏ đối với con người hoặc v.v.). Các đường dẫn được phân tách bằng tab sẽ giữ lại thứ tự chính xác cho đến khi có các tab hoặc ký tự điều khiển trong tên mặt hàng - có thể dễ dàng kiểm tra và loại trừ mà không làm mất khả năng sử dụng.
Rất đơn giản để sửa đổi truy vấn cuối cùng để mở rộng bất kỳ cây con tùy ý nào - bạn chỉ cần thay thế điều kiện parent_id is null với perent_id=1 (Ví dụ). Lưu ý rằng biến thể truy vấn này sẽ trả về tất cả các cấp và đường dẫn liên quan đến Item 1 .
Và bây giờ là về những sai lầm điển hình . Sai lầm điển hình đáng chú ý nhất dành riêng cho các truy vấn đệ quy là xác định điều kiện dừng xấu trong lựa chọn đệ quy, dẫn đến lặp vô hạn.
Ví dụ:nếu chúng ta bỏ qua where n>1 điều kiện trong mẫu giai thừa ở trên, việc thực hiện phép chọn đệ quy sẽ không bao giờ cho một tập hợp trống (vì chúng ta không có điều kiện để lọc ra hàng đơn) và vòng lặp sẽ tiếp tục vô hạn.
Đó là lý do có thể xảy ra nhất khiến một số truy vấn của bạn bị treo (lý do không cụ thể nhưng vẫn có thể xảy ra khác là lựa chọn rất không hiệu quả, thực thi trong thời gian hữu hạn nhưng rất lâu).
Không có nhiều hướng dẫn truy vấn cụ thể của RECURSIVE đề cập đến, theo như tôi biết. Nhưng tôi muốn đề xuất (khá rõ ràng) thủ tục xây dựng truy vấn đệ quy từng bước.
-
Xây dựng và gỡ lỗi riêng biệt lựa chọn ban đầu của bạn.
-
Bọc nó bằng giàn giáo VỚI cấu trúc RECURSIVE
và bắt đầu xây dựng và gỡ lỗi lựa chọn đệ quy của bạn.
Cấu trúc la mắng được đề xuất là như sau:
WITH RECURSIVE rec( <Your column names> ) AS (
<Your ready and working initial SELECT>
UNION ALL
<Recursive SELECT that you are debugging now>
)
SELECT * from rec limit 1000
Lựa chọn bên ngoài đơn giản nhất này sẽ xuất ra toàn bộ tập bản ghi bên ngoài, như chúng ta đã biết, chứa tất cả các hàng đầu ra từ lựa chọn ban đầu và mọi thực thi của chọn đĩa khôi phục trong một vòng lặp theo thứ tự đầu ra ban đầu của chúng - giống như trong các mẫu ở trên! limit 1000 một phần sẽ ngăn chặn việc treo, thay thế nó bằng đầu ra quá khổ, trong đó bạn sẽ có thể thấy điểm dừng bị bỏ lỡ.
- Sau khi gỡ lỗi bản dựng ban đầu và đệ quy, hãy chọn và gỡ lỗi lựa chọn bên ngoài của bạn.
Và bây giờ điều cuối cùng cần đề cập - sự khác biệt trong việc sử dụng union thay vì union all trong with recursive đệ quy mệnh đề. Nó giới thiệu ràng buộc về tính duy nhất của hàng dẫn đến hai dòng bổ sung trong mã giả thực thi của chúng tôi:
working-recordset = result of Initial-SELECT
discard duplicate rows from working-recordset /*union-specific*/
append working-recordset to empty outer-recordset
while( working-recordset is not empty ) begin
new working-recordset = result of Recursive-SELECT
taking previous working-recordset as pseudo-entity-name
discard duplicate rows and rows that have duplicates in outer-recordset
from working-recordset /*union-specific*/
append working-recordset to outer-recordset
end
overall-result = result of Outer-SELECT
taking outer-recordset as pseudo-entity-name
