مشاور شما در زمینه پروژه های برنامه نویسی
و مهندسی نرم افزار
09131253620
همیشه در دسترس
(حتی روزهای تعطیل)
 
جستجو در پروژه های وب سایت
صفحه اصلی    |    جستجو در پروژه ها    |    درخواست نمونه پروژه    |    ثبت نام در وب سایت    |    ورود به حساب کاربری    |    سوالات قبل و بعد از خرید    |    درخواست استخدام    |     ارتباط با ما     |    نقشه وب سایت     
مشاهده جزئیات پروژه
>>>>مشاهده سایر پایان نامه های رشته كامپيوتر >>>>

>>>> مشاهده پایان نامه ها به تفکیک رشته >>>>

>>>> مشاهده لیست کامل لیست انواع پایان نامه ها <<<<


 
  خرید
کد پروژه: PA-300179
موضوع پروژه:

بهینه سازی تقاضا تحت رتبه بندی در سیستم های توزیع شده

گروه پروژه: لیست انواع پایان نامه ها
تعداد مشاهدات: 685
قیمت: 85500 (قیمت به ریال)
قالب فایل: Word + Powerpoint
تعداد صفحات: 101
شرح پروژه: word + pdf + powerpoint
فهرست 
عنوان                                                                                                                                                                                                               صفحه
فهرست مطالب                                                                                                             و
فهرست شکلها                                                                                                            ط
فصل اول: مقدمه                                                                                                         1 
  1: تشریح مسئله                                                           3
  2: چالشها                                                                                                                   5
فصل دوم: مفاهیم اولیه و کار های پیشین                                                                            6 
  1: پردازش تقاضا                                                                                                          7
1-1 : تجزيه تقاضا                                        7
1-2 :  بهينه سازي تقاضا                             7
1-3 : اجراي تقاضا                                                                                                         8
2 : روشهاي بهينه سازي تقاضا                           9
3 : تقاضاي  تحت رتبه ‌بندي                            11
4 : کارهای پیشین                                  12
4-1 : یک دستاورد مبتنی بر هرس کردن برای پشتیبانی اتصال تقاضاها یی با K جواب بهتر                 12
    4-1-1: مساله مورد بررسی                                                                                                    12
    4-1-2: معماری کلی روش                                                                                                    14
4-2 : بهینه سازی تقاضای تحت رتبه بندی                                                                            15

عنوان                                                                                                                                                                                                               صفحه
    4-2-1: رتبه بندی تجمعی                                                                                                     16
    4-2-2: عملگرهای تقاضای اتصال رتبه بندي             16
    4-2-3: بهینه سازی تقاضا بر پایه هزینه                17
    4-2-4: طرح شمارش با استفاده از برنامه نویسی پویا                17
    4-2-5: توسعه فضاي شمارشي               18
    4-2-6: طرح هاي هرس               19
4-3 : بهینه سازی تطبیقی تقاضا های تحت رتبه بندی در پایگاه داده های رابطه ای            22
          4-3-1: اجراي تطبيقي تقاضاي رتبه‌بندي                       23 
              4-3-2: اصلاح و استفاده‌ي مجدد طرح‌هاي رتبه‌بندي                     23  
              4-3-3: تغيير طرح بر اساس بهينه‌ساز:                          25
              4-3-4: شيوه طرح اكتشافي تغيير براي تاخيرهاي غيرمنتظره                                                  25
4-4 : بهینه سازی تقاضای محدود شده بهK                                                                            26
             4-4-1: استنتاج فضای وضعیت ایندکس                                                                                  28
             4-4-2: وضعیت  هدف                           29
             4-4-3: الگوریتم *OPT                          32
فصل سوم: روش پیشنهادی                                                          34 
  1: بیان برخی از نقصهای کارهای پیشین                 35
  2: تجزیه کننده تقاضا                    36
  3: بهینه سازی تقاضای تحت رتبه بندی در سیستم متمرکز              37
  3-1: بهینه سازی تقاضای تحت رتبه بندی در سیستم متمرکز مبتنی بر هرس کردن ورودی رابطه ها                38
             3-1-1: ساختار کلی الگوریتم                    40
   3-2: بهینه سازی تقاضای تحت رتبه بندی در سیستم متمرکز با الهام گرفتن از جستجوی آگاهانه              48
  4: بهینه سازی تقاضای تحت رتبه بندی در سیستم توزیع شده            57 
  4-1: بهینه سازی تقاضای تحت رتبه بندی در سیستم توزیع شده مبتنی بر هرس کردن ورودی رابطه ها            61
  4-2: بهینه سازی تقاضای تحت رتبه بندی در سیستم توزیع شده با الهام گرفتن از جستجوی آگاهانه                  72
فصل چهارم: پیاده سازی و آزمایشها                                                       74 

عنوان                                                                                                                                                                                                               صفحه
  1: پیاده سازی های انجام شده            75 
  2: پایگاه داده های نمونه            77 
  3: پارامترهای مورد نظر برای مقایسه روشها          79 
  4: آزمایشهای انجام شده            80
فصل پنجم: نتایج و پیشنهادها                                                          91
  1: نتایج          92 
  2: پیشنهادها                                                                                                           92
مراجع                                                                                                                   94

فهرست شکلها
عنوان                                                                                                                                                                                                                صفحه
فصل اول
  شکل 1-1: تقاضای نمونه                                                                                             4
