Bagaimana Saya Menyimpan dan Membaca Bagan Organisasi Berversi di Database Relasional

Pendahuluan

A. Bagan organisasi yang sekaligus data master

Pemerintah kota tersusun dari perangkat daerah, dan setiap perangkat daerah berbentuk pohon: kepala di puncak, bidang di bawahnya, seksi di bawahnya lagi, dan unit layanan seperti sekolah atau puskesmas di ujung-ujung daunnya. Sistem kepegawaian pemerintah itu wajib menyimpan pohon ini, karena hampir semua data lain menunjuk ke dalamnya. Pegawai bekerja di satu unit. Jabatan — kepala seksi, guru, pelaksana administrasi — melekat pada satu unit. Riwayat jabatan mencatat posisi yang pernah dipegang seseorang, dan dengan begitu unit tempat ia bekerja. Hak akses pun dibatasi olehnya: admin bisa mengelola pegawai satu perangkat daerah, atau hanya satu bidang di dalamnya.

Pohon itu tak pernah diam. Susunan tiap perangkat daerah ditetapkan peraturan wali kota, dan saat peraturan baru terbit, unit ditambah, digabung, diganti nama, dipindah ke induk lain, atau dihapus. Perangkat daerah tidak berubah serentak: satu mengadopsi susunan barunya pada Januari, yang lain pada Juli, yang ketiga bertahan dengan susunannya bertahun-tahun. Sementara itu masa lalu harus tetap terbaca. Pengangkatan lima tahun lalu menunjuk unit sebagaimana adanya lima tahun lalu, dan laporan untuk tahun itu harus memperlihatkan organisasi seperti waktu itu, bukan seperti hari ini.

Tantangannya adalah menyimpan dan membaca bagan organisasi berversi di database relasional: hirarki yang berubah karena peraturan, terbaca sebagaimana adanya pada tanggal mana pun, sementara setiap record yang menunjuk ke dalamnya tetap menunjuk unit yang benar.

Kalimat itu memuat tiga bagian. "Menyimpan" soal cara mewakili pohon di dalam tabel. "Membaca" soal cara mengeluarkannya kembali dalam bentuk bersarang, cukup cepat untuk menggambar bagan seluruh pemerintah. "Berversi" soal waktu: pertanyaan yang sama — seperti apa organisasinya? — harus punya jawaban berbeda untuk setiap tanggal, dan jawaban-jawaban itu harus tersambung, supaya unit di susunan tahun ini bisa ditelusuri ke pendahulunya di susunan tahun lalu.

B. Kenapa hirarki tetap relasional

Sekilas, data hirarkis tampak paling cocok untuk database dokumen atau database graf. Pohon adalah dokumen bersarang; bagan organisasi adalah kumpulan node dan edge. Keduanya sudah saya coba, dan saya kembali ke SQL, karena di sistem ini hirarkinya tidak berdiri sendiri. Hirarki itu adalah data master bagi semua data lain yang memang sudah relasional.

Pegawai, jabatan, riwayat jabatan, dan lingkup akses semuanya tinggal di database relasional, dan masing-masing butuh foreign key ke pohon organisasi. Foreign key itulah yang menjamin pegawai tak mungkin tercatat di unit yang tidak ada, menghapus unit tak bisa diam-diam menelantarkan orang di dalamnya, dan laporan bisa menggabungkan pegawai dengan unit dalam satu query. Begitu pohonnya tinggal di tempat lain, setiap jaminan itu harus dibangun ulang dengan tangan.

C. Pendekatan yang saya tolak

Pendekatan pertama yang saya coba adalah database dokumen, MongoDB, yang menyimpan susunan tiap perangkat daerah sebagai satu dokumen bersarang. Membaca dan menulisnya sebagai pohon utuh memang nyaman, tetapi tabel-tabel lain tetap harus menunjuk unit lewat ID, dan tak ada yang memastikan ID itu ada. Menjaga dua tempat penyimpanan tetap selaras berubah menjadi pekerjaan tersendiri: sinkronisasi sesudah setiap perubahan, memeriksa unit yang hilang dari salah satu sisi, dan menjelaskan laporan yang angkanya tak cocok. Overhead-nya terus ada, dan ketidakkonsistenannya terus muncul.

