PENERAPAN AGGREGATION TREE UNTUK PENANGANAN FUNGSI AGREGASI PADA RELASI BITEMPORAL

PENERAPAN AGGREGATION TREE UNTUK PENANGANAN FUNGSI AGREGASI PADA RELASI BITEMPORAL

LAPORAN TUGAS AKHIR

Disusun sebagai syarat kelulusan tingkat sarjana

oleh : Nurkholis Madjid / NIM 13503047

PROGRAM STUDI TEKNIK INFORMATIKA SEKOLAH TEKNIK ELEKTRO DAN INFORMATIKA INSTITUT TEKNOLOGI BANDUNG 2007

Lembar Pengesahan Program Studi Sarjana Teknik Informatika Penerapan Aggregation Tree untuk Penanganan Fungsi Agregasi pada Relasi Bitemporal

Tugas Akhir Program Studi Sarjana Teknik Informatika ITB

Oleh Nurkholis Madjid / NIM 13503047

Telah disetujui dan disahkan sebagai laporan tugas akhir di Bandung, pada tanggal 27 September 2007

Pembimbing

Tricya E. Widagdo, S.T., M.Sc. NIP. 132164563

i

RINGKASAN

Berbagai macam metode pemrosesan fungsi agregasi terhadap data temporal yang telah dikembangkan saat ini hanya ditujukan untuk relasi valid-time. Sedangkan metode pemrosesan agregasi untuk relasi bitemporal sampai saat ini belum ada. Salah satu metode pemrosesan agregasi untuk relasi valid-time yang telah dikembangkan adalah aggregation tree. Agar aggregation tree dapat dimanfaatkan untuk relasi bitemporal, metode ini perlu dikembangkan lebih lanjut. Pada tugas akhir ini disusun suatu metode pemrosesan agregasi untuk relasi bitemporal menggunakan aggregation tree. Pada tahap awal, dilakukan analisis penerapan fungsi agregasi untuk relasi bitemporal di mana terdapat dua dimensi waktu yang harus diperhatikan. Dalam analisis ini dibahas mengenai berbagai jenis query retrieval temporal terhadap relasi bitemporal khususnya yang mengandung fungsi agregasi. Query temporal ini perlu dikonversi menjadi query relasional agar dapat diproses terhadap relasi bitemporal yang disimpan pada RDBMS. Selanjutnya dilakukan analisis bagaimana aggregation tree dapat dimanfaatkan untuk memproses agregasi pada relasi bitemporal. Analisis ini mencakup modifikasi struktur aggregation tree agar dapat memproses query yang mengandung klausa GROUP BY dan fungsi agregasi spesifik temporal karena aggregation tree belum dapat menanganinya. Untuk pengujian analisis, dibangun sebuah perangkat lunak yang mengimplementasi hasil analisis. Perangkat lunak ini dapat menerima masukan dari user berupa query retrieval temporal yang mengandung fungsi agregasi. Selanjutnya perangkat lunak akan memproses query tersebut dan menampilkan hasilnya kepada user. Proses pembangunan perangkat lunak ini mengadopsi metode Rational Unified Process (RUP). Berdasarkan hasil pengujian menggunakan perangkat lunak yang telah dibangun, metode aggregation tree yang telah dikembangkan lebih lanjut dapat digunakan untuk memproses query dengan fungsi agregasi terhadap relasi bitemporal. Selain itu, modifikasi terhadap struktur pohon aggregation tree, dapat mengatasi kekurangan metode ini dalam hal penanganan query yang mengandung klausa GROUP BY dan fungsi agregasi spesifik temporal. Kata kunci: relasi bitemporal, fungsi agregasi, aggregation tree.

ii

KATA PENGANTAR

Assalaamu’alaykum Warahmatullaahi Wabarakaatuhu Puji dan syukur penulis panjatkan kepada Allah SWT karena berkat rahmat-Nya yang berlimpah Tugas Akhir ini dapat diselesaikan. Tugas akhir ini disusun untuk memenuhi persyaratan akademis mata kuliah IF40Z1 Tugas Akhir I dan IF40Z2 Tugas Akhir II sebagai salah satu syarat kelulusan tingkat sarjana di Departemen Teknik Informatika ITB, Bandung. Ucapan terima kasih penulis haturkan kepada semua pihak yang telah membantu pelaksanaan tugas akhir ini: 1.

