BAB II DASAR TEORI. 2.1 Basis Data Temporal Aspek Waktu

BAB II DASAR TEORI

Dasar teori yang akan diuraikan dalam bab ini mencakup empat hal utama yang menjadi fokus tugas akhir, yaitu konsep basis data temporal, Bitemporal Conceptual Data Model (BCDM), operasi retrieval dengan fungsi agregasi dan metode pemrosesan agregasi yang telah dikembangkan sebelumnya untuk data temporal.

2.1 Basis Data Temporal Saat ini, aplikasi basis data pada dunia nyata, seperti pada bidang keuangan, medis, dan sains, banyak yang membutuhkan pengelolaan aspek temporal dari data yang disimpan. Aspek temporal yang dimaksud di sini adalah waktu keberlakuan data baik pada dunia nyata maupun pada basis data. Basis data yang mendukung aspek temporal, di luar waktu yang didefinisikan oleh user (user-defined time) disebut dengan basis data temporal [JEN98].

2.1.1 Aspek Waktu Dalam merepresentasikan waktu pada basis data, ada beberapa hal yang harus diperhatikan, di antaranya yaitu struktur, interpretasi, representasi, format, dan granularitas waktu yang akan digunakan [WID03]. 2.1.1.1 Struktur Struktur waktu berkaitan dengan pengorganisasian waktu secara internal pada basis data. Pengorganisasian waktu ini dapat dibagi menjadi dua model, yaitu model konseptual dan model struktural [WID03]. 1. Model konseptual Struktur waktu dengan model konseptual menekankan pada perlakuan terhadap waktu sehingga dapat direpresentasikan dalam bentuk himpunan. Struktur waktu dengan model ini terdiri dari model dense time dan discrete time. a. dense time Pada model ini waktu diasosiasikan dengan bilangan real, sehingga pengorganisasian waktu dalam basis data dinyatakan dengan himpunan waktu yang kontinu. Dengan kata lain, selalu terdapat instan waktu di antara dua buah instan waktu. b. discrete time Pada model ini waktu diasosiasikan dengan bilangan integer, sehingga pengorganisasian waktu dinyatakan dengan himpunan waktu yang diskrit atau tidak kontinu. Unit waktu terkecil disebut dengan chronon, yang masing-masing memiliki sebuah successor.

II-1

II-2

2. Model struktural Struktur waktu dengan model struktural lebih menekankan pada bagaimana kelanjutan waktu setelah current time. Pengorganisasian waktu dengan model struktural terdiri dari model linier dan model bercabang. a. model linier Pada model ini waktu berubah dari masa lalu ke masa yang akan datang dengan sebuah urutan tertentu sehingga hanya ada satu kemungkinan kejadian. b. model bercabang (possible futures model) Pada model ini waktu berubah secara linier dari masa lalu hingga saat ini, namun kemudian dapat bercabang menjadi beberapa garis waktu yang menunjukkan urutan kejadian yang mungkin dapat terjadi di masa yang akan datang. 2.1.1.2 Interpretasi Interpretasi waktu merupakan makna yang terkandung dari data yang berupa instan waktu [WID03]. Makna dari data ini dispesifikkan pada saat perancangan basis data oleh perancangnya. Oleh karena itu sebuah atribut waktu dapat memiliki makna yang berbeda pada basis data atau relasi yang berbeda. Contoh perbedaan interpretasi waktu dari dua relasi pada sebuah basis data misalnya adalah sebuah atribut tanggal pada relasi mahasiswa memiliki makna sebagai tanggal lahir mahasiswa, sedangkan atribut tanggal pada relasi kelulusan memiliki makna sebagai tanggal lulusnya mahasiswa. Untuk contoh perbedaan interpertasi waktu dari atribut waktu pada basis data yang berbeda misalnya adalah sebuah atribut tanggal lulus mahasiswa pada suatu basis data berarti tanggal mahasiswa menyelesaikan sidang tugas akhirnya, sedangkan pada basis data lain berarti tanggal mahasiswa diwisuda. 2.1.1.3 Representasi Representasi waktu merupakan cara bagaimana menampilkan waktu kepada pengguna [WID03]. Misalkan tanggal 15 Mei 2007 dapat ditampilkan dengan berbagai macam bentuk representasi, seperti dengan menggunakan angka, yaitu 135 (hari ke-135 pada tahun 2007) atau menggunakan salah satu bentuk penanggalan seperti 15/05/2007. Penentuan representasi waktu yang akan digunakan sangat tergantung pada kebutuhan basis data. Namun tipe data yang didukung oleh DBMS yang digunakan juga ikut mempengaruhi penentuan representasi waktu ini. Misalkan saja DBMS yang digunakan tidak mendukung tipe data tanggal, namun basis data membutuhkan tampilan tanggal dalam salah satu bentuk penanggalan, maka representasi waktu ini harus dibuat sedemikian rupa sehingga pengguna dapat mengerti misalnya dengan memisahkan tanggal, bulan, dan tahun yang masing-masing bertipe numerik.

II-3

2.1.1.4 Format Pada basis data temporal terdapat tiga macam format waktu, yaitu time points, time intervals, dan temporal elements [JEN96]. 1. Time Points Time points merupakan suatu instan waktu yang dapat merepresentasikan dua hal, yaitu: a. waktu saat suatu event terjadi b. waktu saat suatu event dimulai, di mana waktu selesainya suatu event secara implisit didefinisikan sebagai waktu saat event selanjutnya dimulai. Dengan begitu, penyimpanan informasi pada basis data harus terurut secara temporal. 2. Time Intervals Time intervals merepresentasikan suatu durasi waktu, yaitu himpunan chronon yang terurut. Batas bawah dari himpunan chronon tersebut merupakan start time, sedangkan batas atasnya merupakan end time dari keberlakuan data. Terdapat dua jenis representasi dari time intervals, yaitu close-ended dan open-ended. a. close-ended: durasi waktu dengan jenis ini meliputi semua chronon mulai dari start time hingga end time, biasanya dituliskan dengan [start-time, end-time] b. open-ended: durasi waktu dengan jenis ini meliputi semua chronon mulai dari start time hingga satu chronon sebelum end time, biasanya dituliskan dengan [start-time, end-time) 3. Temporal Elements Temporal elements merepresentasikan himpunan chronon yang merupakan hasil operasi penggabungan terbatas sejumlah time intervals yang terpisah. Format waktu ini menggabungkan data yang memiliki informasi sama, namun memiliki atribut waktu yang berbeda (proses coalescing).

Gambar II-1 Perbedaan format waktu