Pendekatan kedua adalah database graf, Neo4j, yang menyimpan unit dan jabatan sebagai node dan hubungannya sebagai edge. Penelusuran memang mudah ditulis, tetapi lama-lama saya melihat susunan itu sebagai anti-pattern untuk sistem ini. Yang terutama saya dapat dari graf adalah gambaran bagaimana node-node saling terhubung — padahal menggambar itu tugas antarmuka user, bukan database. Saya telah memindahkan tampilan ke tempat penyimpanan, dan membayarnya dengan database kedua, persoalan konsistensi kedua, dan bahasa query kedua, demi hasil yang bisa digambar komponen Vue dari daftar bersarang.

Ada juga cara relasional yang sudah dikenal untuk menyimpan pohon, dan tidak saya pilih: nested set, yang menyimpan batas kiri dan kanan setiap node; materialized path, yang menyimpan rantai leluhur sebagai string; dan closure table, yang menyimpan setiap pasangan leluhur–keturunan. Masing-masing membuat sebagian pembacaan lebih murah dengan harga penulisan yang lebih rumit. Di sistem ini pohon per perangkat daerah cukup kecil, dan cukup sering disunting selama susunan baru dirancang, sehingga cara paling sederhana — setiap baris menunjuk induknya — adalah tukar-tambah yang lebih baik.

Jadi pendekatan yang saya pilih punya tiga lapisan, masing-masing dengan satu tugas. Database menyimpan pohon sebagai baris-baris yang menunjuk induknya, lengkap dengan versi dan tanggal berlaku. API membaca baris-baris itu dan mengembalikan struktur bersarang. Antarmuka user menggambarnya.

D. Enam belas hambatan yang menghalangi

Gampang dirumuskan, canggung dibangun. Ada enam belas hal di antara "tabel yang menunjuk dirinya sendiri" dan bagan organisasi yang bisa dibaca pada tanggal mana pun.

Pertama, hirarki mengundang database non-relasional, padahal ia data master bagi record relasional. Database dokumen atau graf saya tolak.

Kedua, mewakili pohon di dalam tabel. Nested set, materialized path, dan closure table adalah alternatif yang tidak saya pilih.

Ketiga, membaca kembali pohon bersarang secara efisien. Satu query per tingkat, atau per node, saya tolak.

Keempat, menjawab "semua yang di atas" dan "semua yang di bawah" satu unit. Menelusuri pohon di kode aplikasi, satu query per langkah, saya tolak.

Kelima, pohon harus tetap pohon. Memercayai setiap suntingan tak akan membentuk lingkaran saya tolak.

Keenam, susunannya berubah karena peraturan. Menyunting pohon yang sedang berlaku di tempat saya tolak, karena itu menghapus susunan yang berlaku kemarin.

Ketujuh, perangkat daerah berubah pada tanggalnya masing-masing. Satu versi untuk seluruh pemerintah saya tolak.

Kedelapan, membaca seluruh pemerintah sebagaimana adanya pada satu tanggal. Menyimpan snapshot bagan untuk setiap tanggal yang mungkin ditanyakan saya tolak.

Kesembilan, mengetahui unit mana di versi baru yang meneruskan unit mana di versi lama. Mencocokkan unit lewat namanya saya tolak.

Kesepuluh, jabatan membentuk hirarki kedua di atas unit. Memperlakukan jabatan sebagai label pada unit saya tolak.

Kesebelas, berapa orang mengisi tiap jabatan pada satu tanggal. Menyimpan angka itu saya tolak.

Kedua belas, record yang menunjuk ke pohon harus ikut maju ke versi terkini. Menunjuk ulang record itu dengan tangan sesudah setiap reorganisasi saya tolak.

Ketiga belas, melihat apa yang diubah versi baru sebelum ia berlaku. Membaca dua pohon berdampingan saya tolak.

Keempat belas, menggambar bagannya. Menyuruh database menghasilkan gambarnya saya tolak.

Kelima belas, mengetahui siapa yang mengubah susunan, dan bagaimana. Mengandalkan backup database untuk merekonstruksi suntingan saya tolak.

