Ketika membuat sistem atau aplikasi, tahap desain basis data merupakan tahapan awal sebelum mulai ngoding. Ada masanya kita bakal berjumpa dengan data dengan struktur hirarki seperti kategori/subkategori, struktur organisasi, thread diskusi, dan lain-lain. Lalu mulailah bingung dan stuck bagaimana cara implementasi data tersebut ke basis data kita. Soalnya data kita tidak berelasi dengan tabel lain, dan bukan data yang cocok untuk database berelasi.
Perkenalkan Database Anti-Pattern
Anti-Pattern merupakan cara implementasi yang tidak sesuai dengan kaedah / desain yang seharusnya. Misalkan dalam OOP, sebuah class harus mempunyai tujuan dan fungsi masing-masing, tetapi anti-pattern nya adalah God Class yang dapat melakukan semuanya.
Database relasi di desain untuk relasi antar tabel, sehingga tidak ada data yang bersifat redudant. Tetapi bagimana untuk struktur data yang tidak lazim seperti hirarki? Kita harus melawan design pattern yang ada agar bisa menerapkannya ke basis data relasi dengan menggunakan anti-pattern.
Masalah: Komentar Bug Report.

Masalah di atas adalah tentang komentar dari suatu thread bug report yang berbentuk seperti hirarki komentar. Untuk penyeleasian permasalahan di atas, ada beberapa solusi yang bisa kita lakukan, yaitu:
- Adjacency List
- Path Enumeration
- Nested Sets
- Closure Table
Adjacency List
Teknik ini merupakan teknik naive yang biasa digunakan oleh semua orang, dimana kita menyimpan parent_id
dari setiap entry yang ada. Kelebihannya adalah untuk setiap entry, kita langsung tahu siapa parent
nya.
comment_id | parent_id | author | comment |
---|---|---|---|
1 | null | Fran | What's the cause of this bug? |
2 | 1 | Ollie | I think it's a null pointer. |
3 | 2 | Fran | No, I checked for that. |
4 | 1 | Kukla | We need to check valid input. |
5 | 4 | Olie | Yes, that's a bug. |
6 | 4 | Fran | Yes, please add a check. |
7 | 6 | Kukla | That fixed it. |
Insert
Untuk melakukan insert komentar terbaru, kita bisa melakukannya dengan perintah sql
INSERT INTO comments (parent_id, author, comment) VALUES (5, 'Fran', 'I agree!');

Update
Untuk updating parent kita bisa menggunakan perintah sql berikut:
UPDATE comments SET parent_id=3 WHERE comment_id=6;

