Database
 sql >> Teknologi Basis Data >  >> RDS >> Database

Dasar-dasar ekspresi tabel, Bagian 6 – CTE rekursif

Artikel ini adalah bagian keenam dari seri tentang ekspresi tabel. Bulan lalu di Bagian 5 saya membahas perlakuan logis CTE nonrekursif. Bulan ini saya membahas perawatan logis CTE rekursif. Saya menjelaskan dukungan T-SQL untuk CTE rekursif, serta elemen standar yang belum didukung oleh T-SQL. Saya memberikan solusi T-SQL yang setara secara logis untuk elemen yang tidak didukung.

Contoh data

Untuk contoh data saya akan menggunakan tabel yang disebut Karyawan, yang menyimpan hierarki karyawan. Kolom empid mewakili ID karyawan dari bawahan (node ​​anak), dan kolom mgrid mewakili ID karyawan dari manajer (node ​​induk). Gunakan kode berikut untuk membuat dan mengisi tabel Karyawan di database tempdb:

SET NOCOUNT ON;
 
USE tempdb;
DROP TABLE IF EXISTS dbo.Employees;
GO
 
CREATE TABLE dbo.Employees
(
  empid   INT         NOT NULL
    CONSTRAINT PK_Employees PRIMARY KEY,
  mgrid   INT         NULL     
    CONSTRAINT FK_Employees_Employees REFERENCES dbo.Employees,
  empname VARCHAR(25) NOT NULL,
  salary  MONEY       NOT NULL,
  CHECK (empid <> mgrid)
);
 
INSERT INTO dbo.Employees(empid, mgrid, empname, salary)
  VALUES(1,  NULL, 'David'  , $10000.00),
        (2,     1, 'Eitan'  ,  $7000.00),
        (3,     1, 'Ina'    ,  $7500.00),
        (4,     2, 'Seraph' ,  $5000.00),
        (5,     2, 'Jiru'   ,  $5500.00),
        (6,     2, 'Steve'  ,  $4500.00),
        (7,     3, 'Aaron'  ,  $5000.00),
        (8,     5, 'Lilach' ,  $3500.00),
        (9,     7, 'Rita'   ,  $3000.00),
        (10,    5, 'Sean'   ,  $3000.00),
        (11,    7, 'Gabriel',  $3000.00),
        (12,    9, 'Emilia' ,  $2000.00),
        (13,    9, 'Michael',  $2000.00),
        (14,    9, 'Didi'   ,  $1500.00);
 
CREATE UNIQUE INDEX idx_unc_mgrid_empid
  ON dbo.Employees(mgrid, empid)
  INCLUDE(empname, salary);

Perhatikan bahwa akar hierarki karyawan—CEO—memiliki NULL di kolom mgrid. Semua karyawan lainnya memiliki manajer, jadi kolom mgrid mereka disetel ke ID karyawan manajer mereka.

Gambar 1 memiliki gambaran grafis hierarki karyawan, yang menunjukkan nama karyawan, ID, dan lokasinya dalam hierarki.

Gambar 1:Hirarki karyawan

CTE rekursif

CTE rekursif memiliki banyak kasus penggunaan. Kategori penggunaan klasik berkaitan dengan penanganan struktur grafik, seperti hierarki karyawan kami. Tugas yang melibatkan grafik sering membutuhkan lintasan panjang yang berubah-ubah. Misalnya diberikan ID karyawan dari beberapa manajer, kembalikan karyawan input, serta semua bawahan karyawan input di semua tingkatan; yaitu bawahan langsung dan tidak langsung. Jika Anda memiliki batasan kecil yang diketahui pada jumlah level yang mungkin perlu Anda ikuti (derajat grafik), Anda dapat menggunakan kueri dengan gabungan per level bawahan. Namun, jika derajat grafik berpotensi tinggi, di beberapa titik menjadi tidak praktis untuk menulis kueri dengan banyak gabungan. Pilihan lain adalah menggunakan kode iteratif imperatif, tetapi solusi seperti itu cenderung panjang. Di sinilah CTE rekursif benar-benar bersinar—mereka memungkinkan Anda menggunakan solusi deklaratif, ringkas, dan intuitif.

Saya akan mulai dengan dasar-dasar CTE rekursif sebelum saya membahas hal-hal yang lebih menarik di mana saya membahas kemampuan penelusuran dan bersepeda.

Ingat bahwa sintaks kueri terhadap CTE adalah sebagai berikut:

WITH [ ( ) ]
AS
(

)
;

Di sini saya menunjukkan satu CTE yang didefinisikan menggunakan klausa WITH, tetapi seperti yang Anda ketahui, Anda dapat mendefinisikan beberapa CTE yang dipisahkan dengan koma.