Perbedaan pemakaian ketiga format waktu untuk merepresentasikan informasi tersebut dapat dilihat pada Gambar II-1. Ketiga tabel pada gambar tersebut menampilkan informasi yang sama namun dalam format yang berbeda. Pada contoh tersebut durasi waktu seorang pegawai bernama Bob bekerja di departemen Ship dari tahun 2001 (‘01) sampai 2003 dan dari tahun 2006 sampai 2007, sedangkan dari tahun 2004 sampai 2005 Bob bekerja di departemen Load.

II-4

2.1.1.5 Granularitas Granularitas waktu adalah kedetilan waktu yang digunakan dalam basis data temporal. Kedetilan waktu yang dibutuhkan setiap aplikasi berbeda-beda. Semakin kecil granularitas akan ketelitian meningkat namun mahal harganya karena akan membutuhkan resource yang besar. Sebaliknya, semakin besar granularitas akan menghemat resource, namun memungkinkan kehilangan informasi. Terdapat dua pendekatan dalam menentukan granularitas waktu pada basis data temporal yaitu single database wide granularity dan multiple granularity [JEN94]. 1. Single Database Wide Granularity Hanya menggunakan satu level granularitas, dengan menetapkan suatu level yang relatif optimum terhadap kebutuhan aplikasi basis data. 2. Multiple Granularities Menggunakan beberapa level granularitas, dengan menyediakan fungsi konversi atau perbandingan antar level.

2.1.2 Dimensi Waktu Secara umum, terdapat tiga dimensi waktu pada basis data temporal, yaitu valid time, transaction time, dan user-defined time [SNO85]. 1. Valid Time Valid time dari sebuah fakta adalah waktu ketika fakta tersebut bernilai benar pada dunia nyata yang dimodelkan pada basis data [JEN98]. Domain dari dimensi waktu ini mencakup waktu di masa lampau, saat ini dan di masa yang akan datang. 2. Transaction Time Sebuah fakta disimpan ke dalam sebuah basis data pada suatu titik waktu, dan kemudian fakta tersebut bersifat current sampai dihapus secara lojik. Transaction time dari sebuah fakta adalah waktu ketika fakta bersifat current pada basis data dan dapat di-retrieve [JEN98]. Dengan begitu, dimensi waktu ini tidak mencakup waktu di masa yang akan datang. 3. User-defined Time User-defined time adalah sebuah domain waktu dari atribut yang tidak dapat diinterpretasi oleh basis data [JEN98]. Semantik dari dimensi waktu ini hanya diketahui oleh perancangnya. Contoh penggunaan user-defined time adalah pada pendefinisian atribut seperti “tanggal lahir”.

2.1.3 Taksonomi Relasi Berdasarkan dimensi waktu yang ditangani, relasi pada basis data temporal dapat diklasifikasikan menjadi empat macam, yaitu snapshot, valid-time, transaction-time, dan bitemporal [JEN94]. 1. Relasi snapshot Relasi snapshot tidak menangani dimensi waktu valid time maupun transaction time. Informasi yang disimpan dianggap current pada suatu waktu tertentu, biasanya saat ini. Pada relasi jenis ini, operasi modifikasi terhadap data akan menyebabkan data lama hilang.

II-5

2. Relasi valid-time Sesuai dengan namanya, relasi valid-time menangani dimensi waktu valid time. Penanganan dimensi valid time dapat dilakukan dengan beberapa cara, di antaranya dengan menambahkan satu atau lebih atribut valid-time tambahan pada skema relasi [JEN98]. Pada relasi jenis ini, operasi modifikasi tehadap data juga akan menyebabkan data lama hilang. 3. Relasi transaction-time Relasi yang sering juga disebut sebagai relasi rollback ini merupakan relasi yang menangani dimensi waktu transaction time. Relasi jenis ini mengelola sejarah status basis data di masa lampau dengan cara menyimpan setiap transaksi bagi setiap objek yang diindeks berdasarkan waktu saat transaksi dimulai. Relasi ini bersifat statis, yang berarti bahwa jika terjadi operasi modifikasi terhadap data, informasi lama dari data tersebut tidak dihapus, namun tetap disimpan. 4. Relasi bitemporal Relasi bitemporal merupakan relasi yang menangani dimensi waktu valid time dan transaction time. Relasi jenis ini merupakan kombinasi dari relasi valid-time dan relasi transaction-time, sehingga mewarisi properti dari kedua relasi tersebut. Pada umumnya tidak ada keterkaitan antara kedua dimensi waktu yang ditangani pada relasi.

2.2 Bitemporal Conceptual Data Model Hal-hal yang perlu untuk dibahas terkait dengan BCDM adalah pengertian BCDM itu sendiri, model representasi yang membuat BCDM dapat diimplementasi, serta dukungan bahasa query temporal (TSQL2) terhadap relasi bitemporal.

2.2.1 Pengertian BCDM Bitemporal Conceptual Data Model (BCDM) merupakan sebuah model data yang dirancang untuk menangkap esensi semantik dari relasi yang bersifat time-varying, namun tidak cocok untuk penyimpanan data dalam level fisik maupun untuk evaluasi query. Hal itulah yang membuat BCDM disebut sebagai model konseptual. Istilah “konseptual” pada BCDM digunakan untuk menekankan bahwa penggunaan model ini hanya untuk perancangan basis data dan sebagai basis bahasa query saja [JEN94]. Relasi Employee pada Gambar II-2 merupakan contoh instans dari relasi bitemporal dengan BCDM. Name Jake

Department Ship

Jake Kate

Load Ship

Timestamp {(5,10), ..., (5,15), ..., (9,10), ..., (9,15), (10,5), ..., (10,20), ..., (14,5), ..., (14,20), (15,10), ..., (15,15), ..., (19,10), ..., (19,15)} {(20,10), ..., (20,15), ..., (UC,10), ..., (UC,15)} {(20,25), ..., (20,30), ..., (UC,25), ..., (UC,30)}

Gambar II-2 Relasi Employee dalam BCDM

II-6

