CTE rekursif

Menelusuri hierarki dan graf dengan WITH RECURSIVE.

Daftar isi

Topik ini membahas CTE rekursif, bentuk CTE yang mengevaluasi dirinya sendiri berulang kali, sehingga kedalaman yang tidak diketahui sebelumnya dapat ditelusuri, seperti hierarki staf atau pohon kategori. Dua bagian pernyataannya dikenal sebagai jangkar (anchor) dan istilah rekursif, dan pemahaman alirannya membuat seluruh kelas pertanyaan penelusuran menjadi mungkin.

Blok penyiapan dataset#

bash

# bagan staf bertingkat untuk latihan rekursi
PGOPTIONS='-c client_min_messages=warning' psql -q -U postgres -d perpustakaan <<'SQL'
DROP TABLE IF EXISTS peminjaman, buku, anggota, kategori, staf CASCADE;
CREATE TABLE kategori (id SERIAL PRIMARY KEY, nama TEXT NOT NULL UNIQUE);
CREATE TABLE anggota (id SERIAL PRIMARY KEY, nama TEXT NOT NULL, email TEXT UNIQUE, bergabung DATE NOT NULL, aktif BOOLEAN NOT NULL DEFAULT TRUE);
CREATE TABLE buku (id SERIAL PRIMARY KEY, judul TEXT NOT NULL, penulis TEXT NOT NULL, tahun INTEGER NOT NULL, kategori_id INTEGER REFERENCES kategori(id));
CREATE TABLE peminjaman (id SERIAL PRIMARY KEY, anggota_id INTEGER NOT NULL REFERENCES anggota(id), buku_id INTEGER NOT NULL REFERENCES buku(id), tanggal_pinjam DATE NOT NULL, tanggal_kembali DATE);
INSERT INTO kategori (nama) VALUES ('Pemrograman'), ('Sains'), ('Sejarah'), ('Fiksi'), ('Statistika');
INSERT INTO anggota (nama, email, bergabung, aktif) VALUES ('Ali Rahman', '[email protected]', '2024-01-15', TRUE), ('Budi Santoso', '[email protected]', '2024-03-02', TRUE), ('Citra Kirana', '[email protected]', '2024-05-20', FALSE), ('Dewi Lestari', '[email protected]', '2024-08-11', TRUE), ('Eka Pratama', NULL, '2025-01-30', TRUE);
INSERT INTO buku (judul, penulis, tahun, kategori_id) VALUES ('Dasar Basis Data', 'Sari Wulandari', 2021, 1), ('Jaringan Komputer', 'Ahmad Fauzi', 2019, 1), ('Fisika untuk Pemula', 'Rina Marlina', 2020, 2), ('Kimia Organik', 'Rina Marlina', 2022, 2), ('Sejarah Nusantara', 'Bambang Wijaya', 2018, 3), ('Cerita Kota Lama', 'Nur Aisyah', 2023, 4), ('Statistika Terapan', 'Sari Wulandari', 2022, 5), ('Algoritma dan Struktur Data', 'Ahmad Fauzi', 2021, 1);
INSERT INTO peminjaman (anggota_id, buku_id, tanggal_pinjam, tanggal_kembali) VALUES (1, 1, '2025-03-01', '2025-03-15'), (1, 7, '2025-03-05', '2025-03-20'), (2, 3, '2025-03-10', NULL), (3, 5, '2025-02-20', '2025-03-01'), (2, 1, '2025-04-02', NULL), (4, 6, '2025-04-07', NULL), (5, 8, '2025-04-09', '2025-04-25'), (4, 2, '2025-05-01', NULL);
CREATE TABLE staf (id SERIAL PRIMARY KEY, nama TEXT NOT NULL, atasan_id INTEGER REFERENCES staf(id));
INSERT INTO staf (nama, atasan_id) VALUES
    ('Hana Zahira', NULL),
    ('Ivan Gunawan', 1),
    ('Joko Prasetyo', 1),
    ('Kartika Dewi', 2),
    ('Lukman Hakim', 2),
    ('Maya Sari', 4);