Dalam CTE reguler, nonrekursif, ekspresi tabel dalam didasarkan pada kueri yang dievaluasi hanya sekali. Dalam CTE rekursif, ekspresi tabel dalam biasanya didasarkan pada dua kueri yang dikenal sebagai anggota , meskipun Anda dapat memiliki lebih dari dua untuk menangani beberapa kebutuhan khusus. Anggota biasanya dipisahkan oleh operator UNION ALL untuk menunjukkan bahwa hasil mereka disatukan.

Seorang anggota dapat menjadi anggota jangkar —artinya dievaluasi hanya sekali; atau bisa menjadi anggota rekursif —artinya dievaluasi berulang kali, hingga mengembalikan kumpulan hasil kosong. Berikut sintaks kueri terhadap CTE rekursif yang didasarkan pada satu anggota jangkar dan satu anggota rekursif:

DENGAN [ ( ) ]
AS
(

UNION ALL

)
;

Apa yang membuat anggota rekursif adalah memiliki referensi ke nama CTE. Referensi ini mewakili kumpulan hasil eksekusi terakhir. Dalam eksekusi pertama anggota rekursif, referensi ke nama CTE mewakili kumpulan hasil anggota jangkar. Dalam eksekusi ke-N, di mana N> 1, referensi ke nama CTE mewakili himpunan hasil dari eksekusi (N – 1) anggota rekursif. Seperti disebutkan, setelah anggota rekursif mengembalikan set kosong, itu tidak dieksekusi lagi. Referensi ke nama CTE di kueri luar mewakili kumpulan hasil terpadu dari eksekusi tunggal anggota jangkar, dan semua eksekusi anggota rekursif.

Kode berikut mengimplementasikan tugas yang disebutkan di atas untuk mengembalikan subpohon karyawan untuk manajer input yang diberikan, meneruskan ID karyawan 3 sebagai karyawan root dalam contoh ini:

DECLARE @root AS INT = 3;
 
WITH C AS
(
  SELECT empid, mgrid, empname
  FROM dbo.Employees
  WHERE empid = @root
 
  UNION ALL
 
  SELECT S.empid, S.mgrid, S.empname
  FROM C AS M
    INNER JOIN dbo.Employees AS S
      ON S.mgrid = M.empid
)
SELECT empid, mgrid, empname
FROM C;

Kueri jangkar dijalankan hanya sekali, mengembalikan baris untuk karyawan root input (karyawan 3 dalam kasus kami).

Kueri rekursif menggabungkan kumpulan karyawan dari tingkat sebelumnya—diwakili oleh referensi ke nama CTE, alias M untuk manajer—dengan bawahan langsung mereka dari tabel Karyawan, alias S untuk bawahan. Predikat join adalah S.mgrid =M.empid, artinya nilai mgrid bawahan sama dengan nilai empid manajer. Kueri rekursif dijalankan empat kali sebagai berikut:

  1. Kembalikan bawahan karyawan 3; keluaran:karyawan 7
  2. Kembalikan bawahan karyawan 7; keluaran:karyawan 9 dan 11
  3. Kembalikan bawahan karyawan 9 dan 11; keluaran:12, 13 dan 14
  4. Kembalikan bawahan karyawan 12, 13 dan 14; keluaran:himpunan kosong; rekursi berhenti

Referensi ke nama CTE di kueri luar mewakili hasil terpadu dari eksekusi tunggal kueri jangkar (karyawan 3) dengan hasil semua eksekusi kueri rekursif (karyawan 7, 9, 11, 12, 13 dan 14). Kode ini menghasilkan output berikut:

empid  mgrid  empname
------ ------ --------
3      1      Ina
7      3      Aaron
9      7      Rita
11     7      Gabriel
12     9      Emilia
13     9      Michael
14     9      Didi

Masalah umum dalam solusi pemrograman adalah kode pelarian seperti loop tak terbatas yang biasanya disebabkan oleh bug. Dengan CTE rekursif, bug dapat menyebabkan eksekusi landasan pacu dari anggota rekursif. Misalnya, dalam solusi kami untuk mengembalikan bawahan dari karyawan input, Anda memiliki bug di predikat bergabung anggota rekursif. Alih-alih menggunakan ON S.mgrid =M.empid, Anda menggunakan ON S.mgrid =S.mgrid, seperti:

DECLARE @root AS INT = 3;
 
WITH C AS
(
  SELECT empid, mgrid, empname
  FROM dbo.Employees
  WHERE empid = @root
 
  UNION ALL
 
  SELECT S.empid, S.mgrid, S.empname
  FROM C AS M
    INNER JOIN dbo.Employees AS S
      ON S.mgrid = S.mgrid
)
SELECT empid, mgrid, empname
FROM C;

