KAL
Menu

CTE Rekursif

Mengunjungi hierarki dan membuat barisan dengan WITH RECURSIVE.

Daftar isi

Klausa WITH RECURSIVE membolehkan sebuah CTE merujuk dirinya sendiri, sehingga query dapat mengulangi langkahnya sampai suatu syarat terpenuhi. Topik ini membahas dua pola yang paling sering dipakai, yaitu menjelajahi hierarki kategori dari induk ke anak dengan kolom kedalaman dan membuat barisan angka, diikuti pembahasan anggota jangkar, anggota rekursif, pemutusan siklus dengan UNION, serta batas kedalaman yang masuk akal. Dataset tabel buku dan kategori yang sama dengan topik lain di modul ini dipakai sepanjang contoh.

Anggota jangkar dan anggota rekursif#

Sebuah CTE rekursif terdiri atas dua bagian yang disatukan dengan UNION ALL atau UNION. Bagian pertama adalah anggota jangkar (anchor member), yaitu query biasa yang menghasilkan baris awal. Bagian kedua adalah anggota rekursif (recursive member), yaitu query yang merujuk nama CTE itu sendiri dan menyusun baris baru dari hasil sebelumnya. SQLite bekerja dengan antrean, yaitu baris jangkar diproses lebih dahulu, lalu setiap baris yang dihasilkan anggota rekursif masuk kembali ke antrean hingga tidak ada baris baru.

Contoh terkecil yang menunjukkan mekanisme ini adalah barisan angka. Jangkar memberi nilai 1, dan anggota rekursif menambah satu selama nilai masih di bawah sepuluh.

sql Barisan angka satu sampai sepuluh 
WITH RECURSIVE angka(n) AS (
  VALUES(1)
  UNION ALL
  SELECT n + 1 FROM angka WHERE n < 10
)
SELECT n FROM angka;
text Keluaran 
1
2
3
4
5
6
7
8
9
10

Syarat WHERE n < 10 pada anggota rekursif adalah bagian yang menghentikan barisan, sehingga tanpa syarat itu query tidak pernah selesai. Selain syarat pada anggota rekursif, klausa LIMIT pada query utama juga menghentikan proses lebih awal begitu jumlah baris yang diminta sudah tercukupi.

sql Barisan dengan batas LIMIT 
WITH RECURSIVE angka(n) AS (
  VALUES(1)
  UNION ALL
  SELECT n + 1 FROM angka WHERE n < 10
)
SELECT n FROM angka LIMIT 5;
text Keluaran 
1
2
3
4
5

Menjelajah hierarki kategori#

Pola yang sama diterapkan pada hierarki tabel kategori yang memuat dua tingkat, yaitu kategori induk dan kategori anak melalui kolom id_induk. Jangkar memilih satu kategori tertentu dengan kedalaman nol, dan anggota rekursif mencari anak dari setiap baris yang sudah tercapai sambil menaikkan kedalamannya satu. Kolom kedalaman inilah yang membuat hasil kunjungan dapat dibaca sebagai struktur, bukan sekadar kumpulan baris.

sql Menuruni hierarki dari satu akar 
CREATE TABLE kategori (
  id       INTEGER PRIMARY KEY,
  nama     TEXT NOT NULL,
  id_induk INTEGER REFERENCES kategori(id)
);
CREATE TABLE buku (
  id          INTEGER PRIMARY KEY,
  judul       TEXT NOT NULL,
  tahun       INTEGER NOT NULL,
  id_kategori INTEGER REFERENCES kategori(id)
);
INSERT INTO kategori (id, nama, id_induk) VALUES
  (1, 'Ilmu Komputer', NULL),
  (2, 'Sastra',        NULL),
  (3, 'Sejarah',       NULL),
  (4, 'Algoritma',     1),
  (5, 'Jaringan',      1),
  (6, 'Puisi',         2),
  (7, 'Prosa',         2);