فصل دوم
  شكل2-1: مراحل پردازش تقاضا                                                                                    7
  شكل2-2: مقایسه کلی ساختار بهينه سازي تقاضا سنتی و تطبيقی                                             10
  شكل2-3: ارزیابی هزینه I/O دو طرح مرتب سازی و اتصال رتبه بندي                                     12
  شکل 2-4: مثالی از روش هرس کردن برای تقاضاها یی با K جواب بهتر                                  13
  شکل 2-5: معماری کلی روش                                                                                     15
  شکل2-6 : الگوریتم برای انتخاب K چند تایی بهتر                                                             15
  شكل 2-7 : شمارش طرح تقاضاي تحت رتبه بندي                                                             19
  شكل2-8: دو طرح شمارش                                                                                         20
  شكل2-9: نمايش دو طرحpold, pnew                                                                                           24
  شکل 2-10 : الگوریتم جستجوی OPT*                                                                         31
فصل سوم
  شکل 3-1: تعیین ورودی های مورد نیاز برای بدست آوردن K جواب بهتر در دو رابطه R2 , R1       38
  شکل 3-2: انواع ساختار درخت اتصال                                                                            39
  شکل3-3: درخت خطی                                                                                             39
  شکل 3-4: ساختار سلسله مراتبی بالا – پایین، تعیین اندازه ورودی رابطه ها                                 40
  شکل 3-5: ایجاد شاخص                                                                                            41
  شکل3-6: جزئیات تابع Prepare_Input_Size                                                                  42
  شکل3-7: جزئیات تابع Min_Item                                                                               42
  شکل3-8: جزئیات رویه Prepare_Left_Deep_Tree                                                         43
  شکل3-9: جابجایی و انتخاب مقادیر بدست آمده در مرحله جاری برای استفاده مرحله بعدی             45
  شکل3-10: زیر برنامه Swap_Item                                                                              46
عنوان                                                                                                                                                                                                                صفحه
  شکل3-11 : جزئیات تابع بهبود یافته Prepare_Input_Size                                                 46
  شکل3-12: جزئیات تابع بهبود یافته Min_Item                                                                47
  شکل3-13: جزئیات رویه بهبود یافته Prepare_Left_Deep_Tree                                         47
  شکل3-14: زیر برنامه Compute_Bounds                                                                     50
  شکل3-15: ساختار داخلی هر گره                                                                                50
  شکل3-16: جزئیات تابع Create_Tree                                                                          51
  شکل3-17: جزئیات زیر برنامه Create_Interleaving                                                        52
  شکل3-18: جزئیات زیر برنامه Assign_Tuples_To_Leaf                                                 52
  شکل3-19: جزئیات تابع Create_Gneral_Tree                                                               53
  شکل3-20: جزئیات زیربرنامه Create_Neighbors_in_Leafs                                              54
  شکل3-21: جزئیات زیربرنامه Achieve_TOPK_Result                                                    56
  شکل3-22: طرح های پايگاه داده توزيع شده                                                                   57
  شکل3-23: نحوه محاسبه تاخیر انتها به انتها                                                                      58
  شکل 3-24: جزئیات زیربرنامه Recognize_Location_for_Relations                                  60
  شکل 3-25: جزئیات زیربرنامه هایی برای انجام عملهای انتخاب، پرتو و مرتب سازی                    62
  شکل 3-26: جزئیات تابع Prepare_Input_Size1                                                             64
  شکل 3-27: جزئیات تابع Prepare_Input_size_In_Relation                                             65
  شکل 3-28: جزئیات زیربرنامه Prepare_Input_size_In_Relations                                     65
  شکل 3-29: جزئیات زیربرنامه Prepare_Input_sizeCommand                                          66
  شکل 3-30: جزئیات زیربرنامه Prepare_Left_Deep_Tree                                                67
  شکل 3-31: جزئیات ارسال اطلاعات اندازه ورودی و خروجی مورد نیاز رابطه ها به سیستمهای دیگر  68
  شکل 3-32: جزئیات تابع Obtain_Transfer_cost                                                           68
  شکل 3-33: جزئیات زیربرنامه های Obtain_Transfer_cost_In_SystemsوObtain_Transfer_costCommand  69
  شکل 3-34: جزئیات زیر برنامه Send_Structure_Local_Tables                                         70
  شکل 3-35: جزئیات زیر برنامه Structure_Table_for_CreateCommand                              70
  شکل 3-36: جزئیات زیربرنامه Save_Relation_To_File                                                   71
عنوان                                                                                                                                                                                                                صفحه
  شکل 3-37: جزئیات زیربرنامه Receive_Data                                                                71
  شکل 3-38: جزئیات زیربرنامه Get_FileCommand                                                         72
  شکل 3-39: کلیات زیربرنامه Select_TOPK                                                                  72
