ค้นหาการพึ่งพาการทำงานในฐานข้อมูลได้อย่างมีประสิทธิภาพ

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

การเลือกงาน

ระหว่างที่เรียนอยู่ที่ศูนย์คอมพิวเตอร์ ผมเริ่มศึกษาฐานข้อมูลอย่างลึกซึ้ง โดยเฉพาะการค้นหาความสัมพันธ์เชิงฟังก์ชันและเชิงอนุพันธ์ หัวข้อนี้เกี่ยวข้องกับหลักสูตรที่ผมเรียนที่มหาวิทยาลัย ดังนั้นระหว่างที่กำลังศึกษาอยู่ ผมจึงเริ่มอ่านบทความเกี่ยวกับความสัมพันธ์เชิงฟังก์ชันต่างๆ ในฐานข้อมูล ผมเขียนบทวิจารณ์เกี่ยวกับสาขานี้ ซึ่งเป็นหนึ่งในบทความแรกๆ ที่ผมเขียน บทความ เป็นภาษาอังกฤษและส่งเข้าประชุม SEIM-2017 ผมตื่นเต้นมากเมื่อได้รับเลือกและตัดสินใจศึกษาหัวข้อนี้ให้ลึกซึ้งยิ่งขึ้น ตัวแนวคิดนี้ไม่ใช่เรื่องใหม่ มีมาตั้งแต่ช่วงทศวรรษ 90 แต่ยังคงได้รับการนำไปประยุกต์ใช้ในหลายสาขาในปัจจุบัน

ในช่วงภาคเรียนที่สองที่ศูนย์วิจัย ฉันได้เริ่มโครงการวิจัยเพื่อปรับปรุงอัลกอริทึมสำหรับการค้นหาความสัมพันธ์เชิงฟังก์ชัน ฉันได้ทำงานร่วมกับนิกิตา โบโบรฟ นักศึกษาระดับบัณฑิตศึกษาจากมหาวิทยาลัยรัฐเซนต์ปีเตอร์สเบิร์ก ที่ JetBrains Research

ความซับซ้อนในการคำนวณของการค้นหาความสัมพันธ์เชิงฟังก์ชัน

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

แผนการแคชสำหรับจุดตัดของพาร์ติชัน

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

ดังนั้นเราจึงเสนอฮิวริสติกที่อิงตามเอนโทรปีของแชนนอนและความไม่แน่นอนของจินี รวมถึงตัวชี้วัดของเราเอง ซึ่งเราเรียกว่าเอนโทรปีผกผัน ฮิวริสติกนี้ดัดแปลงเอนโทรปีของแชนนอนเล็กน้อย และจะเพิ่มขึ้นเมื่อความเฉพาะตัวของชุดข้อมูลเพิ่มขึ้น ฮิวริสติกที่นำเสนอมีดังนี้:

ที่นี่ — ระดับความเป็นเอกลักษณ์ของการแบ่งพาร์ติชันที่คำนวณล่าสุด และ คือค่ามัธยฐานของระดับความเฉพาะตัวของแอตทริบิวต์แต่ละรายการ เมตริกทั้งสามที่อธิบายไว้ข้างต้นได้รับการทดสอบเป็นเมตริกความเฉพาะตัว นอกจากนี้ ฮิวริสติกยังประกอบด้วยตัวปรับแต่งสองตัว ตัวปรับแต่งแรกระบุว่าพาร์ติชันปัจจุบันอยู่ใกล้กับคีย์หลักมากเพียงใด และอนุญาตให้แคชพาร์ติชันที่อยู่ห่างจากคีย์ตัวเลือกได้มากขึ้น ตัวปรับแต่งที่สองจะตรวจสอบการครอบครองแคช จึงส่งเสริมให้เพิ่มพาร์ติชันลงในแคชเมื่อมีพื้นที่ว่าง การแก้ไขปัญหานี้สำเร็จทำให้อัลกอริทึม PYRO สามารถเร่งความเร็วได้ 10-40% ขึ้นอยู่กับชุดข้อมูล เป็นที่น่าสังเกตว่าอัลกอริทึม PYRO ประสบความสำเร็จมากที่สุดในด้านนี้

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

วิธีทางเลือกในการจัดเก็บพาร์ติชั่น

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

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}\ downarrow{Compression}\ pi(X) = {{underbrace{$, 1, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}$$display$$

วิธีนี้สามารถลดการใช้หน่วยความจำระหว่างการทำงานของอัลกอริทึม TANE ได้ 1 ถึง 25% อัลกอริทึม TANE เป็นอัลกอริทึมแบบคลาสสิกสำหรับการค้นหาโซนเชิงตรรกะ โดยใช้การแบ่งพาร์ติชันระหว่างการทำงาน ในทางปฏิบัติ อัลกอริทึม TANE ถูกเลือกเนื่องจากการใช้หน่วยเก็บข้อมูลแบบช่วงเวลานั้นง่ายกว่าอย่างมากเมื่อเทียบกับใน PYRO ในการประเมินความเป็นไปได้ของวิธีการที่นำเสนอ ผลลัพธ์แสดงไว้ในรูปด้านล่าง แกน x เป็นลอการิทึม

การประชุม ADBIS-2019

จากผลการวิจัยดังกล่าว ฉันได้ตีพิมพ์บทความในเดือนกันยายน 2019 การแคชอัจฉริยะเพื่อการค้นพบการอ้างอิงฟังก์ชันที่มีประสิทธิภาพ ในการประชุมวิชาการยุโรปว่าด้วยความก้าวหน้าด้านฐานข้อมูลและระบบสารสนเทศ ครั้งที่ 23 (ADBIS-2019) ผลงานนี้ได้รับการยกย่องจาก Bernhard Thalheim บุคคลสำคัญในสาขาฐานข้อมูล ผลการวิจัยนี้เป็นพื้นฐานสำหรับวิทยานิพนธ์ของดิฉันสำหรับหลักสูตรปริญญาโท คณะคณิตศาสตร์และกลศาสตร์ มหาวิทยาลัยรัฐเซนต์ปีเตอร์สเบิร์ก ซึ่งในระหว่างนั้นได้นำวิธีการทั้งสองที่นำเสนอ (แคชและการบีบอัด) ไปใช้ในอัลกอริทึมทั้งสอง ได้แก่ TANE และ PYRO ผลการวิจัยแสดงให้เห็นว่าวิธีการที่นำเสนอมีความเป็นสากล เนื่องจากอัลกอริทึมทั้งสองแสดงให้เห็นถึงการลดการใช้หน่วยความจำอย่างมีนัยสำคัญและลดเวลาในการประมวลผลลงอย่างมีนัยสำคัญ

ที่มา: will.com