XML (Extensible Markup Language) telah menjadi standar untuk representasi data dan pertukaran data dalam aplikasi Web. Dengan pesatnya perkembangan Internet, terutama meluasnya penggunaan e-commerce, layanan Web, dan aplikasi lainnya, data tipe XML telah menjadi yang terkini. formulir data utama. Oleh karena itu, teknologi pengelolaan data XML, khususnya teknologi kueri data XML, telah menjadi hotspot penelitian saat ini.
Dibandingkan dengan data relasional, XML memiliki berbagai keunggulan, namun kelemahan terbesarnya adalah efisiensinya. Karena pada file data relasional, nama field data hanya perlu muncul satu kali, sedangkan pada file data XML, nama elemen akan muncul berulang kali, yang tentunya akan mempengaruhi efisiensi query. Untuk meningkatkan efisiensi kueri XML sebanyak mungkin, perlu disediakan fungsi pengindeksan untuk tipe XML.
Konsorsium World Wide Web mengidentifikasi XPath 2.0 dan XQuery 1.0 sebagai standar yang direkomendasikan pada tanggal 23 Januari 2007, mengakhiri situasi sebelumnya di mana berbagai bahasa kueri bersaing untuk mendapatkan dominasi. Berdasarkan standar ini, selain pabrikan tradisional, berbagai lembaga penelitian ilmiah telah mengusulkan implementasi XPath dan XQuery (ada lebih dari selusin yang disebutkan dalam literatur), dengan model penyimpanan berbeda, algoritme kueri berbeda, dan metode pengoptimalan Dalam konteks ini, Perusahaan Database Dameng juga mengusulkan model mesin kueri XML-nya sendiri berdasarkan strategi pengembangannya sendiri. Saat ini, mesin kueri XML Dameng sedang dalam pengembangan intensif, dan pembuatan indeks yang efektif untuk data XML merupakan faktor penting yang mempengaruhi XML kinerja kueri data. Berdasarkan analisis mendalam terhadap teknologi pengindeksan produk database yang ada, struktur indeks yang lebih masuk akal dirancang untuk mesin kueri XML Dameng sehingga mesin dapat mencapai kinerja optimal.
Pengenalan teknologi indeks XML
Saat ini, penelitian masyarakat tentang XML terutama dibagi menjadi dua aspek. Salah satunya adalah database asli untuk penyimpanan, kueri, dan pengelolaan data semi-terstruktur seperti XML. Data dan metadata sepenuhnya diekspresikan dalam struktur XML dan tidak ada hubungannya dengan format penyimpanan data yang mendasarinya (seperti model objek, model relasional). , dll.). Cara lainnya adalah konversi timbal balik antara database relasional dan database relasional, menggunakan teknologi database relasional yang matang untuk memproses data XML. Karena arah terakhir memiliki arti yang lebih praktis, hal ini telah menjadi fokus penelitian XML.
Selain solusi penyimpanan, teknologi indeks juga menjadi salah satu faktor terpenting dalam menentukan suatu sistem database. Jika tidak ada struktur indeks yang dibuat untuk dokumen XML, maka kueri apa pun untuk data XML kemungkinan besar akan melintasi seluruh pohon dokumen. Seiring bertambahnya kumpulan data XML, overhead ini tidak dapat ditoleransi. Oleh karena itu, penelitian tentang teknologi indeks XML memiliki nilai teoritis dan praktis yang tinggi.
Meskipun teknologi pengindeksan tradisional telah relatif matang setelah akumulasi jangka panjang, jenis teknologi pengindeksan ini terutama berfokus pada fungsi menemukan catatan data berdasarkan nilai (bukan pola dengan hubungan tertentu), dan tidak terlalu memperhatikan hubungan logis antara catatan data.;Fitur dasar kueri data XML adalah mengekstrak data yang sesuai dengan pola berdasarkan masukan fitur pola (hubungan struktural yang dijelaskan dalam bentuk ekspresi jalur reguler). indeks adalah merancang teknologi yang cocok untuk pencocokan pola.
Klasifikasi indeks XML
Indeks XML berbasis jalur
Indeks berbasis jalur didasarkan pada informasi jalur dari node dalam struktur pohon XML, dan mengadopsi metode reduksi tertentu sehingga struktur pohon yang direduksi hanya mempertahankan informasi jalur yang berbeda dan tidak ada Dua node dengan jalan yang sama. Indeks yang telah diusulkan meliputi: Indeks DataGuides, Indeks Fabric Index, Indeks Jalur Adaptif untuk Data XML (APEX)
Indeks Dataguides adalah ringkasan struktural dari jalur yang disempurnakan mulai dari simpul akar. Jalur string yang dibentuk dengan menggabungkan label tepi hanya dijelaskan satu kali dalam Panduan Data. Panduan data mengurangi jumlah node yang diperlukan saat melintasi kueri jalur, dan efisien dalam melintasi dokumen XML dari akarnya. Namun, kueri jalur yang berisi karakter wildcard atau kueri jalur dengan sumbu turunan atau mandiri yang ditentukan dalam standar XPath memerlukan beberapa operasi koneksi, sehingga menghasilkan efisiensi kueri yang rendah dan redundansi data.
Kemudian tulis file objek Java TestLob.java tentang dua bidang besar ini, dan tentukan tipenya sebagai bidang atribut CLOB dan BLOB sebagai tipe String dan byte[] masing-masing. Karena CLOB adalah tipe teks besar, ini sesuai dengan tipe String di Java , BLOB adalah memproses beberapa file besar yang tidak didefinisikan secara ketat dan disimpan dalam bentuk aliran biner, jadi biarkan menggunakan tipe byte[], lalu tentukan metode Getter dan Setter dari kedua properti ini masing-masing kodenya adalah sebagai berikut:
Indeks panduan data berasal dari simpul akar Ringkasan struktural dari jalur penyempurnaan awal. Jalur string yang dibentuk dengan menggabungkan label tepi hanya dijelaskan satu kali dalam Panduan Data. Panduan data mengurangi jumlah node yang diperlukan saat melintasi kueri jalur, dan efisien dalam melintasi dokumen XML dari akarnya. Namun, kueri jalur yang berisi karakter wildcard atau kueri jalur dengan sumbu turunan atau mandiri yang ditentukan dalam standar XPath memerlukan beberapa operasi koneksi, sehingga menghasilkan efisiensi kueri yang rendah dan redundansi data.
Index Fabric adalah struktur indeks yang dikembangkan pada pohon Patricia Trie. Ini mengkodekan setiap jalur yang ditandai ke setiap node elemen dengan string, dan kemudian memasukkan nilai-nilai yang disandikan ini ke dalam pohon Patricia Trie, sehingga mengonversi kueri data XML sesuai dengan pohon Patricia Trie. jalur ke kueri string. Saat membuat kueri, pertama-tama enkode jalur kueri ke dalam bentuk string, lalu cari di pohon indeks. Keuntungan indeks Index Fabric adalah ia menyimpan informasi struktur hierarki data XML, menangani pengambilan data XML secara seragam dengan informasi skema dan tanpa skema, dan membuat waktu yang diperlukan untuk menanyakan dan memperbarui data XML terkait dengan hierarki daripada ke Panjang kunci indeks terkait. Kerugian dari indeks Index Fabric adalah kehilangan hubungan struktural antar node elemen, karena hanya menyimpan informasi node elemen dengan nilai teks. Oleh karena itu, mirip dengan indeks DataGuides, indeks Index Fabric tidak efisien dalam menangani ekspresi kueri yang cocok sebagian dengan sumbu keturunan atau mandiri yang ditentukan dalam standar XPath.
Untuk tujuan ini, APEX [14] memperkenalkan informasi yang bergantung pada distribusi data XML queries. : Node label pra-simpan yang sesuai dengan pernyataan kueri XML yang sering muncul dalam struktur hash. Fungsinya mirip dengan fungsi Cache: ketika kueri baru memerlukan pemrosesan, ia terlebih dahulu mencari tabel hash untuk melihat apakah ada kumpulan simpul yang memuaskan. Namun kurang efisien untuk ekspresi query dengan nilai elemen atau nilai atribut.
Indeksberbasis node
Indeks berbasis node pada dasarnya menguraikan data XML menjadi kumpulan data unit data, dan pada saat yang sama menyimpan informasi lokasi unit dalam data XML dalam catatan. Tidak seperti indeks berbasis jalur, indeks berbasis simpul mendobrak batasan bahwa simpul harus ditemukan melalui jalur label dan menguraikan data XML menjadi catatan simpul dalam bentuk kanonik. Karena menyimpan informasi lokasi node dan dapat diintegrasikan dengan baik ke dalam sistem manajemen basis data relasional yang matang, indeks ini saat ini merupakan indeks yang paling banyak digunakan.
Menurut metode pengkodean informasi lokasi yang berbeda, indeks berbasis node secara umum dapat dibagi ke dalam kategori berikut:
1. Indeks berbasis awalan
. Indeks berbasis awalan terutama merupakan indeks yang dihasilkan berdasarkan pengkodean Dewey [12], dan pengkodean ORDPATH literatur [13] Metode serupa diadopsi, dan metode kompresi ORDPATH diberikan, yang telah diterapkan pada organisasi indeks SQL Server 2005.
Ide dasar dari pengkodean awalan adalah dengan menggunakan langsung pengkodean dari simpul induk suatu simpul sebagai awalan dari pengkodean simpul tersebut. Untuk pengkodean awalan, untuk menentukan apakah suatu simpul v merupakan turunan dari simpul lain u, Anda hanya perlu menentukan apakah pengkodean u merupakan awalan dari pengkodean v. . Properti penting dari indeks pengkodean awalan adalah pengurutan kamusnya: untuk setiap simpul u dalam subpohon yang berakar pada simpul r, pengkodean awalannya c(u) lebih besar (kurang dari) subpohon saudara kirinya (subpohon saudara kanan) ) Pengkodean awalan dari semua node di . Oleh karena itu, indeks berbasis awalan tidak hanya dapat secara efektif mendukung penghitungan hubungan penyertaan, tetapi juga secara efektif mendukung penghitungan hubungan posisi dokumen.
2. Indeks berdasarkan pengkodean interval
Untuk indeks pengkodean interval, setiap node di pohon T diberi kode interval [mulai, akhir], yang memenuhi: kode interval suatu node mencakup kode interval dari node turunannya mengatakan, node u di pohon T adalah nenek moyang dari node v, jika dan hanya jika
skema pengkodean interval pertama dari start(u) adalah pengkodean Dietz, setiap node di pohon T diberi nomor urut traversal pre-order dan Post- Tuple nomor urut traversal pesanan karena node leluhur u di pohon T harus muncul sebelum (setelah) node keturunannya v dalam traversal pre-order (traversal pasca-order), oleh karena itu, node u dan v adalah hubungan Leluhur/keturunan. , jika dan hanya jika pra(u)
Contoh umum lainnya dari indeks pengkodean interval adalah indeks XISS, yang menetapkan pasangan nomor untuk setiap node, dengan order adalah pengkodean praorder yang diperluas dan ukuran adalah turunan dari cakupan node. Untuk setiap node X dan Y dalam pohon dokumen, jika dan hanya jika
indeks order(x) XISS menguraikan pernyataan kueri asli menjadi subekspresi. Kemudian implementasikan kueri untuk sub-ekspresi ini, dan terakhir gabungkan hasil antara ini untuk mendapatkan kumpulan hasil kueri. Ini dapat lebih mendukung pernyataan kueri yang berisi karakter wildcard. Namun, ia memperoleh hasil kueri akhir setelah menggabungkan setiap hasil antara. Meskipun metode seperti itu memang dapat menyelesaikan semua masalah wildcard, penggabungan hasil antara tersebut kemungkinan akan sangat memakan waktu, terutama untuk ekspresi sederhana dengan jalur yang panjang.
Perbandingan dua mekanisme pengindeksan.
Pengindeksan berbasis jalur terutama didasarkan pada strategi penggabungan node. Melalui teknik seperti kesetaraan node dan kesetaraan jalur, diperoleh struktur indeks yang jauh lebih kecil dari dokumen aslinya , jadi saat memproses kueri, pada dasarnya Anda masih harus melintasi seluruh pohon indeks untuk mendapatkan hasilnya. Indeks berbasis jalur dapat mendukung kueri ekspresi jalur sederhana dengan sangat baik, namun untuk ekspresi jalur reguler, ini tidak berfungsi dengan baik.
Indeks berbasis node mengindeks setiap node melalui teknologi pengkodean. Hubungan struktural antar node dapat ditentukan dalam waktu yang konstan melalui pengkodean. Ini dapat mendukung ekspresi jalur reguler dengan baik, tetapi untuk ekspresi jalur yang panjang, terutama ketika pembuatan kueri Ketika ada banyak hasil antara, operasi gabungan indeks simpul itu mahal.
Pengindeksan berbasis jalur dan pengindeksan berbasis simpul masing-masing memiliki kelebihan dan kekurangan masing-masing, namun dapat saling melengkapi. Saat ini, dalam aplikasi praktis, pengindeksan berbasis node lebih banyak digunakan dan penelitiannya relatif matang. Oleh karena itu, penelitian Perusahaan Dameng tentang struktur indeks XML terutama berfokus pada pengindeksan berbasis node, dan melakukan perbaikan yang sesuai dengan mengacu pada pengindeksan berbasis jalur. .