BAB III ANALISIS PERMASALAHAN

BAB III ANALISIS PERMASALAHAN

Hal-hal yang dianalisis pada bab ini meliputi: 1. Aspek waktu yang akan digunakan. 2. Fungsi agregasi pada relasi bitemporal. 3. Jenis query retrieval yang mengandung fungsi agregasi terhadap relasi bitemporal, termasuk bagaimana konversi query temporal tersebut menjadi bahasa query relasional agar dapat dimengerti oleh RDBMS tempat menyimpan relasi bitemporal. 4. Modifikasi algoritma aggregation tree agar dapat menangani fungsi agregasi spesifik temporal dan penanganan klausa GROUP BY.

3.1 Pemilihan Aspek Waktu Pada penjelasan mengenai BCDM (subbab 2.2.1), telah disebutkan bahwa domain dari kedua dimensi waktu yang didukung (valid time dan transaction time) diasumsikan memiliki presisi yang terbatas. Struktur waktu yang mendukung presisi yang terbatas adalah struktur dengan model konseptual discrete time di mana waktu diasosiasikan dengan bilangan integer. Oleh karena itu pada tugas akhir ini struktur waktu yang digunakan adalah struktur discrete time. Model representasi yang digunakan, yaitu model Snodgrass’, menggunakan empat atribut timestamp yang masing-masing mewakili start time atau end time dari keberlakuan tuple. Format waktu yang cocok dengan model ini adalah time intervals. Penentuan apakah open-ended atau close-ended yang digunakan tidak berdasarkan pada satu pertimbangan tertentu, namun karena contoh yang telah digunakan pada bab-bab sebelumnya menggunakan close-ended, maka format waktu yang dipilih adalah time intervals close-ended. Salah satu batasan dari tugas akhir ini (subbab 1.4) adalah hanya menangani query yang melibatkan sebuah relasi. Dalam sebuah relasi tidak mungkin menggunakan granularitas lebih dari satu. Oleh karena itu granularitas yang digunakan adalah single database wide granularity dengan chronon satu hari. Representasi waktu (hari) yang akan digunakan adalah bentuk penanggalan YYYY-MM-DD di mana YYYY merupakan empat digit tahun (year), MM merupakan dua digit bulan (month), dan DD merupakan dua digit tanggal (day of month). Representasi ini digunakan pada relasi yang disimpan pada RDBMS untuk pengujian, sedangkan contoh-contoh pada dokumen ini hanya akan menampilkan digit tanggal (day of month) untuk mempersingkat.

III-1

III-2

3.2 Fungsi Agregasi pada Relasi Bitemporal Dengan adanya dua dimensi waktu, yaitu valid time dan transaction time, yang didukung oleh relasi bitemporal, penerapan fungsi agregasi terhadap relasi bitemporal berbeda dengan relasi snapshot. Untuk memproses fungsi agregasi pada relasi bitemporal, sebelumnya harus ditentukan terlebih dahulu interval konstan relasi. Interval konstan adalah suatu interval waktu di mana tidak terjadi perubahan data pada atribut eksplisit (non-timestamp). Setelah itu barulah fungsi agregasi dapat diterapkan pada masing-masing interval konstan. Karena relasi bitemporal memiliki dua dimensi waktu, maka proses penentuan interval konstan pada relasi ini akan berbeda dengan relasi valid-time seperti yang telah dijelaskan pada bab sebelumnya. Untuk menentukan interval konstan relasi bitemporal, maka perlu dicari interval konstan pada kedua dimensi waktu, yaitu valid time dan transaction time. Salah satu cara yang mungkin dilakukan adalah dengan melakukan dua tahap partisi relasi. Tahap pertama adalah partisi relasi berdasarkan interval konstan pada dimensi transaction time. Setelah didapatkan relasi yang telah dipartisi berdasarkan transaction time kemudian pada tahap kedua masing-masing partisi tersebut dipartisi lebih lanjut berdasarkan dimensi valid time. Proses ini sangat memakan banyak resource dan cukup rumit untuk diimplementasi. Fungsi agregasi biasanya diterapkan terhadap suatu relasi untuk mendapatkan summary dari data. Untuk basis data temporal, summary data yang dihasilkan tentunya ingin bersifat time-varying. Time-varying yang umumnya dirasakan berguna adalah sejarah keberlakuan data di dunia nyata, yang didukung oleh dimensi valid time. Sedangkan untuk transaction time, sangat jarang penggunaannya. Salah satu contoh yang mungkin dari fungsi agregasi berdasarkan transaction time adalah ketika user ingin melihat perubahan data hasil koreksi karena adanya kesalahan dalam memasukkan data. Contoh seperti ini memang sangat jarang penggunaannya. Mengingat jarangnya penggunaan dari transaction time sebagai aspek yang diperhitungkan dalam agregasi yang bersifat time-varying, maka dalam tugas akhir ini ditetapkan bahwa default dari query retrieval dengan fungsi agregasi terhadap relasi bitemporal adalah hanya mengambil current state dari dimensi transaction time kecuali bila secara eksplisit dispesifikasikan bahwa query harus memperhitungkan transaction time pada snapshot tertentu [SNO96].