Keenam belas, mengubah peraturan baru menjadi versi draf. Mengetik ulang setiap unit setiap perangkat daerah dengan tangan saya tolak.

Urutannya bergerak dari tabel ke luar. Lima yang pertama soal memegang satu pohon dengan benar; keenam sampai kesembilan menambahkan waktu; kesepuluh sampai kedua belas adalah record yang bergantung pada pohon; empat terakhir adalah cara orang meninjau, melihat, mengaudit, dan mengisinya. Pohon yang tidak tersimpan dengan benar tak bisa diberi versi dengan benar, karena itulah penyimpanan datang pertama.

Metode

A. Tetap di SQL

Inilah jawaban atas hambatan pertama: pohon organisasi tinggal di database relasional yang sama dengan semua data yang menunjuknya. Pegawai, jabatan, riwayat jabatan, dan lingkup akses menunjuk unit lewat foreign key biasa, sehingga database sendiri menolak pegawai di unit yang tidak ada, dan laporan menggabungkan orang dengan unit dalam satu query. Hanya ada satu tempat penyimpanan, satu batas transaksi, dan satu bahasa query.

B. Tabel yang menunjuk dirinya sendiri

Setiap unit adalah satu baris dengan foreign key ke baris induknya di tabel yang sama — adjacency list. Akar tak punya induk. Nomor urut menjaga saudara-saudara tetap dalam urutan seperti yang tercantum di peraturan, dan setiap unit milik tepat satu versi.

CREATE TABLE org_unit (
  id         BIGSERIAL PRIMARY KEY,
  version_id BIGINT NOT NULL REFERENCES org_version(id) ON DELETE CASCADE,
  parent_id  BIGINT REFERENCES org_unit(id) ON DELETE CASCADE,
  name       TEXT   NOT NULL,
  position   INTEGER NOT NULL DEFAULT 0
);
CREATE INDEX ON org_unit (version_id, parent_id);

Memindah unit cukup mengubah satu kolom. Menambah unit cukup satu insert. Kesederhanaan itu paling terasa selama susunan baru dirancang, ketika unit dipindah dan diganti nama berkali-kali sebelum versinya final.

C. Satu query, lalu disarangkan dalam sekali jalan

Membaca pohon tak butuh query per tingkat. Saya mengambil semua unit satu versi dalam satu query datar, diurutkan menurut nomor urut, lalu menyarangkannya di API dalam sekali jalan: kelompokkan baris menurut induknya, kemudian bangun anak-anak setiap node dari kelompoknya. Kerjanya tumbuh linear terhadap jumlah unit, dan database cukup ditanya sekali.

$byParent = $nodes->groupBy(fn ($n) => $ids->has($n->parent_id) ? $n->parent_id : 0);

$build = fn (int $parent) => $byParent->get($parent, collect())
    ->map(fn ($n) => present($n) + ['children' => $build($n->id)])
    ->values()->all();

return $build(0);

Ada satu detail yang disengaja. Baris yang induknya tidak ada di hasil ditaruh sebagai akar, tidak dibuang, sehingga cabang yang rusak tampak di bagan dan tidak lenyap tanpa jejak.

D. Query rekursif untuk leluhur dan keturunan

Sebagian pertanyaan menyangkut jalur, bukan pohon utuh: nama lengkap unit dari perangkat daerah sampai ke bawah, atau semua unit di bawah cabang yang akan disalin atau dihapus. Untuk itu saya memakai recursive common table expression, yang membiarkan SQL sendiri menelusuri tautan induk dan mengembalikan seluruh rantainya dalam satu kali bolak-balik.

WITH RECURSIVE up (id, parent_id, depth) AS (
  SELECT id, parent_id, 0 FROM org_unit WHERE id = :unit
  UNION
  SELECT u.id, u.parent_id, up.depth + 1
  FROM org_unit u JOIN up ON u.id = up.parent_id
)
SELECT id, depth FROM up WHERE depth > 0;

Versi ke bawah adalah query yang sama dengan join dibalik. Keduanya pendek, keduanya tetap di dalam database, dan tak satu pun butuh cara khusus untuk menyimpan pohonnya.