Gambar II-2 berisi informasi mengenai nama Employee dan nama Department tempatnya bekerja. Misalnya pada tuple pertama berarti Employee bernama Jake bekerja pada Department Ship. Data pada tuple pertama ini awalnya dicatat pada basis data pada saat transaction time 5, dan berlaku pada dunia nyata selama kurun waktu valid time 10 sampai dengan 15. Namun pada transaction time 10 data diperbaiki karena ada kesalahan bahwa ternyata Jake bekerja di Department Ship dari valid time 5 sampai 20. Pada transaction time 15, data kembali diperbaiki karena ternyata Jake memang bekerja selama kurun waktu valid time 10 sampai 15. Tuple kedua berisi informasi bahwa pada transaction time 20 kembali ditemukan kesalahan bahwa sebenarnya Jake bukan bekerja di Department Ship melainkan di Department Load selama kurun waktu valid time 10 sampai 15. Informasi pada tuple kedua ini masih bernilai valid di basis data sampai saat ini karena terdapat pasangan (tt, vt) yang memiliki transaction time yang bernilai UC (until changed). Sedangkan tuple ketiga berisi informasi bahwa Kate bekerja di Department Ship selama kurun waktu valid time 25 sampai 30 dan sudah tercatat di basis data mulai transaction time 20 sampai saat ini. Tuple dalam sebuah instan relasi bitemporal diasosiasikan dengan nilai waktu dari dua dimensi waktu yang ortogonal, yaitu valid time dan transaction time. Kedua domain diasumsikan memiliki presisi yang terbatas (chronon). Domain dari valid time dinyatakan dengan DVT = {t1, t2, ..., tk} sedangkan domain dari transaction time dinyatakan dengan DTT = {t’1, t’2, ..., t’j} ∪ {UC}. UC (until changed) adalah sebuah nilai khusus yang menunjukkan bahwa sebuah fakta yang diasosiasikan dengan transaction time yang bernilai UC masih current pada basis data. Elemen dari DVT disebut dengan chronon valid-time, sedangkan elemen dari DTT disebut dengan chronon transaction-time. Sebuah chronon bitemporal adalah sebuah pasangan terurut (tt, vt) dari chronon transaction-time tt dan chronon valid-time vt. Pada umumnya, skema relasi bitemporal R terdiri dari n atribut eksplisit dengan domain tertentu yang merepresentasikan sebuah fakta dan sebuah atribut timestamp implisit T yang memiliki domain DTT × DVT. Domain timestamp T merupakan sebuah himpunan chronon bitemporal yang disebut dengan bitemporal element. Sebuah tuple x = (a1, a2, ..., an | tb) dalam instan relasi bitemporal r(R) terdiri dari sejumlah nilai atribut eksplisit representasi dari sebuah fakta diasosiasikan dengan bitemporal element tb, yang berarti bahwa fakta tersebut valid pada dunia nyata untuk masing-masing chronon valid-time pada tb dan current pada basis data pada masingmasing chronon transaction-time pada tb. Dua tuple dengan atribut eksplisit yang bernilai identik tidak diperbolehkan dalam instan relasi bitemporal sehingga keseluruhan sejarah dari sebuah fakta hanya terdapat tepat pada sebuah tuple.

II-7

Gambar II-3 Contoh representasi grafis relasi bitemporal [JEN94]

Relasi bitemporal dapat direpresentasikan dalam grafik dua-dimensi yang dibangun dari dimensi transaction time dan dimensi valid time. Pada representasi grafis ini, sumbu-x merupakan dimensi transaction time, sedangkan sumbu-y merupakan dimensi valid time. Gambar II-3 memperlihatkan contoh representasi grafis relasi bitemporal dari relasi Employee pada Gambar II-2. Tanda panah ke arah kanan menunjukkan bahwa tuple yang direpresentasikan pada gambar tersebut secara lojik belum terhapus. Dengan kata lain tuple tersebut masih terus berlaku dalam dimensi transaction time sampai terjadi perubahan terhadap data tersebut (until changed) yang pada instan relasi bitemporal dinotasikan dengan UC.

2.2.2 Model Representasi BCDM BCDM memiliki struktur yang cukup sederhana, yaitu sebuah himpunan fakta yang masingmasing diberi timestamp sebuah bitemporal element. Walaupun strukturnya tampak sederhana, representasi internal BCDM sulit untuk diimplementasikan karena memiliki atribut yang multivalued. Oleh karena itu, dibutuhkan suatu model representasi yang memungkinkan model konseptual ini dapat diimplemetasikan pada relational database management system (RDBMS). Beberapa model representasi relasi bitemporal baik dengan bentuk relasi 1NF (First Normal Form) maupun N1NF (Non First Normal Form) telah diusulkan[JEN94]. Perbandingan beberapa model representasi dalam bentuk 1NF (model Snodgrass’, Jensen’s, dan Ben-Zvi’s) jika dilihat dari efisiensi ruang penyimpanan dan proses pemetaan antara model representasi dan BCDM serta proses insert, update, dan delete telah dilakukan sebelumnya pada [HAN05]. Alasan dari perbandingan model representasi tersebut hanya melibatkan model dalam bentuk 1NF adalah RDBMS yang ada saat ini hanya melakukan pengelolaan data dalam bentuk 1NF. Hasil perbandingan model representasi ini dapat dilihat pada Tabel II-1.

II-8

Tabel II-1 Perbandingan Ketiga Model Representasi BCDM [HAN05]

Aspek Pembanding Efisiensi penggunaan ruang penyimpanan atribut timestamp Efisiensi penggunaan ruang penyimpanan tuple Proses pemetaan antara model konseptual ke model representasi Proses pemetaan antara model representasi ke model konseptual Proses insert Proses update Proses delete

Snodgrass’

Jensen’s

Ben-Zvi’s kurang efisien

Efisien

Efisien

Efisien

Kurang efisien

efisien

Sederhana

Rumit

rumit

Sederhana

Rumit

rumit

Rumit Sederhana Sederhana

Sederhana Rumit Rumit

rumit sederhana sederhana

Dari Tabel II-1 terlihat bahwa model Snodgrass relatif lebih baik jika dibandingkan dengan dua model lainnya. Oleh karena itu, pelaksanaan tugas akhir ini menggunakan model representasi BCDM Snodgrass’ Tuple Timestamped Representational Scheme. Pada model representasi ini, sebuah relasi bitemporal direpresentasikan dengan sebuah skema relasi sebagai berikut. R = (A1, ..., An, Ts, Te, Vs, Ve) A1, ..., An adalah sejumlah atribut eksplisit yang merepresentasikan sebuah fakta, sedangkan Ts, Te, Vs, Ve merupakan atribut timestamp yang bernilai atomik dan masing-masing mewakili awal transaction time (Ts), akhir transaction time (Te), awal valid time (Vs), dan akhir valid time (Ve). Keempat atribut timestamp ini merepresentasikan bitemporal element pada BCDM. Name Jake Jake Jake Jake Kate

Department Ship Ship Ship Load Ship

Ts 5 10 15 20 20

Te 9 14 19 UC UC

Vs 10 5 10 10 25

Ve 15 20 15 15 30

Gambar II-4 Relasi Employee dalam model representasi Snodgrass [JEN94]