SQL

Bagan kali ini berlapis tiga tingkat, dengan Maya Sari di bawah Kartika Dewi yang berada di bawah Ivan Gunawan.

Alur jangkar dan istilah rekursif#

WITH RECURSIVE mengeksekusi jangkar sekali, lalu mengulang istilah rekursif dengan memasukkan hasil putaran sebelumnya ke dalamnya, sampai putaran menghasilkan kosong. Blok berikut menelusuri seluruh bawahan Hana Zahira sekaligus mencatat kedalamannya.

bash

# seluruh bawahan Hana Zahira beserta kedalamannya
psql -U postgres -d perpustakaan <<'SQL'
WITH RECURSIVE bawahan AS (
    SELECT id, nama, atasan_id, 1 AS kedalaman
    FROM staf WHERE nama = 'Hana Zahira'
    UNION ALL
    SELECT s.id, s.nama, s.atasan_id, b.kedalaman + 1
    FROM staf s JOIN bawahan b ON s.atasan_id = b.id
)
SELECT nama, kedalaman FROM bawahan ORDER BY kedalaman, nama;
SQL

text Keluaran

     nama      | kedalaman
---------------+-----------
 Hana Zahira   |         1
 Ivan Gunawan  |         2
 Joko Prasetyo |         2
 Kartika Dewi  |         3
 Lukman Hakim  |         3
 Maya Sari     |         4
(6 rows)

Jangkar mengambil baris Hana Zahira dengan kedalaman satu, lalu setiap putaran menyandingkan staf yang atasannya ada di hasil putaran terdahulu. Baris berhenti bertambah ketika tidak ada lagi staf yang menunjuk kelompok terakhir, dan kedalaman yang ikut dibawa menjadi bahan pelabelan tingkat pada tampilan.

Menghitung kedalaman dan jalur#

Kedalaman memakai aritmetika biasa pada istilah rekursif, sedangkan jalur memanfaatkan penyambungan teks yang ditambah satu tingkat setiap putaran. Jalur semacam ini menjadi identitas yang mudah dibaca sekaligus bahan pengurutan hierarki.

bash

# jalur hierarki setiap staf
psql -U postgres -d perpustakaan <<'SQL'
WITH RECURSIVE jalur AS (
    SELECT id, nama, nama AS lintasan FROM staf WHERE atasan_id IS NULL
    UNION ALL
    SELECT s.id, s.nama, j.lintasan || ' > ' || s.nama
    FROM staf s JOIN jalur j ON s.atasan_id = j.id
)
SELECT nama, lintasan FROM jalur ORDER BY lintasan;
SQL

text Keluaran

     nama      |                       lintasan
---------------+-------------------------------------------------------
 Hana Zahira   | Hana Zahira
 Ivan Gunawan  | Hana Zahira > Ivan Gunawan
 Kartika Dewi  | Hana Zahira > Ivan Gunawan > Kartika Dewi
 Maya Sari     | Hana Zahira > Ivan Gunawan > Kartika Dewi > Maya Sari
 Lukman Hakim  | Hana Zahira > Ivan Gunawan > Lukman Hakim
 Joko Prasetyo | Hana Zahira > Joko Prasetyo
(6 rows)

Enam staf masing-masing membawa lintasan lengkap dari puncak bagan, dan pengurutan atas lintasan menata hierarki secara alami. Pola jalur ini juga menjadi alat debug yang murah ketika hierarki yang diharapkan tidak cocok dengan data.

Deret angka tanpa tabel#

CTE rekursif tidak harus menelusuri tabel, karena jangkarnya boleh berupa nilai konstan dan istilah rekursifnya menghitung nilai berikutnya. Deret angka semacam ini membangkitkan kerangka kalender atau penghitung tanpa memasang tabel bantu.

bash