E. Aturan yang menjaga pohon tetap pohon

Adjacency list akan menyimpan lingkaran dengan senang hati bila tak ada yang mencegah, jadi API yang mencegahnya. Unit tak boleh dipindah ke bawah dirinya sendiri atau ke bawah keturunannya — daftar keturunannya datang dari query rekursif di atas. Induk dan anak wajib berada di versi yang sama. Cabang dihapus dalam satu statement, sehingga foreign key yang menunjuk tabelnya sendiri diperiksa sesudah seluruh cabang hilang, bukan baris demi baris di tengah jalan.

if ($newParent->id === $node->id
    || in_array($newParent->id, $this->descendantIds($node), true)) {
    throw new CycleException('A unit cannot move under itself or its descendants.');
}

F. Satu versi per peraturan, dibekukan begitu berlaku

Setiap susunan milik satu versi, dan setiap versi milik peraturan yang menetapkannya. Versi punya tiga keadaan. Draf belum punya tanggal berlaku dan bebas disunting. Versi yang diadopsi punya tanggal mulai dan berlaku sejak itu. Versi yang berakhir punya tanggal selesai juga. Begitu versi berlaku, unit-unitnya tidak disunting lagi, karena isinya fakta peraturan; perubahan susunan dituangkan sebagai draf baru yang diadopsi pada tanggalnya sendiri.

CREATE TABLE org_version (
  id             BIGSERIAL PRIMARY KEY,
  agency_id      BIGINT REFERENCES agency(id),       -- null: the mayor's office
  regulation_id  BIGINT NOT NULL REFERENCES regulation(id),
  effective_from DATE,                               -- null: still a draft
  effective_to   DATE,
  previous_id    BIGINT REFERENCES org_version(id)
);

G. Versi per perangkat daerah, masing-masing pada tanggalnya

Versi saya simpan per perangkat daerah, bukan satu versi untuk seluruh pemerintah. Mengadopsi draf pada satu tanggal mengakhiri versi lama perangkat daerah itu pada tanggal yang sama, dan tak menyentuh perangkat daerah lain. Pada tanggal berapa pun, setiap perangkat daerah punya paling banyak satu versi yang berlaku. Adopsi menolak tanggal sebelum peraturannya sendiri berlaku, draf yang kosong, dan tanggal yang bertabrakan dengan versi yang sudah diadopsi untuk tanggal sesudahnya.

Satu versi untuk seluruh pemerintah akan memaksa salinan baru semua perangkat daerah setiap kali salah satunya berubah, dan membuat "susunan pada tanggal ini" bergantung pada reorganisasi perangkat daerah lain yang tak ada hubungannya.

H. Query yang sama, tanggal yang berbeda

Dengan tanggal berlaku pada versi, membaca masa lalu tak butuh snapshot. Versi berlaku pada satu tanggal bila mulainya pada atau sebelum tanggal itu dan belum berakhir saat itu. Memilih versi-versi itu, lalu mengambil semua unitnya dalam satu query lagi dan menyarangkannya per versi, menghasilkan seluruh pemerintah sebagaimana adanya pada tanggal tersebut.

SELECT * FROM org_version
WHERE effective_from IS NOT NULL
  AND effective_from <= :on
  AND (effective_to IS NULL OR effective_to > :on);

Antarmuka cukup mengirim tanggal yang lain. Kemarin, tahun lalu, dan bulan depan — untuk versi yang diadopsi lebih awal — adalah query yang sama dengan parameter berbeda.

I. Tautan garis asal antarversi

Draf baru dimulai sebagai salinan versi perangkat daerah yang sedang berlaku, dan setiap unit salinan mencatat unit asalnya. Tautan itulah, bukan nama unit, yang membuat sistem tahu bahwa satu bidang di susunan baru meneruskan bidang di susunan lama, sekalipun ia sudah diganti nama atau dipindah. Unit disalin dari induknya lebih dulu, sehingga setiap salinan bisa menunjuk induk salinannya.

Sistem lama yang saya gantikan menyalin seluruh pohon untuk setiap periode dengan ID baru dan tanpa tautan antarsalinan. Nama menjadi satu-satunya penyambung, padahal nama berubah tepat ketika susunan berubah. Karena itu pencocokan lewat nama adalah alternatif yang saya tolak untuk dibangun ulang.