3.3 Operasi Retrieval Relasi Bitemporal Operasi retrieval terhadap basis data temporal jika dilihat dari state relasi yang diakses dapat dibagi menjadi empat macam yaitu snapshot query, time-travel query, sequenced query, dan nonsequenced query. Dari jenis-jenis query tersebut, untuk relasi bitemporal yang mendukung dua dimensi waktu maka jenis query berdasarkan state yang diakses menjadi lebih bermacam-macam lagi. Jenis-jenis query yang akan ditangani pada tugas akhir ini adalah: 1. Snapshot Query (perpotongan antara snapshot pada valid time dan transaction time)

III-3

2. Valid Time-travel Query (time-travel pada valid time dan snapshot pada transaction time) 3. Time-travel Query (time-travel pada valid time dan transaction time) 4. Valid Sequenced Query (sequenced pada valid time dan snapshot pada transaction time) 5. Valid Sequenced Time-travel Query (sequenced pada valid time dan time-travel pada transaction time) 6. Valid Non-sequenced Query (non-sequenced pada valid time dan snapshot pada transaction time) 7. Valid Non-sequenced Time-Travel Query (non-sequenced pada valid time dan time-travel pada transaction time) Jenis sequenced dan non-sequenced query pada transaction time tidak ditangani karena jenis query tersebut dengan fungsi agregasi sangat jarang digunakan pada dunia nyata. Hal ini disebabkan dimensi transaction time pada umumnya hanya digunakan untuk keperluan rollback basis data untuk mengembalikan basis data pada suatu state tertentu di masa lampau. Oleh karena itu pengaksesan lebih dari satu state pada dimensi transaction time jarang digunakan.

3.3.1 Snapshot Query Snapshot query terhadap relasi bitemporal akan mengembalikan relasi yang bernilai current baik pada dimensi valid time maupun transaction time. Hasil dari query jenis ini adalah relasi snapshot. Gambar III-1 menunjukkan posisi dari hasil snapshot query terhadap relasi bitemporal. Masingmasing persegi merepresentasikan sebuah state relasi relatif terhadap kedua dimensi waktu, valid time dan transaction time. Pada gambar terlihat bahwa snapshot query hanya melakukan retrieve terhadap relasi pada current state baik pada dimensi valid time maupun transaction time.

Gambar III-1 Snapshot query

Contoh dari snapshot query retrieval dengan fungsi agregasi terhadap relasi bitemporal adalah “Berapakah jumlah pegawai pada saat ini?”, yang bila dituliskan dalam bahasa query temporal dapat dilihat pada Query III-1. Ciri khas dari query jenis ini adalah adanya keyword SNAPSHOT.

III-4

SELECT SNAPSHOT COUNT(*) FROM Employee Query III-1 Contoh snapshot query

3.3.2 Valid Time-travel Query Valid time-travel query adalah suatu jenis query terhadap relasi bitemporal pada suatu state basis data tertentu pada dimensi valid time dan bernilai current pada dimensi transaction time. Gambar III-2 menunjukkan posisi dari hasil valid time-travel query terhadap relasi bitemporal. Pada gambar terlihat bahwa query jenis ini melakukan retrieve terhadap basis data pada salah satu state dimensi valid time yang bernilai current pada transaction time. State yang dapat di-retrieve pada dimensi valid time tidak terbatas hanya pada waktu di masa lampau, dapat juga waktu di masa depan.