Ibu Tricya E. Widagdo, S.T., M.Sc. selaku pembimbing, atas saran, perhatian, dan kesabarannya dalam membimbing penulis menyusun tugas akhir.

2.

Ibu Ir. Hira Laksmiwati Z., M.Sc. selaku penguji presentasi proposal atas masukannya.

3.

Ibu Fazat Nur Azizah, S.T., M.Sc. selaku penguji seminar, prasidang dan sidang atas masukannya.

4.

Ibu Ir. G.A. Putri Saptawati, M.Comm. selaku penguji sidang atas masukannya.

5.

Ibu Henny Yusnita Zubir B.Sc., M.T. selaku dosen wali akademik yang telah memberikan bimbingan selama masa perkuliahan.

6.

Seluruh dosen Teknik Informatika ITB dan staf pengajar lainnya atas pengajaran dan ilmu yang telah diberikan.

7.

Pak Rasidi, Pak Ade, Mbak Nur dan petugas Tata Usaha Akademik lainnya yang telah memberikan bantuan administrasi selama masa perkuliahan dan pengerjaan Tugas Akhir.

8.

Pak Setiawan, Pak Sudarman dan seluruh karyawan Departemen Teknik Informatika yang telah memberikan bantuan fasilitas selama masa perkuliahan dan pengerjaan Tugas Akhir.

9.

Ibu dan Bapak, orang tua penulis atas segala doa, dukungan, kasih sayang, dan kesabaran yang telah diberikan kepada penulis.

10. Pak Mudzakkir dan keluarga, atas bantuannya selama tiga tahun terakhir penulis di Bandung. 11. Yeni, Puput, Fandi, Fuzna, Mbak Ciciek dan Mas Yudi serta sepupu-sepupu penulis lainnya atas semua doa, semangat dan dukungannya.

iii

12. Rika dan Ira, dua sahabat tempat berkeluh kesah, atas dukungan, inspirasi dan bantuan lainnya yang telah kalian berikan. 13. Mida, atas perhatian dan doanya, dan Prabu, atas motivasinya. 14. Maseko, Teguh dan Yosep, teman-teman seperjuangan dalam mengerjakan Tugas Akhir. 15. Fatur, Erik, Kang Opik, dan semua etoser, teman-teman asrama penulis yang telah menjadi keluarga kedua penulis selama di Bandung dalam empat tahun terakhir ini. 16. Rian Permata dan Rian Hadi, atas pinjaman laptop-nya. 17. Rekan-rekan Teknik Informatika angkatan 2003, atas bantuannya, baik dalam hal akademik, maupun lainnya selama masa perkuliahan dan pengerjaan Tugas Akhir. 18. Keluarga laboratorium Basis Data, atas dukungan dan kebersamaanya. 19. Dan seluruh pihak lain yang telah membantu, yang tidak dapat disebutkan satu-persatu. Akhir kata, tidak ada kesempurnaan dalam diri manusia dan hasil karyanya, begitu pula dengan Tugas Akhir ini. Saran dan kritik yang membangun selalu diharapkan oleh penulis sebagai perbaikan di masa datang. Terima kasih. Wassalaamu’alaykum Warahmatullaahi Wabarakaatuhu

Bandung, September 2007

Penulis

iv

DAFTAR ISI

