Pohon Alfabet Optimal (Analisis Algoritma)

Permasalahan Pohon Alfabet Optimal

Permasalahan pohon alfabet kelihatan sangat serupa dengan permasalahan Huffman, kecuali bahwa daun-daun dari pohon alfabet (dibaca dari kiri ke kanan) harus di dalam urutan masukan yang asli. Dengan cara yang sama seperti di pengkodean Huffman, pohon biner harus penuh, yaitu masing-masing simpul internal harus mempunyai persisnya dua anak/cabang.
Kesulitan utama adalah kita tidak bisa melokalisir dengan mudah dua item untuk dikombinasikan.

Asumsikan kita mempunyai suatu urutan dari bobot suatu item n, dimana wi adalah bobot yang tidak negatif dari item ith. Dapat kita tulis α = w1…wn. Urutan itu akan berubah selama algoritma ini.

Pohon alfabet diatas, α adalah satu pohon biner T dengan n daun-daun yang diurutkan, dimana daun ith (urutan dari kiri ke kanan) bersesuaian dengan item ith dari pohon alfabet optimal (OAT/Optimal Alphabetic Tree Problem) adalah untuk menemukan satu pohon alfabet dari biaya yang minimum.

Algoritma Garsia-Wachs memecahkan masalah pohon alfabet, algoritma ini merupakan suatu versi dari algoritma yang sebelumnya oleh Hu dan Tucker, lihat pada referensi [18]. Bagian utama dari algoritma ini adalah permutasi atau mengubah susunan α, meskipun demikian pohon yang akhir perlu mempunyai urutan dari daun-daun sama halnya dengan urutan item di dalam urutan yang asli. Kita mengadopsi aturan bahwa item dari α memiliki nama-nama yang unik, dan bahwa nama-nama ini tetap dipakai meskipun item dipindahkan. Ketika memakainya, kita akan berasumsi bahwa nama-nama itu adalah posisi-posisi item didalam daftar, yakni bilangan bulat di dalam [1…n].


Biaya Komputasi/Perhitungan Pohon Alfabet Optimal

Pertama-tama kita menunjukkan bagaimana untuk menghitung hanya biaya keseluruhan pohon, bagaimanapun perhitungan ini tidak memberi secara otomatis satu pohon alfabet optimal, karena kita akan mengubah susunan dari item. Setiap kali kita kombinasikan dua item yang bersebelahan didalam permutasi yang ada, bagaimanapun item ini tidak perlu berdampingan didalam urutan yang asli, jadi di dalam setiap aturan pohon alfabet anak/cabang tidak bisa dari bapak/sumber yang sama.

Pohon alfabet dibangun dengan mengurangi urutan awal dari item ke suatu urutan yang lebih pendek, ini cara yang serupa dengan algoritma Huffman, dengan satu perbedaannya yang penting. Dalam algoritma Huffman, pasangan item yang minimum dikombinasikan, karena itu dapat ditunjukkan bahwa item-item itu adalah saudara kandung dalam pohon optimal. Jika kita bisa mengidentifikasi dua item yang bersebelahan adalah saudara kandung di dalam suatu pohon alfabet optimal, kita bisa kombinasikan mereka dan diproses secara berulang. Sayangnya, tidak ada cara yang dikenal untuk mengidentifikasi pasangan seperti itu. Bahkan suatu pasangan yang minimal mungkin tidak akan saudara kandung. Pertimbangkan urutan bobot (8 7 7 8). Item yang kedua dan yang ketiga bukanlah saudara kandung di dalam pohon alfabet optimal.

Sebagai gantinya, algoritma-algoritma HT dan GW, seperti juga algoritma-algoritma dari [20, 22, 23, 46], dioperasikan dengan mengidentifikasi pasangan suatu item yang mempunyai tingkatan yang sama dalam pohon optimal. Item ini kemudian dikombinasikan ke dalam suatu “paket,” dengan mengurangi banyaknya item dengan satu. Detail bagaimana hasil proses ini berbeda dalam algoritma-algoritma lain. Didefinisikan, untuk 1 ≤ i
TwoSum(i) = wi + wi+1

Sepasang item yang bersebelahan (i, i + 1) adalah suatu pasangan minimal lokal (locally minimal pair atau disingkat lmp) jika:

TwoSum(i - 1) ≥ TwoSum(i) jika i > 1
TwoSum(i) < TwoSum(i + 1) jika i ≤ n-2

Suatu pasangan minimal yang sekarang ini diproses disebut pasangan yang aktif.

Operator Move (Perpindahan). Jika w adalah setiap item didalam daftar π item yang dihargai, didefinisikan dengan RightPos(w) sebagai predecessor yang posisinya dekat dengan nilai sebelah kanan yang lebih besar atau sama dengan w. Didefinisikan RightPos(w) menjadi |π| + 1.
Move (w, π) menjadi suatu operator untuk merubah π oleh pergerakan w. w disisipkan antara posisi-posisi RightPos(w)-1 dan RightPos(w). Sebagai contoh:

