פבר21
Written by:
ronen ariely
21/02/2011 07:51 
פירוק שרשרת תנאים לתוצאות
נציג לוגיקה פשוטה של פירוק שרשרת תנאים של AND ו OR לשרשרת של כל התוצאות האפשריות.
מושגי יסוד:
בוליאני (Boolean): מתייחס לאלמנט המקבל לערכים לוגיים (אמת או שקר).
שאילתה בוליאנית: שאילתות העושות שימוש באופרטורים בוליאניים (AND, OR, NOT) ומחזירות ערך בוליאני או אוסף של אלמנטים המתאימים לשאילתה (אלמנטים עליהם הפעלת השאילתה מחזירה ערך חיובי).
פקודות בוליאניות:AND, OR, NOT
קינון (NESTING): שימוש בסוגריים ליצירת שאילתות מורכבות והרחבת החיפוש.
מה יש לנו בעמוד זה?
נציג אלגוריתמים אוטומטיים לפירוק שאילתה בוליאנית לרשימת התוצאות האפשריות. את האלגוריתמים נבנה באמצעות לוגיקה פשוטה של פירוק שרשרת תנאים (פקודות בוליאניות) של AND ו OR לשרשרת של כל התוצאות האפשריות. ננסה גם לתת פתרון לקינון שאילתות.
הצגת הבעיה:
עומדת בפנינו בעיה לוגית מהצורה: (A or B) and ((C and D) or (E and F))
אנו רוצים למצוא את כל התוצאות האפשריות המחזירות ערך חיובי אם נפעיל עליהם את השאילתה שלנו.
אפשרות א: עבודה על שרשראות תווים
נכין 3 פונקציות עזר:
פונקציה A_OR_B לטיפול במבנה שרשרת A or B
1. תחפש את הביטוי הראשון הפשוט מהצורה A or B
2. אם נמצא ביטוי כזה:
a. תבצע הכפלה של השרשרת (הוספת סימון מעבר שורה בין שני קטעי השרשרת) כאשר
i. בפעם הראשונה נרשם במקום הביטוי רק A
ii. בפעם השנייה נרשם במקום הביטוי רק B
b. תריץ פונקציה של ניקוי סוגריים
c. תחפש שוב את הביטוי הראשון הפשוט מהצורה A or B
i. אם נמצא ביטוי כזה -> תריץ את עצמה שוב
ii. אם לא נמצא ביטוי כזה -> תריץ את הפונקציה של טיפול בשרשרת A and B ותעביר ערך לפרמטר End= 0
3. אם לא נמצא ביטוי כזה
a. נבדוק אם הפרמטר שהגיע אלינו הוא End= 1
i. אם כן... סיימנו את העבודה
ii. אם לא אז נריץ את הפונקציה של טיפול בשרשרת A and B אבל הפעם תעביר ערך לפרמטר End= 1
** שלב 3 ימנע לולאה אין סופית...
פונקציה Clean לניקוי סוגריים במבנה פשוט (A)
1. מחיקת הסוגריים המיותרים
פונקציה A_AND_B לטיפול במבנה שרשרת A and B
1. תחפש את הביטוי הראשון הפשוט מהצורה A and B
2. אם נמצא ביטוי כזה:
a. פשוט תחליף את ה and בפסיק ,
b. תריץ פונקציה של ניקוי סוגריים
c. תחפש שוב את הביטוי הראשון הפשוט מהצורה A and B
i. אם נמצא ביטוי כזה -> תריץ את עצמה שוב
ii. אם לא נמצא ביטוי כזה -> תריץ את הפונקציה של טיפול בשרשרת A or B ותעביר ערך לפרמטר End= 0
3. אם לא נמצא ביטוי כזה
a. נבדוק אם הפרמטר שהגיע אלינו הוא End= 1
i. אם כן... סיימנו את העבודה
ii. אם לא אז נריץ את הפונקציה של טיפול בשרשרת A or B אבל הפעם תעביר ערך לפרמטר End= 1
דוגמת הרצת הליך מציאת התוצאות האפשריות:
נתונה שרשרת תנאי מקורית:
(Mexico or Peru) and ((Air and Wind) or (Big and Little))
קראנו לפונקציה A_OR_B וקיבלנו באמצע התהליך שלה את:
(Peru) and ((Air and Wind) or (Big and Little))
(Mexico) and ((Air and Wind) or (Big and Little))
הפונקציה A_OR_B הפעילה את פונקציית הניקוי Clean כחלק מההרצה שלה ולכן בסיום קיבלנו:
Peru and ((Air and Wind) or (Big and Little))
Mexico and ((Air and Wind) or (Big and Little))
אין לנו עוד פעולות מזוהות על ידי פונקציית A_OR_B ולכן הופעלה פונקציית A_AND_B
Peru and ((Air,Wind) or (Big,Little))
Mexico and ((Air,Wind) or (Big,Little))
ואחרי הניקוי
Peru and (Air,Win or Big,Little)
Mexico and (Air,Wind or Big,Little)
עכשיו שוב ניתן לראות מימין ביטוי המתאים לביטוי A_AND_B שלנו (פסיק הוא חלק מהביטוי הרגולרי שלנו לזיהוי איבר פשוט A או B) ולכן בשלב הבא כל שורה תתפצל לשני שורות
Peru and (Air,Win)
Peru and (Big,Little)
Mexico and (Air,Wind)
Mexico and (Big,Little)
וניקוי אחרון
Peru and Air,Win
Peru and Big,Little
Mexico and Air,Wind
Mexico and Big,Little
ושוב יש לנו החלפה בפסיק
Peru,Air,Win
Peru,Big,Little
Mexico,Air,Wind
Mexico,Big,Little
וסיימנו את הריצה של החישוב :-)
אפשרות ב: עבודה על בחירת נתונים מרשימה/טבלה
רעיון כללי:
- נכין טבלה הכוללת את כל האפשרויות הקיימות
- נעזר בטבלת כל הנתונים
- נבנה טבלה עם מספר עמודות כמספר המרבי של נתונים שיכולים לחזור עם כל הצירופים האפשריים
i. נבצע Cross JOIN עצמי על הטבלה כמספר העמודות שרוצים
- מהטבלה מעל נייצר טבלה עם רשומה אחת על ידי חיבור הנתונים של כל הרשומות והפרדת פסיק
- נסנן מהטבלה מקרים של נתונים כפולים (נתונים כגון a,b,c ו c,a,b נחשבים זהים לצורך הבעיה שלנו מכיוון שאין חשיבות לסדר)
i. על מנת למצוא נתונים כפולים עזר בפונקציה הלוקחת שרשרת נתונים בהפרדה כלשהי ומחזירה את השרשרת עם נתונים מסודרים לפי השם: ArielyOrderStringMembers
ii. עתה נוכל לבצע סינון על ידי בחירת distinct
- על ידי החלפת טקסט פשוטה ניתן להפוך את התנאים שלנו לתנאים של שאילתת SQL
- כל איבר נתון A יוכנס למשל בעזרת ביטוי רגולרי לטקסט הבא:
[Name] like '%,A,%'
- נריץ את השאילתה שנוצרה לנו וסיימנו
דוגמה:
declare @Tbl table([Name] nvarchar(20))
insert into @Tbl ([Name]) values ('A')
insert into @Tbl ([Name]) values ('B')
insert into @Tbl ([Name]) values ('C')
insert into @Tbl ([Name]) values ('D')
insert into @Tbl ([Name]) values ('E')
insert into @Tbl ([Name]) values ('F')
--select * from @Tbl
--select * from @Tbl
--cross join @Tbl a
--cross join @Tbl b
declare @Tbl1 table([Name] nvarchar(200))
insert into @Tbl1
--select ',' + (a.[Name] + ',' + b.[Name] + ',' + c.[Name]) + ',' S
--הבעיה היחידה כרגע שמוצאים כמה נתונים זהים אם יש חשיבות לסדר כי מקבלים למשל:
-- ,C,A,D,
-- וגם
-- ,A,C,D,
-- הצמצום היה אמור להיות ברמת הטבלה של כל הנתונים
/*
אם נסדר את הנתונים בטבלה של כל האפשרויות לפי סדר הגודל של האיברים נוכל לצמצם איברים דומים
הבעיה שכרגע מבחינת השרת הם אינן דומים
*/
select
',' +
dbo.ArielyOrderStringMembers((a.[Name] + ',' + b.[Name] + ',' + c.[Name]),',')
+ ','
from @Tbl a
cross join @Tbl b
cross join @Tbl c
select distinct [Name] from @Tbl1
select distinct [Name] from @Tbl1
where
----(A or B) and ((C and D) or (E and F))
---- נתחום כל איבר בסימון
---- [Name] like '%,A,%'
(Name like '%,A,%' or Name like '%,B,%' )
and
(
(Name like '%,C,%' and Name like '%,D,%' )
or (Name like '%,E,%' and Name like '%,F,%' )
)