فصل چهارم
  شکل 4-1: نمایی از سیستم طراحی شده                                                                           77
  شکل 4-2: تنظیمات آدرس IP سیستم ها                                                                        77
  شکل 4-3: جزئیات رابطه های پایگاه داده NGDB2                                                           79
  شکل 4-4: سه تقاضای نمونه از پایگاه داده سیستم تولیدکننده                                                81
  شکل 4-5: هزینه زمانی اجرای تقاضای 1 در سیستم متمرکز                                                 82
  شکل 4-6: هزینه زمانی اجرای تقاضای 1 در سیستم توزیع شده                                              83
  شکل 4-7: میزان اطلاعات ارسالی تقاضای 1 در سیستم توزیع شده                                          83
  شکل 4-8: نسبت اندازه ورودی تعیین شده به اندازه ورودی مورد نیاز واقعی برای تقاضای1              84
  شکل 4-9: هزینه زمانی اجرای تقاضای 2 را در سیستم متمرکز                                               85
  شکل 4-10: هزینه زمانی اجرای تقاضای 2 را در سیستم توزیع شده                                           85
  شکل 4-11: میزان اطلاعات ارسالی تقاضای 2 در سیستم توزیع شده                                         86
  شکل 4-12: نسبت اندازه ورودی تعیین شده به اندازه ورودی مورد نیاز واقعی برای تقاضای2            86
  شکل 4-13: هزینه زمانی اجرای تقاضای 3 را در سیستم متمرکز                                             87
  شکل 4-14: هزینه زمانی اجرای تقاضای 3 را در سیستم توزیع شده                                         87
  شکل 4-15: میزان اطلاعات ارسالی تقاضای 3 در سیستم توزیع شده                                         88
  شکل 4-16: نسبت اندازه ورودی تعیین شده به اندازه ورودی مورد نیاز واقعی برای تقاضای3            88
  شکل 4-17: یک تقاضای نمونه از پایگاه داده NGDB2                                                      89
  شکل 4-18: هزینه زمانی اجرای تقاضای 4 را در سیستم متمرکز                                            89
  شکل 4-19: هزینه زمانی اجرای تقاضای 4 را در سیستم توزیع شده                                         90
  شکل 4-20: میزان اطلاعات ارسالی تقاضای 4 در سیستم توزیع شده                                         90
  شکل 4-21: نسبت اندازه ورودی تعیین شده به اندازه ورودی مورد نیاز واقعی برای تقاضای4           91

سپاسگزاری
از تمامي اشخاصی که در مراحل مختلف زندگي راهنما و مشوق من بودند و از تمامی اساتیدی که در این مقطع تحصیلی پشتوانۀ اصلی پیشرفت و ترقّی من گشته اند تقدیر و تشکّر می نمایم. لازم می دانم از جناب استاد محمود نقیب زاده و جناب مهندس علیرضا معظمی که در طی مراحل مختلف این پروژه مشوق و راهنمای من بودند قدردانی و تشکّر نمایم. از خداوند منّان موفقیت ایشان را در طی مراحل مختلف زندگی خواستارم.
چکیده
تقاضای تحت رتبه بندی از کاربردی ترین تقاضا بر اساس نیاز کاربران می باشد، مهمترین مسئله در اجرای این تقاضاها در سیستم های توزیع شده، ارسال اطلاعات مورد نیاز تقاضا و بالطبع حداقل زمان اجرا می باشد، برای این منظور از روشهای بهینه سازی تقاضا تحت رتبه بندی استفاده می شود. در اجرای یک تقاضا، هزینه برترین عمل، عمل اتصال بین رابطه ها می باشد به همین دلیل در این تحقیق ابتدا اندازه مورد نیاز رابطه ها را بر اساس K جواب بهتر، به صورت ساسله مراتبی و طبق درخت چپ ژرف برای عمل اتصال تعیین می نماییم، سپس اطلاعات محدود شده را به سیستمی ارسال می کنیم که هزینه ارسال کمینه گردد و در سیستم مقصد اعمال نهایی برای بدست آوردن K جواب بهتر را بر اساس دو استراتژی پیاده سازی کردیم، در استراتژی اول، پس از دریافت اطلاعات مورد نیاز رابطه های محدود شده، عمل اتصال بین رابطه ها را بر اساس ترتیب تعیین شده انجام می دهیم و در نهایت K جواب بهتر را بدست می آوریم. در استراتژی دوم پس از دریافت اطلاعات مورد نیاز، مسئله بهینه سازی را به جستجوی آگاهانه تبدیل کرده و بر اساس ساختار درخت B+ ایجاد شده طبق رابطه های محدود شده، K جواب بهتر را بدست می آوریم. یک پایگاه داده واقعی در نظر گرفتیم و این دو روش را با روش سنتی بدون بهینه سازی و روش طبق جستجوی آگاهانه A* بیان شده در  [31]مقایسه کردیم که براساس نتایج بدست آمده، به طور متوسط دو روش پیشنهادی زمانیکه میزان K در حدود 20 درصد کل جوابها باشد دارای هزینه کمتری نسبت به روش سنتی و روش طبق جستجوی آگاهانه A* [31] می باشد، در ضمن بر اساس مقدار K، هزینه ارسال اطلاعات نیز از 10 تا 70 درصد کاهش یافته است.
بهینه سازی تقاضا  یکی از مسائل مهم در سیستمهای مدیریت پایگاه داده می باشد. در سالهای اخیر بهینه سازی تقاضا از جنبه های مختلفی مورد بررسی قرار گرفته است که به تفصیل در فصل 2 بیان شده است. مقوله اي كه مورد بررسي قرار داديم بهينه سازي تقاضا تحت رتبه بندي  مي باشد كه براي بدست آوردن  Kجواب بهتر  در یک تقاضا است که K توسط تقاضا تعیین می شود.
پدیدار شدن برنامه های کاربردی که وابسته به تقاضاهای رتبه بندی هستند، پشتيباني كاراي تقاضاهای رتبه بندی را در سیستم های مدیریت پایگاه داده در دنیای واقعی طلب می کنند.  پشتیبانی تقاضاهای رتبه بندی به سیستم های پایگاه داده توانایی پاسخ دادن کارا به تقاضاهای بازیابی اطلاعات را  می دهد. 
در سالهای اخیر، ترکیب مزایای سیستم های بازیابی اطلاعات و پایگاه داده یک هدف اصلی برای خیلی از محققان بوده است. سیستم های پایگاه داده، مدیریت داده را با جامعیت قوی و تضمين سازگاری فراهم می آورند. از طرف دیگر سیستم های بازیابی اطلاعات مکانیزم هایی برای بازیابی کارا و رتبه بندی فازی که برای کاربر مطلوب است، فراهم می نمایند. 
موضوع مهم در اين زمينه تعيين اندازه مورد نياز ورودي ها در N رابطه براي پاسخگويي به تقاضاي تحت رتبه بندي مي باشد تا بدين وسيله بتوان K جواب بهتر مورد نظر را بدست آورد. درمجتمع سازي اطلاعات در مقياس بالا، انتخاب جوابهاي رتبه بندي K جواب بهتر ازچندين منبع خيلي حياتي مي باشد و در كمينه كردن هزينه انتقال نقش اساسي دارد. زيرا هر چه اندازه رابطه ها كوچكتر باشد، هزينه كمتري براي انتقال صرف مي گردد. علاوه براین انتخاب روش مناسب برای تعیین اندازه ورودی مورد نیاز رابطه ها  تاثیر چشم گیری در هزینه کل پردازش دارد بر اساس این مزیت روشهای مختلفی برای بهینه سازی تحت رتبه بندی ارائه شده است که مهمترین آنها را در فصل 2 مورد بررسی قرار دادیم. روشهای بیان شده در زمینه بهینه سازی تقاضا تحت رتبه بندی غالبا در مقوله سیستمهای شخصی بیان شده اند، در حالیکه کاربرد عملی این تقاضاها در سیستمهای تحت وب و توزیع شده می باشد. بر این اساس تصمیم گرفتیم این روشها را برای سیستم توزیع شده  بسط دهیم.



