Inner Join

INNER JOIN adalah tipe join yang akan kita bahas pertama. Tipe join ini akan mengambil semua row dari table asal dan table tujuan dengan kondisi nilai key yang terkait saja - jika ada, dan  jika tidak maka row tersebut tidak akan muncul. 

Kalau tidak terdapat kondisi key terkait antar table, maka semua row dari kedua table dikombinasikan.

Syntax dari INNER JOIN adalah sebagai berikut :

table_reference [INNER] JOIN table_factor [join_condition]

Terlihat bahwa keyword INNER boleh digunakan secara eksplisit atau tidak. Jika tidak digunakan maka konstruksi JOIN tanpa keyword lain dianggap sebagai INNER JOIN.

INNER JOIN Antar Table dengan Kondisi ("ms_cabang" dan "ms_kota" dengan key "kode_kota")

SELECT * FROM ms_cabang INNER JOIN ms_kota ON ms_cabang.kode_kota = ms_kota.kode_kota

Hasil terlihat seperti gambar berikut ini. Disini table sumber adalah ms_cabang (left) mencari referensi row lain dari table ms_kota (right) dengan kondisi nilai kode_kota diantara kedua table tersebut sama. Kondisi ini menggunakan keyword ON. 

Dengan panduan gambar, kita lihat bahwa tiap row dari ms_cabang akan dicari padanan row-nya di ms_kota :

• untuk row pertama kita memiliki kode_kota dengan nilai "KOTA-003", ini akan dicari referensinya ke table ms_kota untuk nilai yang sama dan kita dapatkan row dengan nilai nama_kota "Lhokseumawe" adalah padanannya.
• untuk row kedua kita memiliki kode_kota dengan nilai "KOTA-083", ini akan dicari referensinya ke table ms_kota untuk nilai yang sama dan kita dapatkan row dengan nilai nama_kota "Bau-bau" adalah padanannya.
• demikian seterusnya.

Sekarang mari kita coba hapus referensi untuk "Lhokseumawe" dari table ms_kota :

DELETE FROM ms_kota WHERE nama_kota = 'Lhokseumawe';

Setelah itu coba jalankan kembali perintah JOIN di atas, Anda akan mendapatkan hasil JOIN tanpa referensi row "Lhokseumawe". Jadi INNER JOIN dengan kondisi mengharuskan row dari tiap table memiliki nilai yang sama untuk column referensinya (dalam hal ini kode_kota).

Kembalikan lagi row referensi yang kita hapus tadi dengan perintah INSERT berikut ini :

INSERT INTO `ms_kota` VALUES ('KOTA-003','Lhokseumawe','P33')

INNER JOIN Antar Table Tanpa Kondisi ("ms_cabang" dengan "ms_kota")

SELECT * FROM ms_cabang INNER JOIN ms_kota

Hasilnya adalah untuk tiap row dari ms_cabang akan dikombinasikan dengan semua row dari ms_kota - contoh hasilnya terlihat seperti pada gambar di bawah ini.

 

INNER JOIN antar table "ms_cabang", "ms_kota" dan "ms_propinsi"

SELECT ms_cabang.nama_cabang, 

       ms_kota.nama_kota, 

       ms_propinsi.nama_propinsi 

FROM ms_cabang 

INNER JOIN ms_kota ON ms_cabang.kode_kota = ms_kota.kode_kota

INNER JOIN ms_propinsi ON ms_kota.kode_propinsi = ms_propinsi.kode_propinsi

Hasil eksekusi terlihat seperti gambar berikut. Dengan penggabungan ketiga table ini sekarang kita dapatkan setiap cabang memiliki informasi nama kota dan nama propinsi dimana cabang tersebut berada.

 

Implisit INNER JOIN dengan Koma

INNER JOIN antar table secara implisit dapat menggunakan daftar table yang dipisah dengan tanda koma (,). Pengkondisian menggunakan klausa where.

SELECT ms_cabang.nama_cabang,

       ms_kota.nama_kota    ,

       ms_propinsi.nama_propinsi

FROM   ms_cabang

       , ms_kota

       , ms_propinsi

       WHERE 

       ms_cabang.kode_kota = ms_kota.kode_kota

       AND 

       ms_kota.kode_propinsi = ms_propinsi.kode_propinsi

Tree