Gambar III-2 Valid time-travel query

Contoh dari valid time-travel query retrieval dengan fungsi agregasi terhadap relasi bitemporal adalah “Berapakah jumlah pegawai pada tanggal 15 Mei 2007?”, yang bila dituliskan dalam bahasa query temporal dapat dilihat pada Query III-2. Ciri khas dari query jenis ini adalah state valid time secara eksplisit ditentukan pada query dengan keyword SNAPSHOT pada klausa SELECT dan VALID OVERLAPS pada klausa WHERE. SELECT SNAPSHOT COUNT(*) FROM Employee WHERE VALID OVERLAPS DATE ’2007-05-15’ Query III-2 Contoh valid time-travel query

3.3.3 Time-travel Query Time-travel query adalah suatu jenis query terhadap relasi bitemporal pada suatu state basis data tertentu pada dimensi valid time maupun pada dimensi transaction time. Gambar III-3 menunjukkan posisi dari hasil valid time-travel query terhadap relasi bitemporal. Pada gambar terlihat bahwa query jenis ini melakukan retrieve terhadap basis data pada salah satu state dimensi

III-5

valid time dan state masa lalu pada dimensi transaction time. State yang dapat di-retrieve pada dimensi valid time dapat pada waktu di masa lampau maupun masa depan, sedangkan transaction time hanya pada masa lamapu dan tidak mungkin pada masa depan.

Gambar III-3 Time-travel query

Contoh dari time-travel query retrieval dengan fungsi agregasi terhadap relasi bitemporal adalah “Berapakah jumlah pegawai yang terdata pada tanggal 15 Mei 2007 mengacu pada basis data tanggal 17 Agustus 2007 sebelum dilakukan koreksi terhadap basis data?”, yang bila dituliskan dalam bahasa query temporal dapat dilihat pada Query III-3. Ciri khas dari query jenis ini adalah state valid time dan transaction time secara eksplisit ditentukan pada query dengan keyword SNAPSHOT pada klausa SELECT dan keyword VALID OVERLAPS dan TRANSACTION OVERLAPS pada klausa WHERE. SELECT SNAPSHOT COUNT(*) FROM Employee WHERE VALID OVERLAPS DATE ‘2007-05-15’ AND TRANSACTION OVERLAPS DATE ‘2007-08-17’ Query III-3 Contoh time-travel query

3.3.4 Valid Sequenced Query Valid sequenced query adalah jenis query terhadap relasi bitemporal yang hasilnya membutuhkan beberapa state dari dimensi valid time secara sekuensial. Hasil dari query ini berupa relasi validtime. Gambar III-4 menunjukkan posisi dari hasil valid sequenced query q’ terhadap relasi bitemporal. Pada gambar terlihat bahwa q’ dipecah menjadi beberapa query q yang masing-masing melakukan retrieve terhadap relasi bitemporal pada satu state valid time yang bernilai current pada dimensi transaction time, menghasilkan suatu relasi yang juga terdiri dari beberapa state valid time sesuai dengan sumbernya.

III-6

Gambar III-4 Valid sequenced query

Contoh dari valid sequenced query retrieval dengan fungsi agregasi terhadap relasi bitemporal adalah “Perlihatkan sejarah fluktuasi jumlah pegawai”, yang bila dituliskan dalam bahasa query temporal dapat dilihat pada Query III-4. Ciri khas dari jenis query ini adalah adanya keyword VALIDTIME pada klausa SELECT. VALIDTIME SELECT COUNT(*) FROM Employee Query III-4 Contoh valid sequenced

3.3.5 Valid Sequenced Time-travel Query Valid sequenced time-travel query hampir sama dengan valid sequenced query namun mengakses state masa lampau dari dimensi transaction time, bukan current state. Hasil dari query ini berupa relasi valid-time. Gambar III-5 menunjukkan posisi dari hasil valid sequenced time-travel query q’ terhadap relasi bitemporal. Pada gambar terlihat bahwa q’ dipecah menjadi beberapa query q yang masing-masing melakukan retrieve terhadap relasi bitemporal pada satu state valid time yang terletak pada salah satu state masa lampau pada dimensi transaction time, menghasilkan suatu relasi yang juga terdiri dari beberapa state valid time sesuai dengan sumbernya.