1- تشریح مسئله
هنگامیکه یک تقاضا تحت رتبه بندی داریم که هدف بدست آوردن K جواب بهترمی باشد، در این حالت به تمامی رکورد های جدول نیاز نداریم، بر اساس مقدار K تعدادی از رکوردها در رابطه ها که امتیاز کمی دارند در نتیجه نهایی نقشی ندارند و بهتر است آنها هرس شوند و برای محاسبات و انتقال اطلاعات زمانی را برای این رکوردها تلف نکنیم. ابتدا تعریفی از یک تقاضای تحت رتبه بندی را در زیر بیان        می کنیم.
در تقاضای تحت رتبه بندی، تقاضا بر روی M  صفت A1، A2، ... ، AN  و N رابطه به صورت R1، R2، ... ، RN تعریف می شود که هر  Ai(i=1:M) متعلق به یک رابطه Rj (j=1:N)     می باشد. هر یک از صفتها نسبت به نوع شان دارای دامنه خاصی می باشند. R1، R2، ... ، RN در M سیستم به صورت توزیع شده قرار دارند به صورتیکه هر رابطه به طور کامل بر روی یک سیستم قرار دارد. به عبارت دیگر عمل قسمت بندی  بر روی رابطه ها را در پایگاه توزیع شده بین سیستمها را در این تحقیق نداریم.
 با توجه به تقاضا یکسری از صفتهای این رابطه ها برای عمل پرتو  بکار می روند که به عنوان صفتهایی می باشند که در رکوردهای حاصل مورد استفاده قرار می گیرند. یکسری از صفتهای این رابطه ها برای عمل انتخاب  بکار می روند که در واقع شرط های منطقی هستند که بر روی رکوردهای رابطه ها اعمال می شوند و رکودهایی دارای این محدودیتها می باشند می توانند برای مراحل بعدی مورد استفاده قرار بگیرند. برخی از صفتها برای عمل اتصال مورد استفاده قرار می گیرد، هنگامیکه چند رابطه داریم برای اینکه عمل اتصال بین آنها را بر قرار کنیم، می بایست صفتهای اتصال را برای هر یک از روابط تعیین نماییم. اگر برای دو رابطه Ri و Rj صفتی برای اتصال وجود نداشته باشد، SQL به جای عمل اتصال، ضرب دکارتی را بین این دو رابطه انجام  می دهد. در تقاضا ها ی تحت رتبه بندی بخشی برای رتبه بندی داریم که برخی از صفتهای رابطه ها به صورت یک عبارت رتبه بندی بیان می شود که به آن تابع رتبه بندی گفته می شود. 
تابع رتبه بندی f به صورت ترکیبی از M' صفت تشکیل شده است که درآن M M' می باشد. فرضی که برای تابع رتبه بندی f داریم این است که تغییرات تابع رتبه بندی نسبت به کل رابطه ها یکنواخت باشد. البته در تابع رتبه بندی  مورد نظر تغییرات تابع نسبت به هر رابطه می تواند غیر یکنواخت باشد علاوه براین در تقاضاها ی تحت رتبه بندی تعداد جوابهای مطلوب نیز تعیین می شود که همان K جواب بهتر می باشد. نمونه ای از یک تقاضای تحت رتبه بندی در مثال 1 بیان شده است.

مثال1:  يك خانواده مايل به خريد خانه‌اي در نزديكي يك مدرسه مي‌باشد و هدف آنها كاهش هزينه‌هاي كلي‌شان مي‌باشد. يك تابع رتبه بندی ساده كه مجموع قيمت خانه و هزينه شهریه 5 سال مدرسه را برآورد می كند در نظر بگيريد. می بایست عمل جستجو در دو رابطه  خانه‌ و مدرسه در پايگاه داده،      بر اساس تقاضای شکل 1-1 صورت گیرد. 

        SELECT    *
       FROM House, School
       WHERE ( DISTANCE (House.Location , School.Location) < d)
       ORDER BY ( House.Price + 5 * School.Tuition )
       Top 10

