Reduksi semi join

Abstract

Pada era informasi sekarang ini, sangat diperlukan informasi yang dapat secara cepat, akurat, mudah dan memungkinkan diakses banyak user, dan juga dapat menyimpan data secara aman. Struktur pada basis data memungkinkan untuk menyediakan fasilitas seperti yang disebutkan di atas. Sehingga jika ingin meningkatkan kinerja suatu perusahaan perlu untuk memanfaatkan teknologi basis data. Basis data merupakan fenomena nyata yang dimodelkan; terdiri dari koleksi data dimana terdapat saling hubungan di antara data tersebut. Pada basis data menyebar data disimpan dalam beberapa site, sehingga jika diperlukan informasi atau data dari site lain, maka perlu mengakses ke site tersebut. Akibatnya, pada basis data menyebar terdapat biaya komunikasi antar site, oleh karena itu diperlukan cara untuk meminimalkan biaya komunikasi tersebut. Salah satu cara yang dapat dilakukan untuk meminimalkan biaya komunikasi antar site adalah mengefisienkan query. Query adalah bahasa yang digunakan untuk mengekspresikan keinginan user dalam mengakses informasi atau data dari sistem basis data [Ozsu & Valduriez 1991]. Diasumsikan model data yang digunakan adalah model relasional, pada model ini query diekspresikan dalam operator- operator. Hal yang dapat dilakukan untuk mengefisienkan query adalah menyusun urutan dari operator- operator, kemudian mentransformasi operator join menjadi operator semi join [Ceri & Pelagatti 1985]. Dengan melakukan dua cara di atas, maka diharapkan dapat mengurangi total biaya yang digunakan untuk menyelesaikan query tersebut, sehingga secara keseluruhan diharapkan menjadikan sistem basis data lebih efisien. Tulisan ini menjelaskan transformasi operator join menjadi operator semi join, dan reduksi semi join dalam mengevaluasi suatu query. Reduksi artinya adalah memilih relasi untuk menjawab query, sehingga relasi dan tuple dari relasi yang dilibatkan menjadi minimal. Gugus relasi yang paling minimal dinamakan reduksi penuh, dinotasikan R. R mudah didapatkan pada query dengan graf berbentuk free, namun R sulit diperoleh pada query dengan graf berbentuk cyclic.