Gambar III-5 Valid Sequenced Time-travel Query

III-7

Contoh dari valid sequenced time-travel query retrieval dengan fungsi agregasi terhadap relasi bitemporal adalah “Perlihatkan sejarah fluktuasi jumlah pegawai mengacu pada basis data tanggal 17 Agustus 2007 sebelum dilakukan koreksi terhadap basis data”, yang bila dituliskan dalam bahasa query temporal dapat dilihat pada Query III-5. Ciri khas dari jenis query ini adalah adanya keyword VALIDTIME pada klausa SELECT dan terdapat kondisi transaction time yang harus dipenuhi dengan keyword TRANSACTION OVERLAPS pada klausa WHERE. VALIDTIME SELECT COUNT(*) FROM Employee WHERE TRANSACTION OVERLAPS DATE ‘2007-08-17’ Query III-5 Contoh valid sequenced time-travel query

3.3.6 Valid Non-sequenced Query Berbeda dengan valid sequenced query, di mana informasi dalam sebuah state valid time pada hasil query diperoleh hanya dari state valid time dengan waktu yang sama pada relasi sumber, pada valid non-sequenced query informasi dalam sebuah state valid time pada relasi hasil dapat diperoleh dari state dengan waktu yang berbeda pada relasi sumber. Query yang mengandung fungsi agregasi RISING termasuk ke dalam jenis query ini sebab untuk mendapatkan durasi di mana sebuah atribut bernilai monoton naik harus mengakses lebih dari sebuah state pada dimensi waktu valid-time.

Gambar III-6 Valid Non-sequenced Query

Gambar III-6 menunjukkan posisi dari hasil valid non-sequenced query terhadap relasi bitemporal. Pada gambar terlihat bahwa hasil query pada sebuah state mengambil informasi tidak hanya dari relasi sumber dengan state valid time yang sama dengannya, namun dapat juga dari state valid time yang berbeda. State valid time yang diakses hanyalah state yang terletak pada current time pada dimensi transaction time. Contoh dari valid non-sequenced query retrieval dengan fungsi agregasi terhadap relasi bitemporal adalah “Berapakah jumlah pegawai yang pernah bekerja pada

III-8

perusahaan?”, yang bila dituliskan dalam bahasa query temporal dapat dilihat pada Query III-6. Ciri khas dari query jenis ini adalah adanya keyword NONSEQUENCED VALIDTIME pada klausa SELECT. NONSEQUENCED VALIDTIME SELECT COUNT(DISTINCT Name) FROM Employee Query III-6 Contoh valid non-sequenced query

3.3.7 Valid Non-sequenced Time-travel Query Valid non-sequenced time-travel query hampir sama dengan valid non-sequenced query namun mengakses state masa lampau dari dimensi transaction time, bukan current state. Gambar III-7 Valid non-sequenced time-travel query menunjukkan posisi dari hasil valid non-sequenced timetravel query terhadap relasi bitemporal. Pada gambar terlihat bahwa hasil query pada sebuah state mengambil informasi tidak hanya dari relasi sumber dengan state valid time yang sama dengannya, namun juga dari state valid time yang berbeda. State valid time yang diakses adalah state yang di masa lampau pada dimensi transaction time. Dengan alasan yang sama dengan jenis nonsequenced query, query yang mengandung fungsi agregasi RISING juga dapat termasuk jenis query ini. Valid Time

...

future time

current time

old time

query Result

...

Result

...

Result

...

Result

old time

current time

Transaction Time

Gambar III-7 Valid non-sequenced time-travel query

Contoh dari valid non-sequenced time-travel query retrieval dengan fungsi agregasi terhadap relasi bitemporal adalah “Berapakah jumlah pegawai yang pernah bekerja pada perusahaan mengacu pada basis pada tanggal 17 Agustus 2007 sebelum dilakukan koreksi terhadap basis data?”, yang bila dituliskan dalam bahasa query temporal dapat dilihat pada Query III-7. Ciri khas dari query adalah adanya keyword NONSEQUENCED

VALIDTIME pada klausa SELECT dan state

transaction time secara eksplisit ditentukan dengan keyword TRANSACTION pada klausa WHERE.

OVERLAPS

III-9