INSERT INTO buku (id, judul, tahun, id_kategori) VALUES
  (1, 'Dasar Algoritma',        2018, 4),
  (2, 'Struktur Data Terapan',  2021, 4),
  (3, 'Analisis Kompleksitas',  2019, 4),
  (4, 'Jaringan Komputer',      2020, 5),
  (5, 'Protokol Internet',      2023, 5),
  (6, 'Kumpulan Puisi Lama',    2012, 6),
  (7, 'Antologi Puisi Baru',    2022, 6),
  (8, 'Kamus Istilah Komputer', 2024, 1),
  (9, 'Ensiklopedia Sastra',    2009, NULL);

WITH RECURSIVE turun AS (
  SELECT id, nama, 0 AS kedalaman
  FROM kategori
  WHERE id = 1
  UNION ALL
  SELECT k.id, k.nama, t.kedalaman + 1
  FROM kategori AS k
  JOIN turun AS t ON k.id_induk = t.id
)
SELECT id, nama, kedalaman
FROM turun;
text Keluaran 
1|Ilmu Komputer|0
4|Algoritma|1
5|Jaringan|1

Hasilnya tiga baris sesuai struktur sebenarnya, yaitu Ilmu Komputer di kedalaman nol dengan anaknya Algoritma dan Jaringan di kedalaman satu. Untuk menuruni seluruh pohon sekaligus, jangkarnya diganti menjadi semua kategori tanpa induk, dan setiap cabang diproses dengan mekanisme antrean yang sama.

sql Menuruni seluruh pohon kategori 
CREATE TABLE kategori (
  id       INTEGER PRIMARY KEY,
  nama     TEXT NOT NULL,
  id_induk INTEGER REFERENCES kategori(id)
);
CREATE TABLE buku (
  id          INTEGER PRIMARY KEY,
  judul       TEXT NOT NULL,
  tahun       INTEGER NOT NULL,
  id_kategori INTEGER REFERENCES kategori(id)
);
INSERT INTO kategori (id, nama, id_induk) VALUES
  (1, 'Ilmu Komputer', NULL),
  (2, 'Sastra',        NULL),
  (3, 'Sejarah',       NULL),
  (4, 'Algoritma',     1),
  (5, 'Jaringan',      1),
  (6, 'Puisi',         2),
  (7, 'Prosa',         2);
INSERT INTO buku (id, judul, tahun, id_kategori) VALUES
  (1, 'Dasar Algoritma',        2018, 4),
  (2, 'Struktur Data Terapan',  2021, 4),
  (3, 'Analisis Kompleksitas',  2019, 4),
  (4, 'Jaringan Komputer',      2020, 5),
  (5, 'Protokol Internet',      2023, 5),
  (6, 'Kumpulan Puisi Lama',    2012, 6),
  (7, 'Antologi Puisi Baru',    2022, 6),
  (8, 'Kamus Istilah Komputer', 2024, 1),
  (9, 'Ensiklopedia Sastra',    2009, NULL);
WITH RECURSIVE turun AS (
  SELECT id, nama, 0 AS kedalaman
  FROM kategori
  WHERE id_induk IS NULL
  UNION ALL
  SELECT k.id, k.nama, t.kedalaman + 1
  FROM kategori AS k
  JOIN turun AS t ON k.id_induk = t.id
)
SELECT nama, kedalaman
FROM turun
ORDER BY kedalaman, nama;
text Keluaran 
Ilmu Komputer|0
Sastra|0
Sejarah|0
Algoritma|1
Jaringan|1
Prosa|1
Puisi|1

Tiga kategori induk tampil di kedalaman nol dan empat kategori anak di kedalaman satu, sementara buku Kamus Istilah Komputer tidak berpengaruh karena kunjungan ini hanya menyusuri kategori. Urutan keluaran pada CTE rekursif mengikuti urutan antrean, bukan kebetulan penyimpanan, sehingga ORDER BY pada query utama tetap perlu ditulis bila urutan tampil harus rapi.

UNION, siklus, dan pemutusan#