شکل 1-1: تقاضای نمونه
رابطه های House  و School می توانند در یک سیستم توزیع شده بر روی یک یا دو سیستم وجود داشته باشند. البته از هر رابطه فقط یک نمونه وجود دارد یعنی عمل تکرار  نیز در سیستم مورد بررسی نداریم. در این تقاضا خانواده تنها حداكثر به 10 نتيجه بجاي همه نتايج ممكن احتیاج دارد که از بین این 10 نتیجه تصمیم گیری نماید و خانه مطلوب را انتخاب نماید. راه حل سنتی این است که ابتدا همه رابطه های مورد نیاز تقاضا در صورت عدم وجود به سیستم اجرا کننده تقاضا به طور کامل ارسال می شوند سپس عمل اتصال  بر روي دو رابطه انجام می شود، کلیه جوابها  محاسبه شده و در نهایت بر اساس تابع رتبه بندي جوابها مرتب شده و 10 تای اول انتخاب می شوند. در حالتیکه رابطه ها بزرگ و تعداد جوابها زیاد باشد، هزینه محاسبات و انتقال اطلاعات نسبتا زیاد می باشد. البته برای K های بزرگ روش سنتی هزینه محاسباتی کمتری نسبت به روشهایی که اندازه ورودی را تخمین می زنند، دارد اما در این حالت نیز مشکل هزینه انتقال اطلاعات نسبتا زیاد می باشد. 
در این تحقیق به جای اینکه در ابتدا رابطه ها را به طور کامل به سیستم تقاضا کننده ارسال کنیم، ابتدا بهینه سازی محلی را بر روی رابطه ها اعمال می کنیم و آنها را بر اساس عبارتیکه صفتهای رتبه بندی آنها در تابع رتبه بندی دارند، مرتب می کنیم، سپس ورودی های مورد نیاز برای ورودی ها را برای بدست آوردن K جواب بهتر تعیین می نماییم، هزینه های انتقال را بررسی کرده و میزان اطلاعاتی از رابطه ها را می بایست منتقل شود به سیستمی با کمترین هزینه ارسال می نماییم، در نهایت بر روی رابطه های نهایی عمل اتصال را انجام داده و نتایج نهایی را بدست می آوریم یا در این حالت به جای عمل اتصال با الهام گرفتن از الگوریتمهای جستجوی آگاهانه، مسئله بهینه سازی را تبدیل به جستجوی آگاهانه کرده سپس توسط این رابطه های نهایی گراف را برای جستجو بر اساس صفتها و تابع رتبه بندی تشکیل داده و K جواب بهتر را بدست می آوریم.

2- چالشها
برخی مشکلات برای انجام این تحقیق شامل موارد زیر می باشند:
1- تعیین اندازه ورودی N رابطه بر اساس اندازه خروجی مورد نظر آنها: تا به حال روشهای ارائه شده الگوریتمی را برای N رابطه ارائه نداده اند فقط الگوریتمها برای تعیین اندازه ورودی دو رابطه     می باشد.
2- اعمال الگوریتمی برای سیستم توزیع شده: روشهای بررسی شده برای بهینه سازی تقاضای تحت رتبه بندی، در سیستم های محلی هستند، بکار بردن الگوریتم در سیستم توزیع شده باعث می شود که یکسری محدودیتها را ماهیت سیستم توزیع شده بر روی الگوریتم تحمیل کند، در واقع پارامترهایی که در انتقال اطلاعات بین سیستمها موثرند بر روی روش پیشنهادی تاثیر می گذارند. کنترل ارسال و دریافت اطلاعات و نوع پروتکل نیز در الگوریتم کلی تاثیر گذارند.
3- برای تبدیل مسئله بهینه سازی تقاضا به جستجوی آگاهانه : در این حالت البته روشهای کارایی ارائه شده است که چالش اصلی در آنها ساختن شاخصها بر روی رابطه ها بر اساس عبارتی که صفتهای رتبه بندی آنها در تابع رتبه بندی دارند و در نهایت ایجاد گراف حاصل از تمامی شاخصها بر اساس تابع رتبه بندی و جستجو بر روی آن می باشد. در ایجاد گراف و جستجو بر روی آن می بایست شرایط جستجوی آگاهانه را در نظر گرفت.   
1- پردازش تقاضا  
به مراحل مورد نياز براي تبديل تقاضاي SQL سطح بالا به طرح صحيح و كارا براي اجرا و بازيابي پردازش تقاضا گفته مي شود[14]. پردازش تقاضا شامل سه مرحله اصلي ذیل می باشد، مراحل را به طور كلي در شكل 2-1 مشاهده مي كنيد.
1- تجزیه تقاضا     2- بهینه سازی تقاضا    3- اجرای تقاضا
1-1 تجزيه تقاضا: دراين مرحله اجزاي مختلف يك تقاضا را به طور مفهومي دسته بندي مي كنيم و نرمال سازي بر روي پارامترها را انجام مي دهيم. به طور کلی تجزیه تقاضا شامل مراحل تحلیل نحوی، نرمال سازی، تحلیل معنایی و ساده سازی می باشد که برای مطالعه بیشتر در مورد این مراحل به [5,31] مراجعه کنید.
1-2 بهينه سازي تقاضا: به عمل انتخاب يك طرح اجراي كارا از چندين طرح براي اساس پارامترهاي مطلوب و با استفاده از اطلاعات مختلف موجود از پايگاه داده بهينه سازي تقاضا گفته مي شود[25]. به عبارت دیگر بهینه سازی تقاضا، فعالیتی است که طی آن یک استراتژی کارا برای اجرای تقاضا، تولید می شود[31].
 