NONSEQUENCED VALIDTIME SELECT COUNT(DISTINCT Name) FROM Employee WHERE TRANSACTION OVERLAPS DATE ‘2007-08-17’ Query III-7 Contoh valid non-sequenced time-travel query

3.4 Konversi Query Untuk dapat diproses, query temporal terhadap relasi bitemporal yang disimpan dalam RDBMS harus dikonversi menjadi query relasional. Proses konversi masing-masing jenis query terhadap relasi bitemporal yang telah diuraikan sebelumnya berbeda satu-sama lain. Berikut ini adalah penjelasan konversi query dari temporal menjadi relasional untuk setiap jenis query: 1. Snapshot Query, Valid Time-travel Query, dan Time-travel Query Konversi dilakukan dengan menghilangkan keyword temporal (seperti SNAPSHOT, VALID PERIOD, dan TRANSACTION PERIOD) dan penambahan kondisi untuk mendapatkan state relasi sesuai dengan yang diinginkan pada query baik pada dimensi valid time maupun transaction time. Jenis query ini tidak memerlukan pemrosesan menggunakan aggregation tree. 2. Valid Sequenced Query dan Valid Sequenced Time-travel Query Konversi dilakukan dengan menghilangkan keyword temporal (seperti VALIDTIME, VALID PERIOD, dan TRANSACTION PERIOD) dan penambahan kondisi untuk mendapatkan state yang diinginkan dari relasi sumber. Selain itu operator agregasinya juga perlu dihilangkan terlebih dahulu, namun atribut yang akan diagregasi tetap di dalam klausa SELECT karena yang akan di-retrieve dari relasi yang disimpan dalam RDBMS masih dalam bentuk relasi sumber, belum ada pemrosesan agregasi sama sekali. Hasil retrieve dari RDBMS kemudian diproses menggunakan pohon pemrosesan agregasi. 3. Valid Non-sequenced Query dan Valid Non-sequenced Time-Travel Query Untuk query yang mengandung fungsi agregasi RISING, proses konversinya sama dengan proses konversi jenis valid sequenced dan valid sequenced time-travel, sedangkan query yang tidak mengandung fungsi tersebut proses konversinya sama dengan proses konversi jenis snapshot, valid time-travel, dan time-travel query

3.5 Algoritma Pemrosesan Agregasi Pada sub-bab ini, akan dibahas modifikasi algoritma aggregation tree agar dapat menangani keyword WEIGHTED, fungsi RISING, dan klausa GROUP BY.

3.5.1 Penanganan keyword WEIGHTED Penyesuaian lebih lanjut terhadap algoritma aggregation tree diperlukan untuk memproses query yang mengandung keyword WEIGHTED. Jika query mengandung keyword WEIGHTED maka jumlah chronon pada sebuah tuple (weight) yang telah di-insert pada pohon harus diketahui.

III-10

Weight ini nantinya akan dikalikan dengan nilai atribut yang diagregasi seperti yang telah dijelaskan sebelumnya pada sub-bab 2.3.3 tentang keyword WEIGHTED. Karena informasi weight didapatkan dari tuple, maka diperlukan modifikasi pada proses insert terutama pada saat adjust nilai state agregasi. Pada saat adjust nilai agregasi, nilai atribut yang diagregasi pada tuple harus dikalikan terlebih dahulu dengan weight-nya Untuk mendapatkan informasi weight dapat dilakukan dengan mengurangi end-time dengan start time (ditambah satu untuk close-ended). Selebihnya, pemrosesan agregasi sama dengan algoritma awal.

3.5.2 Penanganan Fungsi RISING Karakteristik dari fungsi agregasi RISING telah dijelaskan pada sub-bab 2.3.3. Karena fungsi ini adalah fungsi agregasi spesifik temporal maka RDBMS tidak mengenalinya. Oleh sebab itu diperlukan penanganan khusus untuk memproses query yang mengandung fungsi ini. Dalam hal ini aggregation tree dapat dimanfaatkan untuk menangani pemrosesan fungsi RISING. Name Jake Jake Jake Jake Kate Kate

Salary 20 25 20 30 25 30

start 11 16 21 26 20 26

end 15 20 25 30 25 30

Gambar III-8 Relasi valid-time Salary2