Diberikan setidaknya satu karyawan dengan ID manajer nonnull yang ada di tabel, eksekusi anggota rekursif akan terus mengembalikan hasil yang tidak kosong. Ingat bahwa kondisi terminasi implisit untuk anggota rekursif adalah ketika eksekusinya mengembalikan kumpulan hasil kosong. Jika mengembalikan kumpulan hasil yang tidak kosong, SQL Server akan mengeksekusinya lagi. Anda menyadari bahwa jika SQL Server tidak memiliki mekanisme untuk membatasi eksekusi rekursif, itu hanya akan terus mengeksekusi anggota rekursif berulang kali selamanya. Sebagai ukuran keamanan, T-SQL mendukung opsi kueri MAXRECURSION yang membatasi jumlah maksimum eksekusi anggota rekursif yang diizinkan. Secara default, batas ini disetel ke 100, tetapi Anda dapat mengubahnya ke nilai SMALLINT nonnegatif apa pun, dengan 0 menunjukkan tanpa batas. Menyetel batas rekursi maksimum ke nilai positif N berarti bahwa N + 1 percobaan eksekusi anggota rekursif dibatalkan dengan kesalahan. Misalnya, menjalankan kode kereta di atas apa adanya berarti Anda mengandalkan batas rekursi maksimum default 100, sehingga eksekusi 101 anggota rekursif gagal:

empid  mgrid  empname
------ ------ --------
3      1      Ina
2      1      Eitan
3      1      Ina
...
Msg 530, Level 16, State 1, Line 121
Pernyataan dihentikan. Rekursi maksimum 100 telah habis sebelum pernyataan selesai.

Katakan bahwa di organisasi Anda, aman untuk mengasumsikan bahwa hierarki karyawan tidak akan melebihi 6 tingkat manajemen. Anda dapat mengurangi batas rekursi maksimum dari 100 ke angka yang jauh lebih kecil, seperti 10 agar aman, seperti:

DECLARE @root AS INT = 3;
 
WITH C AS
(
  SELECT empid, mgrid, empname
  FROM dbo.Employees
  WHERE empid = @root
 
  UNION ALL
 
  SELECT S.empid, S.mgrid, S.empname
  FROM C AS M
    INNER JOIN dbo.Employees AS S
      ON S.mgrid = S.mgrid
)
SELECT empid, mgrid, empname
FROM C
OPTION (MAXRECURSION 10);

Sekarang jika ada bug yang mengakibatkan eksekusi anggota rekursif yang kabur, bug tersebut akan ditemukan pada 11 percobaan eksekusi anggota rekursif, bukan pada eksekusi 101:

empid  mgrid  empname
------ ------ --------
3      1      Ina
2      1      Eitan
3      1      Ina
...
Msg 530, Level 16, State 1, Line 149
Pernyataan dihentikan. Rekursi maksimum 10 telah habis sebelum pernyataan selesai.

Penting untuk dicatat bahwa batas rekursi maksimum harus digunakan terutama sebagai ukuran keamanan untuk membatalkan eksekusi kode pelarian kereta. Ingat bahwa ketika batas terlampaui, eksekusi kode dibatalkan dengan kesalahan. Anda tidak boleh menggunakan opsi ini untuk membatasi jumlah level yang harus dikunjungi untuk tujuan pemfilteran. Anda tidak ingin terjadi kesalahan saat tidak ada masalah dengan kode.

Untuk tujuan pemfilteran, Anda dapat membatasi jumlah level untuk dikunjungi secara terprogram. Anda menentukan kolom bernama lvl yang melacak nomor level karyawan saat ini dibandingkan dengan karyawan root input. Dalam kueri jangkar Anda menyetel kolom lvl ke konstanta 0. Dalam kueri rekursif Anda menyetelnya ke nilai lvl manajer plus 1. Untuk memfilter sebanyak mungkin level di bawah root input sebagai @maxlevel, tambahkan predikat M.lvl <@ maxlevel ke klausa ON dari kueri rekursif. Misalnya, kode berikut mengembalikan karyawan 3 dan dua tingkat bawahan karyawan 3:

DECLARE @root AS INT = 3, @maxlevel AS INT = 2;
 
WITH C AS
(
  SELECT empid, mgrid, empname, 0 AS lvl
  FROM dbo.Employees
  WHERE empid = @root
 
  UNION ALL
 
  SELECT S.empid, S.mgrid, S.empname, M.lvl + 1 AS lvl
  FROM C AS M
    INNER JOIN dbo.Employees AS S
      ON S.mgrid = M.empid
      AND M.lvl < @maxlevel
)
SELECT empid, mgrid, empname, lvl
FROM C;

Kueri ini menghasilkan keluaran berikut:

empid  mgrid  empname  lvl
------ ------ -------- ----
3      1      Ina      0
7      3      Aaron    1
9      7      Rita     2
11     7      Gabriel  2

klausa SEARCH dan CYCLE Standar

