เทคโนโลยีการสืบค้นข้อมูล XML กลายเป็นหัวข้อวิจัยที่ร้อนแรงในปัจจุบัน

เมื่อเปรียบเทียบกับข้อมูลเชิงสัมพันธ์แล้ว XML มีข้อดีหลายประการ แต่ข้อเสียเปรียบที่ใหญ่ที่สุดคือประสิทธิภาพ เนื่องจากในไฟล์ข้อมูลเชิงสัมพันธ์ ชื่อเขตข้อมูลจะต้องปรากฏเพียงครั้งเดียว ในขณะที่ในไฟล์ข้อมูล XML ชื่อองค์ประกอบจะปรากฏขึ้นซ้ำๆ ซึ่งจะส่งผลต่อประสิทธิภาพของแบบสอบถามอย่างแน่นอน เพื่อปรับปรุงประสิทธิภาพการสืบค้นของ XML ให้มากที่สุดเท่าที่จะเป็นไปได้ จำเป็นต้องมีฟังก์ชันการจัดทำดัชนีสำหรับประเภท XML

World Wide Web Consortium ระบุว่า XPath 2.0 และ XQuery 1.0 เป็นมาตรฐานที่แนะนำเมื่อวันที่ 23 มกราคม 2550 ซึ่งยุติสถานการณ์ก่อนหน้านี้ซึ่งภาษาคิวรีต่างๆแข่งขันกันเพื่อครอบงำ ตามมาตรฐานนี้ นอกเหนือจากผู้ผลิตแบบดั้งเดิมแล้ว สถาบันวิจัยทางวิทยาศาสตร์หลายแห่งยังได้เสนอการใช้งาน XPath และ XQuery (มีการกล่าวถึงมากกว่าหนึ่งโหลในวรรณกรรม) โดยมีรูปแบบการจัดเก็บข้อมูลที่แตกต่างกัน อัลกอริธึมแบบสอบถามที่แตกต่างกัน และวิธีการเพิ่มประสิทธิภาพ บริบทนี้ บริษัทฐานข้อมูล Dameng ยังเสนอโมเดลกลไกการสืบค้น XML ของตนเองตามกลยุทธ์การพัฒนาของตนเอง ปัจจุบัน กลไกการสืบค้น XML ของ Dameng อยู่ระหว่างการพัฒนาอย่างเข้มข้น และการสร้างดัชนีที่มีประสิทธิภาพสำหรับข้อมูล XML ถือเป็นปัจจัยสำคัญที่ส่งผลต่อ XML ประสิทธิภาพการสืบค้นข้อมูล จากการวิเคราะห์เชิงลึกของเทคโนโลยีการจัดทำดัชนีของผลิตภัณฑ์ฐานข้อมูลที่มีอยู่ โครงสร้างดัชนีที่สมเหตุสมผลมากขึ้นได้รับการออกแบบสำหรับกลไกการสืบค้น Dameng XML เพื่อให้กลไกสามารถบรรลุประสิทธิภาพสูงสุด

ความรู้เบื้องต้นเกี่ยวกับเทคโนโลยีดัชนี XML

ปัจจุบันการวิจัยของผู้คนเกี่ยวกับ XML แบ่งออกเป็นสองส่วนเป็นหลัก หนึ่งคือฐานข้อมูลดั้งเดิมสำหรับการจัดเก็บ การสืบค้น และการจัดการข้อมูลกึ่งโครงสร้าง เช่น XML ข้อมูลและเมตาดาต้าจะแสดงออกมาอย่างสมบูรณ์ในโครงสร้าง XML และไม่เกี่ยวข้องกับรูปแบบการจัดเก็บข้อมูลที่สำคัญ (เช่น โมเดลออบเจ็กต์ โมเดลเชิงสัมพันธ์ ฯลฯ) อีกประการหนึ่งคือการแปลงร่วมกันระหว่างฐานข้อมูลกับฐานข้อมูลเชิงสัมพันธ์ โดยใช้เทคโนโลยีที่สมบูรณ์ของฐานข้อมูลเชิงสัมพันธ์เพื่อประมวลผลข้อมูล XML เนื่องจากทิศทางหลังมีความสำคัญในทางปฏิบัติมากกว่า จึงกลายเป็นจุดสนใจของการวิจัย XML