# deret satu sampai lima
psql -U postgres -d perpustakaan <<'SQL'
WITH RECURSIVE deret AS (
    SELECT 1 AS n
    UNION ALL
    SELECT n + 1 FROM deret WHERE n < 5
)
SELECT n FROM deret;
SQL

text Keluaran

 n
---
 1
 2
 3
 4
 5
(5 rows)

Bentuk yang sama membangkitkan deret tanggal untuk kerangka laporan tren, dengan syarat berhenti yang dinyatakan pada WHERE istilah rekursifnya. PostgreSQL juga menyediakan generate_series untuk kebutuhan yang sama, sehingga CTE rekursif dipilih ketika langkahnya tidak beraturan atau bergantung pada data.

Siklus dan batas aman#

Data yang melingkar, misalnya baris yang menunjuk induknya sendiri, membuat putaran tidak pernah habis pada UNION ALL. Kata UNION menggantikan UNION ALL untuk membuang baris duplikat sehingga siklus berhenti, dan kolom lintasan menjadi alat deteksi siklus karena nilainya tumbuh tanpa henti.

bash

# tabel melingkar dan henti karena UNION
psql -U postgres -d perpustakaan <<'SQL'
CREATE TABLE rantai (id INTEGER PRIMARY KEY, berikut INTEGER REFERENCES rantai(id));
INSERT INTO rantai VALUES (1, 2), (2, 3), (3, 1);
WITH RECURSIVE langkah AS (
    SELECT id, berikut FROM rantai WHERE id = 1
    UNION
    SELECT r.id, r.berikut FROM rantai r JOIN langkah l ON r.id = l.berikut
)
SELECT id FROM langkah ORDER BY id;
DROP TABLE rantai;
SQL

text Keluaran

CREATE TABLE
INSERT 0 3
 id
----
  1
  2
  3
(3 rows)

DROP TABLE

Tiga baris yang melingkar menghasilkan tiga langkah lalu berhenti, karena UNION menolak baris yang sudah ada. Pada data produksi yang berpotensi melingkar, pilihan UNION dan batas kedalaman pada WHERE menjadi dua pengaman yang dipasang sejak penulisan query, bukan setelah insiden.

Kesalahan umum#

Kesalahan pertama adalah lupa menghubungkan istilah rekursif dengan hasil putaran sebelumnya, sehingga putaran mengulang jangkarnya dan jumlah barisnya membengkak. Kesalahan kedua adalah memakai UNION ALL pada data yang berpotensi melingkar, yang membuat query berjalan tanpa akhir, dan pengaman pertamanya selalu mempertanyakan sifat datanya.

Kesalahan ketiga adalah menaruh ORDER BY atau LIMIT di dalam istilah rekursif, yang maknanya tidak intuitif karena penilaiannya per putaran, dan pengurutan dilakukan pada query luar. Kesalahan keempat adalah mengira setiap putaran melihat seluruh hasil akumulasi, padahal UNION ALL hanya menyuntikkan putaran terakhir, perbedaan yang penting ketika pola perhitungannya bergantung pada kumulasi.

Ringkasan#

WITH RECURSIVE mengeksekusi jangkar sekali lalu mengulang istilah rekursif sampai hasil putarannya kosong.
Kedalaman dihitung dengan aritmetika antar putaran, dan jalur dibentuk dengan penyambungan teks bertingkat.
Jangkar konstan membangkitkan deret angka atau tanggal, dengan generate_series sebagai alternatif untuk deret beraturan.
Data melingkar ditangani dengan UNION yang membuang duplikat dan batas kedalaman yang dinyatakan eksplisit.

Referensi#

Recursive Queries — PostgreSQL Documentation — Referensi resmi WITH RECURSIVE beserta urutan evaluasinya.
WITH Queries (Common Table Expressions) — PostgreSQL Documentation — Kerangka CTE yang menjadi dasar bentuk rekursifnya.
Generate Series — PostgreSQL Documentation — Alternatif bawaan untuk membangkitkan deret.