Standar ISO/IEC SQL mendefinisikan dua opsi yang sangat kuat untuk CTE rekursif. Salah satunya adalah klausa yang disebut SEARCH yang mengontrol urutan pencarian rekursif, dan yang lainnya adalah klausa yang disebut CYCLE yang mengidentifikasi siklus di jalur yang dilalui. Berikut sintaks standar untuk kedua klausa:

7.18

Fungsi

Tentukan pembuatan informasi pengurutan dan deteksi siklus dalam hasil ekspresi kueri rekursif.

Format

::=
[ ]
SEBAGAI

[ ]
::=
| |
::=
SEARCH SET
::=
KEDALAMAN PERTAMA OLEH | LUAS PERTAMA OLEH
::=
::=
CYCLE SET UNTUK
DEFAULT MENGGUNAKAN
::= [ { }… ]
::=
::=
::=
::=
::=

Pada saat penulisan T-SQL tidak mendukung opsi ini, tetapi di tautan berikut Anda dapat menemukan permintaan peningkatan fitur yang meminta penyertaan mereka dalam T-SQL di masa mendatang, dan pilih mereka:

  • Tambahkan dukungan untuk klausa ISO/IEC SQL SEARCH ke CTE rekursif di T-SQL
  • Tambahkan dukungan untuk klausa ISO/IEC SQL CYCLE ke CTE rekursif di T-SQL

Di bagian berikut, saya akan menjelaskan dua opsi standar dan juga memberikan solusi alternatif yang setara secara logis yang saat ini tersedia di T-SQL.

klausa PENCARIAN

Klausa SEARCH standar mendefinisikan urutan pencarian rekursif sebagai BREADTH FIRST atau DEPTH FIRST oleh beberapa kolom pemesanan tertentu, dan membuat kolom urutan baru dengan posisi ordinal dari node yang dikunjungi. Anda menentukan BREADTH PERTAMA untuk mencari pertama di setiap level (breadth) dan kemudian turun ke level (kedalaman). Anda menentukan DEPTH FIRST untuk mencari terlebih dahulu ke bawah (kedalaman) dan kemudian melintasi (breadth).

Anda menentukan klausa SEARCH tepat sebelum kueri luar.

Saya akan mulai dengan contoh untuk urutan pencarian rekursif pertama yang luas. Ingatlah bahwa fitur ini tidak tersedia di T-SQL, jadi Anda tidak akan dapat benar-benar menjalankan contoh yang menggunakan klausa standar di SQL Server atau Azure SQL Database. Kode berikut mengembalikan subpohon karyawan 1, meminta urutan pencarian pertama yang luas dengan empid, membuat kolom urutan yang disebut seqbreadth dengan posisi ordinal dari node yang dikunjungi:

DECLARE @root AS INT = 1;
 
WITH C AS
(
  SELECT empid, mgrid, empname
  FROM dbo.Employees
  WHERE empid = @root
 
  UNION ALL
 
  SELECT S.empid, S.mgrid, S.empname
  FROM C AS M
    INNER JOIN dbo.Employees AS S
      ON S.mgrid = M.empid
)
 
SEARCH BREADTH FIRST BY empid SET seqbreadth
--------------------------------------------
 
SELECT empid, mgrid, empname, seqbreadth
FROM C
ORDER BY seqbreadth;

Inilah output yang diinginkan dari kode ini:

empid  mgrid  empname  seqbreadth
------ ------ -------- -----------
1      NULL   David    1
2      1      Eitan    2
3      1      Ina      3
4      2      Seraph   4
5      2      Jiru     5
6      2      Steve    6
7      3      Aaron    7
8      5      Lilach   8
9      7      Rita     9
10     5      Sean     10
11     7      Gabriel  11
12     9      Emilia   12
13     9      Michael  13
14     9      Didi     14

Jangan bingung dengan fakta bahwa nilai seqbreadth tampaknya identik dengan nilai empid. Itu hanya kebetulan sebagai hasil dari cara saya secara manual menetapkan nilai empiris dalam data sampel yang saya buat.

Gambar 2 memiliki penggambaran grafis dari hierarki karyawan, dengan garis putus-putus yang menunjukkan luasnya urutan pertama di mana node dicari. Nilai empid muncul tepat di bawah nama karyawan, dan nilai seqbreadth yang ditetapkan muncul di sudut kiri bawah setiap kotak.

Gambar 2:Cari luasnya terlebih dahulu

Yang menarik untuk dicatat di sini adalah bahwa dalam setiap level, node dicari berdasarkan urutan kolom yang ditentukan (empid dalam kasus kami) terlepas dari asosiasi induk node. Misalnya, perhatikan bahwa di tingkat keempat Lilach diakses pertama, Rita kedua, Sean ketiga dan Gabriel terakhir. Itu karena di antara semua karyawan di level keempat, itu urutannya berdasarkan nilai-nilai empid mereka. Lilach dan Sean tidak seharusnya digeledah secara berurutan karena mereka adalah bawahan langsung dari manajer yang sama, Jiru.