Query
Untuk query node's children
SELECT * FROM comments c1 LEFT JOIN comments c2 ON (c2.parent_id = c1.comment_id);
Untuk query node's parent
SELECT * FROM comments c1 JOIN comments c2 ON (c1.parent_id = c2.comment_id);
Kelemahan
Kelemahan dari teknik ini adalah tidak bisa menangani tree yang dalam.
SELECT * FROM comments c1
LEFT JOIN comments c2 ON (c2.parent_id = c1.comment_id)
LEFT JOIN comments c3 ON (c3.parent_id = c2.comment_id)
LEFT JOIN comments c4 ON (c4.parent_id = c3.comment_id)
LEFT JOIN comments c5 ON (c5.parent_id = c4.comment_id)
LEFT JOIN comments c6 ON (c6.parent_id = c5.comment_id)
LEFT JOIN comments c7 ON (c7.parent_id = c6.comment_id)
LEFT JOIN comments c8 ON (c8.parent_id = c7.comment_id)
LEFT JOIN comments c9 ON (c9.parent_id = c8.comment_id)
...
Kita bisa mengani nya dengan recursive.
WITH [RECURSIVE] CommentTree (comment_id, bug_id, parent_id, author, comment,depth) AS (
SELECT *, 0 as depth FROM comments WHERE parent_id IS NULL
UNION ALL
SELECT c.*, ct.depth+1 AS depth FROM CommentTree ct JOIN comments c ON (ct.comment_id = c.parent_id))
SELECT * FROM CommentTree WHERE bug_id = 1234;
Tetapi cara diatas hanya bisa dilakukan di PostgreSQL, Oracle 11g, IBM DB2, MS SQL, Apache Derby.
Path Enumeration
Dengan menggunakan teknik ini, kita akan menyimpan urutan rantai ancestor pada setiap node.
comment_id | path | author | comment |
---|---|---|---|
1 | 1/ | Fran | What's the cause of this bug? |
2 | 1/2/ | Ollie | I think it's a null pointer. |
3 | 1/2/3/ | Fran | No, I checked for that. |
4 | 1/4/ | Kukla | We need to check valid input. |
5 | 1/4/5/ | Olie | Yes, that's a bug. |
6 | 1/4/6/ | Fran | Yes, please add a check. |
7 | 1/4/6/7/ | Kukla | That fixed it. |
Teknik ini dapat membuat breadcrumbs dengan mudah, karena kita menyimpan urutan node yang ada di kolom path
.
Query
Cara query ancestor pada komentar #7
SELECT * FROM comments WHERE '1/4/6/7/' LIKE path || '%';
Cara query descendant pada komentar #4
SELECT * FROM comments WHERE path LIKE '1/4/%';
Insert
Cara insert nya adalah dengan menginputkan author
dan comment
, lalu simpan LAST_INSERT_ID()
nya kemudian query-kan path
parentnya lalu simpan ke variabel $parent_path
dan update path
komentar terbarunya.
INSERT INTO Comments (author, comment)
VALUES (‘Ollie’, ‘Good job!’);
SELECT path FROM Comments
WHERE comment_id = 7;
UPDATE Comments
SET path = $parent_path || LAST_INSERT_ID() || ‘/’
WHERE comment_id = LAST_INSERT_ID();
Nested Sets
Dengan menggunakan teknik nested sets kita akan menyimpan nilai left
dan right
dari setiap node yang ada. Untuk aturan yang digunakan dalam penomorannya adalah
- Nomor
left
dari setiap node kurang dari semua nomor yang digunakan oleh descendant-nya. - Nomor
right
dari setiap node lebih dari semua nomor yang digunakan oleh descendant-nya - Nomor node berada diantara nomor yang digunakan oleh ancestor.

comment_id | nsleft | nsright | author | comment |
---|---|---|---|---|
1 | 1 | 4 | Fran | What's the cause of this bug? |
2 | 2 | 5 | Ollie | I think it's a null pointer. |
3 | 3 | 4 | Fran | No, I checked for that. |
4 | 6 | 13 | Kukla | We need to check valid input. |
5 | 7 | 8 | Olie | Yes, that's a bug. |
6 | 9 | 12 | Fran | Yes, please add a check. |
7 | 10 | 11 | Kukla | That fixed it. |
Query ancestor nomor 7
SELECT * FROM comments child
JOIN comments ancestor ON child.nsleft
BETWEEN ancestor.nsleft AND ancestor.nsright
WHERE child.comment_id = 7;

Query subtree di bawah komentar ID 4
SELECT * FROM comments parent
JOIN comments descendant ON descendant.nsleft
BETWEEN parent.nsleft AND parent.nsright
WHERE parent.comment_id = 4;

Insert child pada Komentar ID 5
UPDATE comments
SET nsleft = CASE WHEN nsleft >= 8 THEN nsleft+2
ELSE nsleft END,
nsright = nsright+2
WHERE nsright >= 7;
INSERT INTO comments (nsleft, nsright, author, comment)
VALUES (8, 9, 'Fran', 'I agree!');

Proses ini akan menghitung semua nilai left
untuk semua node di bagian kanan dari child, dan juga nilai right
pada semua node di atas dan kanannya.
Query Parent nomor 6
Parent dari nomor 6 merupakan ancestor yang tidak memiliki descendant yang juga merupakan ancestor dari 6.
SELECT parent.* FROM comments AS c
JOIN comments AS parent
ON (c.nsleft BETWEEN parent.nsleft AND parent.nsright)
LEFT OUTER JOIN comments AS in_between
ON (c.nsleft BETWEEN in_between.nsleft AND in_between.nsright
AND in_between.nsleft BETWEEN parent.nsleft AND parent.nsright)
WHERE c.comment_id = 6 AND in_between.comment_id IS NULL;