Untuk mempermudah penjelasan dalam memanfaatkan aggregation tree pada pemrosesan fungsi RISING berikut ini akan diberikan contoh query dan pemrosesannya. Query III-8 merupakan contoh query yang mengakses relasi Salary2 pada Gambar III-8 untuk mendapatkan durasi waktu di mana pegawai bernama Jake tidak pernah mengalami penurunan gaji. SELECT RISING(Salary) FROM Salary2 WHERE Name = “Jake” Query III-8 Contoh query dengan fungsi RISING

Dari query tersebut dapat dibangun aggregation tree seperti terlihat pada Gambar III-9. Pohon ini dibangun dengan me-retrieve Salary dari relasi Salary2 yang memiliki Name bernilai Jake. Setiap simpul daun akan dibandingkan dengan simpul daun yang yang memiliki start time tepat setelah end time simpul tersebut. Jika nilai agregasi yang terkandung pada simpul setelahnya itu lebih besar maka timestamp kedua simpul tersebut digabungkan. Simpul [11,15] yang memiliki nilai agregasi 20 dibandingkan dengan [16,20] yang memiliki nilai agregasi lebih besar yaitu 25, sehingga kedua timestamp simpul tersebut di-merge.

III-11

Gambar III-9 Aggregation tree untuk Query II-3

Selanjutnya simpul [16,20] dibandingkan dengan simpul [21,25]. Pada tahap ini nilai agregasi dari simpul timestamp yang kecil memiliki nilai agregasi yang lebih besar dari simpul timestamp besar, yang berarti pada perbatasan kedua timestamp gaji dari Jake mengalami penurunan. Timestamp hasil merge pada tahap pertama tidak dapat di-merge lagi dengan [21,25] dan menghasilkan tuple pertama pada relasi hasil yang bernilai [11,20]. Langkah selanjutnya adalah membandingkan simpul [21,25] dengan [26,30]. Dengan kondisi yang sama seperti pada tahap sebelumnya maka didapatkan tuple kedua pada relasi hasil yang bernilai [21,30] hasil merge [21,25] dan [25,30]. Relasi hasil Query III-8 dapat ditunjukkan pada Gambar III-10. RISING(Salary) [11,20] [21,30] Gambar III-10 Relasi hasil Query III-8

3.5.3 Penanganan Klausa GROUP BY Pemrosesan operator agregasi biasanya dilakukan dengan terlebih dahulu mempartisi relasi masukan menjadi beberapa kelompok tuple dengan nilai yang identik untuk satu atau lebih atribut, kemudian menerapkan fungsi agregasi untuk masing-masing kelompok tuple tersebut [BOH06]. Pemrosesan yang terlebih dahulu mempartisi relasi menjadi beberapa kelompok tuple ini ditentukan oleh klausa GROUP BY dalam query yang mengandung fungsi agregasi tersebut. Klausa ini memiliki masukan atribut relasi yang nilainya dijadikan pembanding untuk mengelompokkan tuple yang memiliki nilai yang sama untuk atribut masukan tersebut. Oleh karena itu penanganan klausa GROUP BY perlu dibahas lebih lanjut. Untuk query terhadap relasi temporal, proses pengelompokkan tuple berdasarkan atribut tertentu ini menjadi lebih rumit karena sebelumnya tuple juga telah dikelompokkan berdasarkan interval konstan timestamp-nya. Dengan adanya proses pengelompokkan berkalang ini, pemrosesan agregasi khususnya yang mengandung klausa GROUP BY tidak dapat langsung diterapkan menggunakan aggregation tree. Cara paling sederhana memproses agregasi yang mengandung klausa GROUP BY menggunakan aggregation tree adalah dengan membangun pohon untuk masing-masing kelompok tuple pada relasi yang memiliki nilai atribut pengelompok tertentu. Dengan kata lain, untuk setiap nilai distinct dari atribut pengelompok akan dibangun sebuah pohon dari kelompok tuple yang atribut pengelompoknya bernilai sama dengan nilai distinct tersebut.

III-12

Dengan cara ini, pengaksesan relasi serta pembangunan aggregation tree akan dilakukan sebanyak nilai distinct dari atribut pengelompok. Pengaksesan relasi dan pembangunan pohon yang berulang-ulang tentunya akan membutuhkan ongkos yang besar. Oleh karena itu diperlukan suatu modifikasi terhadap struktur pohon agar memungkinkan klausa GROUP BY ini dapat diproses tanpa harus membangun pohon berulang-ulang. Modifikasi terhadap struktur pohon ini diperlihatkan pada Gambar III-11.

