author

Cara Menyimpan Graf pada MySQL

Awalnya saya tidak begitu paham dengan kegunaan graf pada komputer.

Namun, setelah belajar beberapa teori seperti kecerdasan buatan, analisa algoritma, struktur data, matematika diskrit, kalkulus, dan sebagainya. Saya mendapatkan sedikit pencerahan.

Graf dapat digunakan untuk menyelesaikan berbagai permasalahan seperti pencarian jalur terpendek, relasi hubungan sesuatu, representasi pengetahuan pada AI, dsb.

Saya kemudian tertarik untuk mengetahui cara melakukan komputasi graf.

Sebelumnya saya pernah membahas cara merepresentasikan graf ke dalam kode program dengan bahasa pemrograman python.

Sekarang, bagaimana caranya kita menyimpan graf di dalam database?

mari kita bahas…

Cara Menyimpan Graf di dalam Database Relasional

Memikirkan sendiri cara penyimpanan graf dalam database membuat saya pusing.

Tapi, pada akhirnya saya menemukan sebuah slide milik bapak Karwin yang sangat membantu.

Beliau menjelaskan empat metode penyimpanan graf pada database relasional dan membandingkan setiap metode.

Hasil perbandingannya metode Closeure Table terpilih sebagai cara yang termudah. Termudah yang saya maksudkan di sini adalah mudah untuk melakukan Query CRUD (Create, Read, Update, Delete).

Masing-masing metode memang memiliki kelebihan dan kekurangan.

Contohnya metode Path Enumerattion, bagus digunakan untuk membuat breadcrums. Sedangkan Adjacency List tidak bagus digunakan untuk graf yang punya banyak node.

Metode Closure Table

Mari kita pelajari cara penyimpanan graf dengan metode Closure Table.

Misalkan, kita memiliki graf seperti pada gambar ini.

Anggaplah semua titik-titik pada graf tersebut merupakan sebuah kota yang saling terhubung. Kemudian, yang kita harus lakukan adalah membuat tabel untuk menyimpan kota (titik) dan jalan yang menghubungkannya.

Diagram Relasi Tabel Graf

Relasi yang akan tercipta adalah Many-to-Many. Kolom kota_asal dan kota_tujuan akan menyimpan id dari kota. Kemudian kolom panjang untuk menyimpan panjang jalannya.

create table kota(
    id int,
    nama char,
    PRIMARY KEY(id)
);


create table jalan(
    kota_asal int,
    kota_tujuan int,
    panjang int,
    FOREIGN KEY(kota_asal) REFERENCES kota(id),
    FOREIGN KEY(kota_tujuan) REFERENCES kota(id)
);

Sekarang kita sudah punya dua tabel yang saling berelasi.

Relasi tabel database Graf

Sekarang kita coba menambahkan semua titik pada graf:

INSERT INTO kota (id,nama) VALUE (1,'A');
INSERT INTO kota (id,nama) VALUE (2,'B');
INSERT INTO kota (id,nama) VALUE (3,'C');
INSERT INTO kota (id,nama) VALUE (4,'D');
INSERT INTO kota (id,nama) VALUE (5,'E');
INSERT INTO kota (id,nama) VALUE (6,'F');

Selanjutnya menambahkan data jalan:

INSERT INTO jalan (kota_asal,kota_tujuan,panjang) VALUES (1,2,14);
INSERT INTO jalan (kota_asal,kota_tujuan,panjang) VALUES (1,3,10);
INSERT INTO jalan (kota_asal,kota_tujuan,panjang) VALUES (2,3,6);
INSERT INTO jalan (kota_asal,kota_tujuan,panjang) VALUES (2,4,18);
INSERT INTO jalan (kota_asal,kota_tujuan,panjang) VALUES (3,4,7);
INSERT INTO jalan (kota_asal,kota_tujuan,panjang) VALUES (4,3,9);
INSERT INTO jalan (kota_asal,kota_tujuan,panjang) VALUES (5,6,8);
INSERT INTO jalan (kota_asal,kota_tujuan,panjang) VALUES (6,4,11);

Panjang jalan saya tentukan sendiri. Sekarang semuanya sudah masuk. Mari kita coba-coba melakukan query yang lain. Misalnya, berapakah panjang jalan dari kota B menuju kota D?

SELECT panjang FROM `jalan` WHERE kota_asal=2 AND kota_tujuan=4

Hasilnya:

+---------+
| panjang |
+---------+
|      18 |
+---------+
1 row in set (0,00 sec)

Sebenarnya ada dua jalan yang bisa dilewati dari kota B menuju kota D, yaitu B->D dan B->C->D. Akan tetapi query tersebut hanya memilih jalur B->D saja.

Untuk query yang lebih rumit, mungkin kita bisa lakukan dengan membuat program. Misalnya, program untuk menentukan jalur terpedek.

File SQL contoh di atas dapat anda download di: gist.github.com

Begitulah cara termudah menyimpan graf pada database relasional menurut bapak Karwin.

Metode Closure Table memang yang termudah, namun pasti memiliki kekurangan.

Bagaimana menurutmu?