นอกเหนือจากโซลูชันการจัดเก็บข้อมูลแล้ว เทคโนโลยีดัชนียังเป็นหนึ่งในปัจจัยที่สำคัญที่สุดในการกำหนดระบบฐานข้อมูลอีกด้วย หากไม่มีการสร้างโครงสร้างดัชนีสำหรับเอกสาร XML การสืบค้นข้อมูล XML ก็มีแนวโน้มที่จะส่งผลให้เกิดการข้ามแผนผังเอกสารทั้งหมด เมื่อชุดข้อมูล XML เพิ่มขึ้น โอเวอร์เฮดนี้จึงทนไม่ได้ ดังนั้นการวิจัยเทคโนโลยีดัชนี XML จึงมีคุณค่าทั้งทางทฤษฎีและปฏิบัติสูง

แม้ว่าเทคโนโลยีการจัดทำดัชนีแบบดั้งเดิมจะค่อนข้างเติบโตหลังจากการสะสมในระยะยาว แต่เทคโนโลยีการจัดทำดัชนีประเภทนี้มุ่งเน้นไปที่ฟังก์ชั่นการค้นหาบันทึกข้อมูลตามค่าเป็นหลัก (แทนที่จะเป็นรูปแบบที่มีความสัมพันธ์บางอย่าง) และไม่ได้ให้ความสนใจมากนักกับ ความสัมพันธ์เชิงตรรกะระหว่างบันทึกข้อมูล ; คุณลักษณะพื้นฐานของแบบสอบถามข้อมูล XML คือการดึงข้อมูลที่สอดคล้องกับรูปแบบตามการป้อนข้อมูลของคุณลักษณะรูปแบบ (ความสัมพันธ์เชิงโครงสร้างที่อธิบายไว้ในรูปแบบของการแสดงออกเส้นทางปกติ) ดัชนีคือการออกแบบเทคโนโลยีให้เหมาะสมกับการจับคู่รูปแบบ

การจำแนกประเภทดัชนี XML

ดัชนี XML ตามเส้นทาง

ดัชนีตามเส้นทางจะขึ้นอยู่กับข้อมูลเส้นทางของโหนดในโครงสร้างแผนภูมิ XML และใช้วิธีการลดขนาดบางอย่างเพื่อให้โครงสร้างต้นไม้ที่ลดลงจะรักษาข้อมูลเส้นทางที่แตกต่างกันเท่านั้นและไม่มีอยู่ สองโหนดที่มี เส้นทางเดียวกัน ดัชนีดังกล่าวที่ได้รับการเสนอ ได้แก่ ดัชนี DataGuides ดัชนี Index Fabric ดัชนี Adaptive Path สำหรับข้อมูล XML (APEX)

ดัชนี Dataguides เป็นการสรุปโครงสร้างของเส้นทางที่ได้รับการปรับปรุงโดยเริ่มต้นจากโหนดรูท เส้นทางสตริงที่เกิดจากการต่อป้ายกำกับขอบเข้าด้วยกันจะอธิบายเพียงครั้งเดียวใน Dataguides Dataguides ช่วยลดจำนวนโหนดที่ต้องใช้ในการสำรวจเส้นทาง และมีประสิทธิภาพในการข้ามเอกสาร XML จากราก อย่างไรก็ตาม การสืบค้นเส้นทางที่มีอักขระตัวแทนหรือการสืบค้นเส้นทางที่มีแกนสืบทอดหรือตนเองที่กำหนดไว้ในมาตรฐาน XPath จำเป็นต้องมีการดำเนินการเชื่อมต่อหลายครั้ง ส่งผลให้ประสิทธิภาพการสืบค้นต่ำและความซ้ำซ้อนของข้อมูล

จากนั้นเขียนไฟล์อ็อบเจ็กต์ Java TestLob.java เกี่ยวกับฟิลด์ขนาดใหญ่ทั้งสองนี้ และกำหนดประเภทเป็นฟิลด์แอ็ตทริบิวต์ CLOB และ BLOB เป็นประเภท String และ byte[] ตามลำดับ เนื่องจาก CLOB เป็นประเภทข้อความขนาดใหญ่ จึงสอดคล้องกับประเภท String ใน Java BLOB คือการประมวลผลไฟล์ขนาดใหญ่บางไฟล์ที่ไม่ได้กำหนดไว้อย่างเคร่งครัดและถูกจัดเก็บในรูปแบบของสตรีมไบนารี่ ดังนั้นปล่อยให้มันใช้ประเภท byte[] จากนั้นกำหนดวิธีการ Getter และ Setter ของคุณสมบัติทั้งสองนี้ตามลำดับ รหัสดังต่อไปนี้