Penyambung antara jangkar dan anggota rekursif menentukan perlakuan terhadap baris yang sudah pernah muncul. Dengan UNION ALL, setiap baris hasil diterima apa adanya, sehingga paling efisien untuk struktur berbentuk pohon yang tidak pernah mengulang baris. Dengan UNION, baris yang sudah ada pada hasil tidak diterima lagi, dan penolakan itulah yang memutus perjalanan pada struktur yang mengandung siklus.

Untuk memperagakannya, ubah baris Ilmu Komputer menjadi induk bagi dirinya sendiri dengan pernyataan UPDATE, sehingga struktur yang semula berbentuk pohon menjadi mengandung siklus, kemudian jalankan penelusuran dengan UNION.

sql Menjelajah kategori dengan siklus menggunakan UNION 
CREATE TABLE kategori (
  id       INTEGER PRIMARY KEY,
  nama     TEXT NOT NULL,
  id_induk INTEGER REFERENCES kategori(id)
);
CREATE TABLE buku (
  id          INTEGER PRIMARY KEY,
  judul       TEXT NOT NULL,
  tahun       INTEGER NOT NULL,
  id_kategori INTEGER REFERENCES kategori(id)
);
INSERT INTO kategori (id, nama, id_induk) VALUES
  (1, 'Ilmu Komputer', NULL),
  (2, 'Sastra',        NULL),
  (3, 'Sejarah',       NULL),
  (4, 'Algoritma',     1),
  (5, 'Jaringan',      1),
  (6, 'Puisi',         2),
  (7, 'Prosa',         2);
INSERT INTO buku (id, judul, tahun, id_kategori) VALUES
  (1, 'Dasar Algoritma',        2018, 4),
  (2, 'Struktur Data Terapan',  2021, 4),
  (3, 'Analisis Kompleksitas',  2019, 4),
  (4, 'Jaringan Komputer',      2020, 5),
  (5, 'Protokol Internet',      2023, 5),
  (6, 'Kumpulan Puisi Lama',    2012, 6),
  (7, 'Antologi Puisi Baru',    2022, 6),
  (8, 'Kamus Istilah Komputer', 2024, 1),
  (9, 'Ensiklopedia Sastra',    2009, NULL);
UPDATE kategori SET id_induk = 1 WHERE id = 1;

WITH RECURSIVE turun AS (
  SELECT id, nama
  FROM kategori
  WHERE id = 1
  UNION
  SELECT k.id, k.nama
  FROM kategori AS k
  JOIN turun AS t ON k.id_induk = t.id
)
SELECT nama
FROM turun
ORDER BY nama;
text Keluaran 
Algoritma
Ilmu Komputer
Jaringan

Ketika anggota rekursif mencoba mengembalikan Ilmu Komputer lagi karena baris itu menjadi anak dirinya sendiri, baris yang sama sudah berada pada hasil dan ditolak, sehingga kunjungan berhenti dengan sendirinya. Pada data yang benar-benar berbentuk pohon, UNION ALL tetap menjadi pilihan karena tanpa pemeriksaan baris ganda.

Batas kedalaman yang masuk akal juga sebaiknya dituliskan secara eksplisit. Rekursi pada SQLite hanya berhenti bila anggota rekursif tidak lagi menghasilkan baris, atau bila LIMIT pada query utama tercapai, sehingga syarat seperti WHERE kedalaman < N pada anggota rekursif melindungi query dari struktur yang lebih dalam dari perkiraan maupun dari data yang rusak.

Ringkasan#

  • CTE rekursif tersusun dari anggota jangkar yang memberi baris awal dan anggota rekursif yang menyusun baris baru dari hasil sebelumnya.
  • Rekursi berhenti bila anggota rekursif tidak menghasilkan baris lagi atau bila LIMIT pada query utama tercapai.
  • Kunjungan hierarki membawa kolom kedalaman yang naik satu pada setiap lompatan induk ke anak.
  • UNION ALL cepat untuk pohon, sedangkan UNION menolak baris yang sudah ada dan memutus siklus.

Referensi#