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

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

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

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

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

عنوان صفحه

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

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

فصل اول: مقدمه ۱

۱: تشریح مسئله ۳

۲: چالشها ۵

فصل دوم: مفاهیم اولیه و کار های پیشین ۶

۱: پردازش تقاضا ۷

۱-۱ : تجزیه تقاضا ۷

۱-۲ : بهینه سازی تقاضا ۷

۱-۳ : اجرای تقاضا ۸

۲ : روشهای بهینه سازی تقاضا ۹

۳ : تقاضای تحت رتبه ‌بندی ۱۱

۴ : کارهای پیشین ۱۲

۴-۱ : یک دستاورد مبتنی بر هرس کردن برای پشتیبانی اتصال تقاضاها یی با K جواب بهتر ۱۲

۴-۱-۱: مساله مورد بررسی ۱۲

۴-۱-۲: معماری کلی روش ۱۴

۴-۲ : بهینه سازی تقاضای تحت رتبه بندی ۱۵

عنوان صفحه

۴-۲-۱: رتبه بندی تجمعی ۱۶

۴-۲-۲: عملگرهای تقاضای اتصال رتبه بندی ۱۶

۴-۲-۳: بهینه سازی تقاضا بر پایه هزینه ۱۷

۴-۲-۴: طرح شمارش با استفاده از برنامه نویسی پویا ۱۷

۴-۲-۵: توسعه فضای شمارشی ۱۸

۴-۲-۶: طرح های هرس ۱۹

۴-۳ : بهینه سازی تطبیقی تقاضا های تحت رتبه بندی در پایگاه داده های رابطه ای ۲۲

۴-۳-۱: اجرای تطبیقی تقاضای رتبه‌بندی ۲۳

۴-۳-۲: اصلاح و استفاده‌ی مجدد طرح‌های رتبه‌بندی ۲۳

۴-۳-۳: تغییر طرح بر اساس بهینه‌ساز: ۲۵

۴-۳-۴: شیوه طرح اکتشافی تغییر برای تاخیرهای غیرمنتظره ۲۵

۴-۴ : بهینه سازی تقاضای محدود شده بهK 26

۴-۴-۱: استنتاج فضای وضعیت ایندکس ۲۸

۴-۴-۲: وضعیت هدف ۲۹

۴-۴-۳: الگوریتم ^*OPT 32

فصل سوم: روش پیشنهادی ۳۴

۱: بیان برخی از نقصهای کارهای پیشین ۳۵

۲: تجزیه کننده تقاضا ۳۶

۳: بهینه سازی تقاضای تحت رتبه بندی در سیستم متمرکز ۳۷

۳-۱: بهینه سازی تقاضای تحت رتبه بندی در سیستم متمرکز مبتنی بر هرس کردن ورودی رابطه ها ۳۸

۳-۱-۱: ساختار کلی الگوریتم ۴۰

۳-۲: بهینه سازی تقاضای تحت رتبه بندی در سیستم متمرکز با الهام گرفتن از جستجوی آگاهانه ۴۸

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

۴-۱: بهینه سازی تقاضای تحت رتبه بندی در سیستم توزیع شده مبتنی بر هرس کردن ورودی رابطه ها ۶۱

۴-۲: بهینه سازی تقاضای تحت رتبه بندی در سیستم توزیع شده با الهام گرفتن از جستجوی آگاهانه ۷۲

فصل چهارم: پیاده سازی و آزمایشها ۷۴

عنوان صفحه

۱: پیاده سازی های انجام شده ۷۵

۲: پایگاه داده های نمونه ۷۷

۳: پارامترهای مورد نظر برای مقایسه روشها ۷۹

۴: آزمایشهای انجام شده ۸۰

فصل پنجم: نتایج و پیشنهادها ۹۱

۱: نتایج ۹۲

۲: پیشنهادها ۹۲

مراجع ۹۴

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

عنوان صفحه

فصل اول

شکل ۱-۱: تقاضای نمونه ۴

فصل دوم

شکل۲-۱: مراحل پردازش تقاضا ۷

شکل۲-۲: مقایسه کلی ساختار بهینه سازی تقاضا سنتی و تطبیقی ۱۰

شکل۲-۳: ارزیابی هزینه I/O دو طرح مرتب سازی و اتصال رتبه بندی ۱۲

شکل ۲-۴: مثالی از روش هرس کردن برای تقاضاها یی با K جواب بهتر ۱۳

شکل ۲-۵: معماری کلی روش ۱۵

شکل۲-۶ : الگوریتم برای انتخاب K چند تایی بهتر ۱۵

شکل ۲-۷ : شمارش طرح تقاضای تحت رتبه بندی ۱۹

شکل۲-۸: دو طرح شمارش ۲۰

شکل۲-۹: نمایش دو طرحp_old, p_new ۲۴

شکل ۲-۱۰ : الگوریتم جستجوی OPT* 31

فصل سوم

شکل ۳-۱: تعیین ورودی های مورد نیاز برای بدست آوردن K جواب بهتر در دو رابطه R_۲ , R_۱ ۳۸

شکل ۳-۲: انواع ساختار درخت اتصال ۳۹

شکل۳-۳: درخت خطی ۳۹

شکل ۳-۴: ساختار سلسله مراتبی بالا – پایین، تعیین اندازه ورودی رابطه ها ۴۰

شکل ۳-۵: ایجاد شاخص ۴۱

شکل۳-۶: جزئیات تابع Prepare_Input_Size 42

شکل۳-۷: جزئیات تابع Min_Item 42

شکل۳-۸: جزئیات رویه Prepare_Left_Deep_Tree 43

شکل۳-۹: جابجایی و انتخاب مقادیر بدست آمده در مرحله جاری برای استفاده مرحله بعدی ۴۵