Tree bisa didefinisikan sebagai suatu kumpulan elemen salah satu elemennya disebut dengan akar (root), dan sisa elemen lainnya (yang disebut simpul) terpecah menjadi sejumlah himpunan yang paling tidak berhubungan satu sama lain, yang disebut dengan subpohon (subtree), atau disebut juga cabang. Jika kita melihat pada subpohon, maka subpohon inipun juga mempunyai akar dan sub-subpohonnya masing-masing.

Dalam kehidupan sehari-hari, tree dapat dilihat dari pohon silsilah keluarga. Tingkat yang tertinggi disebut juga sebagai root. Untuk lebih jelasnya lihat gambar, merupakan contoh dari sebuah tree.

Pembagian Tree :
1. Tree Statik : isi node-nodenya tetap karena bentuk pohonnya sudah ditentukan.
2. Tree Dinamik : isi nodenya berubah-ubah karena proses penambahan (insert) dan penghapusan (delete

Terminologi Tree

Akar (Root nodes)
Simpul yang paling atas dalam pohon adalah akar (root node). Menjadi simpul teratas, simpul akar tidak akan memiliki orang tua. Ini merupakan simpul di mana biasanya merupakan tempat untuk memulai operasi dalam pohon (walaupun beberapa algoritma dimulai dengan daun dan berakhir pada akar). Semua simpul yang lain dapat dicapai dari akar dengan menelusuri pinggiran atau pranala. (Dalam definisi resmi, setiap jalan adalah khas). Dalam diagram, ini secara khusus di gambar paling atas. Di beberapa pohon, seperti heap, akar memiliki sifat khusus. Setiap simpul dalam sebuah pohon dapat dilihat sebagai akar dari sub pohon yang berakar pada simpul tersebut.

Daun (Leaf nodes)
Semua simpul yang berada pada tingkat terendah dari pohon dinamakan daun (leaf node). Sejak mereka terletak pada tingkat paling bawah, mereka tidak memiliki anak satupun. Seringkali, daun merupakan simpul terjauh dari akar. Dalam teori grafik, sebuah daun adalah sebuah sudut dengan tingkat 1 selain akar (kecuali jika pohonnya hanya memiliki satu sudut; maka akarnya adalah daunnya juga). Setiap pohon memiliki setidaknya satu daun.
Dalam pohon berdasarkan genetic programming sebuah daun (juga dibilang terminal) adalah bagian terluar dari sebuah program pohon. Jika dibandingkan dengan fungsinya atau simpul dalam, daun tidak memiliki argumen. Di banyak kasus dalam daun-GP input ke programnya.

Representasi Tree menggunakan linked list
Tree dapat dibuat dengan menggunakan linked list secara rekursif.Linked list yang digunakan adalah double linked list non circular.Data yang pertama kali masuk akan menjadi node root.Data yang lebih kecil dari data node root akan masuk dan menempati node kiri dari node root, sedangkan jika lebih besar dari data node root, akan masuk dan menempati node di sebelah kanan node root.

Operasi-operasi pada Tree:
— Insert: menambah node ke dalam Tree secara rekursif. Jika data yang akan dimasukkan lebih besar daripada elemen root, maka akan diletakkan di node sebelah kanan, sebaliknya jika lebih kecil maka akan diletakkan di node sebelah kiri. Untuk data pertama akan menjadi elemen root.
— Find: mencari node di dalam Tree secara rekursif sampai node tersebut ditemukan dengan menggunakan variable bantuan ketemu. Syaratnya adalah tree tidak boleh kosong.
— Traverse: yaitu operasi kunjungan terhadap node-node dalam pohon dimana masing-masing node akan dikunjungi sekali.
— Count: menghitung jumlah node dalam Tree
— Height : mengetahui kedalaman sebuah Tree
— Find Min dan Find Max : mencari nilai terkecil dan terbesar pada Tree
— Child : mengetahui anak dari sebuah node (jika punya)

Jenis-Jenis penelurusan data :
Sebuah pohon biner memiliki operasi traversal yaitu suatu kunjungan pada suatu simpul tepat satu kali. Dengan melakukan kunjungan lengkap kita akan memperoleh urutan informasi secara linier yang tersimpan di dalam pohon biner.
Terdapat tiga jenis kunjungan pada pohon biner, yaitu :

1. PREORDER

Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :

- Cetak isi simpul yang dikunjungi.

- Kunjungi cabang kiri.

- Kunjungi cabang kanan.


Procedure PREORDER(Temp : Tree);

Begin

If Temp <> NIL Then

Begin

Write(Temp^.Info,’ ‘); {Cetak isi simpul}

PREORDER(Temp^.Kiri); {Kunjungi cabang kiri}

PREORDER(Temp^.Kanan); {Kunjungi cabang kanan}

End;

End;


2. INORDER

Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :

- Kunjungi cabang kiri.

- Cetak isi simpul yang dikunjungi.

- Kunjungi cabang kanan.

Prosedur untuk melakukan traversal secara INORDER adalah sebagai

berikut:


Procedure INORDER(Temp : Tree);
Begin
If Temp <> NIL Then
Begin
INORDER(Temp^.Kiri); {Kunjungi cabang kiri}
Write(Temp^.Info,’ ‘); {Cetak isi simpul}
INORDER(Temp^.Kanan); {Kunjungi cabang kanan}
End;
End;


3. POSTORDER

Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :

- Kunjungi cabang kiri.

- Kunjungi cabang kanan.

- Cetak isi simpul yang dikunjungi.


Procedure POSTORDER(Temp : Tree);
Begin
If Temp <> NIL Then
Begin
POSTORDER(Temp^.Kiri); {Kunjungi cabang kiri}
POSTORDER(Temp^.Kanan); {Kunjungi cabang kanan}
Write(Temp^.Info,’ ‘); {Cetak isi simpul}
End;
End;


Dalam pengembangan nantinya, tiga jenis kunjungan ini dapat digunakan sebagai pencarian notasi infix, postfix dan prefix. Kunjungan Preorder untuk mencari prefix, kunjungan Inorder untuk mencari postfix dan kunjungan Postorder untuk mencari infiks.


Cara pertama adalah penyimpanan node secara linked, dalam arti menggunakan tipe data pointer. Pada cara ini, struktur node akan disajikan sebagai berikut:


LPtr Info RPtr

Jika struktur node tersebut diimplementasikan ke dalam Pascal, maka deklarasi node yang sesuai adalah:

1: TYPE

2: BinTreeType = ^BinNodeType;
3: BinNodeType = RECORD

4: LPtr : BinTreeType;
5: Info : BinInfoType;
6: RPtr : BinTreeType;
7: END;

Sort

Proses pengurutan data banyak ditemukan dalam komputer. Hal ini karena data yang sudah di susun atau di urut lebih mudah di cari dengan cepat. Untuk membentuk data yg tidak terurut menjadi data yang urut, terdapat berbagai algoritma yang bisa di gunakan. Pada pengurutan data terdapat beberapa istilah, yaitu pengurutan ascending dan descending

·         Ascending

Pengurutan dengan dasar dari nilai yang kecil menuju ke nilai yang besar (urutan naik)

·         Descending

Pengurutan data yang disusu atas dasar nilai besar ke kecil (urutan turun ).

Macam-macam Sorting:

• Buble Sort :

Merupakan algoritma pengurutan paling tua dengan metode pengurutan paling sederhana. Pengurutan yang dilakukan dengan membandingkan masing-masing item dalam suatu list secara berpasangan, menukar item jika diperlukan, dan mengulaginya sampai akhir list secara berurutan, sehingga tidak ada lagi item yang dapat ditukar.

• Selection Sort :

Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.

• Insertion Sort :

Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan dan yang sudah diurutkan. Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.

• Shell Sort :

Merupakan algoritma yang stau jenis dengan insertion sort, dimana pada setiap nilai i dalam n/i item diurutkan. Pada setiap pergantian nilai, i dikurangi sampai 1 sebagai nilai terakhir

• Merge Sort :

Algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort.

1. Divide

Memilah elemen – elemen dari rangkaian data menjadi dua bagian.

2. Conquer

Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif

3. Kombinasi

Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan

Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.

• Quick Sort :

Algoritma ini berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini hanya mengikuti langkah – langkah sebagai berikut :

1. Divide

Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.

2. Conquer

Mengurutkan elemen pada sub-rangkaian secara rekursif. Pada algoritma quicksort, langkah ”kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array

 

• Heap Sort:

Heap sort adalah sorting yang menggunakan struktur data heap, dengan nilai parent selalu lebih besar dari pada nilai childnya.

Algoritma:

1. Buat suatu heap.
2. Ambil isi dari root masukkan kedalam sebuah array.
3. Hapus element root dengan mempertahankan properti heap.
4. Ulangi sampai tree menjadi kosong