Lembar Pengesahan .................................................................................................................... i RINGKASAN ............................................................................................................................ ii KATA PENGANTAR .............................................................................................................. iii DAFTAR ISI ............................................................................................................................. v DAFTAR TABEL ................................................................................................................... vii DAFTAR GAMBAR .............................................................................................................. viii DAFTAR ALGORITMA .......................................................................................................... x DAFTAR ISTILAH .................................................................................................................. xi DAFTAR QUERY ................................................................................................................... xii BAB I PENDAHULUAN ................................................................................................... I-1 1.1 Latar Belakang ............................................................................................................ I-1 1.2 Rumusan Masalah ....................................................................................................... I-3 1.3 Tujuan.......................................................................................................................... I-3 1.4 Batasan Masalah .......................................................................................................... I-3 1.5 Metodologi .................................................................................................................. I-4 1.6 Sistematika Pembahasan ............................................................................................. I-4 BAB II DASAR TEORI ...................................................................................................... II-1 2.1 Basis Data Temporal .................................................................................................. II-1 2.1.1 Aspek Waktu ....................................................................................................... II-1 2.1.1.1 Struktur .......................................................................................................... II-1 2.1.1.2 Interpretasi ..................................................................................................... II-2 2.1.1.3 Representasi .................................................................................................. II-2 2.1.1.4 Format ........................................................................................................... II-3 2.1.1.5 Granularitas ................................................................................................... II-4 2.1.2 Dimensi Waktu .................................................................................................... II-4 2.1.3 Taksonomi Relasi ................................................................................................ II-4 2.2 Bitemporal Conceptual Data Model ........................................................................... II-5 2.2.1 Pengertian BCDM ............................................................................................... II-5 2.2.2 Model Representasi BCDM ................................................................................. II-7 2.2.3 BCDM pada TSQL2 .......................................................................................... II-10 2.3 Operasi Retrieval dan Fungsi Agregasi .................................................................... II-10 2.3.1 Operasi Retrieval ............................................................................................... II-10 2.3.1.1 Snapshot query ............................................................................................ II-11 2.3.1.2 Time-travel query ........................................................................................ II-11 2.3.1.3 Sequenced query .......................................................................................... II-12 2.3.1.4 Non-sequenced query .................................................................................. II-12 2.3.2 Fungsi Agregasi pada Operasi Retrieval............................................................ II-13 2.3.3 Fungsi Agregasi Spesifik Basis Data Temporal ................................................ II-14 2.4 Pemrosesan Agregasi pada Basis Data Temporal .................................................... II-16 2.4.1 Algoritma dengan Aggregation Tree [KLI95] ................................................... II-16 2.4.2 Algoritma dengan PA-Tree [KIM99]................................................................. II-19 BAB III ANALISIS PERMASALAHAN ............................................................................ III-1 3.1 Pemilihan Aspek Waktu ............................................................................................ III-1 3.2 Fungsi Agregasi pada Relasi Bitemporal .................................................................. III-2 3.3 Operasi Retrieval Relasi Bitemporal ......................................................................... III-2 3.3.1 Snapshot Query ................................................................................................... III-3 3.3.2 Valid Time-travel Query ..................................................................................... III-4 3.3.3 Time-travel Query ............................................................................................... III-4 3.3.4 Valid Sequenced Query ....................................................................................... III-5 3.3.5 Valid Sequenced Time-travel Query ................................................................... III-6 v

3.3.6 Valid Non-sequenced Query ............................................................................... III-7 3.3.7 Valid Non-sequenced Time-travel Query............................................................ III-8 3.4 Konversi Query ......................................................................................................... III-9 3.5 Algoritma Pemrosesan Agregasi ............................................................................... III-9 3.5.1 Penanganan keyword WEIGHTED .................................................................... III-9 3.5.2 Penanganan Fungsi RISING ............................................................................. III-10 3.5.3 Penanganan Klausa GROUP BY ...................................................................... III-11 3.6 Pemrosesan Query .................................................................................................. III-14 BAB IV PEMBANGUNAN PERANGKAT LUNAK ........................................................IV-1 4.1 Deskripsi Umum Perangkat Lunak ...........................................................................IV-1 4.2 Analisis dan Perancangan Perangkat Lunak..............................................................IV-2 4.2.1 Model Use Case ..................................................................................................IV-2 4.2.1.1 Deskripsi actor .............................................................................................IV-3 4.2.1.2 Deskripsi use case ........................................................................................IV-3 4.2.1.3 Skenario Use Case ........................................................................................IV-3 4.2.2 Realisasi Use Case ..............................................................................................IV-5 4.2.2.1 Diagram Sequence ........................................................................................IV-5 4.2.2.2 Perancangan Kelas .......................................................................................IV-8 4.2.2.3 Deskripsi Kelas AggregationTree ................................................................IV-9 4.2.3 Rancangan Antarmuka ......................................................................................IV-13 4.3 Implementasi Perangkat Lunak ...............................................................................IV-15 4.3.1 Batasan Implementasi .......................................................................................IV-15 4.3.2 Lingkungan Implementasi ................................................................................IV-15 4.3.3 Implementasi Perangkat Lunak ........................................................................IV-16 4.3.4 Implementasi Antarmuka ..................................................................................IV-16 4.4 Pengujian .................................................................................................................IV-18 4.4.1 Tujuan Pengujian ..............................................................................................IV-18 4.4.2 Lingkungan Pengujian ......................................................................................IV-18 4.4.3 Prosedur Pengujian ...........................................................................................IV-18 4.4.4 Kasus Uji ..........................................................................................................IV-19 4.4.5 Data Uji .............................................................................................................IV-19 4.4.6 Hasil Pengujian .................................................................................................IV-19 BAB V PENUTUP ............................................................................................................... V-1 5.1 Kesimpulan................................................................................................................. V-1 5.2 Saran ........................................................................................................................... V-2 DAFTAR REFERENSI .......................................................................................................... xiii DAFTAR PUSTAKA ............................................................................................................. xiv Lampiran A AVL Tree .......................................................................................................... A-1 Lampiran B Skyline Problem ................................................................................................ B-1 Lampiran C Kasus Uji ........................................................................................................... C-1 Lampiran D Hasil Pengujian ................................................................................................. D-1