Cukup mudah untuk menghasilkan solusi T-SQL yang menyediakan logika yang setara dengan opsi standar SAERCH DEPTH FIRST. Anda membuat kolom bernama lvl seperti yang saya tunjukkan sebelumnya untuk melacak level node sehubungan dengan root (0 untuk level pertama, 1 untuk yang kedua, dan seterusnya). Kemudian Anda menghitung kolom urutan hasil yang diinginkan di kueri luar menggunakan fungsi ROW_NUMBER. Saat pemesanan jendela, Anda menentukan lvl terlebih dahulu, dan kemudian kolom pemesanan yang diinginkan (empid dalam kasus kami). Berikut kode solusi lengkapnya:

DECLARE @root AS INT = 1;
 
WITH C AS
(
  SELECT empid, mgrid, empname, 0 AS lvl
  FROM dbo.Employees
  WHERE empid = @root
 
  UNION ALL
 
  SELECT S.empid, S.mgrid, S.empname, M.lvl + 1 AS lvl
  FROM C AS M
    INNER JOIN dbo.Employees AS S
      ON S.mgrid = M.empid
)
SELECT empid, mgrid, empname,
  ROW_NUMBER() OVER(ORDER BY lvl, empid) AS seqbreadth
FROM C
ORDER BY seqbreadth;

Selanjutnya, mari kita periksa urutan pencarian DEPTH FIRST. Menurut standar, kode berikut harus mengembalikan subpohon karyawan 1, meminta urutan pencarian pertama yang mendalam oleh empid, membuat kolom urutan yang disebut seqdepth dengan posisi ordinal dari node yang dicari:

DECLARE @root AS INT = 1;
 
WITH C AS
(
  SELECT empid, mgrid, empname
  FROM dbo.Employees
  WHERE empid = @root
 
  UNION ALL
 
  SELECT S.empid, S.mgrid, S.empname
  FROM C AS M
    INNER JOIN dbo.Employees AS S
      ON S.mgrid = M.empid
)
 
SEARCH DEPTH FIRST BY empid SET seqdepth
----------------------------------------
 
SELECT empid, mgrid, empname, seqdepth
FROM C
ORDER BY seqdepth;

Berikut adalah output yang diinginkan dari kode ini:

empid  mgrid  empname  seqdepth
------ ------ -------- ---------
1      NULL   David    1
2      1      Eitan    2
4      2      Seraph   3
5      2      Jiru     4
8      5      Lilach   5
10     5      Sean     6
6      2      Steve    7
3      1      Ina      8
7      3      Aaron    9
9      7      Rita     10
12     9      Emilia   11
13     9      Michael  12
14     9      Didi     13
11     7      Gabriel  14

Melihat output kueri yang diinginkan, mungkin sulit untuk mengetahui mengapa nilai urutan ditetapkan seperti itu. Gambar 3 akan membantu. Ini memiliki penggambaran grafis hierarki karyawan, dengan garis putus-putus yang mencerminkan urutan pencarian pertama yang mendalam, dengan nilai urutan yang ditetapkan di sudut kiri bawah setiap kotak.

Gambar 3:Kedalaman penelusuran terlebih dahulu

Muncul dengan solusi T-SQL yang menyediakan setara logis dengan opsi SEARCH DEPTH FIRST standar agak rumit, namun bisa dilakukan. Saya akan menjelaskan solusinya dalam dua langkah.

Pada Langkah 1, untuk setiap node Anda menghitung jalur pengurutan biner yang dibuat dari segmen per ancestor node, dengan setiap segmen mencerminkan posisi sort ancestor di antara saudara kandungnya. Anda membangun jalur ini mirip dengan cara Anda menghitung kolom lvl. Artinya, mulailah dengan string biner kosong untuk simpul akar dalam kueri jangkar. Kemudian, dalam kueri rekursif Anda menggabungkan jalur induk dengan posisi pengurutan simpul di antara saudara kandung setelah Anda mengonversinya menjadi segmen biner. Anda menggunakan fungsi ROW_NUMBER untuk menghitung posisi, dipartisi oleh induk (mggrid dalam kasus kami) dan diurutkan oleh kolom pemesanan yang relevan (empid dalam kasus kami). Anda mengonversi nomor baris menjadi nilai biner dengan ukuran yang memadai bergantung pada jumlah maksimum turunan langsung yang dapat dimiliki orang tua dalam grafik Anda. BINARY(1) mendukung hingga 255 anak per orang tua, BINARY(2) mendukung 65.535, BINARY(3):16.777.215, BINARY(4):4.294.967.295. Dalam CTE rekursif, kolom yang sesuai di jangkar dan kueri rekursif harus memiliki jenis dan ukuran yang sama , jadi pastikan untuk mengonversi jalur pengurutan ke nilai biner dengan ukuran yang sama di keduanya.