Proses delete (secara lojik) sebuah fakta dilakukan dengan mengubah nilai Ts dari UC menjadi nilai transaction time terakhir fakta tersebut current pada basis data. Sedangkan proses update dilakukan dengan melakukan proses insert fakta baru kemudian diikuti proses delete secara lojik fakta lama. Dengan model ini, maka relasi Employee pada Gambar II-2 direpresentasikan menjadi relasi 1NF seperti pada Gambar II-4. Pada contoh ini [Ts, Te] dan [Vs, Ve] masing-masing membentuk sebuah close-ended time intervals. Hal penting yang perlu diperhatikan pada model representasi 1NF adalah representasi current time dari data baik pada dimensi transaction time maupun valid time. Jika pada transaction time sudah diperkenalkan istilah UC (until changed) untuk merepresentasikan current time (seperti yang telah dijelaskan pada sub-bab 2.2.1), lain halnya dengan valid time. Pada dimensi valid time, adakalanya ketika proses insert sebuah tuple, akhir keberlakuan tuple tersebut pada dunia nyata (end validtime) belum dapat ditentukan. Misalkan pada relasi Employee (Gambar II-4) akan ditambahkan

II-9

seorang pegawai bernama Bob yang mulai bekerja di departemen Load dari valid time 20, namun belum ditentukan sampai kapan masa kerjanya akan berakhir di depertemen tersebut. Pada kasus tersebut dipergunakan istilah ‘now’ pada end valid-time untuk memperlihatkan bahwa sebuah tuple masih berlaku pada current time dari dimensi valid time namun belum diketahui kapan akhir keberlakuan tuple tersebut. Gambar II-5 memperlihatkan relasi Employee dalam model representasi Snodgrass’ setelah dilakukan proses insert pegawai Bob pada transaction time 20. Name Jake Jake Jake Jake Kate Bob

Department Ship Ship Ship Load Ship Load

Ts 5 10 15 20 20 20

Te 9 14 19 UC UC UC

Vs 10 5 10 10 25 20

Ve 15 20 15 15 30 now

Gambar II-5 Relasi Employee setelah penambahan (Bob,Load)

Jika pada suatu waktu tertentu akhir keberlakuan tuple dengan Ve=‘now’ telah diketahui, maka modifikasi harus dilakukan pada tuple tersebut dengan mengganti UC pada Te dengan transaction time ketika terjadi modifikasi jika relasi bersifat open-ended dan (transaction time ketika terjadi modifikasi) - 1 jika close-ended. Perhatikan bahwa hanya nilai UC pada transaction time yang dapat di-update sedangkan nilai lainnya termasuk ‘now’ pada valid time tidak boleh di-update. Setelah proses update terhadap transaction time dilakukan, langkah selanjutnya adalah menambahkan tuple baru dengan nilai atribut eksplisit yang sama (Bob, Load) namun dengan Ve sesuai dengan akhir keberlakuan data di dunia nyata yang telah diketahui. Gambar II-6 memperlihatkan cuplikan relasi Employee yang mengalami perubahan setelah proses modifikasi jika diketahui pada transaction time 25 bahwa masa kerja Bob di departemen Load hanya sampai valid time 25. Name … Bob Bob

Department … Load Load

Ts … 20 25

Te … 24 UC

Vs … 20 20

Ve … now 25

Gambar II-6 Cuplikan relasi Employee setelah modifikasi tuple (Bob,Load)

Dengan penjelasan di atas, terlihat bahwa nilai Ve=‘now’ pada sebuah tuple bukan berarti tuple tersebut masih berlaku sampai current time dari dimensi valid time. Hal tersebut hanya berlaku jika Te dari tuple tersebut bernilai UC atau dengan kata lain tuple tersebut masih current pada basis data. Untuk memperjelas, Gambar II-7 memperlihatkan representasi grafis tuple Bob bekerja di departemen Load. Pada Gambar II-7 terlihat bahwa keberlakuan tuple (Bob,Load) pada dimensi valid time bertambah satu chronon setiap current time maju satu chronon. Hal ini terus berlangsung sampai terjadi modifikasi pada transaction time 25, di mana keberlakuan tuple pada valid time hanya sampai valid time 25.

II-10

Gambar II-7 Representasi grafis tuple (Bob,Load)

2.2.3 BCDM pada TSQL2 Salah satu bahasa query standar untuk basis data temporal adalah TSQL2. Bahasa ini dirancang dengan memodifikasi (dan kadang mengganti) sebagian sintaks SQL92 dan menambahkan beberapa hal berkaitan dengan aspek waktu. Tipe data waktu baru yang diperkenalkan oleh TSQL2 adalah PERIOD, di samping tipe data waktu lain yang telah dispesifikasikan oleh SQL92 (DATE, TIME, TIMESTAMP, INTERVAL). TSQL2 mendukung enam jenis relasi, yaitu relasi Snapshot (non-temporal), relasi Transaction Time, relasi Valid State Time, relasi Valid Event Time, relasi Valid State and Transaction Time, dan relasi Valid Event and Transaction Time. Relasi bitemporal didukung oleh TSQL2 dengan adanya jenis relasi Valid State and Transaction Time, dan relasi Valid Event and Transaction Time karena keduanya mengandung penanganan valid time dan transaction time. Pada Valid State Time sebuah tuple bernilai benar dalam sebuah periode waktu tertentu, sedangkan pada Valid Event Time sebuah tuple bernilai benar dalam sebuah instan waktu.

2.3 Operasi Retrieval dan Fungsi Agregasi Operasi retrieval merupakan jenis operasi pengaksesan basis data yang tidak melakukan modifikasi terhadap basis data. Dalam operasi tersebut, terkadang diperlukan pengaksesan terhadap basis data untuk mendapatkan suatu nilai tertentu yang merupakan agregasi dari sebuah koleksi nilai. Pada jenis pengaksesan seperti inilah fungsi agregasi diperlukan. Operasi retrieval terhadap relasi temporal berbeda dengan relasi nontemporal karena adanya dimensi waktu yang harus diperhatikan. Oleh karena itu diperlukan penanganan khusus untuk operasi retrieval terhadap relasi temporal, khususnya yang mengandung fungsi agregasi di dalamnya.

2.3.1 Operasi Retrieval Operasi retrieval terhadap relasi temporal berbeda dengan operasi terhadap relasi non-temporal. Perbedaannya terletak pada adanya kondisi waktu terkait dengan dimensi waktu pada operasi retrieval terhadap relasi temporal. Operasi retrieval terhadap relasi temporal yang mendukung hanya satu dimensi waktu (yaitu relasi selain relasi bitemporal) jika dilihat dari state relasi yang

II-11

