Database Anti-Patern: Menyimpan Data Hierarki

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:

1. Adjacency List
2. Path Enumeration
3. Nested Sets
4. 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.

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.

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

1. Nomor left dari setiap node kurang dari semua nomor yang digunakan oleh descendant-nya.
2. Nomor right dari setiap node lebih dari semua nomor yang digunakan oleh descendant-nya
3. Nomor node berada diantara nomor yang digunakan oleh ancestor.

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

Table Path

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.

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

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.