Berikut kode yang menerapkan Langkah 1 dalam solusi kami (dengan asumsi BINARY(1) cukup per segmen yang berarti Anda tidak memiliki lebih dari 255 bawahan langsung per manajer):

DECLARE @root AS INT = 1;
 
WITH C AS
(
  SELECT empid, mgrid, empname,
    CAST(0x AS VARBINARY(900)) AS sortpath
  FROM dbo.Employees
  WHERE empid = @root
 
  UNION ALL
 
  SELECT S.empid, S.mgrid, S.empname,
     CAST(M.sortpath
            + CAST(ROW_NUMBER() OVER(PARTITION BY S.mgrid ORDER BY S.empid)
                AS BINARY(1))
       AS VARBINARY(900)) AS sortpath
  FROM C AS M
    INNER JOIN dbo.Employees AS S
      ON S.mgrid = M.empid
)
SELECT empid, mgrid, empname, sortpath
FROM C;

Kode ini menghasilkan output berikut:

empid  mgrid  empname  sortpath
------ ------ -------- -----------
1      NULL   David    0x
2      1      Eitan    0x01
3      1      Ina      0x02
7      3      Aaron    0x0201
9      7      Rita     0x020101
11     7      Gabriel  0x020102
12     9      Emilia   0x02010101
13     9      Michael  0x02010102
14     9      Didi     0x02010103
4      2      Seraph   0x0101
5      2      Jiru     0x0102
6      2      Steve    0x0103
8      5      Lilach   0x010201
10     5      Sean     0x010202

Perhatikan bahwa saya menggunakan string biner kosong sebagai jalur pengurutan untuk simpul akar dari subpohon tunggal yang kita kueri di sini. Jika anggota jangkar berpotensi mengembalikan beberapa akar subpohon, cukup mulai dengan segmen yang didasarkan pada perhitungan ROW_NUMBER dalam kueri jangkar, mirip dengan cara Anda menghitungnya dalam kueri rekursif. Dalam kasus seperti itu, jalur pengurutan Anda akan menjadi satu segmen lebih panjang.

Yang tersisa untuk dilakukan di Langkah 2, adalah membuat kolom seqdepth hasil yang diinginkan dengan menghitung nomor baris yang diurutkan berdasarkan sortpath di kueri luar, seperti

DECLARE @root AS INT = 1;
 
WITH C AS
(
  SELECT empid, mgrid, empname,
    CAST(0x AS VARBINARY(900)) AS sortpath
  FROM dbo.Employees
  WHERE empid = @root
 
  UNION ALL
 
  SELECT S.empid, S.mgrid, S.empname,
     CAST(M.sortpath
            + CAST(ROW_NUMBER() OVER(PARTITION BY S.mgrid ORDER BY S.empid)
                AS BINARY(1))
       AS VARBINARY(900)) AS sortpath
  FROM C AS M
    INNER JOIN dbo.Employees AS S
      ON S.mgrid = M.empid
)
SELECT empid, mgrid, empname,
  ROW_NUMBER() OVER(ORDER BY sortpath) AS seqdepth
FROM C
ORDER BY seqdepth;

Solusi ini setara secara logis dengan menggunakan opsi SEARCH DEPTH FIRST standar yang ditunjukkan sebelumnya bersama dengan output yang diinginkan.

Setelah Anda memiliki kolom urutan yang mencerminkan kedalaman urutan pencarian pertama (kedalaman seq dalam kasus kami), hanya dengan sedikit lebih banyak usaha, Anda dapat menghasilkan penggambaran visual hierarki yang sangat bagus. Anda juga akan membutuhkan kolom lvl yang disebutkan di atas. Anda memesan kueri luar dengan kolom urutan. Anda mengembalikan beberapa atribut yang ingin Anda gunakan untuk mewakili node (misalnya, empname dalam kasus kami), diawali dengan beberapa string (misalnya ' | ') direplikasi lvl kali. Berikut kode lengkap untuk mencapai penggambaran visual tersebut:

DECLARE @root AS INT = 1;
 
WITH C AS
(
  SELECT empid, empname, 0 AS lvl,
    CAST(0x AS VARBINARY(900)) AS sortpath
  FROM dbo.Employees
  WHERE empid = @root
 
  UNION ALL
 
  SELECT S.empid, S.empname, M.lvl + 1 AS lvl,
     CAST(M.sortpath
            + CAST(ROW_NUMBER() OVER(PARTITION BY S.mgrid ORDER BY S.empid)
                AS BINARY(1))
       AS VARBINARY(900)) AS sortpath
  FROM C AS M
    INNER JOIN dbo.Employees AS S
      ON S.mgrid = M.empid
)
SELECT empid,
  ROW_NUMBER() OVER(ORDER BY sortpath) AS seqdepth,
  REPLICATE(' | ', lvl) + empname AS emp