diakses dapat dibagi menjadi empat jenis, yaitu snapshot query, time-travel query, sequenced query, dan non-sequenced query [WID03]. 2.3.1.1 Snapshot query Snapshot query adalah salah satu jenis query terhadap relasi temporal yang tidak memperhatikan dimensi valid time maupun transaction time. Hasil dari query jenis ini adalah relasi snapshot. Snapshot query terhadap relasi bitemporal akan mengembalikan relasi yang bernilai current baik pada dimensi valid time maupun transaction time. Gambar II-8 menunjukkan posisi dari hasil snapshot query terhadap basis data temporal. Masing-masing persegi panjang merepresentasikan sebuah state basis data relatif terhadap waktu. Pada gambar terlihat bahwa snapshot query hanya melakukan retrieve terhadap basis data pada current state. Contoh dari snapshot query retrieval dengan fungsi agregasi terhadap relasi bitemporal adalah “Berapakah jumlah pegawai pada saat ini?”.

Gambar II-8 Snapshot query

2.3.1.2 Time-travel query Time-travel query adalah suatu jenis query terhadap relasi temporal pada suatu state basis data tertentu. Gambar II-9 menunjukkan posisi dari hasil time-travel query terhadap basis data temporal. Pada gambar terlihat bahwa query jenis ini melakukan retrieve terhadap basis data pada salah satu state saja. Untuk relasi valid-time, state yang dapat diakses tidak terbatas hanya pada waktu di masa lampau, dapat juga waktu di masa depan, sedangkan untuk relasi transaction-time hanya memungkinkan untuk me-retrieve state masa lampau. Contoh dari time-travel query retrieval dengan fungsi agregasi terhadap relasi bitemporal adalah “Berapakah jumlah pegawai tahun lalu?” untuk relasi valid-time atau “Berapakah jumlah pegawai yang terdata pada bulan lalu sebelum dilakukan koreksi terhadap basis data?” untuk relasi transaction-time.

Gambar II-9 Time-travel query

II-12

2.3.1.3 Sequenced query Sequenced query adalah salah satu jenis dari query terhadap relasi temporal yang hasilnya membutuhkan beberapa state dari basis data secara sekuensial. Hasil dari query ini dapat berupa relasi valid-time, relasi transaction-time, atau relasi bitemporal tergantung dari query. Gambar II-10 menunjukkan posisi dari hasil sequenced query q’ terhadap basis data temporal. Pada gambar terlihat bahwa q’ dipecah menjadi beberapa query yang masing-masing melakukan retrieve terhadap basis data pada satu state, menghasilkan suatu relasi yang juga terdiri dari beberapa state waktu sesuai dengan sumbernya. Contoh dari sequenced query retrieval dengan fungsi agregasi terhadap relasi bitemporal adalah “Perlihatkan sejarah fluktuasi jumlah pegawai”.

Gambar II-10 Sequenced query

2.3.1.4 Non-sequenced query Berbeda dengan sequenced query, di mana informasi dalam sebuah state pada hasil query diperoleh hanya dari state dengan waktu yang sama pada relasi sumber, pada non-sequenced query informasi dalam sebuah state pada relasi hasil dapat diperoleh dari state dengan waktu yang berbeda pada relasi sumber. Gambar II-11 menunjukkan posisi dari hasil non-sequenced query terhadap basis data temporal. Pada gambar terlihat bahwa hasil query pada sebuah state mengambil informasi tidak hanya dari relasi sumber dengan state yang sama dengannya, namun juga dari state yang berbeda. Contoh dari non-sequenced query retrieval dengan fungsi agregasi terhadap relasi bitemporal adalah “Berapakah jumlah pegawai yang pernah dipekerjakan oleh perusahaan?”.

Gambar II-11 Non-sequenced query

II-13

2.3.2 Fungsi Agregasi pada Operasi Retrieval SQL, sebagai bahasa query standar dalam model data relasional mendukung fungsi agregasi dasar seperti COUNT, SUM, AVG, MIN, dan MAX. Pada SQL92, posisi operator fungsi agregasi pada operasi retrieval dapat dilihat pada sintaks yang ditunjukkan pada Query II-1. ::= SELECT [<set_quantifier>] <select_list> ::= [<where_clause>] [] [] <select_list> ::= * | <select_sublist> [{,<select_sublist>}...] <select_sublist> ::= <derived_column> | .* <derived_column> ::= [] ::= | <string_value_expression> | | | | | <set_function_specification> | <scalar_subquery> | | () | <set_function_specification> ::= COUNT (*) | ::= <set_function_type> ([<set_quantifier>] ) <set_function_type> ::= AVG | MAX | MIN | SUM | COUNT <set_quantifier> ::= DISTINCT | ALL Query II-1 Sintaks query retrieval pada SQL92

Fungsi agregasi dapat dikelompokkan menjadi dua kategori, yaitu agregasi komputasional dan agregasi selektif. Nilai dari agregasi komputasional didapatkan dengan mengakumulasi nilai tertentu dari tuple yang tersimpan dalam sebuah relasi. Sedangkan nilai dari agregasi selektif didapatkan dengan cara memilih sebuah nilai representatif di antara nilai-nilai yang ada pada sejumlah tuple yang tersimpan dalam relasi. COUNT, SUM, dan AVG termasuk ke dalam kategori komputasional agregasi, sedangkan MIN dan MAX termasuk ke dalam kategori agregasi selektif. Untuk beberapa DBMS relasional, fungsi agregasi yang dapat ditangani tidak hanya terbatas pada fungsi agregasi dasar yang didukung oleh SQL. DBMS tersebut mendefinisikan beberapa fungsi agregasi sendiri yang sebagian besar berguna dalam perhitungan statistik.

II-14

2.3.3 Fungsi Agregasi Spesifik Basis Data Temporal Fungsi agregasi yang didukung oleh TSQL2 sama dengan yang didukung oleh SQL92. Perbedaannya hanyalah pada sintaks query retrieval yang memuat operator fungsi agregasi karena pada TSQL2 sintaks query mengalami modifikasi dan penambahan dari SQL92. Perbedaan ini diperlihatkan pada Query II-2. ::= SELECT [<set_quantifier>] [SNAPSHOT] <select_list> ::= <set_function_type> ( [<set_quantifier>] [WEIGHTED] ) <set_function_type> ::= RISING Query II-2 Tambahan sintaks query retrieval pada TSQL2

RISING adalah suatu fungsi agregasi yang mengembalikan durasi waktu maksimal dari atribut masukannya di mana nilai dari atribut tersebut bertambah secara monoton. Tipe data hasil yang dikembalikan oleh fungsi ini berupa period waktu. Name Richard Kate Jake Jake

