author Ahmad Muhardian

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?

Baca Juga ini

Cara Membuat Graf pada Python

Cara Membuat Graf pada Python

Hari ini saya belajar sesuatu yang cukup menantang, yaitu graf. Bagaiaman menulis graf dalam kode? dan memahami beberapa hal tentang graf. Menurut Wikipedia, graf dalam komputer sains (ilmu komputer) adalah sebuah tipe data abstrak. Graf terdiri dari titik-titik (nodes) yang terhubung dengan sisi/busur (edge/arcs).1 Berikut ini contoh graf yang akan kita tulis dalam kode program python: Graf tersebut merupakan graf berarah yang memiliki enam buah titik dan delapan busur (arcs).

Berapa Banyak Data yang Mampu Disimpan pada MySQL dengan AUTO_INCREMENT?

Berapa Banyak Data yang Mampu Disimpan pada MySQL dengan AUTO_INCREMENT?

Ini artikel lama, belum di-update. Isinya mungkin tidak relevan dengan kondisi sekarang AUTO_INCREMENT sangat sering saya gunakan dalam mengerjakan proyek. AUTO_INCREMENT membuat Kita tidak perlu mengisi field secara manual maupun dengan generator dalam kode. Tapi, … apakah ini aman? Apakah tidak masalah bila nanti datanya banyak? Berapa banyak sih data yang mampu ditampung bila menggunakan AUTO_INCREMENT? Mari kita sedikit pikirkan masalah Big Data. Batas AUTO_INCREMENTTernyata AUTO_INCREMENT memiliki batas. Apabila sudah melampaui batas, mungkin sistemnya akan macat.

[Solved] Error phpMyAdmin `mbstring is missing` di Linux

[Solved] Error phpMyAdmin `mbstring is missing` di Linux

Masih segar, Ubuntu saya baru saja ditingkatkan (upgrade) ke versi 16.04. Secara otomatis semua versi software-nya juga ditingkatkan. Tapi, peningkatan versi tidak selalu menjadi lebih baik. Kadang mendapat bugs dan masalah baru. Seperti phpMyAdmin, terjadi error karena menggunakan PHP 7. Pada versi sebelumnya menggunakan PHP 5. Berdasarkan pesan error tersebut, kesalahanya ada pada konfigurasi PHP. Atur konfigurasi agar dapat me-load ekstensi. buka file /etc/php5/apache2/php.ini atau /etc/php/7.0/apache2/php.iniTambahkan extension_dir = /usr/lib/php/20151012/Lokasi /usr/lib/php/20151012/ adalah lokasi ekstensi PHP pada komputer saya.

Bagaimana Cara Menyimpan Tanggal dan Waktu di MySQL?

Bagaimana Cara Menyimpan Tanggal dan Waktu di MySQL?

Ini artikel lama, belum di-update. Isinya mungkin tidak relevan dengan kondisi sekarang Beberapa hari yang lalu, saya melakukan downgrade sistem operasi, dari versi 15.10 ke 14.04. Secara otomatis, versi server MySQL-nya juga ikut di-downgrade, dari versi 5.6.27 ke versi 5.5.47. Pada versi yang lebih lama (5.5.47), tipe data Datetime dengan nilai default current_timestamp tidak diterima. Ketika saya mengimpor dari cadangan database, terjadi error. mysql -u root -p < db_27_feb_2016.sql Enter password:

Cara Backup Database MySQL di Linux (Ekspor dan Impor)

Cara Backup Database MySQL di Linux (Ekspor dan Impor)

Membuat backup (cadangan) database perlu dilakukan sebelum instal ulang server atau untuk berjaga-jaga bila terjadi sesuatu yang tidak diinginkan. Backup sebenarnya bisa kita lakukan melalui Phpmyadmin dengan cara mengekspor semua database. Tapi bagaimana kalau kita belum menginstal Phpmyadmin di Server? Tenang… Kita masih bisa melakukan backup melalui command line. Caranya gimana? Silahkan disimak: Cara Backup Semua DatabaseKita bisa backup database MySQL dengan perintah mysqldump. Perintah ini akan membuat kode SQL.

Belajar PHP: Persiapan Pemrograman PHP di Linux

Belajar PHP: Persiapan Pemrograman PHP di Linux

Apa saja alat yang kita butuhkan untuk coding PHP di Linux? Pelajari semuanya di sini.