FROM C
ORDER BY seqdepth;

Kode ini menghasilkan output berikut:

empid  seqdepth  emp
------ --------- --------------------
1      1         David
2      2          | Eitan
4      3          |  | Seraph
5      4          |  | Jiru
8      5          |  |  | Lilach
10     6          |  |  | Sean
6      7          |  | Steve
3      8          | Ina
7      9          |  | Aaron
9      10         |  |  | Rita
12     11         |  |  |  | Emilia
13     12         |  |  |  | Michael
14     13         |  |  |  | Didi
11     14         |  |  | Gabriel

Itu sangat keren!

klausa CYCLE

Struktur grafik mungkin memiliki siklus. Siklus tersebut bisa valid atau tidak valid. Contoh untuk siklus yang valid adalah grafik yang mewakili jalan raya dan jalan yang menghubungkan kota dan kota. Itulah yang disebut sebagai grafik siklik . Sebaliknya, grafik yang mewakili hierarki karyawan seperti dalam kasus kami tidak seharusnya memiliki siklus. Itulah yang disebut sebagai asiklik grafik. Namun, anggaplah karena beberapa pembaruan yang salah, Anda berakhir dengan siklus secara tidak sengaja. Misalnya, Anda tidak sengaja memperbarui ID manajer dari CEO (karyawan 1) menjadi karyawan 14 dengan menjalankan kode berikut:

UPDATE Employees
  SET mgrid = 14
WHERE empid = 1;

Anda sekarang memiliki siklus yang tidak valid dalam hierarki karyawan.

Apakah siklus valid atau tidak valid, ketika Anda melintasi struktur grafik, Anda tentu tidak ingin terus mengejar jalur siklus berulang kali. Dalam kedua kasus tersebut, Anda ingin berhenti mengejar jalur setelah kemunculan non-pertama dari simpul yang sama ditemukan, dan tandai jalur tersebut sebagai siklik.

Jadi apa yang terjadi ketika Anda membuat kueri grafik yang memiliki siklus menggunakan kueri rekursif, tanpa mekanisme untuk mendeteksinya? Hal ini tergantung pada implementasinya. Di SQL Server, pada titik tertentu Anda akan mencapai batas rekursi maksimum, dan kueri Anda akan dibatalkan. Misalnya, dengan asumsi Anda menjalankan pembaruan di atas yang memperkenalkan siklus, coba jalankan kueri rekursif berikut untuk mengidentifikasi subpohon karyawan 1:

DECLARE @root AS INT = 1;
 
WITH C AS
(
  SELECT empid, mgrid, empname
  FROM dbo.Employees
  WHERE empid = @root
 
  UNION ALL
 
  SELECT S.empid, S.mgrid, S.empname
  FROM C AS M
    INNER JOIN dbo.Employees AS S
      ON S.mgrid = M.empid
)
SELECT empid, mgrid, empname
FROM C;

Karena kode ini tidak menetapkan batas rekursi maksimum yang eksplisit, batas default 100 diasumsikan. SQL Server membatalkan eksekusi kode ini sebelum selesai dan menghasilkan kesalahan:

empid  mgrid  empname
------ ------ --------
1      14     David
2      1      Eitan
3      1      Ina
7      3      Aaron
9      7      Rita
11     7      Gabriel
12     9      Emilia
13     9      Michael
14     9      Didi
1      14     David
2      1      Eitan
3      1      Ina
7      3      Aaron
...
Msg 530, Level 16, State 1, Line 432
Pernyataan dihentikan. Rekursi maksimum 100 telah habis sebelum pernyataan selesai.

Standar SQL mendefinisikan klausa yang disebut CYCLE untuk CTE rekursif, yang memungkinkan Anda menangani siklus dalam grafik Anda. Anda menentukan klausa ini tepat sebelum kueri luar. Jika klausa SEARCH juga ada, Anda menentukannya terlebih dahulu dan kemudian klausa CYCLE. Berikut sintaks klausa CYCLE:

CYCLE
SET KE DEFAULT
MENGGUNAKAN

Deteksi siklus didasarkan pada daftar kolom siklus yang ditentukan . Misalnya, dalam hierarki karyawan kami, Anda mungkin ingin menggunakan kolom empid untuk tujuan ini. Ketika nilai empid yang sama muncul untuk kedua kalinya, sebuah siklus terdeteksi, dan kueri tidak mengejar jalur seperti itu lebih jauh. Anda menentukan kolom tanda siklus baru yang akan menunjukkan apakah siklus ditemukan atau tidak, dan nilai Anda sendiri sebagai tanda siklus dan tanda non-siklus nilai-nilai. Misalnya, itu bisa berupa 1 dan 0 atau 'Ya' dan 'Tidak', atau nilai lain yang Anda pilih. Dalam klausa USING Anda menentukan nama kolom array baru yang akan menampung jalur node yang ditemukan sejauh ini.