ดัชนี Dataguides มาจากโหนดราก สรุปโครงสร้างของเส้นทางการปรับแต่งเริ่มต้น เส้นทางสตริงที่เกิดจากการต่อป้ายกำกับขอบเข้าด้วยกันจะอธิบายเพียงครั้งเดียวใน Dataguides Dataguides ช่วยลดจำนวนโหนดที่ต้องใช้ในการสำรวจเส้นทาง และมีประสิทธิภาพในการข้ามเอกสาร XML จากราก อย่างไรก็ตาม การสืบค้นเส้นทางที่มีอักขระตัวแทนหรือการสืบค้นเส้นทางที่มีแกนสืบทอดหรือตนเองที่กำหนดไว้ในมาตรฐาน XPath จำเป็นต้องมีการดำเนินการเชื่อมต่อหลายครั้ง ส่งผลให้ประสิทธิภาพการสืบค้นต่ำและความซ้ำซ้อนของข้อมูล

Index Fabric เป็นโครงสร้างดัชนีที่พัฒนาบนแผนผัง Patricia Trie โดยจะเข้ารหัสแต่ละเส้นทางที่ทำเครื่องหมายไว้ไปยังแต่ละโหนดองค์ประกอบด้วยสตริง จากนั้นแทรกค่าที่เข้ารหัสเหล่านี้ลงในแผนผัง Patricia Trie ดังนั้นจะแปลงแบบสอบถามข้อมูล XML ตาม เส้นทางเข้าสู่แบบสอบถามของสตริง เมื่อทำการสอบถาม ขั้นแรกให้เข้ารหัสเส้นทางการสืบค้นในรูปแบบสตริง จากนั้นค้นหาในแผนผังดัชนี ข้อดีของดัชนี Index Fabric คือ เก็บข้อมูลโครงสร้างลำดับชั้นของข้อมูล XML จัดการการดึงข้อมูล XML อย่างสม่ำเสมอด้วยข้อมูลสคีมาและแบบไม่มีสคีมา และทำให้ต้องใช้เวลาในการสืบค้นและอัปเดตข้อมูล XML ที่เกี่ยวข้องกับลำดับชั้นมากกว่า ความยาวของคีย์ดัชนีมีความสัมพันธ์กัน ข้อเสียของดัชนี Index Fabric คือ สูญเสียความสัมพันธ์เชิงโครงสร้างระหว่างโหนดองค์ประกอบ เนื่องจากจะเก็บข้อมูลของโหนดองค์ประกอบที่มีค่าข้อความเท่านั้น ดังนั้น เช่นเดียวกับดัชนี DataGuides ดัชนี Index Fabric จึงไม่มีประสิทธิภาพในการจัดการนิพจน์คิวรีที่ตรงกันบางส่วนด้วยแกนสืบทอดหรือแกนตนเองที่กำหนดไว้ในมาตรฐาน XPath

ด้วยเหตุนี้ APEX [14] จึงแนะนำข้อมูลที่อาศัยการกระจายข้อมูล XML แบบสอบถาม : บันทึกโหนดป้ายกำกับล่วงหน้าที่สอดคล้องกับคำสั่งแบบสอบถาม XML ที่เกิดขึ้นบ่อยครั้งในโครงสร้างแฮช ฟังก์ชันจะคล้ายกับฟังก์ชันของ Cache: เมื่อแบบสอบถามใหม่ต้องมีการประมวลผล อันดับแรกจะค้นหาตารางแฮชเพื่อดูว่ามีชุดโหนดที่น่าพอใจหรือไม่ แต่จะมีประสิทธิภาพน้อยกว่าสำหรับนิพจน์แบบสอบถามที่มีค่าองค์ประกอบหรือค่าแอตทริบิวต์

ตามโหนด

