بهینه سازی تقاضا تحت رتبه بندی در سیستم های توزیع شده
|
بهینه سازی تقاضا تحت رتبه بندی در سیستم های توزیع شده
پایان نامه و پروژه پایانی کارشناسی ارشد رشته کامپیوتر گرایش نرم افزار بهینه سازی تقاضا تحت رتبه بندی در سیستم های توزیع شده
|
|
| دسته بندی | کامپیوتر و IT |
| فرمت فایل | doc |
| حجم فایل | 6613 کیلو بایت |
| تعداد صفحات فایل | 90 |
پایان نامه و پروژه پایانی کارشناسی ارشد
رشته کامپیوتر گرایش نرم افزار
بهینه سازی تقاضا تحت رتبه بندی در سیستم های توزیع شده
*به همراه فایل پاورپوینت در 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