شكل2-1: مراحل پردازش تقاضا[25]
بهینه سازی تقاضا از مراحل اساسی پردازش تقاضا می باشد و سیستم در این مرحله، از بین تعدادی طرح اجرا، بهترین را برمی گزیند به گونه ای که اجرای تقاضای کاربر، کمترین هزینه، بویژه کمترین هزینه عملیات I/O، را داشته باشد. در واقع سیستم تقاضای نوشته شده توسط کاربر در یک زبان سطح بالا مثلا SQL را به یک استراتژی صحیح و کارای اجرا، در یک زبان سطح پایین تبدیل می کند[5]. بطوریکه خواهیم دید، در این کار، چندین گونه تبدیل امکان پذیر است وبهینه ساز، بهترین تبدیل را انتخاب و اجرا می کند. هدف کلی بهینه ساز، انتخاب یک استراتژی کارا برای ارزیابی یک عبارت رابطه ای است[6].
به بیان دیگر، اگر S مجموعه استراتژیهای ممکن برای اجرای تقاضای q باشد، هر عضو S، مثلا s دارای یک هزینه ( از نظر زمان CPU و زمان I/O ) است، اگر این هزینه را با C(s) نشان دهیم، هدف هر استراتژی بهینه سازی یافتن عضوی از S مثلا s0 است به نحوی که[1] :     
(2-1)                                                                              
1-3 اجراي تقاضا: بر اساس طرح اجرايي انتخاب شده، اعمال بر روي پايگاه داده انجام داده مي شود و نتايج بيان مي گردد.
مطلب مورد بررسي ما در مورد روشهاي مختلف بهينه سازي تقاضا مي باشد، اين مقوله يكي از زمينه هايي است كه در چند سال اخير از جنبه هاي مختلف مورد تحقيق قرار گرفته است. در ابتدا قبل از بيان اجمالي اين روشها، چند فاكتور مهم براي ايجاد ومقايسه و دسته بندي اين روشها را در ذيل بيان مي كنيم.
زمان اجرا و فضاي جستجو: يك پارامتر مهم در روشهاي بهينه سازي تقاضا زمان اجرا و فضاي جستجو مي باشد. چيزي كه واضح است اين است كه هر چه فضاي جستجوي وسيعتري داشته باشيم مي توانيم طرح مناسب تري را  انتخاب نماييم درعوض مي بايست زمان بيشتري را صرف نماييم. اما روشي مناسب است كه بر اساس نيازهاي موجود يك حد مياني بين دقت و سرعت را براي رسيدن به كارايي مطلوب برگزيند. البته اين بسته به نوع مسئله، متفاوت است. فضاي جستجو و به تبع زمان اجرا در روشها مي تواند به صورت چند جمله اي يا نمايي باشد.
نوع روش: در واقع نحوه عملكرد يك روش بهينه سازي تقاضا را مشخص مي كند كه  مي تواند به صورت با قاعده يا به صورت اكتشافي باشد. 
قطعيت: در يك روش بهينه سازي تقاضا، تصميم گيري برای انتخاب طرحها از کل فضای حالت مي تواند به صورت قطعي ، احتمالي يا تصادفي  باشد.
نوع ساختار: يك الگوريتم بهينه سازي تقاضا از لحاظ نوع ساختار مي تواند ساختمند  يا قابل تغيير  در مراحل مختلف تصميم گيري طرح مورد نظر باشد. الگوریتمهای ساختمند انعطاف پذیری کمی دارند در  بین اجرا اگر تغییراتی در  اطلاعات پایگاه داده رخ دهد که احتیاج باشد طرح اجرایی عوض شود در این روشها نیاز به اجرای مجدد تقاضا می باشد اما در الگوریتمهای قابل تغییر، بخشهایی از اجرا که انجام شده و در طرح جدید نیز بکار می رود، دوباره اجرا  نمی شود[25]. پارامترهاي ديگري نيز مي توان در نظر گرفت كه در روشها به آنها اشاره مي نماييم.

2- روشهاي بهينه سازي تقاضا
روشهاي بهينه سازي تقاضا به طور كلي به دو دسته تقسيم مي شوند:
بهينه سازي تقاضا بوسيله تخمين هزينه[9,10,11] و بهينه سازي تقاضا با استفاده از قوانين معادل وجايگزيني آنها با هم مي باشد[12]. البته برخي از اين روشها از تركيب ايندو استفاده مي كنند. به طور   كلي برخي از روشهاي بهينه سازي تقاضا را در زير بيان مي كنيم و سپس به تشريح بخش اصلي تحقيق         مي پردازيم.
بهينه سازي تقاضا در هر دوي  پايگاه داده هاي متمركز و توزيع شده مورد استفاده قرار مي گيرد و شامل الگوريتمهاي مختلفي مي باشد. اما بر اساس پارامتر های بیان شده، اين الگوريتمها به سه دسته اصلي تقسيم مي شوند: الگوريتمهاي جستجوي جامع، اكتشافي و تصادفي.
     الگوريتم هاي برنامه نويسي پويا از معمول ترين نوع الگوريتمهاي جستجوي جامع مي باشند كه اين الگوریتمها زمان اجرا و فضاي جستجو از مرتبه نمايي دارند همچنين با قاعده، قطعي و ساختمند مي باشند؛ در نتيجه تضمين مي كنند بهترين طرح را بر اساس يك مدل هزينه خاص بدست مي آورند[15,20,23]. البته الگوريتمهاي جستجوي جامع قابل تغيير نيز داريم الگوريتم هاي برنامه نويسي پويا بالا–پایین  شامل اين دسته اند كه روشهاي پياده سازي شده EXODUS, Volcano از اين دسته اند[7,8].
