מצא ביעילות תלות פונקציונלית בבסיסי נתונים

מציאת תלות פונקציונלית בנתונים משמשת בתחומים שונים של ניתוח נתונים: ניהול מסדי נתונים, ניקוי נתונים, הנדסה לאחור של מסד נתונים וחקר נתונים. כבר פרסמנו על התלות עצמן מאמר אנסטסיה ביריו וניקיטה בוברוב. הפעם, אנסטסיה, בוגרת המרכז למדעי המחשב השנה, משתפת בפיתוח עבודה זו כחלק מעבודת המחקר עליה הגנה במרכז.

בחירת משימות

תוך כדי הלימודים במרכז CS התחלתי ללמוד מאגרי מידע לעומק, כלומר חיפוש אחר תלות פונקציונלית והבדל. נושא זה היה קשור לנושא הקורסים שלי באוניברסיטה, אז תוך כדי העבודה על הקורס התחלתי לקרוא מאמרים על תלות שונות במאגרי מידע. כתבתי ביקורת על האזור הזה - אחת הראשונות שלי מאמרים באנגלית והגיש אותו לכנס SEIM-2017. שמחתי מאוד כשגיליתי שהיא בכל זאת התקבלה, והחלטתי להעמיק בנושא. הקונספט עצמו אינו חדש - הוא החל להיות בשימוש עוד בשנות ה-90, אבל גם עכשיו הוא נמצא בשימוש בתחומים רבים.

במהלך הסמסטר השני שלי במרכז התחלתי פרויקט מחקר לשיפור אלגוריתמים למציאת תלות תפקודית. היא עבדה על זה יחד עם הסטודנטית לתואר שני באוניברסיטת סנט פטרסבורג ניקיטה בוברוב ב-JetBrains Research.

מורכבות חישובית של חיפוש תלות פונקציונלית

הבעיה העיקרית היא מורכבות חישובית. מספר התלות המינימלית והלא-טריוויאלית האפשרית מוגבל לעיל על ידי הערך איפה - מספר תכונות הטבלה. זמן הפעולה של האלגוריתמים תלוי לא רק במספר התכונות, אלא גם במספר השורות. בשנות ה-90, אלגוריתמי חיפוש בחוק הפדרלי במחשב שולחני רגיל יכלו לעבד מערכי נתונים המכילים עד 20 תכונות ועשרות אלפי שורות תוך עד מספר שעות. אלגוריתמים מודרניים הפועלים על מעבדים מרובי ליבות מזהים תלות עבור מערכי נתונים המורכבים ממאות תכונות (עד 200) ומאות אלפי שורות בערך באותו זמן. עם זאת, זה לא מספיק: זמן כזה אינו מקובל עבור רוב היישומים בעולם האמיתי. לכן, פיתחנו גישות להאצת אלגוריתמים קיימים.

סכימות שמירה במטמון עבור צומתים של מחיצות

בחלק הראשון של העבודה, פיתחנו סכימות מטמון עבור מחלקה של אלגוריתמים המשתמשים בשיטת צומת מחיצות. מחיצה עבור תכונה היא קבוצה של רשימות, כאשר כל רשימה מכילה מספרי שורות עם אותם ערכים עבור תכונה נתונה. כל רשימה כזו נקראת אשכול. אלגוריתמים מודרניים רבים משתמשים במחיצות כדי לקבוע אם מתקיימת תלות או לא, כלומר, הם מצייתים ללמה: תלות נערך אם . הנה מוגדרת מחיצה ונעשה שימוש במושג גודל המחיצה - מספר האשכולות בה. אלגוריתמים המשתמשים במחיצות, כאשר התלות מופרת, מוסיפים תכונות נוספות לצד השמאלי של התלות, ולאחר מכן מחשבים אותה מחדש, תוך ביצוע פעולת חיתוך המחיצות. פעולה זו נקראת התמחות במאמרים. אבל שמנו לב שניתן לעשות שימוש חוזר פעיל במחיצות לתלות שיישמרו רק לאחר כמה סבבי התמחות, מה שיכול להפחית משמעותית את זמן הריצה של האלגוריתמים, שכן פעולת ההצטלבות יקרה.

לכן, הצענו היוריסטיקה המבוססת על שאנון אנטרופיה וחוסר וודאות של ג'יני, כמו גם המדד שלנו, שקראנו לו אנטרופיה הפוכה. זהו שינוי קל של שאנון אנטרופיה ועולה ככל שהייחודיות של מערך הנתונים עולה. ההיוריסטיקה המוצעת היא כדלקמן:

כאן - מידת הייחודיות של המחיצה שחושבה לאחרונה ו - הוא החציון של דרגות הייחודיות עבור תכונות בודדות. כל שלושת המדדים שתוארו לעיל נבדקו כמדד ייחודיות. אתה יכול גם לשים לב שיש שני משנה בהיוריסטיקה. הראשונה מציינת עד כמה המחיצה הנוכחית קרובה למפתח הראשי ומאפשרת לך לשמור במטמון במידה רבה יותר את המחיצות הרחוקות מהמפתח הפוטנציאלי. השינוי השני מאפשר לך לעקוב אחר תפוסת המטמון ובכך מעודד הוספת מחיצות נוספות למטמון אם יש מקום פנוי. הפתרון המוצלח של בעיה זו אפשר לנו להאיץ את אלגוריתם ה-PYRO ב-10-40%, תלוי במערך הנתונים. ראוי לציין שאלגוריתם PYRO הוא המוצלח ביותר בתחום זה.

באיור שלהלן תוכלו לראות את התוצאות של יישום היוריסטיקה המוצעת בהשוואה לגישה בסיסית של מטמון מטבעות. ציר X הוא לוגריתמי.

דרך חלופית לאחסון מחיצות

לאחר מכן הצענו דרך חלופית לאחסון מחיצות. מחיצות הן קבוצה של אשכולות, שכל אחד מהם מאחסן מספרים של tuples עם ערכים זהים עבור תכונות מסוימות. אשכולות אלה עשויים להכיל רצפים ארוכים של מספרי טפול, למשל אם הנתונים בטבלה מסודרים. לכן, הצענו סכימת דחיסה לאחסון מחיצות, כלומר אחסון מרווחים של ערכים באשכולות של מחיצות:

$$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). במהלך המצגת צוינה העבודה על ידי ברנהרד טהלהיים, אדם משמעותי בתחום מאגרי המידע. תוצאות המחקר היוו את הבסיס לעבודה שלי בתואר שני במתמטיקה ומכניקה באוניברסיטת סנט פטרסבורג, שבמהלכה יושמו שתי הגישות המוצעות (מטמון ודחיסה) בשני האלגוריתמים: TANE ו-PYRO. יחד עם זאת, התוצאות הראו כי הגישות המוצעות הן אוניברסליות, שכן בשני האלגוריתמים, בשתי הגישות, נצפתה הפחתה משמעותית בצריכת הזיכרון, וכן הפחתה משמעותית בזמן הפעולה של האלגוריתמים.

מקור: www.habr.com