شکل۳-۱۰: زیر برنامه Swap_Item 46

عنوان صفحه

شکل۳-۱۱ : جزئیات تابع بهبود یافته Prepare_Input_Size 46

شکل۳-۱۲: جزئیات تابع بهبود یافته Min_Item 47

شکل۳-۱۳: جزئیات رویه بهبود یافته Prepare_Left_Deep_Tree 47

شکل۳-۱۴: زیر برنامه Compute_Bounds 50

شکل۳-۱۵: ساختار داخلی هر گره ۵۰

شکل۳-۱۶: جزئیات تابع Create_Tree 51

شکل۳-۱۷: جزئیات زیر برنامه Create_Interleaving 52

شکل۳-۱۸: جزئیات زیر برنامه Assign_Tuples_To_Leaf 52

شکل۳-۱۹: جزئیات تابع Create_Gneral_Tree 53

شکل۳-۲۰: جزئیات زیربرنامه Create_Neighbors_in_Leafs 54

شکل۳-۲۱: جزئیات زیربرنامه Achieve_TOPK_Result 56

شکل۳-۲۲: طرح های پایگاه داده توزیع شده ۵۷

شکل۳-۲۳: نحوه محاسبه تاخیر انتها به انتها ۵۸

شکل ۳-۲۴: جزئیات زیربرنامه Recognize_Location_for_Relations 60

شکل ۳-۲۵: جزئیات زیربرنامه هایی برای انجام عملهای انتخاب، پرتو و مرتب سازی ۶۲

شکل ۳-۲۶: جزئیات تابع Prepare_Input_Size1 64

شکل ۳-۲۷: جزئیات تابع Prepare_Input_size_In_Relation 65

شکل ۳-۲۸: جزئیات زیربرنامه Prepare_Input_size_In_Relations 65

شکل ۳-۲۹: جزئیات زیربرنامه Prepare_Input_sizeCommand 66

شکل ۳-۳۰: جزئیات زیربرنامه Prepare_Left_Deep_Tree 67

شکل ۳-۳۱: جزئیات ارسال اطلاعات اندازه ورودی و خروجی مورد نیاز رابطه ها به سیستمهای دیگر ۶۸

شکل ۳-۳۲: جزئیات تابع Obtain_Transfer_cost 68

شکل ۳-۳۳: جزئیات زیربرنامه های Obtain_Transfer_cost_In_SystemsوObtain_Transfer_costCommand 69

شکل ۳-۳۴: جزئیات زیر برنامه Send_Structure_Local_Tables 70

شکل ۳-۳۵: جزئیات زیر برنامه Structure_Table_for_CreateCommand 70

شکل ۳-۳۶: جزئیات زیربرنامه Save_Relation_To_File 71

عنوان صفحه

شکل ۳-۳۷: جزئیات زیربرنامه Receive_Data 71

شکل ۳-۳۸: جزئیات زیربرنامه Get_FileCommand 72

شکل ۳-۳۹: کلیات زیربرنامه Select_TOPK 72

فصل چهارم

شکل ۴-۱: نمایی از سیستم طراحی شده ۷۷

شکل ۴-۲: تنظیمات آدرس IP سیستم ها ۷۷

شکل ۴-۳: جزئیات رابطه های پایگاه داده NGDB2 79

شکل ۴-۴: سه تقاضای نمونه از پایگاه داده سیستم تولیدکننده ۸۱

شکل ۴-۵: هزینه زمانی اجرای تقاضای ۱ در سیستم متمرکز ۸۲

شکل ۴-۶: هزینه زمانی اجرای تقاضای ۱ در سیستم توزیع شده ۸۳

شکل ۴-۷: میزان اطلاعات ارسالی تقاضای ۱ در سیستم توزیع شده ۸۳

شکل ۴-۸: نسبت اندازه ورودی تعیین شده به اندازه ورودی مورد نیاز واقعی برای تقاضای۱ ۸۴

شکل ۴-۹: هزینه زمانی اجرای تقاضای ۲ را در سیستم متمرکز ۸۵

شکل ۴-۱۰: هزینه زمانی اجرای تقاضای ۲ را در سیستم توزیع شده ۸۵

شکل ۴-۱۱: میزان اطلاعات ارسالی تقاضای ۲ در سیستم توزیع شده ۸۶

شکل ۴-۱۲: نسبت اندازه ورودی تعیین شده به اندازه ورودی مورد نیاز واقعی برای تقاضای۲ ۸۶

شکل ۴-۱۳: هزینه زمانی اجرای تقاضای ۳ را در سیستم متمرکز ۸۷

شکل ۴-۱۴: هزینه زمانی اجرای تقاضای ۳ را در سیستم توزیع شده ۸۷

شکل ۴-۱۵: میزان اطلاعات ارسالی تقاضای ۳ در سیستم توزیع شده ۸۸

شکل ۴-۱۶: نسبت اندازه ورودی تعیین شده به اندازه ورودی مورد نیاز واقعی برای تقاضای۳ ۸۸

شکل ۴-۱۷: یک تقاضای نمونه از پایگاه داده NGDB2 89

شکل ۴-۱۸: هزینه زمانی اجرای تقاضای ۴ را در سیستم متمرکز ۸۹

شکل ۴-۱۹: هزینه زمانی اجرای تقاضای ۴ را در سیستم توزیع شده ۹۰

شکل ۴-۲۰: میزان اطلاعات ارسالی تقاضای ۴ در سیستم توزیع شده ۹۰

شکل ۴-۲۱: نسبت اندازه ورودی تعیین شده به اندازه ورودی مورد نیاز واقعی برای تقاضای۴ ۹۱