Gambar III-11 Struktur aggregation tree yang dimodifikasi

Struktur baru aggregation tree ini mengambil ide dari struktur PA-Tree untuk agregasi selektif seperti pada Gambar II-20. Nilai state agregasi pada T-node (tree node atau simpul pohon) yang sebelumnya hanya memuat sebuah nilai, pada struktur baru ini digantikan dengan sebuah linked list yang dinamakan G-List. G-list terdiri dari sejumlah simpul G-node. Struktur G-node terdiri dari G-value, nilai state agregasi (yang berupa lingkaran pada Gambar III-11), dan sebuah pointer menuju simpul G-node selanjutnya. G-value menyimpan nilai dari atribut pengelompok, yaitu atribut masukan dari klausa GROUP BY pada query. Name Jake Jake Kate Kate Bob Bob

Department Load Ship Ship Load Ship Load

start 11 16 16 26 26 36

end 15 35 25 40 35 ∞

Gambar III-12 Relasi valid-time Employee2

Untuk memperjelas bagaimana struktur aggregation tree yang telah dimodifikasi memproses query retrieval yang mengandung klausa GROUP BY, berikut akan diuraikan contoh penggunaan pohon ini untuk memproses Query III-9 yang me-retrieve relasi valid-time close-ended pada Gambar III-12 untuk mendapatkan jumlah pegawai dari masing-masing Department. SELECT Department, COUNT(Name) FROM Employee2 GROUP BY Department Query III-9 Contoh query dengan GROUP BY

Jika Query III-9 harus diproses menggunakan aggregation tree yang belum dimodifikasi, maka pohon yang harus dibangun sebanyak dua buah, masing-masing untuk nilai distinct atribut Department, yaitu Load dan Ship. Sedangkan pemrosesan query tersebut menggunakan

III-13

aggregation tree yang dimodifikasi hanya membutuhkan pembangunan sebuah pohon. Pembangunan pohon tersebut dapat dilihat pada Gambar III-13.

Gambar III-13 Pembangunan aggregation tree yang dimodifikasi

Pembangunan pohon dimulai dengan pohon awal yang hanya memiliki sebuah simpul dengan start time 0 dan end time ∞. G-list dari simpul tersebut masih belum diinisialisasi seperti dapat dilihat pada Gambar III-13.a. Pembangunan pohon dilanjutkan dengan melakukan insert tuple pertama pada relasi, yaitu tuple (Jake, Load, [11,15]). Proses insert tuple baru ini sama saja dengan proses insert pada aggregation tree yang telah dijelaskan sebelumnya. Timestap dari tuple ini membagi tiga timestamp simpul awal sehingga dihasilkan pohon dengan tiga simpul daun yang masingmasing memiliki timestamp [0,10], [11,15], dan [16,∞] seperti pada Gambar III-13.b. Pada tahap ini G-list simpul akar diisi sebuah G-node dengan G-value bernilai Load, yaitu nilai atribut pengelompok dari tuple yang di-insert dan nilai agregasi 0. Sedangkan G-list simpul yang memiliki timestamp sesuai dengan tuple yaitu [11,15] diisi dengan G-node dengan G-value Load dan nilai agregasi 1. Langkah selanjutnya adalah insert tuple kedua relasi yaitu (Jake, Ship, [16,35]). Pada langkah ini G-list simpul akar ditambahkan G-node dengan G-value Ship dan nilai agregasi 0 karena nilai atribut pengelompok tuple kedua ini (Ship) merupakan nilai baru yang belum terdapat pada pohon. Seperti pada langkah sebelumnya, G-list simpul dengan timestamp [16,35] diisi G-node dengan Gvalue Ship dan nilai agregasi 1. Gambar III-13.c menggambarkan pohon setelah proses insert tuple kedua.

III-14