J. Jabatan, hirarki kedua

Jabatan menempel pada unit, dan ia punya hirarkinya sendiri: kepala seksi melapor ke kepala bidang, yang melapor ke kepala perangkat daerah. Jabatan adalah slot berkapasitas — berapa orang yang dibutuhkan — bukan label. Di dalam versi yang berlaku, revisi peta jabatan menutup baris lama pada satu tanggal dan membuka baris baru yang mencatat pendahulunya. Tautan pendahulu bersifat banyak-ke-banyak, karena reorganisasi sering menggabungkan beberapa jabatan menjadi satu atau memecah satu menjadi beberapa. Untuk menemukan atasan satu jabatan pada tanggal tertentu, sistem mengikuti atasan yang tercatat maju lewat penerus-penerusnya sampai menemukan yang berlaku pada tanggal itu.

K. Pengisian jabatan dihitung, bukan disimpan

Jumlah orang yang mengisi satu jabatan pada satu tanggal tak pernah diketik. Ia diturunkan dari riwayat jabatan: untuk setiap pegawai aktif, pengangkatan terakhir pada atau sebelum tanggal itu, dihitung untuk jabatan yang ditunjuknya atau untuk jabatan yang meneruskannya. Angka yang diturunkan dengan cara ini tak mungkin melenceng dari data pengangkatan, dan bisa ditanyakan untuk tanggal berapa pun, termasuk sebelum reorganisasi.

L. Record ikut maju bersama pohon

Unit kerja pegawai saat ini diturunkan dari jabatannya yang berjalan, lalu diikuti maju lewat tautan garis asal sampai versi yang berlaku hari ini. Saat versi baru diadopsi, atau saat jabatan berubah, unit turunan itu disegarkan; tugas harian menyusul versi yang tanggal mulainya baru tiba belakangan. Tak ada yang menunjuk ulang pegawai dengan tangan sesudah reorganisasi, dan riwayat pengangkatan tetap menunjuk unit sebagaimana adanya dulu.

M. Diff sebelum draf berlaku

Sebelum draf diadopsi, antarmuka membandingkannya dengan versi asalnya, memakai tautan garis asal yang sama. Setiap unit dilaporkan sebagai ditambah, dihapus, diganti nama, dipindah ke induk lain, atau berganti jenis unit, dan jabatan dibandingkan per field. Peninjau membaca daftar perubahan, bukan memindai dua bagan besar untuk mencari bedanya.

N. Database mengirim data, antarmuka yang menggambar

API mengembalikan pohon sebagai data bersarang, setiap unit dengan children-nya. Menggambarnya adalah tugas antarmuka. Di Vue, node bagan adalah komponen yang merender kotaknya sendiri lalu merender dirinya lagi untuk setiap anak, dan garis penghubung bagannya cukup CSS biasa. Cabang bisa dilipat, deretan panjang unit daun ditumpuk vertikal supaya bagan tetap terbaca, dan bagannya bisa dicetak.

<!-- ChartNode.vue: one box, then itself again for each child -->
<li>
  <div class="chart-box">{{ node.name }}</div>
  <ul v-if="open && node.children.length">
    <ChartNode v-for="child in node.children" :key="child.id" :node="child" />
  </ul>
</li>

Di samping bagan, timeline mendaftar versi-versi perangkat daerah beserta peraturan dan periodenya, dan field tanggal meminta API mengirim susunan pada hari apa pun. Inilah pekerjaan yang dulu saya dorong ke database graf: di antarmuka ia cukup satu komponen rekursif.

O. Setiap perubahan dicatat

Setiap suntingan pada versi atau unit ditulis ke log perubahan dalam transaksi yang sama: dibuat, diubah, dipindah, diurutkan ulang, disalin, dihapus, diadopsi, diakhiri — lengkap dengan pelakunya dan nilai sebelum serta sesudahnya. Log tetap ada saat draf atau cabang dihapus. Ketika seseorang bertanya kenapa satu unit berada di tempatnya, jawabannya cukup satu query, bukan penyelidikan lewat backup.