ดัชนีตามโหนดจะแยกย่อยข้อมูล XML ลงในชุดบันทึกของหน่วยข้อมูล และในเวลาเดียวกันจะบันทึกข้อมูลตำแหน่งของหน่วยในข้อมูล XML ในบันทึก ต่างจากดัชนีตามเส้นทาง ดัชนีตามโหนดทำลายข้อจำกัดที่ต้องพบโหนดผ่านเส้นทางเลเบล และแยกย่อยข้อมูล XML ลงในบันทึกโหนดในรูปแบบมาตรฐาน เนื่องจากจะบันทึกข้อมูลตำแหน่งของโหนดและสามารถรวมเข้ากับระบบการจัดการฐานข้อมูลเชิงสัมพันธ์ที่ครบถ้วนได้ดี ดัชนีดังกล่าวจึงเป็นดัชนีที่ใช้กันอย่างแพร่หลายในปัจจุบัน

ตามวิธีการเข้ารหัสข้อมูลตำแหน่งที่แตกต่างกัน โดยทั่วไปดัชนีตามโหนดสามารถแบ่งออกเป็นประเภทต่างๆ ดังต่อไปนี้:

1. ดัชนี

ตามคำนำหน้า ดัชนีตามคำนำหน้าส่วนใหญ่เป็นดัชนีที่สร้างจากการเข้ารหัส Dewey [12] และการเข้ารหัส ORDPATH ของวรรณกรรม [13] มีการนำวิธีการที่คล้ายกันมาใช้ และวิธีการบีบอัด ORDPATH ได้ถูกนำไปใช้กับองค์กรดัชนีของ SQL Server 2005

แนวคิดพื้นฐานของการเข้ารหัสคำนำหน้าคือการใช้การเข้ารหัสของโหนดหลักของโหนดโดยตรงเป็นคำนำหน้าของการเข้ารหัสของโหนด สำหรับการเข้ารหัสคำนำหน้าเพื่อตรวจสอบว่าโหนด v เป็นผู้สืบทอดของโหนดอื่นหรือไม่ คุณเพียงแค่ต้องกำหนดเท่านั้น ว่าการเขียนโค้ดของ u นั้นเป็นคำนำหน้าของการเขียนโค้ดของ v หรือไม่ คุณสมบัติที่สำคัญของดัชนีการเข้ารหัสคำนำหน้าคือการเรียงลำดับพจนานุกรม: สำหรับโหนดใด ๆ u ในทรีย่อยที่รูทที่โหนด r การเข้ารหัสคำนำหน้า c(u) นั้นมากกว่า (น้อยกว่า) ทรีย่อยพี่น้องด้านซ้าย (ทรีย่อยพี่น้องด้านขวา) ) การเข้ารหัสคำนำหน้า ของโหนดทั้งหมดใน . ดังนั้น ดัชนีตามคำนำหน้าไม่เพียงแต่สนับสนุนการคำนวณความสัมพันธ์แบบรวมได้อย่างมีประสิทธิภาพ แต่ยังสนับสนุนการคำนวณความสัมพันธ์ตำแหน่งเอกสารอย่างมีประสิทธิภาพอีกด้วย

2. ดัชนีตามการเข้ารหัสช่วงเวลา

สำหรับดัชนีการเข้ารหัสช่วงเวลา แต่ละโหนดในแผนผัง T จะได้รับการกำหนดโค้ดช่วงเวลา [เริ่มต้น, สิ้นสุด] ซึ่งเป็นไปตาม: โค้ดช่วงเวลาของโหนดจะรวมโค้ดช่วงเวลาของโหนดที่สืบทอดมาด้วย กล่าวคือ โหนด u ในแผนผัง T เป็นบรรพบุรุษของโหนด v ถ้าหาก

รูปแบบการเข้ารหัสช่วงแรกของ start(u) คือการเข้ารหัสของ Dietz แต่ละโหนดในแผนผัง T จะถูกกำหนดหมายเลขลำดับการแวะผ่านการสั่งซื้อล่วงหน้าและโพสต์- tuple หมายเลขลำดับการแวะผ่านลำดับ เนื่องจากโหนดบรรพบุรุษ u ในแผนผัง T ต้องปรากฏก่อน (หลัง) โหนดลูกหลาน v ในการแวะผ่านลำดับก่อน (การแวะผ่านลำดับหลัง) ดังนั้นโหนด u และ v จึงเป็นความสัมพันธ์ระหว่างบรรพบุรุษ/ผู้สืบทอด ถ้า pre(u)

