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

 پایان نامه و پروژه پایانی  کارشناسی ارشد

رشته کامپیوتر گرایش نرم افزار 

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

*به همراه فایل پاورپوینت در 27 اسلاید

فهرست

عنوان                                           صفحه

فهرست مطالب                                                                                                             و

فهرست شکلها                                                                                                            ط

فصل اول: مقدمه                                                                                                         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