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

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

การเลือกงาน

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

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

ความซับซ้อนในการคำนวณของการค้นหาการขึ้นต่อกันของฟังก์ชัน

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

รูปแบบการแคชสำหรับการแยกพาร์ติชัน

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

ดังนั้นเราจึงเสนอฮิวริสติกโดยอิงตาม Shannon Entropy และ Ginny Uncertainty รวมถึงหน่วยวัดของเรา ซึ่งเราเรียกว่า Reverse Entropy เป็นการปรับเปลี่ยน Shannon Entropy เล็กน้อยและเพิ่มขึ้นเมื่อเอกลักษณ์ของชุดข้อมูลเพิ่มขึ้น ฮิวริสติกที่นำเสนอมีดังนี้:

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

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

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

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

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5__{First Interval}, Underbrace{7, 8__{Second Interval}, 10}}\ downarrow{ การบีบอัด} \ pi(X) = {{อันเดอร์เบรซ{$, 1, 5__{First~interval}, อันเดอร์เบรซ{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