อีกตัวอย่างทั่วไปของดัชนีการเข้ารหัสช่วงเวลาคือดัชนี XISS ซึ่งกำหนดคู่ตัวเลขให้กับแต่ละโหนด โดยที่ order คือการเข้ารหัสการสั่งซื้อล่วงหน้าแบบขยายและขนาดคือลูกหลานของขอบเขต สำหรับโหนด X และ Y ใดๆ ในแผนผังเอกสาร หาก

ดัชนี order(x) XISS แยกย่อยคำสั่งสืบค้นต้นฉบับเป็นนิพจน์ย่อย จากนั้นใช้การสืบค้นสำหรับนิพจน์ย่อยเหล่านี้ตามลำดับ และสุดท้ายก็รวมผลลัพธ์ระดับกลางเหล่านี้เข้าด้วยกันเพื่อให้ได้ชุดผลลัพธ์การสืบค้น ซึ่งสามารถรองรับคำสั่งสืบค้นที่มีอักขระตัวแทนได้ดียิ่งขึ้น อย่างไรก็ตาม จะได้รับผลลัพธ์แบบสอบถามสุดท้ายหลังจากเชื่อมต่อผลลัพธ์ระดับกลางแต่ละรายการเข้าด้วยกัน แม้ว่าวิธีการดังกล่าวจะสามารถแก้ปัญหา wildcard ได้ทั้งหมด แต่การเชื่อมโยงผลลัพธ์ขั้นกลางดังกล่าวเข้าด้วยกันนั้นน่าจะใช้เวลานานมาก โดยเฉพาะอย่างยิ่งสำหรับนิพจน์ทั่วไปที่มีเส้นทางยาว

การเปรียบเทียบกลไกการจัดทำดัชนีสองแบบ การจัด

ทำดัชนีตามเส้นทางนั้นขึ้นอยู่กับกลยุทธ์การรวมโหนดเป็นหลัก ด้วยเทคนิคต่าง ๆ เช่น การเทียบเท่าโหนดและความเท่าเทียมกันของเส้นทาง ทำให้ได้โครงสร้างดัชนีที่เล็กกว่าเอกสารต้นฉบับมาก ดังนั้นใน เมื่อประมวลผลแบบสอบถาม คุณยังคงต้องสำรวจแผนผังดัชนีทั้งหมดเพื่อให้ได้ผลลัพธ์ ดัชนีตามเส้นทางสามารถรองรับการสืบค้นนิพจน์เส้นทางแบบง่ายได้เป็นอย่างดี แต่สำหรับนิพจน์เส้นทางปกติ จะทำงานได้ไม่ดีนัก

ดัชนีตามโหนดจะจัดทำดัชนีแต่ละโหนดผ่านเทคโนโลยีการเข้ารหัส ความสัมพันธ์เชิงโครงสร้างระหว่างโหนดสามารถกำหนดได้ในเวลาคงที่ผ่านการเข้ารหัส สามารถรองรับนิพจน์พาธปกติได้ดี แต่สำหรับนิพจน์พาธแบบยาว โดยเฉพาะอย่างยิ่งเมื่อมีการสร้างแบบสอบถาม เมื่อมีผลลัพธ์ระดับกลางจำนวนมาก การดำเนินการรวมของดัชนีโหนดมีราคาแพง

การทำดัชนีตามเส้นทางและการทำดัชนีตามโหนดต่างก็มีข้อดีและข้อเสียของตัวเอง แต่สามารถเสริมซึ่งกันและกันได้ ปัจจุบันในการใช้งานจริง การทำดัชนีตามโหนดมีการใช้กันอย่างแพร่หลายมากขึ้น และการวิจัยยังค่อนข้างสมบูรณ์ ดังนั้น การวิจัยของบริษัท Dameng เกี่ยวกับโครงสร้างดัชนี XML จึงมุ่งเน้นไปที่การจัดทำดัชนีตามโหนดเป็นหลัก และทำการปรับปรุงที่เหมาะสมโดยอ้างอิงถึงการจัดทำดัชนีตามเส้นทาง .