Salary 40 45 35 37

start 18 8 7 14

end ∞ 20 13 21

Gambar II-12 Relasi valid-time Salary

Untuk memperjelas bagaimana penerapan fungsi RISING, Query II-3 berikut merupakan contoh query yang mengandung fugnsi RISING terhadap relasi Salary (relasi valid time dengan interval close-ended) pada Gambar II-12. SELECT Name, RISING(Salary) FROM Salary S GROUP BY Name Query II-3 Contoh query dengan fungsi RISING

Query II-3 dapat diartikan dengan “Perlihatkan durasi waktu di mana salary pegawai tidak pernah turun (tetap atau naik) untuk masing-masing pegawai”. Hasil dari query ini diperlihatkan pada Gambar II-13. Name Richard Kate Jake

RISING(Salary) [18,∞] [8,20] [7,21]

Gambar II-13 Hasil Query II-3

Tuple pertama (Richard,[18,∞]) pada relasi hasil ini memiliki arti bahwa salary pegawai bernama Richard pada durasi waktu [18,∞] tidak pernah turun karena memang hanya ada sebuah tuple dengan nama pegawai Richard pada relasi sumber. Begitu juga dengan tuple kedua (Kate, [8,20]).

II-15

Berbeda halnya dengan tuple ketiga (Jake,[7,21]) di mana durasi [7,21] merupakan penggabungan dari [7,12] dan [13,21] karena dari durasi tuple [7,12] ke tuple selanjutnya yaitu [13,21] salary Jake naik dari 35 menjadi 37. Kembali kepada sintaks query retrieval seperti yang ditunjukkan pada Query II-2, jika keyword SNAPSHOT ditambahkan pada query, maka relasi hasilnya adalah sebuah relasi snapshot. Jika WEIGHTED ditambahkan pada fungsi agregasi, berlaku aturan tambahan sesuai dengan rumus yang diperlihatkan pada Gambar II-14. y y y y y y

MAX MIN SUM

: (nilai atribut * jumlah chronon) maksimal : (nilai atribut * jumlah chronon) minimal : ∑ (nilai atribut * jumlah chronon) ∑ (jumlah chronon) . AVG : SUM (kardinalitas atribut) COUNT : tidak berpengaruh RISING : period di mana (nilai atribut * jumlah chronon) monoton naik Gambar II-14 Rumus aturan WEIGHTED

Misalkan A adalah atribut yang ingin diagregasi dan T adalah kumpulan tuple yang memenuhi kondisi pada table expression, maka: 1. Untuk MAX, hasilnya adalah nilai atribut A pada T, di mana hasil kali atribut A tersebut dengan jumlah chronon pada timestamp-nya adalah maksimal. 2. Untuk MIN, hasilnya adalah nilai atribut A pada T, di mana hasil kali atribut A tersebut dengan jumlah chronon pada timestamp-nya adalah minimal. 3. Untuk SUM, hasilnya adalah total (sum) dari hasil kali seluruh atribut A pada T dengan jumlah chronon pada timestamp-nya masing-masing, kemudian dibagi dengan jumlah seluruh timestamp tuple. 4.

Untuk AVG, hasilnya adalah fungsi SUM (pada point nomor 3) untuk T kemudian dibagi dengan kardinalitas T.

5.

Untuk COUNT, penambahan WEIGHTED tidak berpengaruh.

6.

Untuk RISING, hasilnya adalah period di mana hasil kali dari atribut A pada T dengan jumlah chronon pada timestamp-nya bertambah secara monoton.

Untuk memperjelas penggunaan keyword WEIGHTED, Query II-4 berikut merupakan contoh query yang menggunakan keyword WEIGHTED terhadap relasi Salary (relasi valid time dengan interval close-ended) pada Gambar II-12. SELECT SUM (WEIGHTED Salary) FROM Salary S Query II-4 Contoh query dengan WEIGHTED

Relasi hasil dari Query II-4 diperlihatkan pada Gambar II-15. Hal pertama yang harus dilakukan sebelum menghitung nilai agregasi dari query tersebut adalah mengelompokkan tuple yang

II-16

memiliki keberlakuan waktu yang sama. Algoritma pengelompokkan tuple ini belum akan dibahas di sini, namun akan dibahas pada dua sub-bab selanjutnya karena contoh ini hanya untuk memperlihatkan bagaimana efek keyword WEIGHTED terhadap query. Sum 35 41.5 41.95 ∞

Start 7 8 14 18

End 7 13 17 ∞

Gambar II-15 Relasi hasil Query II-4

Pada interval [7,7] hanya tuple (Jake,35) yang berlaku, sehingga nilai sum pada timestamp tersebut adalah 35, yaitu hasil dari (35*7)/7 dengan 7 merupakan weight dari timestamp (Jake,35) yaitu [7,13]. Selanjutnya pada interval [8,13] ada dua tuple yang berlaku yaitu (Kate,45) dan (Jake,35) sehingga nilai sum pada timestamp tersebut adalah 41.5, yaitu hasil dari [(45*13)+(35*7)] / (13+7) dengan 7 merupakan weight dari timestamp (Jake,35) yaitu [7,13] dan 13 merupakan weight dari timestamp (Kate,45) yaitu [8,20]. Begitu selanjutnya sampai pada timestamp [18, ∞] yang menghasilkan nilai sum ∞ karena weight dari (Richard,40) adalah ∞.

2.4 Pemrosesan Agregasi pada Basis Data Temporal Dengan adanya aspek temporal, pemrosesan fungsi agregasi pada basis data temporal akan menjadi lebih kompleks karena harus memperhatikan dimensi waktu dari data yang disimpan. Biasanya pemrosesan fungsi agregasi terhadap data temporal memerlukan proses tambahan pada saat mempartisi relasi masukan menjadi kelompok tuple, yaitu mengelompokkan data yang memiliki waktu keberlakuan yang sama. Sebenarnya saat ini sudah banyak metode yang telah dikembangkan untuk memproses fungsi agregasi pada basis data temporal. Namun kesemuanya itu hanya membahas pemrosesan fungsi agregasi khusus untuk relasi valid-time, dan belum ada yang mengembangkan metode untuk relasi bitemporal. Salah satu metode tersebut adalah algoritma dengan aggregation tree. Kekurangan dari aggregation tree adalah dalam hal penanganan GROUP BY. Oleh karena itu, selain aggregation tree, pada bab ini juga akan dibahas algoritma lain yaitu PA-Tree yang nantinya dijadikan bahan referensi untuk modifikasi aggreation tree.