Pembangunan pohon dilanjutkan dengan melakukan insert tuple selanjutnya dengan cara yang sama seperti tuple pertama dan kedua. Jika timestamp tuple yang di-insert tepat overlap seluruh timestamp dari sebuah simpul, proses insert dilakukan dengan meng-update G-list dari simpul tersebut dan tidak perlu menambah simpul baru. Proses update ini dilakukan dengan menambahkan nilai agregasi pada G-node yang memiliki G-value yang sama dengan nilai atribut pengelompok pada tuple atau menambahkan G-node baru jika belum ada pada list. Hasil akhir pembangunan aggregation tree ini dapat dilihat pada Gambar III-13.d. Department COUNT(Name) Load 0 Ship 0 Load 1 Ship 0 Load 0 Ship 2 Load 1 Ship 2 Load 2 Ship 0 Load 1 Ship 0

start 0 0 11 11 16 16 26 26 36 36 41 41

End 10 10 15 15 25 25 35 35 40 40 ∞ ∞

Gambar III-14 Relasi hasil Query III-9

Relasi hasil dari pembangunan aggregation tree ini ditunjukkan pada Gambar III-14. Setiap simpul pada pohon akan menghasilkan tuple pada relasi hasil sebanyak nilai distinct atribut pengelompok relasi sumber. Penghitungan nilai agregasi untuk mendapatkan relasi hasil dilakukan dengan penelusuran pohon dari akar sampai simpul. Sebagai contoh, simpul [36,40] jika ditelusuri dari akar maka akan menghasilkan nilai agregasi untuk kelompok tuple Load sebesar 2 (yaitu 1 dari simpul [36,∞] dan 1 dari simpul [36,40]) dan nilai agregasi untuk kelompok tuple Ship sebesar 0 sebab pada penelusuran dari akar sampai simpul tersebut tidak ditemukan simpul yang memiliki G-list dengan G-node yang G-value-nya bernilai Ship.

3.6 Pemrosesan Query Hal pertama yang perlu dilakukan dalam pemrosesan query temporal adalah menentukan jenis query. Penentuan jenis query adalah sebagai berikut: 1. Jika terdapat keyword SNAPSHOT, maka termasuk jenis snapshot query 2. Jika terdapat kondisi VALID OVERLAPS DATE , maka termasuk jenis valid time-travel query 3. Jika terdapat kondisi VALID

OVERLAPS

DATE

dan kondisi

TRANSACTION OVERLAPS DATE , maka termasuk jenis time-travel query 4. Jika terdapat keyword VALIDTIME, maka termasuk jenis valid sequenced query.

III-15

5. Jika terdapat keyword VALIDTIME dan kondisi TRANSACTION

OVERLAPS

DATE

, maka termasuk jenis valid sequenced query. 6. Jika terdapat keyword NONSEQUENCED VALIDTIME, maka termasuk jenis valid nonsequenced query. 7. Jika terdapat keyword NONSEQUENCED

VALIDTIME dan kondisi TRANSACTION

OVERLAPS DATE , maka termasuk jenis valid non-sequenced query. Setelah jenis query ditentukan, maka dilakukan konversi menjadi query relasional sesuai dengan jenisnya seperti yang telah dijelaskan pada sub-bab 0. Untuk jenis snapshot, valid time-travel, dan time-travel query, serta valid non-sequenced dan valid non-sequenced time-travel query yang tidak mengandung fungsi agregasi RISING, hasil eksekusi dari query relasional dari proses konversi ini akan langsung merupakan relasi hasil. Sedangkan untuk jenis valid sequenced dan valid sequenced time-travel query serta valid non-sequenced dan valid non-sequenced time-travel query yang mengandung fungsi agregasi RISING, hasilnya merupakan relasi valid-time yang nantinya akan menjadi input pembangunan aggregation tree. Bagan alur pemrosesan query temporal dengan fungsi agregasi sampai didapatkan hasilnya diilustrasikan pada Gambar III-15. Query temporal dengan fungsi agregasi

Penentuan jenis query

Jenis query: 1. Snapshot 2. Valid time-travel 3. Time-travel

Konversi query

Jenis query: 1. Valid non-sequenced 2. Valid non-sequenced time-travel

Tidak mengandung fungsi RISING

Mengandung fungsi RISING

Query relasional

Akses basis data

Jenis query: 1. Valid sequenced 2. Valid sequenced time-travel

Konversi query

Query relasional

Pemrosesan dengan aggregation tree

Relasi valid-time

Akses basis data

Hasil query

Gambar III-15 Bagan alur pemrosesan query