الگوريتمهاي اكتشافي زمان اجرا و فضاي جستجویی از مرتبه چند جمله اي دارند، اما اغلب طرحهايي با هزينه بيشتر از بهترین طرح ممکن را انتخاب مي كنند، همچنين ايده اصلي اين روش بر پايه         انتخاب پذيري  كمينه و قواعد حريصانه مي باشد[21,24,27,28]. روشهای اکتشافی از قوائد زیر پیروی می کنند:
اجرای عمل انتخاب حتی الامکان هر چه زودتر.
اجرای عمل پرتو حتی الامکان هر چه زودتر.
تعیین اینک کدام عمل انتخاب و پرتو، رابطه ای کوچکتر تولید می کنند.
پردازش زیر عبارتهای مشترک در درخت، حتی الامکان یکبار و ...[32]
براي جلوگيري از هزينه جستجوي جامع، طرحهاي تصادفي مثلSimulated Annealing, Randomized walk, Genetic algorithm پيشنهاد شدند كه سعي مي كنند يك راه حل خوب را بر اساس پارامترها ي مورد نظر بدست بياورند نه لزوما بهترين طرح[13,31]. الگوريتمهاي ديگري بر اساس تركيب اين سه نوع روش داريم. كه در واقع يك حد ميانه بين دقت و سرعت را در نظر مي گيرند[18,20]. علاوه براين يكسري از الگوريتمهاي بهينه سازي تقاضا داريم كه براي اهداف خاصي طراحي شده اند كه         مي بايست به طور موضوعي آنها را بر اساس هدف مورد بررسي قرارداد. براي نمونه SDD-1 كه بر اساس الگوريتم hill-climbing عمل مي كند[2]. 
ديگر تكنيكهاي بهينه سازي تقاضا: بهينه سازي تقاضا بر پايه قاعده كه در آن فضاي جستجو و الگوريتم جستجو را از هم متمايز مي كند. بوسيله قوانين فضاي جستجو را تعريف مي كند و براي جستجو از الگوريتمهاي جستجوي عمومي استفاده مي كنند[31]. بهینه سازی تقاضا بر پایه قاعده زمانیکه تقاضای کاربر پیچیده باشد از جمله از نظر تعداد عملگر اتصال، کاراتر عمل می کند[22]. بهينه سازي تقاضا به طور تطبيقي در اين نوع روشها يك تعامل بين بهينه سازي و اجرا وجود دارد. در شكل 2-2 يك نمايي از    بهينه سازي تقاضا به طور تطبيقي  را مشاهده مي كنيد. 
 
