ריקורסיה בMYSQL, הכיצד? (בלי SP)

[רון טובלר]

ריקורסיה בMYSQL, הכיצד? (בלי SP)

נניח מקרה פשוט, שיש לי טבלא שכל מה שיש בה זה ID ועמודה שניה ParentID.

בהנתן ID מסויים, אני רוצה למצוא את כל השושלת כלומר למצוא את האבא, הסבא וכל מי שאפשר כלפי מעלה, ואז את כל מי שאפשר כלפי מטה.

זה אפשרי?

 

[koler]

אתה יכול לעשות פיתרון עגום

לתת ID לכל עץ (במקרה הזה יכול להיות הID של הודעת האב הראשונה).
ואז לעשות במספר לתת id במספר יורד לפי הסדר לכל הודעה , ולשלוף לפי הID הזה.
רקורסיה אתה לא יכול לעשות עם SQL כי היא לא שפת תכנות בסופו של דבר.

בהצלחה.

 

[על מה אני מדבר]

רקורסיה לא

הפיתרון הוא במקום לשמור רק את ה-ParentID כמו שהצעת, לשמור את כל ה-ParentIDs (כלומר ברבים) ברשימה מופרדת בפסיקים. ואז ניתן בקלות לשלוף בעזרת פונקציית FIND_IN_SET, לדוגמא:
SELECT ... WHERE FIND_IN_SET('1', parent_ids)

זה יחזיר את כל הרשומות שהן צאצאים של אבא עם ID מספר 1.
שים לב שיתבצע full table scan, כלומר לא ניתן להשתמש באינדקסים לאופטימיזציה.

 

[terra2]

גם מימוש רקורסיבי לא יהיה לך יעיל בהכרח

מבחינת מהירות ואלגוריתם..

במקום שיהיה לך מערך (או טור- אותו עקרון) עם id ומערך של parent_id.

תוכל אולי להעזר במבנה נתונים הבא: ולחסוך בטור אחד ובהרצה רקורסיבית (שלא חוסכת במשאבים יקרים ועוד בכלל במסדי נתונים)

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


a מערך בגודל n. העבודה היא עם integer.

a=array(
(a(i),a(i+1),a(i+2),a(i+3.) ...+ a(i+n)


i=i*2 :child 1
i=2*i+1 : child 2

אב: j=j/2

העץ:

.............(parent)(a0)
................... \........./
.............. child2...child1
............... \..../........ \..../
.............ch2..ch1..ch2..ch1

לשים לב כי לאינדקסים (id) בשורה האחרונה אין בנים.

תנסה לשרטט את העץ ולרשום את המערך כדי להבין את הלוגיקה ולראות אם היא יעילה לך.

 

[terra2]

אגב זה נקרא

עץ חיפוש בינארי לא מצאתי טקסט עליו במערך אחד ..

http://he.wikipedia.org/wiki/עץ_חיפוש

תקרא אולי על התיאוריה ותשמש בנוסחא שהבאתי לך במערך אחד. (או טור) כשהאינדסקים שלו ממוינים בסדר ( 0 1 2 3 n+1...) עולה.
גם אם זה סתם בשביל להשכיל כי זה מבנה נתונים די מוכר ופשוט.

 

[amitayh]

ממליץ להשתמש בשיטת ה-nested set

הרבה יותר יעילה לשליפות. יש גם כל מיני ספריות שעוטפות את האלגוריתם ועושות את זה פשוט לשנות ולקרוא את העץ.
http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/
http://ftp.nchu.edu.tw/MySQL/tech-resources/articles/hierarchical-data.html

 

[רון טובלר]

תודה לכולם והבהרה

הצורך שלי הוא אד-הוק. אני לא יכול לשנות את המבנה של הטבלא מאותה סיבה שאני לא יכול להוסיף SP. חשבתי שיש דרך לעקוף את זה.

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

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

תודה על הנכונות לעזור!

 

[gilmad]

אם זה חד פעמי

אז למה לא לעשות את הרקורסיה בקוד? כלומר בPHP,
במקום בMYSQL...

 

[רון טובלר]

זה מה שעשיתי בסוף

אבל אני ממש אוהב ריקורסיות וגם משתדל לגשת כמה שפחות פעמים ל-DB.

עכשיו כשאני חושב על זה, האם אפשר לעשות SP "זמני" כמו טבלא זמנית?

 

[על מה אני מדבר]

לדעתי זאת טעות

לעשות כמה עשרות שאילתות אם אפשר לעשות זאת בשאילתה אחת (כמו שרשמתי למעלה).

 

[רון טובלר]

זה פתרון נאה, אך לא מתאים למקרה שלי

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

 

[terra2]

עדיף בכללי שלא להשתמש ברקורסיה על מערכים גדו

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