Inilah cara Anda menangani permintaan untuk bawahan dari beberapa karyawan root input, dengan kemampuan untuk mendeteksi siklus berdasarkan kolom empid, menunjukkan 1 di kolom tanda siklus saat siklus terdeteksi, dan 0 sebaliknya:

DECLARE @root AS INT = 1;
 
WITH C AS
(
  SELECT empid, mgrid, empname
  FROM dbo.Employees
  WHERE empid = @root
 
  UNION ALL
 
  SELECT S.empid, S.mgrid, S.empname
  FROM C AS M
    INNER JOIN dbo.Employees AS S
      ON S.mgrid = M.empid
)
 
CYCLE empid SET cycle TO 1 DEFAULT 0
------------------------------------
 
SELECT empid, mgrid, empname
FROM C;

Inilah output yang diinginkan dari kode ini:

empid  mgrid  empname  cycle
------ ------ -------- ------
1      14     David    0
2      1      Eitan    0
3      1      Ina      0
7      3      Aaron    0
9      7      Rita     0
11     7      Gabriel  0
12     9      Emilia   0
13     9      Michael  0
14     9      Didi     0
1      14     David    1
4      2      Seraph   0
5      2      Jiru     0
6      2      Steve    0
8      5      Lilach   0
10     5      Sean     0

T-SQL saat ini tidak mendukung klausa CYCLE, tetapi ada solusi yang menyediakan setara logis. Ini melibatkan tiga langkah. Ingatlah bahwa sebelumnya Anda membuat jalur pengurutan biner untuk menangani urutan pencarian rekursif. Dengan cara yang sama, sebagai langkah pertama dalam solusi, Anda membangun jalur ancestor berbasis string karakter yang terbuat dari ID node (ID karyawan dalam kasus kami) dari ancestor yang mengarah ke node saat ini, termasuk node saat ini. Anda ingin pemisah antara ID node, termasuk satu di awal dan satu di akhir.

Berikut kode untuk membangun jalur leluhur seperti itu:

DECLARE @root AS INT = 1;
 
WITH C AS
(
  SELECT empid, mgrid, empname,
    CAST('.' + CAST(empid AS VARCHAR(4)) + '.' AS VARCHAR(900)) AS ancpath
  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
  FROM C AS M
    INNER JOIN dbo.Employees AS S
      ON S.mgrid = M.empid
)
SELECT empid, mgrid, empname, ancpath
FROM C;

Kode ini menghasilkan output berikut, masih mengejar jalur siklus, dan karena itu dibatalkan sebelum selesai setelah batas rekursi maksimum terlampaui:

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, Level 16, State 1, Line 492
Pernyataan dihentikan. Rekursi maksimum 100 telah habis sebelum pernyataan selesai.

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, cycle
FROM 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.                 0
2      1      Eitan    .1.2.               0
3      1      Ina      .1.3.               0
7      3      Aaron    .1.3.7.             0
9      7      Rita     .1.3.7.9.           0
11     7      Gabriel  .1.3.7.11.          0
12     9      Emilia   .1.3.7.9.12.        0
13     9      Michael  .1.3.7.9.13.        0
14     9      Didi     .1.3.7.9.14.        0
1      14     David    .1.3.7.9.14.1.      1
2      1      Eitan    .1.3.7.9.14.1.2.    0
3      1      Ina      .1.3.7.9.14.1.3.    1
7      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, cycle
FROM C;

This code runs to completion, and generates the following output:

empid  mgrid  empname  cycle
------ ------ -------- -----------
1      14     David    0
2      1      Eitan    0
3      1      Ina      0
7      3      Aaron    0
9      7      Rita     0
11     7      Gabriel  0
12     9      Emilia   0
13     9      Michael  0
14     9      Didi     0
1      14     David    1
4      2      Seraph   0
5      2      Jiru     0
6      2      Steve    0
8      5      Lilach   0
10     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 = NULL
WHERE empid = 1;

Run the recursive query and you will find that there are no cycles present.

Kesimpulan

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.


  1. Database
    2.   
  2. Mysql
    3.   
  3. Oracle
    4.   
  4. Sqlserver
    5.   
  5. PostgreSQL
    6.   
  6. Access
    7.   
  7. SQLite
    8.   
  8. MariaDB

  1. Dasar-dasar ekspresi tabel, Bagian 3 – Tabel turunan, pertimbangan pengoptimalan

  2. Hekaton dengan twist:TVP dalam memori – Bagian 1

  3. SQL Kunci Asing:Semua yang Perlu Anda Ketahui Tentang Operasi Kunci Asing

  4. Tipe Data Tanggal Waktu T-SQL

  5. Dasar-dasar ekspresi tabel, Bagian 9 – Tampilan, dibandingkan dengan tabel turunan dan CTE