2.4.1 Algoritma dengan Aggregation Tree [KLI95] Algoritma ini terdiri dari dua langkah, yaitu membangun aggregation tree (pohon agregasi), dan melakukan operasi depth first search untuk memproses nilai hasil agregasi pada setiap simpul daunnya (leaf). Masing-masing simpul (node) pada pohon menyimpan informasi nilai state agregasi, waktu awal (start) dan akhir (end). Waktu awal dan waktu akhir pada simpul daun membangun sebuah interval konstan pada hasil query. Masing-masing simpul daun juga mengandung hasil agregasi parsial untuk interval konstan

II-17

yang dimilikinya. Untuk lebih jelasnya, berikut ini akan dijabarkan langkah-langkah pembangunan aggregation tree dari contoh relasi valid-time pada Gambar II-12 untuk memproses query TSQL2 pada Query II-5. SELECT COUNT(Name) FROM Salary Query II-5 Contoh query TSQL2 dengan fungsi COUNT

Pembangunan aggregation tree dimulai dengan sebuah simpul yang memiliki waktu awal 0 dan waktu akhir ∞, serta memiliki nilai COUNT 0 (Gambar II-16.a). Untuk masing-masing tuple, cari simpul-simpul dengan interval konstan yang meliputi kedua timestamp (waktu awal dan waktu akhir) tuple. Setelah ditemukan, jika timestamp terletak di antara interval konstan, maka interval itu dipecah (split) menjadi dua.

Gambar II-16 Pembangunan aggregation tree

Gambar II-16.b memperlihatkan efek yang terjadi pada pohon ketika ditambahkan interval tuple [18,∞]. Langkah pertama adalah mencari simpul pada pohon awal (Gambar II-16.a) dengan interval konstan yang mengandung 18 di dalamnya. Pada simpul tersebut terlihat bahwa waktu akhir timestamp tuple (∞) sama dengan waktu akhir interval konstan simpul. Oleh karena itu, interval konstan simpul dipecah menjadi dua menjadi [0,17] dan [18,∞]. Karena interval konstan simpul sudah mencakup waktu akhir timestamp tuple, maka tidak perlu lagi mencari simpul yang mengandung timestamp akhir. Proses pembangunaan pohon dilanjutkan dengan memasukkan tuple kedua dengan interval timestamp [8,20]. Simpul untuk waktu awal 8 dicari pada pohon current (Gambar II-16.b). Simpul [0,17] dibagi menjadi [0,7] dan [8,17]. Namun karena waktu akhir timestamp tuple masih belum tercakup pada interval konstan simpul, maka pencarian terus dilakukan untuk mencari simpul yang

II-18

mengandung timestamp akhir 20. Kemudian simpul [18, ∞] dibagi menjadi [18,20] dan [21, ∞]. Hasil penambahan ini ditunjukkan pada Gambar II-16.c. Perhatikan bahwa penyesuaian (adjustment) nilai agregasi pada simpul hanya dilakukan jika seluruh interval konstannya overlap dengan timestamp tuple current. Simpul [8,17] menyimpan nilai COUNT 1 karena merupakan bagian dari [0,17] yang overlap dengan timestamp tuple current. Sedangkan simpul anak dari [0,17] lainnya, [0,7] tidak overlap dengan tuple current sehingga diinisialisasi dengan nilai COUNT 0. Simpul [0,17] sendiri tetap memiliki nilai COUNT 0 karena interval konstannya tidak seluruhnya overlap dengan timestamp tuple current. Salah satu kelebihan dari algoritma ini adalah pencarian tidak perlu harus sampai simpul daun, karena jika seluruh interval konstan timestamp tuple sudah ditemukan maka pencarian tidak perlu dilanjutkan, tinggal menyesuaikan nilai agregasi pada simpul tersebut. Misalkan terdapat sebuah tuple yang memiliki timestamp yang tepat sama dengan sebuah interval konstan pada simpul nonleaf (bukan daun), maka pencarian tidak dilanjutkan karena hanya perlu menyesuaikan nilai agregasi pada simpul tersebut saja. Pembangunan pohon dilanjutkan dengan tuple ketiga dan keempat sehingga menghasilkan sebuah aggregation tree yang ditunjukkan pada Gambar II-16.d. Setelah proses pembangunan pohon selesai, langkah selanjutnya adalah melakukan operasi depth first search yang menyimpan (keep track) penambahan nilai agregasi COUNT secara rekursif dari akar pohon. Setiap mencapai simpul daun, nilai agregasi disimpan sesuai dengan interval konstan yang dimiliki simpul tersebut. Sebagai contoh, ketika mencapai simpul daun [8,13] (pada Gambar II-16.d), maka nilai COUNT dihitung dari akar sampai simpul tersebut yang akan menghasilkan nilai 2 (dari 0+0+1+1). Hasil dari algoritma ini akan terurut berdasarkan waktu, seperti dapat dilihat pada Gambar II-17 yang merupakan relasi hasil Query II-5. Count 0 1 2 2 3 2 1

Start 0 7 8 14 18 21 22

End 6 7 13 17 20 21 ∞

Gambar II-17 Relasi hasil Query II-5

Karena tuple pada relasi Salary tidak terurut berdasarkan waktu, maka sebuah tuple dapat ditambahkan pada bagian manapun dari pohon. Namun berbeda halnya jika tuple pada relasi sumber terurut berdasarkan waktu. Penambahan tuple hanya akan terjadi pada satu bagian pohon sehingga akan menghasilkan pohon yang tidak seimbang (imbalanced tree). Oleh karena itu, kekurangan dari algoritma ini adalah kompleksitas pembangunan pohon O(n2) pada kasus terburuk karena pohon akan berupa list linier. Untuk operator fungsi agregasi lain, nilai agregasi yang

II-19

disimpan dalam simpul harus disesuaikan. Misalkan untuk operator SUM, yang disimpan adalah nilai atribut yang ingin dijumlahkan, sedangkan untuk MAX yang disimpan adalah nilai maksimum atribut tertentu.

2.4.2 Algoritma dengan PA-Tree [KIM99] Berbeda dengan aggregation tree, struktur PA-Tree tidak menyimpan semua interval waktu yang telah dipartisi dari sebuah tuple tetapi hanya menyimpan informasi waktu awal dan waktu akhirnya saja. Ada dua macam simpul yang terdapat pada PA-Tree, simpul pohon dan simpul untuk linkedlist tambahan. Simpul pohon (dinotasikan dengan T-node), berisi sebuah timestamp (dapat berupa “waktu awal” maupun “waktu akhir” untuk open-ended dan “waktu akhir + 1” untuk close-ended) yang berperan sebagai key, sebuah nilai state agregasi (dinotasikan dengan C-value), dan juga sebuah pointer menuju linked-list (dinotasikan dengan S-list) untuk pemrosesan agregasi selektif. Struktur dari T-node dapat dilihat pada Gambar II-18.