Move(7, (2, 5, 7, 2, 4, 9, 3, 4) = (2, 5, 2, 4, 7, 9, 3, 4)

Ketepatan dari algoritma itu adalah suatu persoalan yang sulit. Ada dua pembuktian yang disederhanakan, lihat pada referensi [19, 30] dan kita mengacu pada dokumen tersebut untuk bukti yang terperinci. Di dalam referensi [19] hanya pasangan minimal rightmost/terbesar sebelah kanan dapat diproses setiap kali, sedangkan referensi [30] memberi ketepatan dari algoritma umum ketika setiap pasangan minimal diproses, ini adalah suatu yang penting didalam komputasi/perhitungan paralel, yaitu ketika kita memproses secara serentak banyak pasangan seperti itu. pembuktian dalam referensi [30] menunjukkan bahwa ketepatan adalah segmen-segmen dasar yang dengan baik dibentuk dari pohon-pohon alfabet optimal, ini dinyatakan sebagai suatu teorema struktural dalam referensi [30] yang memberi lebih banyak pengertian yang mendalam ke dalam struktur yang global dari pohon-pohon alfabet optimal.

Untuk j > i+1 ditunjukkan oleh π i,j urutan π dimana unsur-unsur i, i +1 dipindahkan tepat sebelum yang ditinggalkan j.

TEOREMA 1. [Ketepatan dari algoritma GW]
Dimungkinkan (i, i + 1) adalah suatu pasangan minimal dan RightPos(i, i + 1) = j, dan memungkinkan T' adalah suatu pohon dengan urutan π i,j, optimal antar semua pohon dengan π i,j dimana i, i+1 adalah saudara kandung. Kemudian adalah satu pohon alfabet optimal T diatas urutan yang asli π = (1,…n) seperti T≅T'.

Ketepatan dapat juga dinyatakan sebagai kesamaan antara beberapa kelas dari pohon-pohon.
Dua pohon biner T1 dan T2 disebut tingkatan yang sama (ditulis T_1≅T_2) jika T1, dan T2 mempunyai set yang sama dari daun-daun (mungkin di suatu urutan yang berbeda) dan levelT1 =levelT2 (Tingkatan T1 = Tingkatan T2).

Ditunjukkan oleh OPT(i) set dari semua pohon alfabet di atas, urutan daun (1,…n) yang bersifat optimal antar pohon-pohon dimana i dan i+1 adalah tingkatan yang sama. Asumsikan pasangan (i, i+1) adalah minimal lokal. Dimungkinkan OPTmoved(i) adalah set dari semua pohon alfabet diatas, urutan daun π i,j yang bersifat optimal antar semua pohon dimana daun-daun i dan i+1 adalah tingkatan yang sama, dimana j = RightPos(i, i +1).

TEOREMA 2.
Misalkan (i, i + 1) adalah suatu pasangan minimal lokal. Maka :
(1) OPT(i) = OPTmoved(i) .
(2) OPT(i) berisi satu pohon alfabet optimal T.
(3) OPTmoved(i) berisi suatu pohon T' dengan i, i +1 sebagai saudara kandung.


Konstruksi dari Pohon Alfabet Optimal

Algoritma Garsia-Wachs yang penuh pertama menghitung tingkatan. Pohon ini dapat dengan mudah dibangun didalam fungsi GW(π) ketika menghitung biaya pohon alfabet. Setiap kali kita menjumlahkan bobot dari dua item (diciptakan baru atau asli) lalu kita membuat item baru yang bapak/sumber mereka merupakan jumlahan dari bobot dari anak/cabang.

Begitu kita mempunyai suatu tingkatan pohon, pohon alfabet optimal dapat dibangun dengan mudah di dalam waktu yang linier. Gambar 14.6, Gambar 14.7, dan Gambar 14.8 menunjukkan proses konstruksi tingkatan pohon dan konstruksi satu pohon alfabet optimal yang diketahui tingkatan item aslinya.

LEMA 1. Asumsikan kita mengetahui tingkat masing-masing daun dalam satu pohon alfabet optimal. Lalu pohon itu dapat dibangun di dalam waktu yang linier.

Pembuktian tingkatan-tingkatan “bentuk” dari pohon,
Asumsikan l1, l2, l3,…, ln adalah urutan dari tingkatan-tingkatan. Kita melihat/menscan urutan ini dari kiri ke kanan sampai kita menemukan dua tingkat pertama li, li+1 yang merupakan sama. Lalu kita mengetahui bahwa daun-daun i dan i+1 adalah para anak/cabang dari bapak/unsur yang sama, karenanya kita menghubungkan daun-daun ini untuk menciptakan bapak/unsur dan kita menghapus daun-daun ini, di dalam urutan tingkatan, pasangan li, li+1 digantikan oleh suatu tingkatan li - 1. Berikutnya kita memeriksa jika li-1 = li-1, jika tidak kita mencari di sebelah kanan. Kita menyimpan hasil scan/pengamatan tersebut dan menciptakan tingkatan-tingkatan yang baru dalam tumpukan/memori. Waktu total adalah linear.

TEOREMA 3. Pohon alfabet optimal dapat dibangun didalam waktu O(n log n).

Pembuktian kita menyimpan tingkat array/barisan item. Tingkat array/barisan adalah ukuran globalnya (2n -1).

Indeksnya adalah nama-nama dari simpul, yaitu, item n yang asli dan paket simpul-simpul (n - 1) yang diciptakan selama eksekusi algoritma. Algoritma bekerja dalam waktu kwadrat, jika diterapkan di suatu cara yang sederhana. Menggunakan deretan-deretan prioritas, itu bekerja dalam waktu O(n log n).
Mengikuti ketepatan dari Teorema 14.7. secara langsung.

DAFTAR PUSTAKA / REFERENSI

[1] Alok Aggarwal, Baruch Schieber, Takeshi Tokuyama: Finding a Minimum-Weight k-Link Path Graphs with the Concave Monge Property and Applications. Discrete & Computational Geometry 12: 263-280 (1994).

[2] Doris Altenkamp and Kurt Mehlhorn, “Codes: Unequal Probabilities, Unequal Letter Costs,” J. Assoc. Comput. Mach. 27 (3) (July 1980), 412–427.

[3] M. J. Atallah, S. R. Kosaraju, L. L. Larmore, G. L. Miller, and S-H. Teng. Constructing trees in parallel, Proc. 1st ACM Symposium on Parallel Algorithms and Architectures (1989), pp. 499–533.

[4] Julia Abrahams, “Code and Parse Trees for Lossless Source Encoding,” Sequences ’97, (1997).

[5] P. Berman, M. Karpinski, M. Nekrich, Approximating Huffman codes in parallel, Proc. 29th ICALP, LNCS vol. 2380, Springer, 2002, pp. 845-855.

[6] P. Bradford, M. Golin, L. Larmore, W. Rytter, Optimal Prefix-Free Codes for Unequal Letter Costs and Dynamic Programming with the Monge Property, Journal of Algorithms, Vol. 42, No. 2, February 2002, p. 277-303.

[7] A. Aggarwal, M. Klawe, S. Moran, P. Shor, and R. Wilber, Geometric applications of a matrix-searching algorithm, Algorithmica 2 (1987), pp. 195–208.

[8] Serap A. Savari, “Some Notes on Varn Coding,” IEEE Transactions on Information Theory, 40 (1) (Jan. 1994), 181–186.

[9] Siu-Ngan Choi and M. Golin, “Lopsided trees: Algorithms, Analyses and Applications,”Automata, Languages and Programming, Proceedings of the 23rd International Colloquium on Automata, Languages, and Programming (ICALP 96).

[10] N. Cot, “A linear-time ordering procedure with applications to variable length encoding,”Proc. 8th Annual Princeton Conference on Information Sciences and Systems, (1974), pp. 460–463.

[11] A. M. Garsia and M. L. Wachs, A New algorithm for minimal binary search trees, SIAM Journal of Computing 6 (1977), pp. 622–642.

[12] T. C. Hu. A new proof of the T-C algorithm, SIAM Journal of Applied Mathematics 25 (1973), pp. 83–94.

[13] E. N. Gilbert, “Coding with Digits of Unequal Costs,” IEEE Trans. Inform. Theory, 41 (1995).

[14] A. Gibbons, W.Rytter, Efficient parallel algorithms, Cambridge Univ. Press 1997.

[15] M. Golin and G. Rote, “A Dynamic Programming Algorithm for Constructing Optimal Prefix-Free Codes for Unequal Letter Costs,”Proceedings of the 22nd International Colloquium on Automata Languages and Programming (ICALP ’95), (July 1995) 256-267.

[16] D. S. Hirschberg and L. L. Larmore, The Least weight subsequence problem, Proc. 26th IEEE Symp. on Foundations of Computer Science Portland Oregon (Oct. 1985), pp. 137–143. Reprinted in SIAM Journal on Computing 16 (1987), pp. 628–638.

[17] D. A. Huffman. A Method for the constructing of minimum redundancy codes, Proc. IRE 40 (1952), pp. 1098–1101.

[18] T. C. Hu and A. C. Tucker, Optimal computer search trees and variable length alphabetic codes, SIAM Journal of Applied Mathematics 21 (1971), pp. 514–532.

[19] J. H. Kingston, A new proof of the Garsia-Wachs algorithm, Journal of Algorithms 9 (1988) pp. 129–136.

[20] M. M. Klawe and B. Mumey, Upper and Lower Bounds on Constructing Alphabetic Binary Trees, Proceedings of the 4 th ACM-SIAM Symposium on Discrete Algorithms (1993), pp. 185–193.

[21] L. L. Larmore and D. S. Hirschberg, A fast algorithm for optimal length–limited Huffman codes, Journal of the ACM 37 (1990), pp. 464–473.

[22] L. L. Larmore and T. M. Przytycka, The optimal alphabetic tree problem revisited, Proceedings of the 21 st International Colloquium, ICALP’94, Jerusalem, LNCS 820, Springer-Verlag, (1994), pp. 251–262.

[23] L. L. Larmore, T. M. Przytycka, and W. Rytter, Parallel construction of optimal alphabetic trees, Proceedings of the 5 th ACM Symposium on Parallel Algorithms and Architectures (1993), pp. 214–223.

[24] M. Golin and G. Rote, “A Dynamic Programming Algorithm for Constructing Optimal Prefix-Free Codes for Uneq ual Letter Costs,” Proceedings of the 22nd International Colloquium on Automata Languages and Progr amming (ICALP ’95),(July 1995) 256-267. Expanded version to appear in IEEE Trans. Inform. Theory.

[25] R. G¨uttler, K. Mehlhorn and W. Schneider. Binary search trees: average and worst case behavior, Electron. Informationsverarb Kybernet, 16 (1980) pp. 41–61.

[26] Sanjiv Kapoor and Edward Reingold, “Optimum Lopsided Binary Trees,” Journal of the Association for Computing Machinery 36 (3) (July 1989), 573–590.

[27] R. M. Karp, “Minimum-Redundancy Coding for the Discrete Noiseless Channel,”IRE Transactions on Information Theory, 7 (1961) 27-39.

[28] M. Karpinski, L. Larmore, Yakov Nekrich, A work efficient algorithm for the construction of length-limited Huffman codes, to appear in Parallel Processing Letters.

[29] M. Karpinski, L. Larmore and W. Rytter, Sequential and parallel subquadratic work constructions of approximately optimal binary search trees, the 7th ACM Symposium on Discrete Algorithms, SODA’96.

[30] Marek Karpinski, Lawrence L. Larmore, and Wojciech Rytter. Correctness of constructing optimal alphabetic trees revisited. Theoretical Computer Science, 180(1-2):309-324, 10 June 1997.

[31] M. Karpinski, W. Rytter, On a Sublinear Time Parallel Construction of Optimal Binary Search Trees, Parallel Processing Letters, Volume 8 - Number 3, 1998.

[32] D. G. Kirkpatrick and T. M. Przytycka, Parallel construction of binary trees with almost optimal weighted path length, Proc. 2nd Symp. on Parallel Algorithms and Architectures (1990).

[33] D. G. Kirkpatrick and T. M. Przytycka, An optimal parallel minimax tree algorithm, Proc. 2nd IEEE Symp. of Parallel and Distributed Processing (1990), pp. 293–300.

[34] D. E. Knuth, Optimum binary search trees, Acta Informatica 1 (1971) pp. 14–25.

[35] D. E. Knuth. The Art of computer programming, Addison–Wesley (1973).

[36] L. L. Larmore, and T. M. Przytycka, Parallel construction of trees with optimal weighted path length, Proc. 3rd ACM Symposium on Parallel Algorithms and Architectures (1991), pp. 71–80.

[37] L. L. Larmore, and T. M. Przytycka, Constructing Huffman trees in parallel, SIAM J. Computing 24(6), (1995) pp. 1163-1169.

[38] L.Larmore, W. Rytter, Optimal parallel algorithms for some dynamic programming problems, IPL 52 (1994) 31-34.

[39] Ch. Levcopulos, T. Przytycka, A work-time trade-off in parallel computation of Huffman trees and concave least weight subsequence problem, Parallel Processing Letters 4(1-2) (1994) pp. 37-43.

[40] Ruy Luiz Milidiu, Eduardo Laber, The warm-up algorithm:a Lagrangian construction of length limited Huffman codes, SIAM J. Comput. 30(5): 1405-1426 (2000).

[41] Ruy Luiz Milidi, Eduardo Sany Laber: Linear Time Recognition of Optimal LRestricted Prefix Codes (Extended Abstract). LATIN 2000: 227-236.

[42] Ruy LuizMilidi, Eduardo Sany Laber: Bounding the Inefficiency of Length-Restricted Prefix Codes. Algorithmica 31(4): 513-529 (2001).
[43] W. Rytter, Efficient parallel computations for some dynamic programming problems, Theo. Comp. Sci. 59 (1988), pp. 297–307.

[44] K. Mehlhorn, Data structures and algorithms, vol. 1, Springer 1984.

[45] Y. Perl, M. R. Garey, and S. Even, “Efficient generation of optimal prefix code: Equiprobable words using unequal cost letters,” Journal of the Association for Computing Machinery 22 (2) (April 1975), pp 202–214.

[46] P. Ramanan, Testing the optimality of alphabetic trees, Theoretical Computer Science 93 (1992), pp. 279–301.

[47] W. Rytter, The space complexity of the unique decipherability problem, IPL 16 (4) 1983.

[48] Fast parallel computations for some dynamic programming problems, Theoretical Computer Science (1988).

[49] Baruch Schieber, Computing a Minimum Weight k-Link Path in Graphs with the Concave Monge Property. 204-222.

[50] J. S. Vitter, “Dynamic Huffman Coding,” ACM Trans. Math. Software 15 (June 1989), pp 158–167.

[51] R. Wilber, The Concave least weight subsequence problem revisited, Journal of Algorithms 9 (1988), pp. 418–425.

[52] F. F. Yao, Efficient dynamic programming using quadrangle inequalities, Proceedings of the 12 th ACM Symposium on Theory of Computing (1980), pp. 429–435.

[53] Rinaldi Munir, Algoritma & Pemrograman : Dalam Bahasa Pascal dan C, Penerbit Informatika Bandung, 2007.

[54] Suarga, Algoritma Pemrograman, penerbit Andi Yogyakarta, 2006.

[55] Intan Yuniar Purbasari, Desain & Analisis Algoritma, Penerbit Graha Ilmu Yogyakarta, 2007.

[56] Eko Budi Purwanto, Perancangan & Analisis Algoritma, Penerbit Graha Ilmu Yogyakarta, 2008.

INTEGRASI DATA (DATA INTEGRATION)

PENDAHULUAN

Banyak database, khususnya database tingkat perusahaan, dibuat dengan menggabungkan data dari sumber data internal dan eksternal yang sudah ada, memungkinkan juga dengan data baru untuk mendukung aplikasi baru. Hampir semua organisasi memiliki database yang berbeda-beda untuk tujuan yang berbeda pula.

Penerapan database pada perusahaan misalnya beberapa untuk proses transaksi dalam bagian yang berbeda dari perusahaan (contohnya: perencanaan produksi dan kontrol, dan memasukkan order/pesanan); beberapa untuk kepentingan lokal, taktis, atau pembuatan keputusan strategis (contohnya: kalkulasi harga produk dan ramalan penjualan); dan beberapa untuk koordinasi perusahaan luas dan membuat keputusan (contohnya: untuk manajemen hubungan dengan konsumen dan manajemen rangkaian persediaan). Organisasi-organisasi giat bekerja untuk memecahkan gudang/sumber data, namun membolehkan beberapa tingkat untuk otonomi lokal. Untuk mencapai koordinasi ini, disaat yang sama data harus diintegrasi melalui sumber data yang berbeda.

Tidak mengapa anda mengatakan tidak bisa menghindari berhubungan dengan integrasi data. Sebagai database profesional atau bahkan pengguna dari database yang dibuat dari sumber data lain yang sudah ada, disana banyak konsep integrasi data yang harus anda pahami untuk mengerjakan pekerjaan anda atau untuk memahami masalah yang mungkin akan anda hadapi. Inilah tujuan dari bagian selanjutnya pada bab ini.

Penggudangan data membuat data disimpan untuk mendukung pembuatan keputusan dan inteligensi bisnis. Kita akan meninjau dalam bagian selanjutnya bagaimana data dibawa bersama melalui proses extract-transform-load (ETL): ekstrak-perubahan-pemuatan, yang disebut di bab 11 sebagai lapisan data yang digabungkan dari pendekatan penggudangan data menjadi integrasi data. Tapi sebelum kita menggali lebih detail ke dalam pendekatan ini, sangat membantu untuk meninjau dua pendekatan umum lainnya (tidak termasuk ETL) yang bisa digunakan untuk integrasi data, masing-masing memiliki tujuan berbeda dan masing-masing pendekatan ideal dibawah lingkungan yang berbeda.


PEMBAHASAN

Integrasi data merupakan proses mengkombinasikan dua atau lebih set data agar mempermudah dalam berbagi dan analisis, dalam rangka mendukung manajemen informasi di dalam sebuah lingkungan kerja. Integrasi data menggabungkan data dari berbagai sumber database yang berbeda ke dalam sebuah penyimpanan seperti gudang data (data warehouse).
Alasan perlunya dilakukan integrasi data adalah:

• Data yang sama (misalnya: data penduduk) dapat dipakai bersama antar bagian organisasi (antar instansi).

• Data suatu instansi dapat dipakai bersama oleh instansi-instansi lain yang memerlukan (tidak perlu ada duplikasi data dalam suatu lingkungan organisasi).

• Meskipun fokus integrasi adalah data, tapi perlu juga integrasi hal-hal lain yang terkait.

• Integrasi data perlu dilakukan secara cermat karena kesalahan pada integrasi data bisa menghasilkan ouput/keluaran yang menyimpang dan bahkan menyesatkan pengambilan keputusan nantinya.

Syarat integrasi data dapat dipenuhi dengan berbagai cara seperti konsisten dalam penamaan variabel, konsisten dalam ukuran variabel, konsisten dalam struktur pengkodean dan konsisten dalam atribut fisik dari data. Masalah-masalah yang ada pada integrasi data yaitu heterogenitas data, otonomi sumber data, kebenaran dan kinerja query/permintaan.
Integrasi data membuat penyatuan pandangan dari data bisnis. Pandangan ini bisa dibuat dengan bermacam teknik, yang akan kita paparkan selanjutnya. Bagaimanapun juga, integrasi data bukanlah jalan satu-satunya untuk data bisa digabungkan melalui sebuah perusahaan. Cara lain untuk menggabungkan data adalah dengan:

• Integrasi Aplikasi (Aplication Integration)

Dicapai dengan mengkoordinasikan aliran kejadian informasi antara aplikasi bisnis (arsitektur yang berorientasi pada pelayanan dapat memfasilitasi integrasi aplikasi).

• Integrasi Proses Bisnis (Business Process Integration)

Dicapai oleh perapatan koordinasi aktivitas melalui proses bisnis (contoh: penjualan dan penagihan), jadi aplikasi dapat dibagi dan terlebih lagi integrasi aplikasi dapat terlaksana.

• Integrasi Interaksi Pengguna (User Interaction Integration)

Dicapai oleh pembuatan antar muka pengguna yang memberikan sistem data yang berbeda (contoh: menggunakan pintu keluar perusahaan untuk berinteraksi dengan data dan sistem inteligensi bisnis yang berbeda).

Pusat dari metode integrasi data adalah teknik untuk menangkap perubahan data (Changed Data Capture atau CDC). CDC merupakan teknik untuk menunjukkan data yang telah berubah sejak terakhir aktivitas integrasi data. Jadi hanya data yang telah berubah yang butuh direfres (penyegaran) oleh metode integrasi. Data yang berubah dapat diidentifikasi oleh tanda atau tanggal dari update/perubahaan terakhir. Alternatif lain, catatan transaksi dapat dianalisis untuk melihat data yang telah diperbarui.

Tiga teknik bentuk blok bangunan pendekatan integrasi data yaitu: konsolidasi/penggabungan data, federasi/persekutuan data, dan penyebaran data. Penggabungan data telah diberikan contohnya oleh proses ETL yang digunakan untuk penggudangan data. Kita sediakan bagian selanjutnya dari bab ini yaitu pada penjelasan lebih lanjut dari pendekatan ini. Dua pendekatan lainnya ditinjau sebagai berikut ini.


Federasi/Persekutuan Data (Data Federation)

Federasi data menyediakan pandangan nyata dari data yang terintegrasi (seperti jika semua dalam satu database) tanpa membawa semua data menjadi satu bentuk, sentralisasi database. Federasi data merupakan suatu teknik untuk integrasi data yang menyediakan tampilan sesungguhnya dari data terpadu tanpa membuat satu database terpusat yang sebenarnya. Ketika suatu aplikasi menginginkan data, mesin federasi menerima data yang relevan dari sumber yang aktual (dalam waktu nyata) dan mengirim hasilnya ke aplikasi yang meminta (sehingga terlihat seperti mesin federasi suatu database untuk aplikasi yang meminta). Transformasi data telah selesai secara dinamis seperti yang dibutuhkan. Integrasi Informasi perusahaan (Enterprise Information Integration atau EII) adalah satu syarat yang biasa digunakan untuk masuk ke pendekatan federasi data. XML (Extensible Markup Language) sering digunakan sebagai sarana untuk mentransfer data dan metadata antara sumber data dan server aplikasi.

Keuntungan utama dari pendekatan federasi adalah akses pada data yang sedang berlangsung (tidak ada penundaan karena jarangnya refres/penyegaran dari gabungan data yang tersimpan). Keuntungan lainnya adalah pendekatan ini menyembunyikan detail dari aplikasi lain dan bagaimana data disimpan didalamnya dengan memberikan query/permintaan atau aplikasi. Tetapi, hal ini memberatkan data dalam jumlah besar atau aplikasi yang membutuhkan aktivitas integrasi data yang terus menerus. Federasi membutuhkan beberapa bentuk dari distribusi query/permintaan untuk diciptakan dan dijalankan, tetapi teknologi EII akan menyembunyikan ini dari penulis query/permintaan atau pengembang aplikasi. Federasi bekerja paling baik untuk aplikasi query/permintaan dan laporan (hanya baca), dan ketika keamanan dari data yang bisa dikonsentrasikan pada sumber data dalam keadaan sangat penting. Pendekatan federasi juga digunakan sebagai teknik pembatas-berhenti sampai database yang terintegrasi dan aplikasi yang lebih kuat bisa dibuat.


Penyebaran Data (Data Propagation)

Pendekatan ini menduplikat data melalui database, biasanya dengan penundaan yang mendekati waktu sebenarnya. Data didorong untuk menduplikat tempat ketika update/perubahan berlangsung (yang disebut penyebaran event-driven: jalan-kejadian). Perubahan ini bisa diselaraskan/sinkron atau tidak diselaraskan/tidak sinkron, yang memisahkan update/perubahan ke salinan yang jauh. Teknik Integrasi aplikasi perusahaan (Enterprise Application Integration atau EAI) dan Replikasi Data Perusahaan (Enterprise Data Replication atau EDR) digunakan untuk penyebaran data.

Keuntungan utama dari pendekatan penyebaran data pada integrasi data adalah mendekati waktu nyata/sebenarnya menyelesaikan perubahan data melalui organisasi. Teknologi yang spesial sangat dibutuhkan untuk penyebaran data agar mencapai performa tinggi dan untuk mengatasi update/perubahan yang terus menerus. Waktu nyata aplikasi penggudangan data, memerlukan penyebaran data (yang sering disebut “aliran produksi” dalam penggudangan data).


Manajemen Master Data

Walaupun beberapa aplikasi membutuhkan pandangan yang terintegrasi dari semua data perusahaan, kategori data tertentu diterangkan lebih sering melalui perusahaan dalam sistem operasional dan analisa. Hampir semua sistem informasi dan database umumnya mengarah pada subyek area dari data (orang, benda, tempat) dan seringkali menambahkan data tadi dengan data lokal (transaksi) yang relevan hanya pada aplikasi atau database itu saja. Master data (kadang disebut sumber/referensi data) adalah sesuatu/entitas yang kuat di dalam diagram E-R (Entity-Relationship). Semua aplikasi yang menggunakan data umum dari area-area ini, seperti konsumen, produk, pegawai, tagihan/faktur, dan fasilitas harus mengarah pada harga-harga/nilai-nilai yang sama atau bagian lain dari organisasi tidak dapat berhubungan satu sama lain tanpa kesalahan/kekacauan. Manajemen Master Data (Master Data Management atau MDM) mengarah pada disiplin, teknologi, dan metode untuk memastikan nilai, maksud, dan kualitas dari sumber/referensi data dengan dan melalui berbagai subyek area (White dan Imhoff, 2006). MDM memastikan bahwa setiap orang mengetahui deskripsi yang ada dari produk, gaji yang ada dari pegawai, dan alamat tagihan yang ada untuk konsumen. Master data dapat menjadi simpel sebagai daftar yang diterima seperti nama kota dan singkatan. MDM tidak mengalamatkan data transaksi yang terbagi, seperti pembelian konsumen.

Satu sistem sumber umumnya mengandung “catatan penting” dari seluruh fakta relevan mengenai subyek data. Contohnya, master data konsumen mungkin terintegrasi dari manajemen hubungan konsumen, tagihan, ERP (Enterprise Resource Planning), dan sumber-sumber data pembelian. MDM menentukan sumber terbaik dari setiap satuan data (contoh: alamat atau nama konsumen) dan memastikan bahwa semua aplikasi bersumber dari “catatan penting” yang sesungguhnya. MDM juga menyediakan analisis dan layanan laporan untuk menginformasikan manajer kualitas data tentang kualitas dari master data melalui database (contohnya: persentase dari data kota yang tersimpan di masing-masing database yang memenuhi nilai-nilai master kota).

MDM menjadi makin umum karena gabungan dan akuisisi yang aktif dan untuk memenuhi peraturan, seperti penetapan Sarbanes-Oxley (Sarbanes-Oxley adalah hukum federal Amerika Serikat yang ditetapkan pada 30 Juli 2002. Perundang-undangan ini menetapkan suatu standar baru dan lebih baik bagi semua dewan dan manajemen perusahaan publik serta kantor akuntan publik walaupun tidak berlaku bagi perusahaan tertutup. Akta ini terdiri dari 11 judul atau bagian yang menetapkan hal-hal mulai dari tanggung jawab tambahan dewan perusahaan hingga hukuman pidana). Banyak vendor (konsultan dan penyuplai teknologi) yang ada untuk menyediakan pendekatan dan teknologi MDM.

Ada tiga arsitektur terkenal untuk manajemen master data yaitu: register (registry) identitas, pusat (hub) integrasi, dan tetap (persistent). Di dalam pendekatan register identitas, master data masih dalam sistem sumbernya, dan aplikasi-aplikasi yang mengacu pada register untuk menentukan bagian mana yang disetujui dari keberadaan beberapa sumber data (seperti alamat konsumen). Register membantu masing-masing sistem mencocokkan catatan utamanya dengan catatan utama yang cocok di sistem sumber yang lain dengan menggunakan identitas global untuk setiap instansi dari subyek area. Register menjaga daftar lengkap dari semua elemen master data dan mengetahui sistem sumber mana yang dapat diakses untuk nilai yang terbaik untuk setiap atribut. Jadi, sebuah aplikasi dibolehkan mengakses beberapa database untuk menerima semua data yang dibutuhkannya, dan database mengizinkan lebih banyak aplikasi untuk mengaksesnya. Ini sama seperti gaya federasi pada integrasi data.

Dalam pendekatan pusat integrasi, perubahan data disiarkan (khususnya bersifat asinkron) melalui layanan pusat untuk semua database yang berlangganan/berhubungan. Data yang berlebihan (redundant) di simpan, tapi ada mekanisme-mekanisme untuk memastikan kekonsistenan, akan tetapi setiap aplikasi tidak harus mengumpulkan dan menjaga semua data yang dibutuhkannya. Ketika pusat integrasi ini dibuat, ia bertindak seperti bentuk penyebaran integrasi data. Tetapi dalam beberapa kasus, pusat penyimpanan master data juga dibuat untuk beberapa master data, jadi mungkin ini adalah kombinasi dari penyebaran dan penggabungan. Bagaimanapun juga, bahkan dengan penggabungan, sistem pencatat atau pemasukan (sistem transaksi yang didistribusikan) masih mengatur databasenya sendiri termasuk data lokal dan data yang disebarkan sesuai yang mereka butuhkan untuk hampir seluruh proses.

Dalam pendekatan tetap, satu catatan gabungan diatur dan semua aplikasi menggambarkan satu “catatan penting” aktual untuk data umum. Jadi, pekerjaan cukup penting untuk mendorong semua data yang ditangkap dalam setiap aplikasi kepada catatan yang tetap yang menyebabkan hal itu mengandung nilai-nilai yang baru dan menuju pada catatan penting ketika sistem manapun membutuhkan data umum. Ada kemungkinan terjadi kelebihan (redundancy) data dengan pendekatan yang tetap karena setiap database aplikasi bisa juga mengatur versi lokal dari elemen-elemen data dalam keleluasaannya, bahkan mengatur dalam tabel penggabungan yang tetap. Ini adalah pendekatan penggabungan integrasi data murni untuk master data.
Penting untuk menegaskan bahwa manajemen master data adalah bagian dari integrasi data karena hanya master data yang diintegrasikan. Master data tidak hanya merupakan bagian dari tabel pada setiap database (tabel untuk subyek besar dari pelanggan, produk, fasilitas, karyawan/pegawai, dan lain-lain) tetapi hanya elemen-elemen data itu yang terbagi melalui perusahaan. Data yang hanya untuk penggunaan lokal dan data yang harus diamankan oleh sistem lokal, tidak termasuk dari arsitektur integrasi data bahkan untuk catatan master data.

Ada beberapa bentuk spesialisasi dari MDM. Satu yang paling didiskusikan adalah Integrasi Data Konsumen (Costumer Data Integration atau CDI), yang mana MDM hanya fokus pada data konsumen (Dyche dan Levy, 2006). Selain itu adalah Integrasi Data Produk (Product Data Integration atau PDI). Bentuk apapun dari MDM tidak dimaksudkan untuk menggantikan gudang data, terutama karena hanya master data dan biasanya hanya master data yang sedang berjalan yang diintegrasi, dimana gudang data membutuhkan pandangan asal usul dari master dan transaksi data. Tetapi sebuah gudang data, bisa jadi (dan sering kali) salah satu dari sistem yang menggunakan master data, apakah sebagai sumber untuk menyuplai gudang atau sebagai perluasan dari gudang untuk hampir setiap data ketika pengguna gudang ingin masuk lewat sumber data. MDM melakukan pembersihan data, seperti apa yang dilakukan dengan penggudangan data. Dengan alasan ini, MDM juga bukan sebuah tempat penyimpanan data operasional (lihat bab 11 untuk deskripsi dari sebuah ODS). MDM juga dipertimbangkan oleh banyak orang sebagai bagian dari infrastruktur data dari organisasi, dimana sebuah ODS (Operational Data Store) dan bahkan penggudangan data, dianggap sebagai landasan aplikasi.

Sebuah model data untuk MDM secara nyata benar-benar simpel. Masing-masing subyek area cirinya dikelilingi oleh MDM karena disana tidak ada data transaksi yang terhubung dengan kategori master yang berbeda. Masing-masing tabel master data intinya adalah sebuah file datar (flat file), bahkan tanpa hubungan hirarki. MDM dengan tegas mengambil satu pandangan dari data tentang setiap instansi dari setiap tipe master data. Karena master data adalah “catatan penting”, tidak ada satupun aplikasi yang memiliki master data. Agaknya, master data adalah benar-benar aset perusahaan, dan manajer bisnis harus mengambil tanggung jawab untuk kualitas master data. Pelayanan data dan pemerintahan data yang kuat sangat penting sekali untuk sebuah program MDM menjadi efektif.