Closure Table
Teknik ini akan membuat tabel sendiri untuk menyimpan Path yang ada.

Tabel Komentar
comment_id | author | comment |
---|---|---|
1 | Fran | What's the cause of this bug? |
2 | Ollie | I think it's a null pointer. |
3 | Fran | No, I checked for that. |
4 | Kukla | We need to check valid input. |
5 | Olie | Yes, that's a bug. |
6 | Fran | Yes, please add a check. |
7 | Kukla | That fixed it. |
Table Path
ancestor | descendant |
---|---|
1 | 1 |
1 | 2 |
1 | 3 |
1 | 4 |
1 | 5 |
1 | 6 |
1 | 7 |
2 | 2 |
2 | 3 |
3 | 3 |
4 | 4 |
4 | 5 |
4 | 6 |
4 | 7 |
5 | 5 |
6 | 6 |
6 | 7 |
7 | 7 |
Teknik ini membutuhkan jumlah baris O(n)^2 .
Query descendant dari ID 4
SELECT c.* FROM comments c
JOIN tree_path t
ON (c.comment_id = t.descendant)
WHERE t.ancestor = 4;

Query ancestor dari 6
SELECT c.* FROM comments c
JOIN tree_path t
ON (c.comment_id = t.ancestor)
WHERE t.descendant = 6;

Insert child dari ID 5
INSERT INTO comments
VALUES (8, ‘Fran’, ‘I agree!’);
INSERT INTO tree_path (ancestor, descendant)
SELECT ancestor, 8 FROM tree_path
WHERE descendant = 5
UNION ALL SELECT 8, 8;

Delete ID 7
DELETE FROM tree_path
WHERE descendant = 7;

Delete semua path dibawah 4
DELETE FROM tree_path
WHERE descendant IN
(SELECT descendant FROM tree_path
WHERE ancestor = 4);

Salah cara optimasi dari teknik ini adalah dengan menambahkan length
dari path yang ada.
ancestor | descendant | length |
---|---|---|
1 | 1 | 0 |
1 | 2 | 1 |
1 | 3 | 2 |
1 | 4 | 1 |
1 | 5 | 2 |
1 | 6 | 2 |
1 | 7 | 3 |
2 | 2 | 0 |
2 | 3 | 1 |
3 | 3 | 0 |
4 | 4 | 0 |
4 | 5 | 1 |
4 | 6 | 1 |
4 | 7 | 2 |
5 | 5 | 0 |
6 | 6 | 0 |
6 | 7 | 1 |
7 | 7 | 0 |
Hal ini mempermudah untuk query kedalaman tree.
Select MAX(length) from tree_path
dan juga query untuk parent dan child.
SELECT c.*
FROM comments c
JOIN tree_path t
ON (c.comment_id = t.descendant)
WHERE t.ancestor = 4
AND t.length = 1;
Berikut Kesimpulan dari teknik di atas
Design | Table | Query child | Query Subtree | Delete Node | Insert Node | Move Subtree | Referential Integrity |
---|---|---|---|---|---|---|---|
Adjacency List | 1 | Easy | Hard | Easy | Easy | Easy | Yes |
Path Enumeration | 1 | Hard | Easy | Easy | Easy | Easy | No |
Nested Sets | 1 | Hard | Easy | Hard | Hard | Hard | No |
Closure Table | 2 | Easy | Easy | Easy | Easy | Easy | Yes |
Demikian teknik-teknik yang bisa digunakan untuk menyimpan data hierarki pada RDBMS. Jika ada pertanyaan, tinggalkan di kolom komentar ya.
Photo by Campaign Creators on Unsplash
Materi ini dirangkum dari www.slideshare.net/billkarwin oleh Bill Karwin.