Gambar II-18 Struktur T-node dari PA-Tree

Perhatikan bahwa “key” merupakan sebuah timestamp, sedangkan “C-value” merupakan besarnya perubahan nilai agregasi komputasional pada timestamp “key”. Nilai agregasi pada “key” merupakan nilai agregasi pada timestamp yang lebih kecil darinya (dapat dari simpul parent-nya atau simpul left child-nya) yang mengalami perubahan sebesar C-value, dan berlaku sampai timestamp berikutnya (dapat dari simpul parent-nya atau simpul right child-nya) ketika nilai agregasi akan kembali berubah. Gambar II-19 mengilustrasikan pembangunan PA-Tree untuk relasi Salary pada Gambar II-12. SList dari pohon ini belum dibangun karena hanya akan digunakan untuk pemrosesan agregasi selektif. Dua buah T-node yang memiliki “waktu awal” dan “waktu akhir + 1” sebagai key ditambahkan ke dalam pohon untuk setiap interval sebuah tuple pada relasi. C-value dari simpul diisi dengan besarnya perubahan nilai agregasi pada saat nilai key untuk masing-masing simpul. Oleh karena itu, untuk simpul dengan key yang merupakan “waktu awal” dari sebuah tuple bernilai positif sedangkan yang “waktu akhir” bernilai negatif. Pada proses penambahan simpul, pohon diseimbangkan menggunakan teknik seperti pada AVL-Tree [KIM99]. Penjelasan lebih lanjut dari AVL-Tree dapat dilihat pada Lampiran A.

II-20

Gambar II-19 Pembangunan PA-Tree untuk relasi Salary

Untuk agregasi selektif, diperlukan S-list dalam PA-Tree. Sebuah simpul list (dinotasikan dengan L-node) berisi panjang interval waktu dari sebuah tuple yang memiliki waktu awal sama dengan key pada T-node yang berkorespondensi dengannya, dan sebuah nilai untuk agregasi selektif (dinotasikan dengan S-node). Gambar II-20 memperlihatkan struktur sebuah simpul pada PA-Tree yang memiliki S-list untuk agregasi selektif.

Gambar II-20 Struktur PA-Tree untuk agregasi selektif

Pada agregasi selektif, dua buah T-node ditambahkan untuk setiap interval waktu tuple seperti pada penjelasan sebelumnya. Sebuah L-node untuk interval waktu tuple juga ditambahkan ke dalam S-list dari T-node yang memiliki waktu awal sebagai nilai key. Panjang interval (length) dan nilai agregasi yang berkorespondensi dengannya juga disimpan dalam L-node. Perhatikan bahwa S-list hanya dibangun untuk agregasi selektif. Gambar II-21 menunjukkan hasil akhir PA-Tree untuk agregasi selektif relasi Salary pada Gambar II-12. Jika sebuah L-node tidak memberikan pengaruh pada pemrosesan nilai agregasi selektif, maka dapat dieliminasi dari S-list untuk mengurangi waktu pemrosesan. Sebagai contoh, pada Gambar II-21, jika sebuah tuple dengan nilai ([18,∞], 45) ditambahkan setelah tuple ([18,∞], 40), maka L-node sebelumnya dapat dihapus untuk agregasi MAX.

II-21

Gambar II-21 PA-Tree agregasi selektif untuk relasi Salary

Penghitungan agregasi komputasional pada PA-Tree cukup sederhana. Setiap T-node dikunjungi sesuai dengan urutan waktu (nilai key), dan setiap C-value dari simpul yang dikunjungi merepresentasikan besarnya perubahan nilai agregasi pada saat tersebut. Misalkan Query II-6 berikut ini akan diproses menggunakan PA-Tree pada Gambar II-19. SELECT SUM(Salary) FROM Salary S Query II-6 Contoh query TSQL2 dengan fungsi SUM

Urutan T-node yang dikunjungi adalah <7,35>, <8,45>, <13,-35>, <14,37>, dan seterusnya. Dengan begitu, hasil dari agregasi SUM adalah sebagai berikut: 35 pada waktu 7, 35+45 = 80 dari waktu 8 sampai 13, 80+2 = 82 pada waktu 14, dan seterusnya. Gambar II-22 menampilkan relasi hasil Query II-6. Sum 35 80 82 122 77 40

Start 7 8 14 18 21 22

end 7 13 17 20 21 ∞

Gambar II-22 Relasi hasil Query II-6

Sedangkan untuk agregasi selektif, pemrosesannya cukup kompleks menggunakan S-list. Pemrosesan agregasi selektif dengan S-list dapat diasosiasikan dengan skyline problem. Pada skyline problem, dicari nilai maksimum dari sejumlah interval waktu dengan nilai untuk masingmasing interval diketahui. Solusi dari skyline problem berupa pasangan terurut (int, max), di mana int merupakan sebuah interval dengan sebuah nilai maksimum konstan max. Solusi untuk skyline problem ini identik dengan solusi untuk agregasi selektif dengan operator MAX. Sedangkan untuk operator MIN solusinya sama saja, namun dengan mengganti tanda (+/-) dari nilai agregasi. Dengan demikian, teknik penyelesaian skyline problem dapat langsung diterapkan untuk agregasi selektif MAX dan MIN pada PA-Tree.

II-22

Gambar II-23 Contoh skyline problem dan solusinya

Gambar II-23 mengilustrasikan contoh dari skyline problem dan solusinya. Pada PA-Tree, sketsa bangunan dibentuk menggunakan informasi yang tersimpan pada S-list pada T-node, yaitu panjang interval dan nilai agregasi. Penjelasan lebih lanjut mengenai skyline problem dijelaskan pada Lampiran B. Untuk menerapkan teknik penyelesaian skyline problem dalam pemrosesan agregasi selektif, khususnya MAX, garis mendatar pada representasi grafis skyline problem (Gambar II-23) dapat diasosiasikan dengan garis waktu yang terdiri dari chronon-chronon sedangkan building (persegi panjang) pada gambar tersebut

diasosiasikan dengan sebuah tuple. Tinggi building

merepresentasikan besarnya nilai atribut (yang ingin dicari nilai agregasi selektifnya) dari tuple yang berasosiasi dengannya, sedangkan lebar dari building merepresentasikan timestamp dari tuple tersebut yang berupa interval. Untuk fungsi MIN, teknik penyelesaiannya perlu dimodifikasi lebih lanjut, seperti dengan mengganti tanda positif (+) dengan negatif (-).