vi

DAFTAR TABEL

Tabel II-1 Perbandingan Ketiga Model Representasi BCDM [HAN05] ....................................... II-8  Tabel IV-1 Tabel deskripsi actor ................................................................................................. IV-3  Tabel IV-2 Tabel penjelasan use case ......................................................................................... IV-3  Tabel IV-3 Tabel skenario use case Open connection................................................................. IV-3  Tabel IV-4 Tabel skenario use case Close connection ................................................................ IV-4  Tabel IV-5 Tabel skenario use case Execute query ..................................................................... IV-4  Tabel IV-6 Tabel skenario use case Save tree ............................................................................. IV-5  Tabel IV-7 Penjelasan atribut kelas AggregationTree ................................................................. IV-9  Tabel IV-8 Tabel keterangan item pada rancangan layar utama................................................ IV-14  Tabel IV-9 Tabel keterangan item pada layar Open Database................................................... IV-15  Tabel IV-10 Daftar file hasil implementasi ............................................................................... IV-16 Tabel C- 1 Tabel uji kebenaran hasil analisis ................................................................................ C-1  Tabel C- 2 Tabel kasus uji pesan kesalahan .................................................................................. C-3 Tabel D- 1 Hasil pengujian kebenaran hasil analisis ..................................................................... D-1  Tabel D- 2 Hasil pengujian pesan kesalahan ................................................................................. D-8 

vii

DAFTAR GAMBAR

Gambar II-1 Perbedaan format waktu ........................................................................................... II-3  Gambar II-2 Relasi Employee dalam BCDM ................................................................................ II-5  Gambar II-3 Contoh representasi grafis relasi bitemporal [JEN94] .............................................. II-7  Gambar II-4 Relasi Employee dalam model representasi Snodgrass [JEN94] .............................. II-8  Gambar II-5 Relasi Employee setelah penambahan (Bob,Load)................................................... II-9  Gambar II-6 Cuplikan relasi Employee setelah modifikasi tuple (Bob,Load) .............................. II-9  Gambar II-7 Representasi grafis tuple (Bob,Load)...................................................................... II-10  Gambar II-8 Snapshot query ........................................................................................................ II-11  Gambar II-9 Time-travel query .................................................................................................... II-11  Gambar II-10 Sequenced query ................................................................................................... II-12  Gambar II-11 Non-sequenced query ............................................................................................ II-12  Gambar II-12 Relasi valid-time Salary ........................................................................................ II-14  Gambar II-13 Hasil Query II-3 .................................................................................................... II-14  Gambar II-14 Rumus aturan WEIGHTED .................................................................................... II-15  Gambar II-15 Relasi hasil Query II-4 .......................................................................................... II-16  Gambar II-16 Pembangunan aggregation tree ............................................................................ II-17  Gambar II-17 Relasi hasil Query II-5 .......................................................................................... II-18  Gambar II-18 Struktur T-node dari PA-Tree ............................................................................... II-19  Gambar II-19 Pembangunan PA-Tree untuk relasi Salary .......................................................... II-20  Gambar II-20 Struktur PA-Tree untuk agregasi selektif .............................................................. II-20  Gambar II-21 PA-Tree agregasi selektif untuk relasi Salary ....................................................... II-21  Gambar II-22 Relasi hasil Query II-6 .......................................................................................... II-21  Gambar II-23 Contoh skyline problem dan solusinya.................................................................. II-22  Gambar III-1 Snapshot query ....................................................................................................... III-3  Gambar III-2 Valid time-travel query ........................................................................................... III-4  Gambar III-3 Time-travel query ................................................................................................... III-5  Gambar III-4 Valid sequenced query ............................................................................................ III-6  Gambar III-5 Valid Sequenced Time-travel Query ....................................................................... III-6  Gambar III-6 Valid Non-sequenced Query ................................................................................... III-7  Gambar III-7 Valid non-sequenced time-travel query .................................................................. III-8  Gambar III-8 Relasi valid-time Salary2 ...................................................................................... III-10  Gambar III-9 Aggregation tree untuk Query II-3 ....................................................................... III-11  Gambar III-10 Relasi hasil Query III-8 ...................................................................................... III-11  Gambar III-11 Struktur aggregation tree yang dimodifikasi ...................................................... III-12  Gambar III-12 Relasi valid-time Employee2.............................................................................. III-12  Gambar III-13 Pembangunan aggregation tree yang dimodifikasi ............................................ III-13  Gambar III-14 Relasi hasil Query III-9 ...................................................................................... III-14  Gambar III-15 Bagan alur pemrosesan query ............................................................................. III-15  Gambar IV-1 Gambaran umum perangkat lunak......................................................................... IV-1  Gambar IV-2 Diagram Use Case ................................................................................................. IV-2  Gambar IV-3 Diagram sequence untuk use case Open connection ............................................. IV-5  Gambar IV-4 Diagram sequence untuk use case Close connection ............................................ IV-6  Gambar IV-5 Diagram sequence untuk use case Execute query ................................................. IV-6  Gambar IV-6 Diagram sequence untuk use case Save tree ......................................................... IV-7  Gambar IV-7 Diagram Kelas ....................................................................................................... IV-8  Gambar IV-8 Rancangan antarmuka layar utama ...................................................................... IV-14  Gambar IV-9 Rancangan layar Open Database ......................................................................... IV-15  Gambar IV-10 Layar Utama BitemporalAggregator ................................................................. IV-17  Gambar IV-11 Layar Open Database BitemporalAggregator ................................................... IV-17  viii

