کارشناسی ارشد: بهینه سازی تقاضا تحت رتبه بندی در سیستم های توزیع شده
اختصاصی از یارا فایل کارشناسی ارشد: بهینه سازی تقاضا تحت رتبه بندی در سیستم های توزیع شده دانلود با لینک مستقیم و پرسرعت .
پروژه دوره کارشناسی ارشد
رشته کامپیوتر گرایش نرم افزار
بهینه سازی تقاضا تحت رتبه بندی در سیستم های توزیع شده
word and pdf and powerpoint
چکیده
تقاضای تحت رتبه بندی از کاربردی ترین تقاضا بر اساس نیاز کاربران می باشد، مهمترین مسئله در اجرای این تقاضاها در سیستم های توزیع شده، ارسال اطلاعات مورد نیاز تقاضا و بالطبع حداقل زمان اجرا می باشد، برای این منظور از روشهای بهینه سازی تقاضا تحت رتبه بندی استفاده می شود. در اجرای یک تقاضا، هزینه برترین عمل، عمل اتصال بین رابطه ها می باشد به همین دلیل در این تحقیق ابتدا اندازه مورد نیاز رابطه ها را بر اساس K جواب بهتر، به صورت ساسله مراتبی و طبق درخت چپ ژرف برای عمل اتصال تعیین می نماییم، سپس اطلاعات محدود شده را به سیستمی ارسال می کنیم که هزینه ارسال کمینه گردد و در سیستم مقصد اعمال نهایی برای بدست آوردن K جواب بهتر را بر اساس دو استراتژی پیاده سازی کردیم، در استراتژی اول، پس از دریافت اطلاعات مورد نیاز رابطه های محدود شده، عمل اتصال بین رابطه ها را بر اساس ترتیب تعیین شده انجام می دهیم و در نهایت K جواب بهتر را بدست می آوریم. در استراتژی دوم پس از دریافت اطلاعات مورد نیاز، مسئله بهینه سازی را به جستجوی آگاهانه تبدیل کرده و بر اساس ساختار درخت B+ ایجاد شده طبق رابطه های محدود شده، K جواب بهتر را بدست می آوریم. یک پایگاه داده واقعی در نظر گرفتیم و این دو روش را با روش سنتی بدون بهینه سازی و روش طبق جستجوی آگاهانه A* بیان شده در [31]مقایسه کردیم که براساس نتایج بدست آمده، به طور متوسط دو روش پیشنهادی زمانیکه میزان K در حدود 20 درصد کل جوابها باشد دارای هزینه کمتری نسبت به روش سنتی و روش طبق جستجوی آگاهانه A* [31] می باشد، در ضمن بر اساس مقدار K، هزینه ارسال اطلاعات نیز از 10 تا 70 درصد کاهش یافته است.
فهرست
عنوان صفحه
فهرست مطالب و
فهرست شکلها ط
فصل اول: مقدمه 1
1: تشریح مسئله 3
2: چالشها 5
فصل دوم: مفاهیم اولیه و کار های پیشین 6
1: پردازش تقاضا 7
- : تجزیه تقاضا 7
- : بهینه سازی تقاضا 7
- : اجرای تقاضا 8
- : روشهای بهینه سازی تقاضا 9
- : تقاضای تحت رتبه بندی 11
- : کارهای پیشین 12
- : یک دستاورد مبتنی بر هرس کردن برای پشتیبانی اتصال تقاضاها یی با K جواب بهتر 12
4-1-1: مساله مورد بررسی 12
4-1-2: معماری کلی روش 14
- : بهینه سازی تقاضای تحت رتبه بندی 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
- : بهینه سازی تطبیقی تقاضا های تحت رتبه بندی در پایگاه داده های رابطه ای 22
4-3-1: اجرای تطبیقی تقاضای رتبه‌بندی 23
4-3-2: اصلاح و استفاده‌ی مجدد طرح‌های رتبه‌بندی 23
4-3-3: تغییر طرح بر اساس بهینه‌ساز: 25
4-3-4: شیوه طرح اکتشافی تغییر برای تاخیرهای غیرمنتظره 25
- : بهینه سازی تقاضای محدود شده به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
عنوان &