P. Draf dibangun dari peraturan

Saat peraturan baru datang, daftar unitnya dikurasi menjadi file sederhana per perangkat daerah — tiap baris berisi jalur dari akar perangkat daerah dan jenis unitnya — lalu diubah menjadi versi draf. Setiap unit di file ditautkan ke padanannya di versi berjalan bila jalurnya sama, atau lewat tabel kecil berisi penggantian nama yang sudah diketahui, sehingga garis asalnya sudah terpasang sejak awal. Unit yang tak diatur peraturan itu, seperti unit layanan yang punya peraturan sendiri, dibawa dari versi berjalan. Draf itu lalu melewati diff dan adopsi yang sama dengan draf lain.

Hasil dan Pembahasan

A. Yang dimungkinkan rancangan ini

Bagan organisasi seluruh pemerintah bisa digambar untuk tanggal mana pun dengan dua query dan sekali jalan penyarangan. Setiap record yang menunjuk ke pohon dilindungi foreign key. Reorganisasi adalah draf yang bisa ditinjau sebagai daftar perubahan, diadopsi satu perangkat daerah pada tanggalnya sendiri, dan ditelusuri sesudahnya lewat log. Tak satu pun dari ini butuh database kedua.

B. Harga yang dibayar

Adjacency list menjaga penulisan tetap sederhana dan memindahkan ongkosnya ke pembacaan jalur utuh, yang ditangani query rekursif dengan baik pada skala ini. Versi menyalin unit dan tidak berbagi unit, jadi penyimpanan bertambah setiap reorganisasi; itu saya terima, karena salinan yang dibekukan justru membuat masa lalu terbaca tanpa rekonstruksi. Tautan garis asal harus dijaga cermat saat draf dibangun, dan itulah sebabnya draf dibangkitkan lengkap dengan tautannya dan ditinjau lewat diff, bukan diketik.

C. Di mana pendekatan ini cocok

Pendekatan ini cocok untuk hirarki yang menjadi data master bagi record relasional lain dan berubah pada tanggal yang diketahui: bagan organisasi, susunan bagan akun, kategori produk yang diatur regulasi. Ia kurang cocok untuk graf yang sangat dalam dan sangat besar yang terutama ditanyai lewat penelusuran, seperti jejaring sosial, tempat database graf layak dipakai karena penelusuran itu sendirilah produknya.

Simpulan

Bagan organisasi yang berubah karena peraturan tetaplah data relasional. Saya menyimpannya sebagai adjacency list di dalam versi bertanggal berlaku, membacanya dengan satu query datar yang disarangkan dalam sekali jalan dan dengan query rekursif untuk jalur, menyambung versi lewat tautan garis asal dan bukan nama, menurunkan pengisian jabatan dan unit kerja terkini ketimbang menyimpannya, dan menyerahkan urusan menggambar kepada komponen Vue rekursif.

Dua database yang saya coba sebelumnya bukan alat yang salah secara umum. Keduanya tempat yang salah untuk data ini, karena pohonnya tak pernah berdiri sendiri: semua data lain di sistem menunjuk ke dalamnya, dan database yang menyimpan semua data lain itulah yang sanggup menjaga penunjuk-penunjuk itu tetap jujur.

Istilah

Adjacency list

Cara menyimpan pohon di tabel, dengan setiap baris memegang foreign key ke baris induknya.

Recursive common table expression

Query SQL yang merujuk dirinya sendiri, dipakai untuk menelusuri tautan induk dan mengembalikan seluruh rantai leluhur atau keturunan dalam satu kali bolak-balik.

Versi

Susunan satu perangkat daerah menurut satu peraturan, dengan tanggal mulai sesudah diadopsi dan tanggal selesai sesudah digantikan.

Tautan garis asal

Rujukan dari unit atau jabatan ke pendahulunya di versi sebelumnya, dipakai sebagai pengganti pencocokan nama.

Jabatan

Slot pada unit dengan jumlah pemangku yang dibutuhkan dan jabatan atasan tersendiri.

Perangkat daerah

Dinas atau badan pemerintah kota yang susunan internalnya ditetapkan peraturannya sendiri.