TUGAS DATA WAREHOUSE OLAP OVER UNCERTAIN AND IMPRECISE DATA
Oleh: Rizza Febriyanto (08560139) Muhammad Iqbal (08560151)
FAKULTAS TEKNIK TEKNIK INFORMATIKA UNIVERSITAS MUHAMMADIYAH MALANG 2011
Dalam makalah ini, kami memperpanjang model multidimensi OLAP data untuk merepresentasikan data yang ambiguitas, khususnya Ketidasamaan dan ketidakpastian, dan mempelajari kemungkinan semantik untuk agregasi query atas data tersebut. Sementara ada banyak pekerjaan dalam mempresentasikan dan proses query pada data yang ambigu, dan bahkan sebagian bekerja dalam konteks OLAP, untuk pengetahuan kita ini merupakan paper pertama untuk mengidentifikasi kriteria yang harus dipenuhi dalam setiap pendekatan untuk penanganan ambiguitas dalam pengaturan OLAP, dan untuk menggunakan kriteria tersebut dalam cara berprinsip untuk tiba di semantik yang tepat untuk query. Kriteria pertama kami, disebut konsistensi, rekening untuk hubungan antara query sejenis yang dikaitkan pada node yang terkait dalam hirarki domain dalam rangka memenuhi harapan pengguna “ berdasarkan harapan karena mereka menavigasi hirarki atas dan bawah. Kriteria kedua, disebut kesetiaan, menangkap intuisi data yang lebih tepat untuk mengarah pada hasil yang lebih baik. Kriteria ketiga, yang disebut korelasi-pelestarian, pada dasarnya mensyaratkan bahwa statistik sifat dari data seharusnya tidak terpengaruh oleh alokasi catatan data ambigu. Sementara dua kriteria terakhir tidak dikhususkan untuk OLAP, sepengetahuan kami, mereka belum diajukan sebelumnya.
Kami memperluas model data OLAP dalam dua dasar cara. Pertama, kita bersantai pembatasan bahwa dimensi Izin untuk menyalin tanpa semua biaya atau sebagian dari bahan ini diberikan diberikan bahwa salinan tidak dibuat atau didistribusikan untuk komersial langsung keuntungan, hak cipta pemberitahuan VLDB dan judul publikasi dan tanggal yang muncul, dan pemberitahuan yang diberikan bahwa penyalinan adalah dengan izin dari Sangat Besar Data Base Endowment. Untuk menyalin sebaliknya, atau untuk menerbitkan, membutuhkan biaya dan / atau izin khusus dari Endowment tersebut. Prosiding Konferensi VLDB 31, Trondheim, Norwegia, 2005 sebenarnya atribut harus diberi daun-tingkat nilai dari hirarki domain yang mendasari, dalam rangka untuk ketidaktepatan model. Sebagai contoh, kita dapat menunjukkan bahwa perbaikan tertentu berlangsung di Texas, tanpa menentukan sebuah kota. Jelas, ini memiliki implikasi untuk bagaimana kita menjawab pertanyaanuntuk query bahwa biaya perbaikan agregat di Austin, harus contoh perbaikan dimasukkan, dan jika demikian, bagaimana? Ekstensi yang kedua kami adalah untuk memperkenalkan jenis baru mengukur atribut yang mewakili ketidakpastian. Secara intuitif, nilai pasti mengkodekan kisaran nilai yang mungkin sama dengan keyakinan kami kemungkinan dari masing-masing nilai yang mungkin. Secara khusus, kami mewakili nilai untuk mengukur pasti sebagai fungsi distribusi probabilitas (Pdf) atas nilai-nilai dari sebuah domain yang terkait "dasar". Kontribusi kami dapat diringkas sebagai berikut: 1.
Generalisasi dari model OLAP untuk merepresentasikan data ambiguitas. Untuk pengetahuan kita, ini adalah seperti pertama generalisasi yang membicarakan baik dimensi tidak tepat nilai-nilai dan nilai-nilai pengukuran tidak pasti.
2. Pengenalan kriteria (konsistensi, kesetiaan, korelasi-pelestarian) yang memandu pilihan semantik untuk permintaan agregasi atas data ambigu. 3. Sebuah dunia yang mungkin-interpretasi ambiguitas Data yang mengarah ke pendekatan berbasis alokasi baru untuk mendefinisikan semantik untuk query agregasi, dan hati-hati
studi pilihan yang timbul dalam pengobatan data ambiguitas, menggunakan konsistensi, kesetiaan, dan korelasi-kriteria pelestarian. 4. Algoritma untuk mengevaluasi query agregasi (termasuk RATA-RATA, COUNT, SUM untuk biasa dan langkah-langkah, dan langkah-langkah pasti LinOp), bersama-sama dengan analisis kompleksitas. 5. Suatu evaluasi eksperimental yang alamat skalabilitas serta kualitas hasil. •
RelatedWork Sementara ada literatur yang luas pada permintaan atas ambigu data, hanya beberapa dokumen [24, 28, 29, 16] telah dianggap sebuah OLAP pengaturan. [24] adalah mungkin paling dekat dengan pekerjaan kami dalam hal ini mempertimbangkan semantik agregasi query, tetapi tidak mempertimbangkan ketidakpastian atau menyelidiki kriteria yang menjelaskan semantik yang sesuai permintaan. [28, 29] mempertimbangkan masalah imputing mengukur hilang nilai-nilai, dengan menggunakan persamaan linear, maksimisasi entropi, minimisasi entropi silang, atau kendala pemrograman teknik. [16] menjelaskan metode untuk memperkirakan kesalahan kubus agregat untuk data tertentu; generalisasi metode mereka untuk data pasti tidak jelas. Pekerjaan awal pada permintaan agregat atas tidak tepat data [8], dan itu diikuti oleh [20, 9, 25], namun, tidak ada makalah ini mempertimbangkan data-tingkat hierarki (Yang adalah pusat untuk OLAP). Pendekatan dalam [8] menyebabkan untuk algoritma eksponensial-waktu untuk SUM. [9] model ketidakpastian menggunakan interval dan PDF dan menyediakan algoritma untuk menggabungkan mereka. [25] mengembangkan pemrograman linier berbasis semantik untuk agregat komputasi lebih probabilistik database. Kami mencatat bahwa [20] juga membahas ketidakpastian, dan [26] mendukung fungsi agregat untuk data pasti, tetapi tidak mendukung ketidaktepatan atau hirarki. Kami percaya bahwa kontribusi kunci dari makalah ini adalah kita metodologi-mengidentifikasi kriteria intuitif seperti konsistensi, kesetiaan, dan korelasi-pelestarian dan menggunakan mereka untuk mempelajari semantik permintaan alternatif adalah pendekatan yang dapat diterapkan di luar pengaturan OLAP (dan memang, kesetiaan dan korelasi-pelestarian yang tidak spesifik untuk OLAP). Dalam hal ini, pendekatan kami adalah memiliki semangat yang sama penggunaan summarizability, yang diperkenalkan untuk belajar interaksi antara sifat-sifat data dan agregasi operator (yaitu, sifat-sifat apa yang harus data yang dimiliki untuk hasil fungsi agregasi tertentu bisa bermakna) [18, 19]. Sejumlah makalah pertimbangkan ketidaktepatan dan ketidakpastian untuk non-agregasi query. Penggunaan yang mungkin dunia semantik untuk merepresentasikan data tidak tepat dibahas dalam [1]. [7, 13, 4, 17, 12] mengasosiasikan sebuah distribusi probabilitas dengan data (baik pada elemen data atau tingkat tupel), dan generalisasi operator aljabar relasional untuk mencerminkan terkait probabilitas. [2, 3] berusaha untuk mengidentifikasi data yang tidak konsisten dan untuk "memperbaiki" database ini ke keadaan yang konsisten, sebaliknya, kita fokus pada data tidak tepat namun konsisten, dan melakukan tidak mempertimbangkan batasan integritas (selain kendala domain). Berbagai sumber ambiguitas data yang diklasifikasikan dalam [22, 23], bersama-sama dengan pendekatan untuk mewakili dan pengolahan ambiguitas. [27] membahas banyak kesamaan antara database statistik dan OLAP.
•
Model Data Pada bagian ini kami menyajikan generalisasi kita dari standar model data multidimensi, menggabungkan Ketidaktelitian dan ketidakpastian. - Data Representation
Atribut dalam model OLAP standar terdiri dari dua jenis- dimensi dan ukuran. Kami memperluas model untuk mendukung ketidakpastian dalam nilai mengukur dan ketidaktepatan dalam dimensi nilai-nilai. Definisi 1 (Domain Ketidakpastian). Domain yang tidak pasti U di atas dasar domain O adalah himpunan semua kemungkinan yang mungkin distribusi fungsi, atau PDF, lebih dari O.? Dengan demikian, masing-masing u nilai dalam U adalah pdf yang, secara intuitif, menunjukkan kami derajat keyakinan bahwa "benar" nilai yang diwakili o, untuk setiap o di dasar domain O.
Definisi 2 (Domain tidak tepat). Domain yang tepat Saya lebih dari base domain B adalah subset dari Powerset B dengan; / 2 I; unsur-unsur dari I disebut nilai-nilai tidak tepat. ? Secara intuitif, nilai tidak tepat adalah mengatur non-kosong dari kemungkinan nilai-nilai. Membiarkan atribut dimensi untuk memiliki tepat domain memungkinkan kita, misalnya, untuk menggunakan tepat Wisconsin nilai untuk atribut lokasi dalam data catatan jika kita tahu bahwa penjualan terjadi di Wisconsin namun tidak yakin tentang kota. Dalam OLAP, dimensi masing-masing memiliki hirarki yang terkait, misalnya, dimensi mungkin lokasi Kota atribut dan Negara, dengan generalisasi yang menunjukkan Negara Kota; ini menunjukkan kasus khusus alami tidak tepat disebut domain hirarkis domain, yang kita mendefinisikan berikutnya.
Definisi 3 (Domain hirarkis). Sebuah domain hirarkis H di atas dasar domain B didefinisikan menjadi tidak tepat domain atas B sehingga (1) H berisi setiap set tunggal (Yaitu, sesuai dengan beberapa unsur dari B) dan (2) untuk setiap sepasang elemen h1, h2 2 H, h1? h2 atau h1 \ h2 =;. ? Secara intuitif, setiap rangkaian tunggal adalah simpul daun dalam domain hirarki dan masingmasing mengatur non-tunggal di H adalah suatu nonleaf simpul, dengan demikian, Madison, Milwaukee, dll daun node dengan orang tua Wisconsin (yang, pada gilirannya mungkin telah USA sebagai induknya). Kita akan sering merujuk ke domain hirarkis dalam hal node daun dan nondaun, untuk kenyamanan.
Definisi 4 (Schemas Tabel Fakta dan Contoh). Sebuah fakta skema tabel adalah ha1, A2,. . . , Ak, M1,. . . , MNI dimana (i) setiap atribut dimensi Ai, saya 2 1. . . k, memiliki terkait domain dom (Ai) yang tidak tepat, dan (ii) setiap ukuran atribut Mj, j 2 1. . . n, memiliki domain yang terkait dom (Mj) yang baik numerik atau tidak pasti.Sebuah contoh database skema tabel ini sebenarnya adalah koleksi dari fakta-fakta, bentuk ha1 a2,. . . , Ak, m1,. . . , MNI dimana ai 2 dom (Ai), saya 2 1. . . k dan mj 2
dom (Mj), j 2 1. . . n. Secara khusus, jika dom (Ai) adalah hirarkis, ai dapat setiap node daun atau non-daun di dom (Ai). ?
Definisi 5 (Kawasan dan Sel). Pertimbangkan tabel fakta skema dengan dimensi atribut A1, A2,. . . , Ak. Sebuah vektor HC1, c2,. . . , CKI disebut sel jika setiap ci adalah elemen dari domain dasar Ai, saya 2 1. . . k. Wilayah dimensi vektor ha1, a2,. . . , Aki didefinisikan sebagai himpunan sel {HC1, c2,. . . , CKI | ci 2 ai, i 2 1. . . k}. Mari reg (r) menunjukkan daerah yang terkait dengan fakta r.
Proposisi 1. Pertimbangkan fakta skema tabel dengan dimensi atribut A1, A2,. . . , Ak bahwa semua memiliki hirarki domain. Pertimbangkan ruang k-dimensi di mana setiap sumbu i adalah diberi label dengan node daun dom (Ai). Untuk setiap wilayah, himpunan dari semua sel di wilayah tersebut adalah k-contiguous dimensi hiper-persegi panjang yang ortogonal terhadap sumbu. Jika setiap atribut dimensi memiliki domain hirarkis, sehingga kita memiliki interpretasi intuitif fakta masing-masing dalam database sebagai sebuah daerah di ruang k-dimensi. Jika semua ai adalah simpul daun, pengamatan adalah tepat, dan menggambarkan wilayah terdiri dari sel tunggal. Jika satu atau lebih Ai yang ditugaskan non-node daun, pengamatan adalah tidak tepat dan menggambarkan daerah k-dimensi yang lebih besar. Setiap sel di dalam daerah ini merupakan penyelesaian yang mungkin dari suatu tepat Bahkan, dibentuk dengan mengganti non-daun ai node dengan node daun dari subtree berakar di ai. Proses menyelesaikan setiap fakta tidak tepat dengan cara ini merupakan yang mungkin dunia untuk database (Bagian 4).
- Motivating Example
Pertimbangkan skenario produsen mobil dengan menggunakan CRM aplikasi untuk melacak dan mengelola permintaan layanan di seluruh di seluruh dunia agen operasi. Sebuah tabel fakta yang menggambarkan data tersebut ditunjukkan pada Tabel 1. Setiap Bahkan menggambarkan sebuah "insiden". Dua kolom pertama adalah atribut dimensi Automobile (Auto) dan Lokasi (Loc), dan mengambil nilai-nilai dari domain yang terkait hirarkis. Struktur dari domain dan daerah dari faktafakta yang ditampilkan dalam Gambar 1. Fakta yang tepat, p1-p8 pada Tabel 1, memiliki node daun ditugaskan untuk kedua atribut dimensi dan dipetakan ke yang sesuai sel dalam Gambar 1. P9 p10 dan Fakta, pada sisi lain, adalah tidak tepat. Fakta p9 ini tidak tepat karena dimensi Lokasi ditugaskan untuk node non-daun Timur dan wilayahnya mengandung sel-sel (NY, F150) dan (MA, F150). Demikian pula, wilayah untuk p10 berisi sel (TX, F150) dan (TX, Sierra). Bahkan masing-masing berisi nilai untuk atribut yang menunjukkan ukuran numerik Perbaikan biaya perbaikan yang terkait dengan insiden tersebut. Kami ingin mengklasifikasikan insiden berdasarkan jenis masalah (Misalnya, "rem", "transmisi", "kebisingan mesin" dll), seperti yang dijelaskan dalam atribut Teks tambahan. Subyektif sifat teks menghalangi klasifikasi jelas laporan layanan ke dalam jenis masalah yang berbeda. Kami dapat model ambiguitas ini dengan mendefinisikan suatu ukuran yang tidak pasti nilai-nilai yang direpresentasikan sebagai PDF di atas set masalah jenis. Namun, karena sifat
dinamis dari teks mesin analisis, jenis masalah baru akan terus ditambahkan. Oleh karena itu, tidak praktis untuk menganggap bahwa dasar domain dari jenis masalah bisa diperbaiki apriori. Untuk mengatasi ini, kita asumsikan terdapat pengklasifikasi dilatih untuk setiap jenis masalah (misalnya, lihat [30]) bahwa output probabilitas distribusi diskrit didasarkan pada analisis isi dari atribut teks; output pdf mencerminkan ketidakpastian melekat dalam pengklasifikasi tersebut. Dalam contoh tersebut, output dari classifier untuk topik rem direpresentasikan sebagai pdf lebih dari dua nilai Ya dan Tidak, dan disimpan dalam ketidakpastian Brake mengukur atribut sebagai sepasang probabilitas. (Seperti yang ditunjukkan pada Tabel 1). Namun, kami mencatat bahwa analisis semua dan algoritma disajikan selanjutnya berlaku untuk atribut dengan domain basis lebih besar dari 2.
- Query
Sementara paradigma OLAP menawarkan array kaya operator query, query dasar terdiri dari memilih sebuah node untuk satu atau lebih dimensi dan menerapkan operator agregasi untuk mengukur atribut tertentu. Misalnya, memilih Lokasi simpul TX dan node Automobile Civic dan menerapkan SUM untuk mengembalikan ukuran Perbaikan total jumlah yang dibelanjakan untuk perbaikan mobil Civic di Texas. Semua lainnya query (seperti roll-up, iris, drill-down, poros, dll) dapat digambarkan dalam hal aplikasi berulang dari dasar query. Oleh karena itu kami berkonsentrasi pada belajar semantik pertanyaan dasar dalam terang kedua ekstensi model data; ekstensi ke array penuh permintaan operator OLAP sangat mudah, dan dihilangkan karena kurangnya ruang.
Definisi 6 (Pertanyaan dan Hasil Query). Sebuah query T selama database D dengan skema ha1, A2,. . . , Ak, M1,. . . , MNI memiliki bentuk Q,, mana (a1,, ak Mi, A...): (i) a1,. . . , Ak menggambarkan wilayah k-dimensi yang dipertanyakan, (ii) Mi menggambarkan ukuran bunga, dan (iii) A adalah suatu agregasi fungsi. Hasil Q diperoleh dengan menerapkan A untuk satu set fakta MENCARI-RELEVAN (a1,..., ak, D). Hal ini dijelaskan secara rinci di bawah. ? Fungsi MENCARIRELEVAN mengidentifikasi seperangkat fakta dalam D dianggap "relevan" untuk wilayah query, dan yang sesuai definisi fungsi ini merupakan masalah penting dibahas dalam makalah ini. Semua fakta yang tepat dalam query wilayah secara alami dimasukkan, tapi kami memiliki desain yang penting keputusan sehubungan dengan fakta-fakta tidak tepat. Kami memiliki tiga pilihan: mengabaikan semua fakta tidak tepat (opsi Tidak Ada), termasuk hanya mereka yang terkandung di wilayah query (Berisi pilihan), atau mencakup semua fakta yang tidak tepat daerah tumpang tindih (yaitu, memotong) wilayah query (Tumpang tindih pilihan) -
Motivating Example (Contd.) Bagaimana menangani fakta-fakta tidak tepat saat menjawab pertanyaan adalah pusat masalah, yang sekarang kita menggambarkan melalui contoh. Pada bagian berikutnya, kita mempelajari
berbagai pilihan untuk menentukan yang relevan untuk query yang lebih ketat fakta. Kami mempertimbangkan permintaan agregat dari jenis "Apa perbaikan biaya untuk F150 di Timur ", yaitu?, agregat SUM nilai untuk atribut Perbaikan mengukur dalam kawasan itu dilambangkan oleh (F150, Timur). Semua pertanyaan yang digambarkan pada Gambar 1 sebagai kotak melampirkan wilayah query. Misalnya, di atas permintaan sesuai dengan Q5.
Untuk pertanyaan yang tumpang tindih daerah hanya fakta-fakta yang tepat, misalnya, Q1 dan Q2, himpunan fakta yang relevan jelas. Untuk lainnya query, misalnya, Q5, ini lebih sulit. Jika kita menggunakan opsi Tidak Ada, hasil dari Q5 adalah A (p1, p2); fakta tidak tepat p9 diabaikan. Jika kita menggunakan opsi Berisi, hasilnya adalah A (p1, p2, p9). Jawaban mana yang lebih baik? Menggunakan p9 untuk menjawab Q5 tampaknya masuk akal karena wilayah untuk Q5 mengandung p9, dan hasilnya mencerminkan semua data yang tersedia. Namun, ada masalah halus dengan menggunakan Berisi pilihan untuk menentukan relevan fakta. Dalam standar OLAP, jawaban untuk Q5 adalah agregat jawaban untuk Q3 dan Q4, yang jelas tidak kasus sekarang, karena Q3 = A (p2) dan Q4 = A (p1). Mengamati bahwa "tumpang tindih" p9 sel c1 = (F150, NY) dan c2 = (F150, MA), kita dapat memilih untuk menetapkan sebagian p9 untuk kedua sel, proses yang kita sebut sebagai alokasi. Para tugas parsial ditangkap oleh bobot wc1 dan wc2, sehingga wc1 + wc2 = 1, yang mencerminkan efek p9 harus terhadap nilai agregat dihitung untuk sel c1 dan c2, masing-masing. Jika opsi Tumpang tindih digunakan, maka Q3 = A (p2, wc1 p9?) Dan Q4 = A (p1, wc2 p9?). Amati pengguna "diharapkan" hubungan antara Q3, Q4, dan Q5, yang kita sebut sebagai konsistensi, sekarang dipertahankan. Dalam Selain konsistensi, ada pengertian kualitas hasil relatif terhadap kualitas input data untuk query, yang kita sebut sebagai kesetiaan. Misalnya, jawabannya dihitung untuk Q3 harus berkualitas tinggi jika p9 yang tepat dikenal. Untuk lebih menggambarkan peran alokasi, pertimbangkan permintaan Q6. Jika p10 dialokasikan untuk semua sel di wilayahnya kemudian Q6 dapat dijawab. Jika tidak, jawaban untuk Q6 tidak terdefinisi, seperti di OLAP biasa. Meskipun alokasi dapat dicapai beberapa cara masuk akal untuk mengharapkan alokasi yang adalah permintaan independen. Sebagai contoh, Q7 dan Q8 harus dijawab dengan menggunakan alokasi yang sama untuk p10. Konsistensi dan kesetiaan dibahas lebih lanjut dalam Bagian 3 dan 5. Sebuah diskusi tentang kemungkinan-dunia semantik alokasi yang mendasari disajikan dalam Bagian 4, dan algoritma alokasi dibahas dalam Bagian 6. Untuk kejelasan eksposisi, hanya pernyataan klaim teoritis termasuk dalam tubuh utama kertas. Penjelasan dan bukti-bukti dapat ditemukan di [6]. 2,5 Agregasi Tindakan Pasti Pertimbangkan query ketik "Bagaimana mungkin adalah rem masalah bagi sedan di TX? "Ini sesuai dengan permintaan Q2 mana agregasi selesai ukuran pasti 'Rem'. Jawaban untuk query ini merupakan agregasi dari yang PDF untuk p5, p6, p7, p8. Gagasan menggabungkan PDF berkaitan erat dengan masalah belajar dalam literatur statistik di bawah nama opini penyatuan [15]. Informal, penyatuan pendapat problemis untuk memberikan opini konsensus dari satu set pendapat?. Pendapat di? serta sebagai pendapat konsensus direpresentasikan sebagai PDF melalui diskrit domain O. Banyak operator penyatuan telah dipelajari, dan LinOp operator linear adalah salah satu yang paling banyak digunakan. LinOp (?) Menghasilkan P konsensus pdf yang merupakan tertimbang lPinear kombinasi dari PDF dalam, yaitu?, P (x) = P2? WP · P (x), untuk x 2 O. Di sini, bobot yang nonnegatif
jumlah summing ke satu. Kecuali ada beberapa bentuk pengetahuan sebelumnya, kita berasumsi bahwa bobot yang seragam, yaitu, WP = 1 /|?|, dalam hal ini P (x) adalah hanya rata-rata probabilitas P (x) untuk P 2?. Ini sangat mudah untuk menghitung LinOp menggunakan fungsi agregasi dalam saat ini sistem OLAP. •
OLAP Requirement
Dalam memberikan dukungan untuk OLAP queries gaya kehadiran ketidaktepatan dan ketidakpastian, kami berpendapat bahwa jawaban pertanyaan ini harus memenuhi seperangkat persyaratan yang wajar yang dapat dianggap generalisasi persyaratan dipenuhi oleh queries sistem standar OLAP. Kami mengusulkan dua persyaratan untuk penanganan ketidaktepatan, yaitu konsistensi dan kesetiaan, yang berlaku baik langkah-langkah numerik dan tidak pasti. (Beberapa persyaratan untuk penanganan ketidakpastian telah diusulkan dalam [14].) Kami menggunakan persyaratan untuk berpendapat bahwa hanya pilihan Tumpang tindih untuk penanganan hasil ketidak-akuratan dalam query berkelakuan baik di konteks dari OLAP.
- Konsistensi
Intuisi di balik persyaratan konsistensi adalah bahwa pengguna mengharapkan untuk melihat beberapa hubungan alami terus antara jawaban untuk pertanyaan yang terkait dengan agregasi yang berbeda (Terhubung) daerah dalam suatu hierarki.
Definisi 7 (?-Konsistensi). Mari? (X, x1, x2,..., Xp) akan predikat seperti bahwa argumen masingmasing? mengambil nilai-nilai dari jangkauan A. Operator agregasi tetap Pertimbangkan koleksi query Q, Q1,. . . , Qp seperti bahwa (1) wilayah query Q adalah dipartisi oleh daerah permintaan Q1,. . . , Qp, yaitu, reg (T) = [i reg (Qi) dan reg (Qi) \ reg (Q) =; untuk setiap i 6 = j, dan (2) menentukan setiap query bahwa A diterapkan untuk mengukur atribut yang sama. Mari q, q1,. . . , Qm menunjukkan set terkait jawaban di D. Kita katakan bahwa algoritma memuaskan?-Konsistensi dengan hormat untuk A jika? (q, q1,..., qp) berlaku untuk setiap database D dan untuk setiap koleksi seperti query Q, Q1,. . . , Qp. ? Gagasan konsistensi dalam semangat summarizability, diperkenalkan pada [18, 19], meskipun tujuan-tujuan khusus yang berbeda. Mengingat sifat dari data yang mendasarinya, hanya beberapa fungsi agregasi yang tepat, atau memiliki perilaku pengguna mengharapkan.
- Bentuk Spesisfik Konsistensi
Kita sekarang mendefinisikan predikat konsistensi yang tepat untuk operator agregasi dipertimbangkan dalam makalah ini, menggunakan catatan diberikan dalam definisi?-konsistensi.
Definisi 8 (Sum-konsistensi). Sum-konsistensi didefinisikan dengan q = Pi qi. ? Di atas adalah sebuah gagasan intuitif konsistensi untuk SUM dan COUNT. Karena SUM adalah fungsi SUM, distributif untuk wilayah permintaan harus sama dengan nilai yang diperoleh oleh menambahkan hasil SUM untuk sub query-daerah yang partisi wilayah tersebut. Semua pernyataan untuk SUM dalam makalah ini berlaku untuk COUNT juga, dan tidak akan secara eksplisit disebutkan dalam kepentingan ruang.
Definisi 9 (boundedness-konsistensi). Untuk numerik mengukur, ini predikat konsistensi didefinisikan sebagai Mini {} qi? q? maxi {qi}. Untuk ukuran yang tidak pasti, ketidaksetaraan di atas harus berlaku untuk probabilitas yang terkait dengan semua elemen dalam domain dasar. Secara formal, jika q (o) adalah probabilitas untuk setiap elemen o, maka Mini {qi (o)}? q (o)? maxi {qi (o)}. ? Boundedness-konsistensi secara intuitif sesuai untuk apapun operator rata-rata untuk langkahlangkah numerik dan agregasi operator untuk langkah-langkah pasti. Secara khusus, RATA-RATA untuk wilayah permintaan harus dalam batas-batas dari RATA-RATA untuk sub query-daerah yang partisi wilayah. Dalam kasus LinOp, properti yang sama harus terus unsur-bijaksana untuk PDF terkait. Sebuah konsekuensi penting dari konsistensi-? Berbagai sifat yang didefinisikan di atas adalah bahwa pilihan Berisi tidak sesuai untuk penanganan ketidaktepatan, seperti yang ditunjukkan di bawah ini:
Teorema 1. Ada permintaan agregat ada SUM yang melanggar Sum-konsistensi bila pilihan Berisi digunakan untuk menemukan fakta-fakta yang tepat yang relevan di MENCARI-RELEVAN. Teorema yang sama dapat ditampilkan untuk agregasi lainnya operator juga, tapi kami menghilangkan mereka untuk kepentingan ruang.
- Faithfulnes
Dimulai dengan D database, misalkan kita meningkatkan ketidak-akuratan di D oleh fakta-fakta pemetaan dalam database untuk daerah-daerah yang lebih besar. Kami berharap bahwa jawaban untuk setiap query pada Q ini database baru D0 akan berbeda dari jawaban asli. Fauthfulnes ini dimaksudkan untuk menangkap properti intuitif bahwa perbedaan ini harus sekecil mungkin. Karena suatu algoritma agregasi hanya akan melihat D0 sebagai masukan dan tidak menyadari database "asli" D seseorang tidak bisa berharap secara umum untuk menyatakan batas bawah dan atas yang tepat untuk ini perbedaan. Tujuan kami bukan untuk negara akan sifat lemah yang mencirikan perbedaan, misalnya, apakah itu monoton sehubungan dengan jumlah ketidaktepatan. Para definisi berikut sangat membantu dalam memformalkan kesetiaan.
Definisi 10 (Ukur-mirip Database). Kita katakan bahwa dua database D dan D0 adalah mengukursama jika D0 adalah diperoleh dari D dengan (sewenang-wenang) memodifikasi (hanya) dimensi
nilai atribut dalam setiap fakta r. Mari r0 2 D0 menotasikan Bahkan diperoleh dengan memodifikasi r 2 D, kita mengatakan bahwa r sesuai untuk r0. ? Pertimbangkan Q query seperti fakta bahwa setiap daerah baik benar-benar terkandung dalam wilayah query Q atau benar-benar disjoin dari itu. Dalam situasi seperti itu, adalah wajar untuk memperlakukan fakta seolah-olah yang tepat terhadap Q sejak ketidakakuratan dalam fakta-fakta tidak menimbulkan ambiguitas dengan terhadap wilayah query Q. Bentuk pertama dari kesetiaan meresmikan properti ini, dan diilustrasikan dalam Gambar 2a.
Definisi 11 (kesetiaan Dasar). Kita mengatakan bahwa dua mengukur-mirip databasesD andD0 secara identik tepat sehubungan dengan permintaan Q jika untuk setiap pasangan yang sesuai fakta r 2 D dan r0 2 D0, baik kedua reg (r) dan reg (r0) adalah benar-benar terkandung dalam reg (Q) atau keduanya benar-benar adalahmenguraikan fromreg (Q). Kami mengatakan bahwa algorithmsatisfies dasar kesetiaan terhadap sebuah functionA agregasi jika untuk setiap queryQ yang menggunakan A, algoritma memberikan identik jawaban untuk setiap pasangan mengukur-mirip database D dan D0 yang identik yang tepat sehubungan dengan Q.? Dasar kesetiaan memungkinkan kita untuk berpendapat bahwa ada yang pilihan ketidaktepatan penanganan dengan mengabaikan semua tidak tepat catatan adalah tidak pantas, seperti yang kita harapkan secara intuitif:
Teorema 2. SUM, COUNT, RATA-RATA dan LinOp melanggar dasar kesetiaan ketika pilihan ada digunakan untuk menangani ketidaktepatan. Teorema 1 dan 2 menunjukkan ketidaksesuaian dari Berisi dan pilihan Tidak untuk penanganan ketidaktepatan, dan kita tidak menganggap mereka lebih lanjut. Opsi yang tersisa, Tumpang tindih yaitu, adalah fokus dari upaya kami untuk sisa kertas, dan itu menimbulkan tantangan tentang bagaimana untuk menangani relevan fakta bahwa sebagian tumpang tindih wilayah query. Kami menangani masalah ini dalam bagian berikutnya menggunakan pendekatan alokasi berbasis untuk meringkas â € œpossible worldsâ thatmay € telah menyebabkan dataset tidak tepat. Bentuk berikutnya kesetiaan ini dimaksudkan untuk menangkap sama intuisi sebagai dasar dalam kesetiaan yang lebih kompleks pengaturan fakta tidak tepat yang sebagian tumpang tindih query. Kami pertama mendefinisikan memesan yang membandingkan jumlah ketidaktepatan dalam dua database sehubungan dengan Q permintaan, dalam rangka untuk alasan tentang jawaban atas Q sebagai jumlah ketidaktepatan tumbuh.
Definisi 12 (T urutan parsial). Perbaiki query T. Kita mengatakan bahwa hubungan IQ (D, D0) memegang pada dua pengukuran yang sama database D dan D0 jika semua pasangan yang sesuai fakta di D dan D0 adalah identik, kecuali untuk satu pasangan fakta r 2 D dan r0 2 D0 seperti yang reg (r0) diperoleh dari reg (r) dengan menambahkan sel c / 2 reg (Q) [reg (r). Menentukan urutan parsial Q untuk menjadi penutupan, refleksif transitif dari IQ. Gambar 2b menggambarkan definisi Q untuk query QA € "jumlah ketidaktepatan untuk setiap fakta r0 2 D0 adalah lebih besar dari kenyataan yang sesuai r 2 D tetapi hanya dalam sel luar wilayah query. Alasan untuk ini pembatasan ini adalah bahwa memungkinkan r0 memiliki proyeksi yang lebih besar
di dalam wilayah permintaan tidak selalu berarti bahwa itu adalah kurang relevan dengan Q dari r (lih. faithfulnes dasar). -
Bentuk Spesifik Faithfulnes
Sekarang kita membahas bagaimana-kesetiaan berlaku untuk agregasi operasi dipertimbangkan dalam makalah ini. SUM: Jika kita mempertimbangkan lebih dari non-SUM negativemeasure nilai, gagasan intuitif kesetiaan adalah bahwa sebagai data di daerah permintaan menjadi tidak tepat dan tumbuh di luar wilayah query, SUM harus non-meningkat. RATA-RATA dan LinOp: Sulit, sayangnya, untuk menentukan sebuah contoh yang tepat-kesetiaan untuk RATA-RATA dan LinOp. Pertimbangkan bagaimana RATA-RATA berperilaku sebagai fakta di daerah permintaan menjadi lebih tepat dan tumbuh di luar wilayah query: SUM untuk wilayah permintaan berkurang, tetapi menghitung juga menurun. Karena baik pembilang dan penyebut menurun, nilai RATA-RATA bisa baik meningkat atau menurun. Pengamatan yang sama berlaku untuk LinOp juga. •
PossibleWorlds Kami sekarang menggambarkan interpretasi yang mungkin-dunia dari database yang berisi fakta D tidak tepat, serupa dengan yang diusulkan dalam [1], sebagai pendahuluan untuk mendefinisikan semantik permintaan saat Tumpang tindih pilihan digunakan untuk mencari fakta yang relevan. Pertimbangkan r tidak tepat fakta yang peta untuk daerah R sel. Mengingat kembali dari Proposisi pembahasan berikut 1 bahwa setiap sel dalam R merupakan penyelesaian yang mungkin dari r yang menghilangkan ketidakakuratan dalam r. Mengulangi proses ini untuk setiap Bahkan tepat di D mengarah ke database yang berisi D0 hanya fakta yang tepat. Kami menyebutnya D0 dunia yang mungkin bagi D, dan kelipatan pilihan untuk menghilangkan menyebabkan ketidaktepatan pada set kemungkinan dunia untuk D. Kami menggambarkan kemungkinan dunia dalam contoh berikut. Contoh 1. Gambar 3 menunjukkan pandangan multidimensi data dalam contoh kita menjalankan (Gambar 1), bersama dengan semua empat kemungkinan dunia yang bisa dihasilkan dengan membuat dua tepat fakta p9 p10 dan tepat. Fakta p9 dapat dilakukan tepat dalam dua cara yang mungkin, menempatkannya di sel (MA, F150) atau (NY, F150). Demikian pula, p10 dapat dibuat tepat dalam dua cara yang mungkin, menempatkannya di (TX, F150) atau (TX, Sierra). Berbagai kombinasi ini (2? 2) pilihan mengarah pada kemungkinan dunia {D1, D2, D3, D4}. ? Kami menafsirkan kemungkinan dunia {D1, D2,. . . , Dm} sebagai koleksi dari "benar" database dari yang diberikan Database D diperoleh; yang likelihoods dari setiap kemungkinan dunia yang "benar" satu belum tentu sama. Untuk menangkap kemungkinan ini, kita kaitkan berat non-negatif Di wi dengan masing-masing, dinormalisasi sehingga P i wi = 1. Para bobot memberikan kita fleksibilitas untuk model perilaku yang berbeda yang menyebabkan ketidaktepatan, sementara normalisasi memungkinkan untuk interpretasi probabilistik dari kemungkinan dunia.
- Model Data Extended Jika ada k fakta tidak tepat dalam dataset D, dan wilayah untuk fakta tidak tepat engan mengandung sel ci, jumlah dunia yang mungkin adalah Qk i = 1 ci. Untuk mengatasi kompleksitas karena ini jumlah yang eksponensial kemungkinan dunia, kami mempertimbangkan Bahkan masing-masing r tidak tepat dan menetapkan probabilitas untuk "benar" nya nilai yang c, untuk setiap c sel dalam wilayahnya. Tugas untuk semua fakta tidak tepat secara kolektif (dan secara implisit) asosiasi probabilitas (bobot) dengan masing-masing dunia yang mungkin, seperti yang kita jelaskan di bawah.
Definisi 15 (Alokasi). Untuk r fakta dan sel c 2 reg (r), biarkan pc, r menyatakan probabilitas bahwa r selesai ke c di dunia yang mendasari "benar". Kami menyebutnya pc, r alokasi Bahkan r ke c sel, dan mengharuskan P c2reg (r) pc, r = 1. Pertimbangkan proses probabilistik berikut, mulai dengan database yang berisi k D fakta tidak tepat: Mandiri Bahkan untuk setiap ri tidak tepat, memilih ci sel dengan probabilitas pci, ri dan memodifikasi dimensi atribut dalam ri sehingga fakta yang dihasilkan milik ci sel. Himpunan database yang dapat timbul melalui proses ini mungkin merupakan dunia. Berat berhubungan dengan dunia kemungkinan D0 sama Qk i = 1 pci, ri. Prosedur untuk menugaskan pc, r disebut sebagai alokasi kebijakan. Hasil menerapkan kebijakan seperti ke Database D adalah D database yang dialokasikan?. Skema dari D? berisi semua kolom dari kolom D dan tambahan untuk melacak sel-sel yang memiliki alokasi ketat positif. Misalkan r Bahkan di D memiliki pengenal yang unik dinotasikan dengan ID (r). Sesuai untuk setiap fakta r 2 D, kita membuat satu set fakta (s) HID (r), r, c, pc, ri di D? untuk setiap c 2 reg (r) sehingga pc, r> 0 dan P pc, r = 1. ? Kebijakan alokasi dijelaskan secara rinci dalam Bagian 6. Ukuran dari D? hanya bertambah linear dalam jumlah tepat fakta. Namun, karena wilayah yang tidak tepat Bahkan secara eksponensial besar dalam jumlah atribut dimensi yang ditugaskan non-node daun, perawatan harus diambil dalam menentukan sel yang mendapatkan alokasi positif. Contoh 2. Sebagai contoh pada Gambar 3, anggaplah bahwa probabilitas untuk p9 adalah 0,6 dan 0,4 untuk sel (MA, F150) dan (NY, F150) masing-masing. Kemudian di D? kita akan membuat dua sesuai dengan p11-satu fakta milik (MA, F150) dengan berat badan 0,6 dan lain untuk (NY, F150) dengan berat 0,4 baik ditandai dengan identifier yang sama. Demikian pula ada 2 fakta untuk p10, milik (TX, F150) dan (TX, Sierra) dengan id yang sama, p10. ?
- Ringkasan PossibleWorlds
Bobot Alokasi menyandikan satu set kemungkinan dunia, {D1,. . . , Dm} dengan bobot terkait w1,. . . , Wm. Para Jawaban untuk query Q adalah multiset1 {v1,. . . , Vm}. Kami 1A multiset karena dunia banyak kemungkinan dapat memberikan jawaban yang sama. kiri dengan masalah semantik yang tepat untuk meringkas {V1,. . . vm}. Ingat bahwa bobot memberikan interpretasi probabilistik dari kemungkinan dunia, yaitu, database Di dipilih dengan wi probabilitas. Kami meringkas jawaban
yang mungkin {V1,. . . vm} dengan mendefinisikan suatu variabel acak diskrit, Z, terkait dengan distribusi ini. Definisi 16 (variabel Jawaban). Pertimbangkan multiset yang {V1,. . . vm} dari jawaban yang mungkin untuk query Q. Kami mendefinisikan variabel jawaban Z terkait dengan Q menjadi acak variabel dengan pdf Pr [Z = vi] = P j s.t. vi = v w, i, j 2 1,. . . , M. ? Jawaban untuk query dapat diringkas sebagai yang pertama dan kedua momen (nilai harapan dan varians) dari variabel Z. jawaban Menggunakan E [Z] untuk menjawab pertanyaan ini dibenarkan oleh teorema berikut:
Teorema 3. Kesetiaan Basic puas jika jawaban atas query dihitung dengan menggunakan nilai yang diharapkan dari jawaban variabel. Pendekatan di atas untuk meringkas kemungkinan dunia untuk menjawab pertanyaan agregasi, meskipun secara intuitif menarik, memperumit masalah karena jumlah kemungkinan dunia tumbuh secara eksponensial dalam jumlah tepat fakta. Alokasi kompak dapat mengkodekan ini secara eksponensial set besar namun tantangannya sekarang adalah untuk meringkas tanpa harus secara eksplisit menggunakan alokasi untuk iterate atas semua mungkin dunia. Sekarang kita akan memproses untuk merancang algoritma yang efisien untuk merangkum berbagai operator agregasi menggunakan model data diperpanjang. Notasi berikut ini berguna dalam deskripsi algoritma di bawah ini. Perbaiki Q permintaan yang terkait wilayah adalah q. Himpunan fakta-fakta yang berpotensi berkontribusi terhadap jawabannya adalah mereka yang memiliki alokasi positif untuk q. Jika C (r) = {c | pc, r> 0} menunjukkan himpunan sel yang Bahkan r memiliki alokasi ketat positif, diinginkan set fakta-fakta diberikan oleh R (T) = {r | C (r) \ q 6 =;}. Kita mengatakan bahwa R (T) adalah himpunan fakta calon Q. permintaan Untuk Bahkan setiap kandidat r, biarkan Yr = Yr, Q indikator 0-1 variabel acak untuk acara yang kemungkinan penyelesaian r milik q. Kami memiliki, Pr [Yr = 1] = P C2C (r) \ q pc, r Karena Yr adalah variabel acak 0-1, Pr [Yr = 1] = E [Yr]; persamaan di atas mengatakan bahwa E [thn] sama dengan jumlah alokasi r untuk wilayah permintaan dari Q. Dengan sedikit penyalahgunaan notasi, kita mengatakan bahwa E [thn] adalah alokasi r untuk Q query; itu penuh jika E [thn] = 1 dan parsial sebaliknya. Akhirnya, perhatikan bahwa asumsi kemerdekaan pada kita ketidaktepatan pemodelan menunjukkan bahwa variabel acak Tahun untuk r yang berbeda adalah statistik independen. Kami menjawab Q query dalam model data diperpanjang dalam dua langkah-langkah:
Langkah 1: Kami mengidentifikasi set fakta kandidat r 2 R (T) dan menghitung alokasi sesuai dengan Q. Mantan dilakukan dengan menggunakan filter untuk wilayah permintaan sedangkan yang terakhir dicapai oleh kelompok-kelompok mengidentifikasi darimfakta yang berbagi identifier yang sama pada kolom ID dan kemudian menyimpulkan alokasi masing-masing kelompok. Pada akhir langkah ini, kita memiliki satu set yang berisi fakta-fakta untuk Bahkan masing-masing r 2 R (T), alokasi r untuk Q dan mengukur nilai yang terkait dengan r. Perhatikan bahwa langkah ini tergantung hanya pada wilayah permintaan q.
Langkah 2: Langkah ini adalah khusus untuk operator agregasi, dan dua komentar adalah dalam rangka. Pertama, kita berusaha untuk mengidentifikasi informasi yang diperlukan untuk menghitung summarization sementara menghindari kemungkinan pencacahan dunia. Kedua, adalah mungkin dalam beberapa kasus untuk menggabungkan ini langkah kedua dengan yang pertama dalam rangka untuk mendapatkan penghematan lebih lanjut, misalnya, nilai yang diharapkan dari SUM dapat dihitung demikian. Langkah optimasi tambahan tidak akan dibahas lebih lanjut.
- SUM
Variabel acak sesuai dengan jawaban untuk SUM permintaan Q adalah diberikan oleh Z = P R2R (Q) vrYr, mana vr adalah nilai ukuran numerik untuk merekam r. Menggunakan ungkapan ini, kita efisien dapat menghitung harapan dan varians untuk SUM:
Teorema 4. Harapan dan varians dapat dihitung tepat untuk SUM oleh single pass atas set kandidat fakta. Harapan dari jumlah yang dihitung dari diperpanjang data model memenuhi Sum-konsistensi. Untuk SUM,-kesetiaan dapat dilanggar jika diperpanjang model data dibangun menggunakan kebijakan alokasi sewenang-wenang. Kami mendefinisikan kelas kebijakan alokasi yang kita dapat jaminan kesetiaan. Kebijakan alokasi tersebut akan dibahas dalam Bagian 6.
Definisi 17 (Kebijakan Alokasi monoton). Misalkan D dan D0 menjadi dua set data yang sama dengan properti yang terkait daerah adalah identik untuk setiap pasangan yang sesuai fakta, kecuali untuk satu pasangan (r, r0), r 2 D, r0 2 D0 seperti yang reg (r0) = reg (r) [{c?}, untuk beberapa c sel?. Memperbaiki kebijakan alokasi A, dan biarkan pc, r (resp. p0 c, r) menyatakan dihasilkan alokasi di D (resp. D0) dihitung dengan hormat A. Kita katakan bahwa A adalah kebijakan alokasi monotonik jika pc, s? p0 c, s untuk setiap fakta dan untuk setiap sel c 6 = c?. ? Kemonotonan adalah kuat tetapi yang wajar dan intuitif properti kebijakan alokasi. Ketika database tidak memiliki ketidaktepatan, ada dunia yang mungkin unik dengan berat badan 1. Tetapi sebagai jumlah meningkat ketidaktepatan, himpunan kemungkinan dunia akan meningkat juga. Monoton alokasi kebijakan membatasi cara di mana bobot untuk yang lebih besar set kemungkinan dunia didefinisikan. Secara khusus, sebagai wilayah semakin besar, alokasi untuk sel lama didistribusikan ke sel-sel baru.
Teorema 5. Harapan SUM memenuhi Sumfaithfulness jika kebijakan alokasi yang digunakan untuk membangun diperpanjang Model data monoton.
- RATA-RATA
Dalam hal ini, variabel acak yang sesuai untuk menjawab diberikan oleh Z = Pr2R (Q) vrYr Pr2R (Q) Yr . Sayangnya, komputasibahkan harapan menjadi sulit karena penampilan Yr di kedua pembilang dan penyebut. Seperti ditunjukkan dalam teorema berikut, kita perangkat non-sepele algoritma untuk RATA-RATA.
Teorema 6. Misalkan n dan m adalah jumlah parsial dan benar-benar dialokasikan fakta di wilayah permintaan, masing-masing. Nilai yang diharapkan tepat RATA-RATA dapat dihitung dalam waktu O (m + n3), dengan n melewati himpunan kandidat fakta. Sedangkan algoritma di atas adalah layak, biaya komputasi yang RATA-RATA tepat adalah tinggi jika jumlah sebagian fakta dialokasikan untuk Q adalah tinggi. Untuk mengatasi ini, Teorema berikut menunjukkan bahwa kita efisien dapat menghitung pendekatan untuk RATA-RATA, diberikan oleh Z = E [Pr2R (Q) vrYr] E [Pr2R (Q) Yr]
Teorema 7. Perkiraan perkiraan untuk RATA-RATA dapat dihitung dalam waktu O (m + n) menggunakan single pass atas set fakta kandidat. Kesalahan relatif dari estimasi ini diabaikan bila n? m. Asumsi n? m di teorema di atas adalah wajar terutama database karena kita berharap bahwa fraksi fakta dengan nilai-nilai yang hilang yang berkontribusi untuk query apapun akan menjadi kecil. Kami sekarang kita membandingkan dua solusi untuk RATA-RATA, yaitu estimasi perkiraan yang tepat dan dalam hal persyaratan. Pertama, kita dapat menunjukkan bahwa:
Teorema 8. Harapan yang dihitung RATA-RATA dari model data diperpanjang memenuhi kesetiaan dasar tapi melanggar boundedness-konsistensi. Di sisi lain:
Teorema 9. Perkiraan perkiraan untuk RATA-RATA didefinisikan memenuhi atas boundednesskonsistensi dan dasar kesetiaan. Teorema di atas menunjukkan tradeoff antara yang akurat dalam menjawab pertanyaan dan bersikap konsisten. Mengingat aspek efisiensi dan kesalahan relatif kecil (di bawah kondisi yang wajar) untuk estimasi perkiraan, kita mengusulkan menggunakan perkiraan untuk menjawab pertanyaan.
- Ketidakpastian Pengukuran
Pada Bagian 2.5 kita mengusulkan LinOP sebagai agregasi wajar operator untuk langkah-langkah pasti. Kita sekarang alamat masalah meringkas LinOp atas dunia mungkin. Satu pendekatan adalah untuk menghitung LinOp atas semua fakta di semua dunia secara bersamaan, dimana fakta-fakta di
dunia adalah Di mana vr mewakili vektor pdf ukuran r. ? Serupa dengan estimasi perkiraan untuk RATA-RATA, AggLinOp dapat dihitung secara efisien, dan memenuhi mirip macam persyaratan.
Teorema 10. AggLinOp dapat dihitung dalam single pass atas serangkaian fakta kandidat, dan Boundednessconsistency memenuhi dan kesetiaan dasar. •
Alokasi Kebijakan
Pada bagian sebelumnya, kami merancang algoritma yang efisien untuk operator agregasi berbagai data diperpanjang model, dan terbukti beberapa konsistensi dan kesetiaan properti. Kita sekarang beralih ke tugas membangun diperpanjang model data dari data yang tidak tepat melalui alokasi yang tepat kebijakan, yaitu, desain algoritma untuk mendapatkan pc, r untuk setiap Bahkan tidak tepat r dan setiap sel c 2 reg (r). Seperti sebelumnya biarkan A1, A2,. . . , Ak menunjukkan atribut dimensi. Untuk setiap r Bahkan, mengingat dari Proposisi 1 bahwa reg (r) sama dengan beberapa k dimensi hiper-persegi panjang C1 × C2 ×. . Ck sel., Di mana setiap Ci adalah subset dari daun node dalam dom (Ai). Setiap sel c 2 reg (r) didefinisikan oleh tupel (c1, c2,..., ck) dimana ci 2 Ci. Oleh karena itu, mengalokasikan r untuk jumlah sel c untuk mengganti atribut ke-I nilai dengan ci untuk setiap i. Ruang alokasi kebijakan sangat besar, dan untuk memudahkan diskusi, kita mengkategorikan kebijakan alokasi sebagai dimensi-independen, pengukuran tidak menyadari, atau korelasi-melestarikan.
Definisi 19 (Dimensi-independentAllocation). Alokasi kebijakan dikatakan dimensi independen jika properti berikut berlaku untuk setiap fakta r. Menduga reg (r) = C1 C2 × ×. . Ck.. Kemudian, untuk setiap i dan setiap 2 b Ci, terdapat nilai-nilai i (b) sedemikian sehingga (1) P b2Ci i (b) = 1 dan (2) jika c = (c1, c2,..., ck), kemudian pc, r = T I i (ci). ? Definisi di atas dapat ditafsirkan dalam probabilistik istilah seperti memilih secara independen untuk setiap i, node daun ci 2 Ci dengan probabilitas i (ci). Bagian (1) dalam definisi di atas memastikan bahwa saya mendefinisikan distribusi probabilitas hukum Ci. Bagian (2) mengatakan bahwa alokasi pc, r sama dengan probabilitas 2A meringkas perkiraan untuk langkah-langkah pasti yang analog dengan perkiraan yang tepat untuk RATA-RATA juga dapat didefinisikan tetapi tidak dianggap di sini karena ia memiliki kelemahan yang sama. sel c adalah dipilih oleh proses ini. Sebuah kebijakan yang seragam alokasi adalah salah satu dimana masing-masing r sebenarnya adalah seragam dialokasikan kepada setiap sel di reg (r), dan mungkin yang paling sederhana dari semua kebijakan. Kami dapat menunjukkan bahwa:
Teorema 11. Alokasi Uniform adalah dimensionindependent dan kebijakan alokasi monoton. Meskipun kebijakan ini sederhana untuk melaksanakan, kelemahan adalah bahwa ukuran model data diperpanjang (yang tergantung pada jumlah sel dengan non-probabilitas nol) menjadi prohibitively besar ketika ada fakta-fakta tidak tepat dengan daerah yang besar.
Definisi 20 (Ukur menyadari Alokasi). Alokasi kebijakan dikatakan mengukur-menyadari jika berikut memegang. Misalkan D database apapun dan membiarkan D0 diperoleh dari D oleh kemungkinan memodifikasi nilai-nilai pengukuran atribut di Bahkan masing-masing r sewenang-wenang tetapi menjaga atribut dimensi nilai dalam r utuh. Kemudian, alokasi yang dihasilkan oleh kebijakan identik untuk fakta-fakta terkait dalam D dan D0. ? Sebenarnya alokasi seragam juga merupakan measureoblivious kebijakan. Namun, secara umum, kebijakan di kelas ini tidak memerlukan dimensi menjadi mandiri. Sebuah contoh kebijakan tersebut adalah menghitung berbasis alokasi. Di sini, data dibagi menjadi dua kelompok yang terdiri dari tepat dan fakta tidak tepat. Biarkan Nc menunjukkan jumlah fakta yang tepat bahwa peta ke sel c. Untuk setiap fakta tepat r dan c sel, Dengan demikian, alokasi fakta tidak tepat ditentukan oleh distribusi dari fakta-fakta yang tepat dalam sel-sel multidimensiruang.
Teorema 12. Hitung berbasis alokasi adalah measureoblivious dan kebijakan alokasi monoton. Sebuah kelemahan potensial penghitungan berbasis alokasi yang sekali fakta-fakta tidak tepat telah dialokasikan, ada â € œrich mendapatkan richerâ € efek. Untuk memahami ini, pertimbangkan daerah. Sebelum alokasi, wilayah ini memiliki distribusi tertentu fakta yang tepat atas sel-sel daerah. Setelah menghitung alokasi berbasis, sangat dibayangkan bahwa ini distribusi mungkin berbeda secara signifikan. Dalam beberapa kasus mungkin diinginkan untuk mempertahankan distribusi asli dipamerkan oleh fakta-fakta yang tepat. Menerapkan persyaratan ini ke seluruh multi-dimensi ruang memotivasi pendahuluan korelasi kelas-melestarikan kebijakan.
Definisi 21 (Korelasi-Melestarikan Alokasi). Mari Corr () adalah fungsi korelasi yang dapat diterapkan untuk setiap database yang hanya terdiri dari fakta-fakta yang tepat. Misalkan () menjadi fungsi yang dapat digunakan untuk menghitung jarak antara hasil penerapan Corr () untuk database yang tepat. Misalkan A adalah sebarang kebijakan alokasi. Untuk setiap database yang terdiri D fakta tepat dan tidak tepat, biarkan D1, D2,. . . , Dm sebagai himpunan Ford kemungkinan dunia. Biarkan pc, ra € ™ s melambangkan alokasi diproduksi oleh A pada D. Ingat dengan definisi 15, bahwa pc, itu r menentukan wi berat untuk Di, i 2 1. . . m. Para kuantitas? (Corr (D0), P i wi · Corr (Di)) disebut korelasi jarak A terhadap D. Kami mengatakan bahwa sebuah kebijakan alokasi Sebuah korelasimelestarikan jika untuk setiap Database D, jarak korelasi A dengan hormat D minimum atas semua kebijakan. ? Dengan instantiating Corr () dengan dimensi lebih dari pdf dan mengukur atribut (A1,..., Ak, M) dan? dengan Kullback-Leibler divergence3DKL, berikut
Definisi 21, kita dapat memperoleh wi dengan meminimalkan DKL (P0, P i wiPi), di mana Pi = Corr (Di), saya 2 0. . . m. Sayangnya, ini adalah masalah optimasi yang sulit karena ada jumlah eksponensial besar kemungkinan dunia.
- Fungsi pengganti Tujuan
Misalkan P menunjukkan pdf P i wiPi dalam ekspresi di atas DKL (P0, P i wiPi), di mana itu wi ditentukan dari pc tidak diketahui, yang r. Karena P adalah pdf, arah yang tepat yang diambil dalam belajar statistik adalah memperlakukan P sebagai "Statistik model" dan mendapatkan parameter dari P dengan memaksimalkan D kemungkinan data yang diberikan sehubungan dengan P. Kami nanti akan menunjukkan bagaimana untuk mendapatkan bobot alokasi sekali kita telah memecahkan untuk parameter P. Keuntungannya dari metode ini adalah bahwa hal itu juga generalizes sangat baik untuk kasus tindakan tidak pasti, yang sekarang kita lanjutkan ke berasal di bawah ini. Ingat bahwa nilai untuk sebuah atribut ukuran yang tetap tidak pasti pada kenyataannya r adalah dilambangkan oleh vr vektor, di mana vr (o) adalah probabilitas berhubungan dengan elemen base domain o. Jika vr (o) dipandang sebagai distribusi empiris diinduksi oleh sampel diberikan yaitu (, didefinisikan oleh frekuensi dari kejadian di sampel) maka langkah-langkah pasti hanya ringkasan pengamatan beberapa individu untuk setiap fakta. Akibatnya, fungsi kemungkinan untuk kasus ini dapat ditulis juga. Setelah beberapa aljabar sederhana tetapi tidak jelas, kita memperoleh fungsi berikut tujuan yang setara dengan fungsi kemungkinan: dimana Pc adalah distribusi ukuran untuk sel c (yaitu, pdf atas domain dasar) Literatur yang luas pada optimasi nonlinier [5] menyediakan beberapa algoritma untuk mendapatkan solusi untuk di atas optimasi masalah. Tapi tujuan kami adalah untuk mendapatkan alokasi bobot pc, r, yang tidak muncul dalam tujuan ini fungsi. Untungnya, mekanika Ekspektasi yang Maksimalisasi (EM) algoritma [11] memberikan solusi elegan. Seperti dijelaskan di bawah variabel ganda dalam EM algoritma dapat secara alami terkait dengan alokasi beban sehingga memberikan link yang nyaman kembali ke kemungkinan dunia semantik. Gambar 4 menyajikan algoritma EM untuk fungsi kemungkinan. Rincian cukup standar derivasi dihilangkan untuk kepentingan ruang. Perhatikan sekarang hasil pada langkah E-mana kita memperoleh Q (c | r, o). Pada konvergensi dari algoritma ini merupakan distribusi posterior atas nilai yang berbeda c 2 reg (r). Sebuah interpretasi alternatif menyenangkan, di kami konteks, adalah untuk melihat mereka sebagai variabel ganda (lihat [21]). Dalam tampilan baik, Q (c | r, o), hampir memenuhi persyaratan kami untuk alokasi. Satu komplikasi adalah ketergantungan ditambahkan pada ukuran domain o. Setiap r kenyataannya sekarang ini sebagai alokasi banyak bobot sebagai jumlah nilai yang mungkin dari o. Hal ini konsisten dengan model data diperpanjang kami. Namun, hal ini dapat dengan mudah diperbaiki dengan marginalizingQ (c | r, o) atas o dihasilkan dalam ekspresi berikut. Alokasi kebijakan untuk numericmeasures juga bisa berasal sepanjang garis algoritma yang dijelaskan di atas dalam cara dan mudah dihilangkan dalam kepentingan ruang. •
Eksperimen Pada bagian ini kita mengevaluasi kontribusi utama dari kertas, yaitu kita ekstensi untuk OLAP untuk menangani ketidak-akuratan dan ketidakpastian. Untuk tujuan ini kita dirancang dan dilakukan percobaan untuk mengevaluasi baik skalabilitas dan kualitas. Percobaan skalabilitas ditargetkan konstruksi dan dengan query model data diperpanjang; percobaan kualitas target kinerja alokasi yang berbeda kebijakan di bawah berbagai karakteristik dari data.
- Skalabilitas dari DataModel Perpanjangan
Percobaan dilakukan pada Pentium 4 2.4GHz machinewith 1 GB physicalmemory dan disk IDE tunggal. Back-end adalah sebuah sistem database komersial relasional dengan ukuran kolam penyangga diatur ke 100 MB. Tidak terwujud views atau indeks dibangun pada data. Untuk menyediakan lingkungan yang terkendali untuk evaluasi, kita digunakan sintetis dihasilkan data yang terdiri dari 4 dimensi. Percobaan menggunakan kedua ukuran numerik dan ukuran pasti (atas base domain ukuran 2) adalah dilakukan. Semua dimensi harus domain hirarki dengan tiga tingkatan. Untuk tiga dari domain hirarkis, akar pohon yang sesuai memiliki 5 anak-anak; akar setiap anak memiliki 10 anak masing-masing (yang mengakibatkan 50 node daun); yang percabangan yang sesuai faktor untuk dimensi yang tersisa adalah 10 dan 10, masing-masing (100 node daun). Jadi, ada 12,5 juta sel dalam ruang multidimensi. Data awal terdiri dari 1 juta fakta (densitas = 1/12.5 = 8%), masing-masing dihasilkan dengan memilih (dengan probabilitas seragam) node daun dari hirarki yang sesuai untuk masing-masing dimensi. Ketidaktepatan diperkenalkan dengan mengganti daun node untuk dimensi dengan orangtua yang sesuai dalam hirarki. Untuk 50% dari fakta-fakta tidak tepat, dimensi kedua dibuat tidak tepat juga (misalnya, jika 10% dari fakta-fakta yang tidak tepat, 5% tidak tepat dalam 1 dimensi dan 5% tidak tepat dalam 2 dimensi). Gambar 5a plot waktu berjalan untuk alokasi yang berbeda kebijakan. Perhatikan bahwa mereka semua meningkat (hampir) linear sehubungan dengan jumlah record tidak tepat. Berjalan waktu memiliki 2 komponen, satu untuk memproses input data dan yang lainnya untuk menulis fakta-fakta untuk diperpanjang model data. Untuk EM komponen pertama adalah tinggi, karena adalah algoritma iteratif membutuhkan beberapa scan. Hal ini menjelaskan alasan lagi berjalan waktu dari Seragam dan Count yang hanya memerlukan satu scan. Berjalan yang lebih besar waktu untuk Uniform sehubungan dengan Count adalah karena kedua komponen. Karena kepadatan data input rendah, Seragam mengalokasikan ke sel kosong banyak, sehingga jumlah yang dialokasikan fakta diciptakan oleh Uniform signifikan lebih besar dari Perhitungan dan EM. Misalnya, dengan ketidaktepatan 25%, Seragam telah 14,5 juta fakta bahwa Count dan EMeach memiliki 2,3 juta fakta. Perbedaan relatif antara Seragam dan Hitung harus meningkatkan sebagai masukan data kepadatan berkurang. Percobaan kedua mengevaluasi kinerja standar query OLAP titik menggunakan model data diperpanjang dibuat di atas. Sebagai contoh, SUM dapat dihitung dalam SQL menggunakan template berikut: PILIH redup-nilai, SUM (mengukur berat *), DARI fakta-meja, remang-tabel MANA kualifikasi-daftar GROUP BY redup-nilai Untuk memahami perilaku runtime kita secara acak total 25 pertanyaan dengan memilih tingkat acak dan node untuk setiap dimensi. Gambar 5b menunjukkan rata-rata permintaan berjalan waktu untuk SUM. Karena perilaku runtime LinOp dan RATA-RATA (perkiraan perkiraan) adalah serupa, mereka dihilangkan dalam kepentingan ruang. Pada umumnya waktu berjalan didominasi oleh biaya I / O untuk pemindaian model data diperpanjang. Seperti yang terlihat di atas, ini jauh lebih tinggi untuk Seragam daripada Count atau EM.
- Kualitas Kebijakan Alokasi
Percobaan ini mengevaluasi bagaimana data karakteristik mempengaruhi perilaku kebijakan yang diusulkan kami alokasi. Jika semua fakta yang tepat, dependensi antara dimensi yang sempurna dikodekan dalam jumlah sel. Sebagai fakta yang menjadi tidak tepat, sebagian dari informasi ini korelasi hilang. Para kekuatan pengkodean ini terhadap kehilangan tersebut dapat diukur sebagai jumlah yang diharapkan dari catatan dalam setiap sel non-kosong. Kami mendefinisikan gagasan baru dari kepadatan sebagai pseudo-kepadatan. Secara intuitif, pseudo-density tinggi memastikan tidak ada sel kosong dibuat sebagai catatan menjadi tidak tepat. Karakteristik lain bahwa kita memilih untuk memeriksa adalah ukuran korelasi, yang menangkap pengaruh nilai dimensi pada ukuran nilai. Kami menggunakan data yang dihasilkan secara sintetis terdiri dari 2 dimensi dengan 128 daun di masing-masing dimensi (128x128 grid) dan ukuran pasti tunggal atas domain basis {Y es, Tidak ada}. Kita mulai dengan menghasilkan data yang tepat ditetapkan dengan yang diinginkan pseudo-kepadatan dan mengukur korelasi. Dari jaringan total, hanya 1 dari 8 sel memiliki catatan data (yaitu, teratur kepadatan tetap pada 12,5%). Kami kemudian pilih secara acak persentase catatan untuk membuat tepat (antara 10 - 30%). Sebuah catatan dibuat tepat dengan memperluas horizontal lebih dari 64 sel. Dari dataset yang dihasilkan tidak tepat, diperpanjang model data dibuat dengan menggunakan alokasi yang berbeda kebijakan (Uniform, Count, EM). Untuk setiap data diperpanjang model, kita menghitung agregat LinOp pada setiap sel dalam grid. Jika sebuah sel kosong, maka kita menetapkan distribusi seragam atas domain ukuran pasti (misalnya, sel-sel kosong ditugaskan nilai (0,5, 0,5) dalam kasus ini). Kualitas metrik adalah perbedaan mutlak ratarata untuk hasil sebagai dibandingkan dengan data yang tepat asli ditetapkan. Gambar 6a memperlihatkan hasil percobaan menunjukkan efek pseudo-kepadatan. Data itu dihasilkan sehingga tidak ada korelasi antara ukuran dan dimensi. Kepadatan pseudo-ditetapkan untuk 1 (yaitu, tak kosong masing-masing sel berisi catatan tunggal). Hasil penelitian menunjukkan bahwa Kebijakan alokasi Uniform memiliki com-kesalahan yang lebih rendah relatif dibandingkan dengan Count dan EM. Alasan untuk ini adalah hilangnya dimensi-nilai korelasi informasi ketika sebuah record dibuat tidak tepat. Sebagai contoh, jika r catatan dalam sel c dibuat tidak tepat, c menjadi kosong, karena r adalah catatan hanya dalam sel itu. Selama alokasi, Count dan EM tidak akan mengalokasikan setiap bagian dari r untuk c. Di sisi lain, Seragam akan mengalokasikan sebagian dari r ke c, menghasilkan alokasi yang lebih baik (yaitu, salah satu yang lebih mencerminkan jawaban yang benar). Gambar 6b menunjukkan hasil untuk percobaan serupa, namun dengan dataset memiliki pseudo-kepadatan 4. Sekali lagi, ada tidak ada korelasi antara ukuran dan dimensi. Sejak pseudo-kepadatan lebih tinggi, kurang dimensi-nilai korelasi informasi yang hilang sebagai catatan lebih menjadi tidak tepat. Jadi Hitung dan EM menghasilkan alokasi yang lebih baik, sedangkan Seragam menderita karena mengabaikan korelasi yang tersedia informasi dan mengalokasikan ke sel kosong juga. Gambar 6c menunjukkan hasil untuk satu set data yang memiliki tinggi korelasi antara ukuran dan nilai-nilai dimensi. Data dihasilkan sehingga catatan pada paruh kiri grid memiliki probabilitas ukuran yang tinggi untuk Y es sedangkan di bagian kanan memiliki probabilitas yang lebih besar untuk No Pseudo-kepadatan masih diatur ke 4. Hasil menunjukkan bahwa EM kini secara
signifikan performanya melebihi Hitung dan Seragam. Hal ini karena EM menggunakan korelasi antara ukuran dan dimensi saat melakukan alokasi, Hitung sedangkan tidak. Sebagai contoh, mempertimbangkan catatan r di kiri setengah dari grid yang dibuat tidak tepat untuk tumpang tindih beberapa sel di bagian kanan. Hitungan akan mengalokasikan r untuk sel-sel di bagian kanan, sedangkan EM akan mengalokasikan r hanya ke sel di kiri setengah karena pemberitahuan korelasi antara nilai r dan ukuran sel-sel di paruh kiri. Arah Masa Depan 8 Sebuah aspek penting dari makalah ini adalah penanganan pasti langkah-langkah sebagai fungsi distribusi probabilitas (PDF). Para contoh data pada Tabel 1 memberikan pandangan konseptual ini model dengan kolom "pdf" tipe untuk Rem. Berdasarkan asumsi-asumsi dari model yang dibahas dalam makalah ini, menambahkan mengukur pasti baru (misalnya, Transmisi) akan menghasilkan di kolom lain dengan jenis yang sama "pdf". Sebuah jelas generalisasi adalah untuk menangkap hubungan antara kedua langkah tidak pasti. Pertimbangkan query dari jenis "Berapa besar kemungkinan adalah Rem dan Transmisi masalah di Camry didorong di Texas? ". Agregasi ini lebih rumit permintaan memerlukan informasi dependensi tambahan antara dua uncertainmeasures dan ini dapat ditangkap sebagai set kendala baik yang diberikan oleh pengguna atau dipelajari dari data. Lebih umum kami percaya bahwa pendekatan yang diprakarsai generalizes sini untuk menangani aspek-aspek yang lebih umum ketidakpastian-penanganan dalam DBMS, dan kami secara aktif menyelidiki generalisasi ini.
