Pada artikel ini kita akan membahas tentang dependensi fungsional dalam database - apa itu dependensi, di mana penggunaannya, dan algoritma apa yang ada untuk menemukannya.
Kami akan mempertimbangkan ketergantungan fungsional dalam konteks database relasional. Secara kasar, dalam database tersebut, informasi disimpan dalam bentuk tabel. Selanjutnya, kita menggunakan konsep perkiraan yang tidak dapat dipertukarkan dalam teori relasional yang ketat: kita akan menyebut tabel itu sendiri sebagai relasi, kolom - atribut (himpunannya - skema relasi), dan himpunan nilai baris pada subset atribut - sebuah tupel.
Misalnya pada tabel di atas, (Benson, M, Morgan) adalah tupel atribut (Pasien, Paul, Dokter).
Secara lebih formal, ini ditulis sebagai berikut: [Pasien, Jenis Kelamin, Dokter] = (Benson, M, M organ).
Sekarang kita dapat memperkenalkan konsep ketergantungan fungsional (FD):
Definisi 1. Relasi R memenuhi hukum federal X → Y (di mana X, Y ⊆ R) jika dan hanya jika untuk tupel apa pun , ∈ R berlaku: jika [X] = [X], lalu [Y] = [kamu]. Dalam hal ini, kita mengatakan bahwa X (determinan, atau himpunan atribut yang menentukan) secara fungsional menentukan Y (himpunan dependen).
Dengan kata lain, adanya undang-undang federal X→Y artinya jika kita memiliki dua tupel R dan mereka cocok dalam atribut X, maka atributnya akan sama Y.
Dan sekarang, secara berurutan. Mari kita lihat atributnya Seorang pasien и Jenis kelamin untuk itu kita ingin mengetahui apakah ada ketergantungan diantara keduanya atau tidak. Untuk sekumpulan atribut tersebut, dependensi berikut mungkin ada:
- Pasien → Jenis Kelamin
- Jenis Kelamin → Pasien
Seperti yang didefinisikan di atas, agar ketergantungan pertama tetap ada, setiap nilai kolom unik Seorang pasien hanya satu nilai kolom yang harus cocok Jenis kelamin. Dan untuk contoh tabel memang demikian. Namun, hal ini tidak berlaku sebaliknya, yaitu ketergantungan kedua dan atribut tidak terpenuhi Jenis kelamin bukan merupakan penentu untuk Sabar. Begitu pula jika kita mengambil ketergantungan Dokter → Pasien, Anda dapat melihat bahwa itu dilanggar, karena nilainya robin atribut ini memiliki beberapa arti berbeda - Ellis dan Graham.
Dengan demikian, ketergantungan fungsional memungkinkan untuk menentukan hubungan yang ada antara kumpulan atribut tabel. Mulai sekarang dan seterusnya kita akan mempertimbangkan koneksi yang paling menarik, atau lebih tepatnya seperti itu X→Yapa itu:
- non-trivial, yaitu ruas kanan ketergantungan bukan merupakan himpunan bagian kiri (Y ̸⊆ X);
- minimal, yaitu tidak ada ketergantungan seperti itu Z → kamuBahwa Z ⊂ X.
Ketergantungan yang dipertimbangkan sampai saat ini sangat ketat, yaitu tidak memberikan pelanggaran apa pun pada tabel, tetapi selain itu, ada juga yang memungkinkan beberapa ketidakkonsistenan antara nilai-nilai tupel. Ketergantungan tersebut ditempatkan dalam kelas terpisah, yang disebut perkiraan, dan diperbolehkan untuk dilanggar untuk sejumlah tupel tertentu. Jumlah ini diatur oleh indikator kesalahan maksimum emax. Misalnya saja tingkat kesalahannya = 0.01 dapat berarti bahwa ketergantungan dapat dilanggar oleh 1% tupel yang tersedia pada kumpulan atribut yang dipertimbangkan. Artinya, untuk 1000 record, maksimal 10 tupel dapat melanggar Hukum Federal. Kami akan mempertimbangkan metrik yang sedikit berbeda, berdasarkan nilai berbeda berpasangan dari tupel yang dibandingkan. Untuk kecanduan X→Y pada sikap r itu dianggap seperti ini:
Mari kita hitung kesalahannya Dokter → Pasien dari contoh di atas. Kami memiliki dua tupel yang nilainya berbeda pada atributnya Seorang pasien, tapi bertepatan Dokter: [Dokter, Pasien] = (Robin, Ellis) Dan [Dokter, Pasien] = (Robin, Graham). Mengikuti definisi kesalahan, kita harus memperhitungkan semua pasangan yang bertentangan, yang berarti akan ada dua pasangan: (, ) dan inversinya (, ). Mari kita substitusikan ke dalam rumus dan dapatkan:
Sekarang mari kita coba menjawab pertanyaan: “Untuk apa semua ini?” Faktanya, undang-undang federal berbeda. Tipe pertama adalah dependensi yang ditentukan oleh administrator pada tahap desain database. Biasanya jumlahnya sedikit, ketat, dan aplikasi utamanya adalah normalisasi data dan desain skema relasional.
Tipe kedua adalah dependensi, yang merepresentasikan data “tersembunyi” dan hubungan antar atribut yang sebelumnya tidak diketahui. Artinya, ketergantungan tersebut tidak terpikirkan pada saat desain dan sudah ditemukan untuk kumpulan data yang ada, sehingga nantinya, berdasarkan banyak undang-undang federal yang teridentifikasi, kesimpulan apa pun dapat ditarik tentang informasi yang disimpan. Ketergantungan inilah yang kami tangani. Mereka ditangani oleh seluruh bidang penambangan data dengan berbagai teknik pencarian dan algoritma yang dibangun atas dasar mereka. Mari kita cari tahu bagaimana dependensi fungsional yang ditemukan (tepat atau perkiraan) dalam data apa pun dapat bermanfaat.
Saat ini, salah satu aplikasi utama dependensi adalah pembersihan data. Ini melibatkan pengembangan proses untuk mengidentifikasi “data kotor” dan kemudian memperbaikinya. Contoh menonjol dari “data kotor” adalah duplikat, kesalahan atau kesalahan ketik data, nilai yang hilang, data usang, spasi tambahan, dan sejenisnya.
Contoh kesalahan data:
Contoh duplikat data:
Misalnya, kita memiliki tabel dan seperangkat undang-undang federal yang harus dipatuhi. Pembersihan data dalam hal ini melibatkan perubahan data sehingga Undang-Undang Federal menjadi benar. Dalam hal ini, jumlah modifikasi harus minimal (prosedur ini memiliki algoritmanya sendiri, yang tidak akan kita bahas dalam artikel ini). Di bawah ini adalah contoh transformasi data tersebut. Di sebelah kiri adalah hubungan asli, di mana, jelas, FL yang diperlukan tidak terpenuhi (contoh pelanggaran salah satu FL disorot dengan warna merah). Di sebelah kanan adalah hubungan yang diperbarui, dengan sel hijau menunjukkan nilai yang diubah. Setelah prosedur ini, ketergantungan yang diperlukan mulai dipertahankan.
Aplikasi populer lainnya adalah desain database. Di sini perlu diingat kembali bentuk normal dan normalisasi. Normalisasi adalah proses membawa suatu relasi agar sesuai dengan serangkaian persyaratan tertentu, yang masing-masing ditentukan oleh bentuk normal dengan caranya sendiri. Kami tidak akan menjelaskan persyaratan berbagai bentuk normal (ini dilakukan di buku mana pun tentang kursus database untuk pemula), tetapi kami hanya akan mencatat bahwa masing-masing bentuk normal menggunakan konsep ketergantungan fungsional dengan caranya sendiri. Bagaimanapun, FL pada dasarnya adalah batasan integritas yang diperhitungkan saat merancang database (dalam konteks tugas ini, FL terkadang disebut superkey).
Mari kita perhatikan penerapannya untuk empat bentuk normal pada gambar di bawah. Ingatlah bahwa bentuk normal Boyce-Codd lebih ketat dibandingkan bentuk ketiga, tetapi kurang ketat dibandingkan bentuk keempat. Kami tidak mempertimbangkan yang terakhir untuk saat ini, karena perumusannya memerlukan pemahaman tentang ketergantungan multi-nilai, yang tidak menarik bagi kami dalam artikel ini.
Area lain di mana dependensi telah diterapkan adalah mengurangi dimensi ruang fitur dalam tugas-tugas seperti membuat pengklasifikasi Bayes yang naif, mengidentifikasi fitur-fitur penting, dan melakukan parameterisasi ulang model regresi. Dalam artikel asli, tugas ini disebut penentuan relevansi redundan dan fitur [5, 6], dan diselesaikan dengan penggunaan aktif konsep database. Dengan munculnya karya-karya seperti itu, kita dapat mengatakan bahwa saat ini ada permintaan akan solusi yang memungkinkan kita menggabungkan database, analitik, dan implementasi masalah optimasi di atas ke dalam satu alat [7, 8, 9].
Ada banyak algoritme (baik modern maupun tidak modern) untuk mencari undang-undang federal dalam kumpulan data. Algoritme tersebut dapat dibagi menjadi tiga kelompok:
- Algoritma menggunakan traversal kisi aljabar (Algoritma traversal kisi)
- Algoritma berdasarkan pencarian nilai-nilai yang disepakati (algoritma Difference-and-agree-set)
- Algoritma berdasarkan perbandingan berpasangan (Algoritma induksi ketergantungan)
Penjelasan singkat masing-masing jenis algoritma disajikan pada tabel di bawah ini:
Anda dapat membaca lebih lanjut tentang klasifikasi ini [4]. Di bawah ini adalah contoh algoritma untuk setiap jenis:
Saat ini, muncul algoritma baru yang menggabungkan beberapa pendekatan untuk menemukan ketergantungan fungsional. Contoh algoritma tersebut adalah Pyro [2] dan HyFD [3]. Analisis terhadap karya mereka diharapkan dapat ditemukan pada artikel berikutnya dalam seri ini. Pada artikel ini kita hanya akan membahas konsep dasar dan lemma yang diperlukan untuk memahami teknik deteksi ketergantungan.
Mari kita mulai dengan yang sederhana - himpunan perbedaan dan persetujuan, yang digunakan dalam algoritma jenis kedua. Diffrence-set adalah himpunan tupel yang tidak memiliki nilai yang sama, sedangkan sebaliknya, agreement-set adalah tupel yang memiliki nilai yang sama. Perlu dicatat bahwa dalam kasus ini kami hanya mempertimbangkan sisi kiri ketergantungan.
Konsep penting lainnya yang ditemui di atas adalah kisi aljabar. Karena banyak algoritma modern yang beroperasi pada konsep ini, kita perlu memiliki gambaran tentang apa itu.
Untuk memperkenalkan konsep kisi, perlu didefinisikan himpunan terurut sebagian (atau himpunan terurut sebagian, disingkat poset).
Definisi 2. Suatu himpunan S dikatakan terurut sebagian berdasarkan relasi biner ⩽ jika untuk semua a, b, c ∈ S sifat-sifat berikut terpenuhi:
- Refleksivitas, yaitu a ⩽ a
- Antisimetri, yaitu jika a ⩽ b dan b ⩽ a, maka a = b
- Transitivitas, yaitu untuk a ⩽ b dan b ⩽ c maka a ⩽ c
Relasi seperti ini disebut relasi tatanan parsial (longgar), dan himpunan itu sendiri disebut himpunan terurut sebagian. Notasi formal: ⟨S, ⩽⟩.
Sebagai contoh paling sederhana dari himpunan terurut sebagian, kita dapat mengambil himpunan semua bilangan asli N dengan relasi orde biasa ⩽. Sangat mudah untuk memverifikasi bahwa semua aksioma yang diperlukan terpenuhi.
Contoh yang lebih bermakna. Misalkan himpunan semua himpunan bagian {1, 2, 3} yang diurutkan berdasarkan relasi inklusi ⊆. Memang benar, relasi ini memenuhi semua kondisi keteraturan parsial, jadi ⟨P ({1, 2, 3}), ⊆⟩ adalah himpunan terurut sebagian. Gambar di bawah menunjukkan struktur himpunan ini: jika suatu elemen dapat dijangkau dengan panah ke elemen lainnya, maka elemen tersebut berada dalam hubungan keteraturan.
Kita memerlukan dua definisi sederhana lagi dari bidang matematika - supremum dan infimum.
Definisi 3. Misalkan ⟨S, ⩽⟩ adalah himpunan terurut sebagian, A ⊆ S. Batas atas A adalah elemen u ∈ S sehingga ∀x ∈ S: x ⩽ u. Misalkan U adalah himpunan semua batas atas S. Jika terdapat elemen terkecil pada U, maka elemen tersebut disebut supremum dan dilambangkan dengan sup A.
Konsep batas bawah yang tepat diperkenalkan dengan cara yang sama.
Definisi 4. Misal ⟨S, ⩽⟩ adalah himpunan terurut parsial, A ⊆ S. Maksimum dari A adalah sebuah elemen l ∈ S sehingga ∀x ∈ S: l ⩽ x. Misalkan L adalah himpunan semua batas bawah S. Jika terdapat elemen terbesar di L, maka elemen tersebut disebut infimum dan dilambangkan dengan inf A.
Perhatikan sebagai contoh himpunan terurut sebagian di atas ⟨P ({1, 2, 3}), ⊆⟩ dan carilah supremum dan infimum di dalamnya:
Sekarang kita dapat merumuskan definisi kisi aljabar.
Definisi 5. Misalkan ⟨P,⩽⟩ adalah himpunan terurut sebagian sehingga setiap himpunan bagian yang terdiri dari dua elemen mempunyai batas atas dan batas bawah. Maka P disebut kisi aljabar. Dalam hal ini, sup{x, y} ditulis sebagai x ∨ y, dan inf {x, y} sebagai x ∧ y.
Mari kita periksa apakah contoh kerja kita ⟨P ({1, 2, 3}), ⊆⟩ adalah sebuah kisi. Memang benar, untuk setiap a, b ∈ P ({1, 2, 3}), a∨b = a∪b, dan a∧b = a∩b. Misalnya, perhatikan himpunan {1, 2} dan {1, 3} dan temukan minimum dan supremumnya. Jika kita memotongnya, kita akan mendapatkan himpunan {1}, yang merupakan bilangan terkecil. Kita mendapatkan supremumnya dengan menggabungkannya - {1, 2, 3}.
Dalam algoritma untuk mengidentifikasi masalah fisik, ruang pencarian sering direpresentasikan dalam bentuk kisi, di mana himpunan satu elemen (baca kisi pencarian tingkat pertama, di mana sisi kiri dependensi terdiri dari satu atribut) mewakili setiap atribut dari relasi aslinya.
Pertama, kita pertimbangkan ketergantungan dalam bentuk ∅ → Atribut tunggal. Langkah ini memungkinkan Anda menentukan atribut mana yang merupakan kunci utama (untuk atribut tersebut tidak ada determinan, sehingga sisi kirinya kosong). Selanjutnya, algoritma tersebut bergerak ke atas sepanjang kisi. Perlu dicatat bahwa tidak seluruh kisi dapat dilintasi, yaitu, jika ukuran maksimum sisi kiri yang diinginkan diteruskan ke masukan, maka algoritme tidak akan melangkah lebih jauh dari level dengan ukuran tersebut.
Gambar di bawah menunjukkan bagaimana kisi aljabar dapat digunakan dalam soal mencari FZ. Di sini setiap sisi (X, XY) mewakili ketergantungan X→Y. Misalnya, kita telah melewati level pertama dan mengetahui bahwa kecanduannya tetap ada SEBUAH→B (kami akan menampilkan ini sebagai koneksi hijau antar simpul A и B). Ini berarti bahwa selanjutnya, ketika kita bergerak ke atas sepanjang kisi, kita mungkin tidak memeriksa ketergantungannya SEBUAH, C → B, karena tidak lagi minimal. Demikian pula, kami tidak akan memeriksanya jika ketergantungannya ditahan C→B.
Selain itu, sebagai aturan, semua algoritme modern untuk mencari undang-undang federal menggunakan struktur data seperti partisi (dalam sumber aslinya - partisi yang dilucuti [1]). Definisi formal dari partisi adalah sebagai berikut:
Definisi 6. Misalkan X ⊆ R adalah himpunan atribut untuk relasi r. Cluster adalah sekumpulan indeks tupel di r yang mempunyai nilai X yang sama, yaitu c(t) = {i|ti[X] = t[X]}. Partisi adalah sekumpulan klaster, tidak termasuk klaster dengan panjang satuan:
Dengan kata sederhana, partisi untuk suatu atribut X adalah sekumpulan daftar, dimana setiap daftar berisi nomor baris dengan nilai yang sama X. Dalam literatur modern, struktur yang mewakili partisi disebut indeks daftar posisi (PLI). Cluster dengan panjang satuan dikecualikan untuk tujuan kompresi PLI karena merupakan cluster yang hanya berisi nomor rekaman dengan nilai unik yang akan selalu mudah diidentifikasi.
Mari kita lihat sebuah contoh. Mari kita kembali ke tabel yang sama dengan pasien dan membuat partisi untuk kolomnya Seorang pasien и Jenis kelamin (kolom baru telah muncul di sebelah kiri, di mana nomor baris tabel ditandai):
Apalagi menurut definisinya, partisi untuk kolom Seorang pasien sebenarnya akan kosong, karena cluster tunggal dikecualikan dari partisi.
Partisi dapat diperoleh dengan beberapa atribut. Dan ada dua cara untuk melakukan ini: dengan menelusuri tabel, membangun partisi menggunakan semua atribut yang diperlukan sekaligus, atau membangunnya menggunakan operasi perpotongan partisi menggunakan subset atribut. Algoritma pencarian hukum federal menggunakan opsi kedua.
Dengan kata sederhana, misalnya untuk mendapatkan partisi berdasarkan kolom ABC, Anda dapat mengambil partisi untuk AC и B (atau himpunan himpunan bagian terpisah lainnya) dan berpotongan satu sama lain. Operasi perpotongan dua partisi memilih cluster dengan panjang terbesar yang sama untuk kedua partisi.
Mari kita lihat sebuah contoh:
Dalam kasus pertama, kami menerima partisi kosong. Jika dilihat dari tabelnya, maka memang tidak ada nilai yang sama untuk kedua atribut tersebut. Jika kita sedikit memodifikasi tabelnya (kasus di sebelah kanan), kita akan mendapatkan persimpangan yang tidak kosong. Apalagi baris 1 dan 2 sebenarnya mengandung nilai atribut yang sama Jenis kelamin и Dokter.
Selanjutnya, kita memerlukan konsep seperti ukuran partisi. Secara formal:
Sederhananya, ukuran partisi adalah jumlah cluster yang termasuk dalam partisi (ingat bahwa cluster tunggal tidak termasuk dalam partisi!):
Sekarang kita dapat mendefinisikan salah satu lemma utama, yang untuk partisi tertentu memungkinkan kita menentukan apakah suatu ketergantungan dipertahankan atau tidak:
Lemma 1. Ketergantungan A, B → C berlaku jika dan hanya jika
Menurut lemma tersebut, untuk menentukan apakah suatu ketergantungan berlaku, empat langkah harus dilakukan:
- Hitung partisi untuk sisi kiri ketergantungan
- Hitung partisi untuk sisi kanan ketergantungan
- Hitung hasil kali langkah pertama dan kedua
- Bandingkan ukuran partisi yang diperoleh pada langkah pertama dan ketiga
Di bawah ini adalah contoh pengecekan apakah ketergantungan berlaku menurut lemma ini:
Dalam artikel ini, kami memeriksa konsep-konsep seperti ketergantungan fungsional, perkiraan ketergantungan fungsional, melihat di mana mereka digunakan, serta algoritma apa untuk mencari fungsi fisik yang ada. Kami juga memeriksa secara rinci konsep dasar namun penting yang secara aktif digunakan dalam algoritma modern untuk mencari undang-undang federal.
Referensi:
- Huhtala Y. dkk. TANE: Algoritma yang efisien untuk menemukan ketergantungan fungsional dan perkiraan // Jurnal komputer. – 1999. – T.42. – No. 2. – hal.100-111.
- Kruse S., Naumann F. Penemuan perkiraan ketergantungan yang efisien // Prosiding VLDB Endowment. – 2018. – T.11. – No. 7. – hal.759-772.
- Papenbrock T., Naumann F. Pendekatan hibrid untuk penemuan ketergantungan fungsional //Prosiding Konferensi Internasional Manajemen Data 2016. – ACM, 2016. – hal.821-833.
- Papenbrock T. dkk. Penemuan ketergantungan fungsional: Evaluasi eksperimental tujuh algoritma //Prosiding VLDB Endowment. – 2015. – T.8. – No. 10. – hal.1082-1093.
- Kumar A.dkk. Untuk bergabung atau tidak?: Berpikir dua kali tentang bergabung sebelum pemilihan fitur //Prosiding Konferensi Internasional Manajemen Data 2016. – ACM, 2016. – hal.19-34.
- Abo Khamis M. dkk. Pembelajaran dalam database dengan tensor renggang //Prosiding Simposium ACM SIGMOD-SIGACT-SIGAI ke-37 tentang Prinsip Sistem Basis Data. – ACM, 2018. – hal.325-340.
- Hellerstein JM dkk. Pustaka analitik MADlib: atau keterampilan MAD, SQL //Prosiding VLDB Endowment. – 2012. – T.5. – No. 12. – hal.1700-1711.
- Qin C., Rusu F. Perkiraan spekulatif untuk optimasi penurunan gradien terdistribusi terascale //Prosiding Lokakarya Keempat tentang Analisis Data di Cloud. – ACM, 2015. – Hal.1.
- Meng X. dkk. Mllib: Pembelajaran mesin di apache spark // Jurnal Penelitian Pembelajaran Mesin. – 2016. – T.17. – No. 1. – hal.1235-1241.
Penulis artikel: , peneliti di , и , peneliti di
Sumber: www.habr.com