شكل2-2: مقایسه کلی ساختار بهينه سازي تقاضا سنتی و تطبيقي
روش مفهومي بهينه سازي تقاضا يكي ديگر از  تحقيقات در زمينه بهينه سازي است كه طرح را بر اساس مفهوم تقاضا انتخاب نماييم كه در آن از مفاهيم پايگاه داده هاي منطقي استفاده شده است. البته این روش بیشتر به عنوان مکمل با روشهای دیگر بکار می رود. مثلا در [17]  با استفاده از اطلاعات نتیجه شده از محدودیتهای دیگر، تقاضای کاربر به گونه ای تغییر داده می شود که ضمن تامین مجموعه جواب مورد نظر کاربر، اجرای آن کاراتر می شود. 
علاوه براین روشها، تکنیکها و روشهایی هم برای بهینه سازی تقاضا در حالت معماریهای نامتمرکز پایگاهی ارائه شده اند، از جمله بهينه سازي تقاضاهاي چندگانه، بهينه سازي تقاضا در پایگاه داده های توزیع شده، در سیستم چند پایگاهی، در سیستم پایگاهی به صورت موازي و سیستم پایگاه داده های فشرده شده مي باشد[3,4,9,16]. 
در مباحث بالا بررسي اجمالي برالگوريتمهاي بهينه سازي تقاضا را بيان كرديم كه اكثر اين الگوريتمها براي عمل اتصال پياده سازي شده اند زيرا زمانبرترين قسمت در يك تقاضا مي باشد. مقوله اي كه ما مورد بررسي انجام داديم بهينه سازي تقاضا تحت رتبه بندي مي باشد كه براي بدست آوردن  Kجواب بهتر بكار مي روند. دراين تحقيق چند روش براي بهينه سازي تقاضا تحت رتبه بندي را مورد بررسي قرار داده و چگونگي اجراي تطبيقي تقاضاي رتبه ‌بندي را بيان مي كنيم.[9,10]
3- تقاضاي  تحت رتبه ‌بندي: 
رتبه بندی یک خصوصیت مهم است که مي بايست توسط موتورهای تقاضای رابطه ای پشتیباني شود. اخیراً چندین عملگر تقاضای اتصال تحت رتبه بندي بر پایۀ الگوریتم های رتبه بندی تجمعی پیشنهاد شده است. عملگر های اتصال رتبه بندي ترجیحاً هنگام عمل اتصال، نتایج اتصال را رتبه بندی می کنند. عملگر های جدید یک اثر مستقیم روی بهینه سازی و پردازش تقاضاهای سنتی دارند. روش مورد بررسي بر پایه توسعه سیستم الگوریتم برنامه نویسی پویا می باشد. رتبه بندی به عنوان یک خصوصیت مطلوب تعریف مي شود که طرح های تقاضای تحت رتبه بندی را بوجود می آورد. بر خلاف عملگرهای اتصال سنتی، بهینه سازی برای عملگرهای اتصال رتبه بندي وابسته به تخمين اندازه ورودی رابطه ها در این عملگرها می باشد که می بایست یک مدل احتمالی برای تخمين اندازه ورودی تعیین کرده و از این رو هزینه عملگر اتصال رتبه بندي تخمین زده شود. هزینه طرح های رتبه بندی در واقع به عنوان چالشی در زمینه بهینه سازی است، با این حال آن برای مجتمع سازی کامل عملگرهای اتصال رتبه بندي در موتورهای پردازش تقاضاها یک مسئله اساسی است.
یک دستاورد جديد، مجتمع سازی سیستمهای بازیابی اطلاعات و پایگاه داده می باشد تا بتوانیم تقاضاهای به سبک بازیابی اطلاعات که به عنوان یک نوع چالش برای تقاضاهای پایگاه داده است را پاسخ دهیم. بر اين اساس مي بايست تغييراتي در ساختارهاي زبان تقاضا داد و عملگرهاي جديدي بوجود آورد. بر خلاف تقاضاهای اتصال سنتی، پاسخ گویی به یک تقاضای اتصال K جواب بهتر یک مجموعۀ مرتب شده بر طبق مقداری می باشد که تابعی بر اساس ترکیب امتیازهای هر ورودی آنرا بدست مي آورد.  
برای اینکه عملگرهای رتبه بندی جدید به طور عملی مفید باشند، آنها می بایست در بهینه سازهای تقاضای دنیای واقعی بوجود آیند. عملگر اتصال رتبه بندي ممکن است همیشه بهترین روش برای فراهم کردن نتایج رتبه بندی مورد نیاز نباشد. در حقیقت، وابسته به بسیاری پارامترها ( برای مثال انتخاب پذیری اتصال، مسیرهای قابل دسترسی و اندازه حافظه ) می باشد که یک طرح سنتی اتصال سپس مرتب سازی ممکن است یک روش بهتری را برای نتایج رتبه بندی فرآهم آورد. بايد بسته به شرايط روش بهتر انتخاب شود.شکل 2-3 ارزیابی هزینه I/O را برای مقادیر مختلف انتخاب پذیری اتصال برای دو طرح ( طرح مرتب سازی و طرح اتصال رتبه بندي ) نشان می دهد. طرح مرتب سازی یک طرح سنتی است که عمل اتصال را بر روی دو ورودی انجام داده و نتایج را طبق تابع رتبه بندی مرتب می کند، در حالیکه طرح اتصال       رتبه بندي یک عملگر اتصال رتبه بندي را مورد استفاده قرار می دهد که به طور تدریجی نتایج اتصال     رتبه بندی شده را طبق تابع رتبه بندی بدست می آورد.
 
شكل2-3: ارزیابی هزینه I/O دو طرح مرتب سازی و اتصال رتبه بندي[9]
بر خلاف عملگرهای تقاضای سنتی، تخمين هزینه عملگرهای اتصال رتبه بندي سخت می باشد زیرا آنها خروج زودرس دارند. هر وقت که K جواب بهتر بدست آید، اجرا بدون استفاده از همه ورودی ها متوقف می شود. در اين روش مفهوم خصوصیات مطلوب در بهینه سازی تقاضا که شامل عبارات رتبه بندی مطلوب است، توسعه داده شده است و سپس بر اساس هزينه طرحهاي نا مطلوب هرس مي شود. در واقع یک مجتمع سازی بین الگوریتم های رتبه بندی تجمعی به سبک بازیابی اطلاعات و پردازش تقاضاهای رابطه ای رایج، اعمال شده است. حال که تا حدودی با مفاهیم رتبه بندی و تقاضا های تحت رتبه بندی آشنا شدیم، در بخش بعدی چند مقاله را در زمینه تقاضا های تحت رتبه بندی مورد بررسی قرار می دهیم.
4- کارهای پیشین
برای آشنایی مناسبتر با مسئله بهینه سازی تقاضای تحت رتبه بندی چند مقاله که انجام این  تحقیق تاثیر زیادی داشته اند را بیان می نماییم. یکی از جنبه های مهم در بهینه سازی تقاضای تحت رتبه بندی، تعیین اندازه ورودی برای رابطه های شرکت کننده در تقاضا می باشد. در بخش ذیل مقاله ای در این زمینه را که برای تقاضاهایی با دو رابطه بیان شده است را مورد بررسی قرار می دهیم.
 4-1 یک دستاورد مبتنی بر هرس کردن برای پشتیبانی اتصال تقاضاها یی با K جواب بهتر[19]
يك موضوع مهم در مجتمع سازي اطلاعات در مقياس بالا، انتخاب جوابهاي رتبه بندي K جواب بهتر ازچندين منبع مي باشد به طوريكه هزينه انتقال كمينه گردد. این مقاله این موضوع را با پیشنهاد یک دستاورد کارای مبتنی بر هرس کردن برای پاسخگویی اتصال تقاضاهایی با K جواب بهتر، حل می کند....
HyperLink
این مطلب را به اشتراک بگذارید:

     
Design And programming By www.bitasoft.ir