Gambar A-1 Rotasi pohon AVL-Tree ............................................................................................ A-1 Gambar B-1 Contoh skyline problem ............................................................................................ B-1 Gambar B-2 Hasil proses merge building...................................................................................... B-2

ix

DAFTAR ALGORITMA

Algoritma IV-1 Algoritma method buildTree ...................................................................... IV-10 Algoritma IV-2 Algoritma method insert ............................................................................. IV-11 Algoritma IV-3 Algoritma method computeAggregate ..................................................... IV-12 Algoritma IV-4 Algoritma method compute .......................................................................... IV-13

x

DAFTAR ISTILAH

Istilah

Penjelasan

Chronon

Unit waktu terkecil yang didefinisikan dalam basis data

Current

Waktu relatif saat ini

Depth first search Operasi retrieval RDBMS

Rekursif Time-varying

Proses pencarian dalam suatu struktur yang mendahulukan penelusuran ke bawah daripada ke samping Operasi pengaksesan basis data tanpa memodifikasi data yang disimpan Relational Database Management System, suatu sistem pengelolaan basisdata relasional Sifat dari suatu fungsi atau prosedur yang di dalamnya memanggil dirinya sendiri Berubah-ubah relatif terhadap waktu

xi

DAFTAR QUERY

Query II-1 Sintaks query retrieval pada SQL92 .......................................................................... II-13 Query II-2 Tambahan sintaks query retrieval pada TSQL2 ........................................................ II-14 Query II-3 Contoh query dengan fungsi RISING ....................................................................... II-14 Query II-4 Contoh query dengan WEIGHTED ............................................................................. II-15 Query II-5 Contoh query TSQL2 dengan fungsi COUNT ............................................................ II-17 Query II-6 Contoh query TSQL2 dengan fungsi SUM ................................................................. II-21 Query III-1 Contoh snapshot query .............................................................................................. III-4 Query III-2 Contoh valid time-travel query .................................................................................. III-4 Query III-3 Contoh time-travel query ........................................................................................... III-5 Query III-4 Contoh valid sequenced ............................................................................................. III-6 Query III-5 Contoh valid sequenced time-travel query ................................................................ III-7 Query III-6 Contoh valid non-sequenced query ........................................................................... III-8 Query III-7 Contoh valid non-sequenced time-travel query ......................................................... III-9 Query III-8 Contoh query dengan fungsi RISING .................................................................... III-10 Query III-9 Contoh query dengan GROUP BY........................................................................... III-12

xii