فروشگاه

توضیحات

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

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

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

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

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

جواب بهتر، به صورت ساسله مراتبی و طبق درخت چپ ژرف برای عمل اتصال تعیین می نماییم، سپس اطلاعات محدود شده را به سیستمی

ارسال می کنیم که هزینه ارسال کمینه گردد و در سیستم مقصد اعمال

نهایی برای بدست آوردن K جواب بهتر را بر اساس دو استراتژی پیاده سازی

کردیم، در استراتژی اول، پس از دریافت اطلاعات مورد نیاز رابطه های محدود شده، عمل اتصال بین رابطه ها را بر اساس ترتیب تعیین شده انجام می

دهیم و در نهایت K جواب بهتر را بدست می آوریم. در استراتژی دوم پس از دریافت اطلاعات مورد نیاز، مسئله بهینه سازی را به جستجوی آگاهانه تبدیل

کرده و بر اساس ساختار درخت B+ ایجاد شده طبق رابطه های محدود شده،

K جواب بهتر را بدست می آوریم. یک پایگاه داده واقعی در نظر گرفتیم و این

دو روش را با روش سنتی بدون بهینه سازی و روش طبق جستجوی آگاهانه A* بیان شده در [۳۱]مقایسه کردیم که براساس نتایج بدست آمده، به طور

متوسط دو روش پیشنهادی زمانیکه میزان K در حدود ۲۰ درصد کل جوابها باشد دارای هزینه کمتری نسبت به روش سنتی و روش طبق جستجوی آگاهانه A* [31] می باشد، در ضمن بر اساس مقدار K، هزینه ارسال اطلاعات نیز از ۱۰ تا ۷۰ درصد کاهش یافته است.

 

۹۰صفحه فایل ورد (Word) فونت ۱۴ منابع  دارد

 

پس از پرداخت آنلاین میتوانید فایل کامل این پروژه را دانلود کنید 

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

 

 

فهرست
عنوان صفحه
فهرست مطالب و
فهرست شکلها ط
فصل اول: مقدمه ۱
۱: تشریح مسئله ۳
۲: چالشها ۵
فصل دوم: مفاهیم اولیه و کار های پیشین ۶
۱: پردازش تقاضا ۷
۱-۱ : تجزیه تقاضا ۷
۱-۲ : بهینه سازی تقاضا ۷
۱-۳ : اجرای تقاضا ۸
۲ : روشهای بهینه سازی تقاضا ۹
۳ : تقاضای تحت رتبه ‌بندی ۱۱

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

عنوان صفحه
۴-۲-۱: رتبه بندی تجمعی ۱۶
۴-۲-۲: عملگرهای تقاضای اتصال رتبه بندی ۱۶
۴-۲-۳: بهینه سازی تقاضا بر پایه هزینه ۱۷
۴-۲-۴: طرح شمارش با استفاده از برنامه نویسی پویا ۱۷
۴-۲-۵: توسعه فضای شمارشی ۱۸
۴-۲-۶: طرح های هرس ۱۹

۴-۳ : بهینه سازی تطبیقی تقاضا های تحت رتبه بندی در پایگاه داده های رابطه ای ۲۲
۴-۳-۱: اجرای تطبیقی تقاضای رتبه‌بندی ۲۳
۴-۳-۲: اصلاح و استفاده‌ی مجدد طرح‌های رتبه‌بندی ۲۳
۴-۳-۳: تغییر طرح بر اساس بهینه‌ساز: ۲۵
۴-۳-۴: شیوه طرح اکتشافی تغییر برای تاخیرهای غیرمنتظره ۲۵
۴-۴ : بهینه سازی تقاضای محدود شده بهK 26
۴-۴-۱: استنتاج فضای وضعیت ایندکس ۲۸

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

۴-۴-۲: وضعیت هدف ۲۹
۴-۴-۳: الگوریتم *OPT 32
فصل سوم: روش پیشنهادی ۳۴
۱: بیان برخی از نقصهای کارهای پیشین ۳۵
۲: تجزیه کننده تقاضا ۳۶
۳: بهینه سازی تقاضای تحت رتبه بندی در سیستم متمرکز ۳۷
۳-۱: بهینه سازی تقاضای تحت رتبه بندی در سیستم متمرکز مبتنی بر هرس کردن ورودی رابطه ها ۳۸
۳-۱-۱: ساختار کلی الگوریتم ۴۰
۳-۲: بهینه سازی تقاضای تحت رتبه بندی در سیستم متمرکز با الهام گرفتن از جستجوی آگاهانه ۴۸

۴: بهینه سازی تقاضای تحت رتبه بندی در سیستم توزیع شده ۵۷
۴-۱: بهینه سازی تقاضای تحت رتبه بندی در سیستم توزیع شده مبتنی بر هرس کردن ورودی رابطه ها ۶۱
۴-۲: بهینه سازی تقاضای تحت رتبه بندی در سیستم توزیع شده با الهام گرفتن از جستجوی آگاهانه ۷۲
فصل چهارم: پیاده سازی و آزمایشها ۷۴

عنوان صفحه
۱: پیاده سازی های انجام شده ۷۵
۲: پایگاه داده های نمونه ۷۷
۳: پارامترهای مورد نظر برای مقایسه روشها ۷۹
۴: آزمایشهای انجام شده ۸۰
فصل پنجم: نتایج و پیشنهادها ۹۱
۱: نتایج ۹۲
۲: پیشنهادها ۹۲
مراجع

 

 

بهینه سازی تقاضا یکی از مسائل مهم در سیستمهای مدیریت پایگاه داده می باشد. در سالهای اخیر بهینه سازی تقاضا از جنبه های مختلفی مورد

بررسی قرار گرفته است که به تفصیل در فصل ۲ بیان شده است. مقوله ای که مورد بررسی قرار دادیم بهینه سازی تقاضا تحت رتبه بندی می باشد که برای بدست آوردن Kجواب بهتر در یک تقاضا است که K توسط تقاضا تعیین می شود.

پدیدار شدن برنامه های کاربردی که وابسته به تقاضاهای رتبه بندی هستند،

پشتیبانی کارای تقاضاهای رتبه بندی را در سیستم های مدیریت پایگاه داده در دنیای واقعی طلب می کنند. پشتیبانی تقاضاهای رتبه بندی به سیستم های پایگاه داده توانایی پاسخ دادن کارا به تقاضاهای بازیابی اطلاعات را می دهد.
در سالهای اخیر، ترکیب مزایای سیستم های بازیابی اطلاعات و پایگاه داده یک هدف اصلی برای خیلی از محققان بوده است. سیستم های پایگاه داده، مدیریت داده را با جامعیت قوی و تضمین سازگاری فراهم می آورند. از طرف دیگر سیستم های بازیابی اطلاعات مکانیزم هایی برای بازیابی کارا و رتبه بندی فازی که برای کاربر مطلوب است، فراهم می نمایند.

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

موضوع مهم در این زمینه تعیین اندازه مورد نیاز ورودی ها در N رابطه برای پاسخگویی به تقاضای تحت رتبه بندی می باشد تا بدین وسیله بتوان K جواب بهتر مورد نظر را بدست آورد. درمجتمع سازی اطلاعات در مقیاس بالا، انتخاب

جوابهای رتبه بندی K جواب بهتر ازچندین منبع خیلی حیاتی می باشد و در کمینه کردن هزینه انتقال نقش اساسی دارد. زیرا هر چه اندازه رابطه ها کوچکتر باشد، هزینه کمتری برای انتقال صرف می گردد. علاوه براین انتخاب

روش مناسب برای تعیین اندازه ورودی مورد نیاز رابطه ها تاثیر چشم گیری در هزینه کل پردازش دارد بر اساس این مزیت روشهای مختلفی برای بهینه سازی تحت رتبه بندی ارائه شده است که مهمترین آنها را در فصل ۲ مورد بررسی قرار دادیم. روشهای بیان شده در زمینه بهینه سازی تقاضا تحت رتبه بندی غالبا در مقوله سیستمهای شخصی بیان شده اند، در حالیکه کاربرد عملی این تقاضاها در سیستمهای تحت وب و توزیع شده می باشد. بر این اساس تصمیم گرفتیم این روشها را برای سیستم توزیع شده بسط دهیم.

 

۱- تشریح مسئله

هنگامیکه یک تقاضا تحت رتبه بندی داریم که هدف بدست آوردن 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 جواب بهتر می باشد. نمونه ای از یک تقاضای تحت رتبه بندی در مثال ۱ بیان شده است.

 

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

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

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

دو سیستم وجود داشته باشند. البته از هر رابطه فقط یک نمونه وجود دارد یعنی عمل تکرار نیز در سیستم مورد بررسی نداریم. در این تقاضا خانواده تنها حداکثر به ۱۰ نتیجه بجای همه نتایج ممکن احتیاج دارد که از بین این

۱۰ نتیجه تصمیم گیری نماید و خانه مطلوب را انتخاب نماید. راه حل سنتی این است که ابتدا همه رابطه های مورد نیاز تقاضا در صورت عدم وجود به

سیستم اجرا کننده تقاضا به طور کامل ارسال می شوند سپس عمل اتصال بر روی دو رابطه انجام می شود، کلیه جوابها محاسبه شده و در نهایت بر اساس تابع رتبه بندی جوابها مرتب شده و ۱۰ تای اول انتخاب می شوند. در حالتیکه رابطه ها بزرگ و تعداد جوابها زیاد باشد، هزینه محاسبات و انتقال

اطلاعات نسبتا زیاد می باشد. البته برای K های بزرگ روش سنتی هزینه محاسباتی کمتری نسبت به روشهایی که اندازه ورودی را تخمین می زنند، دارد اما در این حالت نیز مشکل هزینه انتقال اطلاعات نسبتا زیاد می باشد.

در این تحقیق به جای اینکه در ابتدا رابطه ها را به طور کامل به سیستم تقاضا کننده ارسال کنیم، ابتدا بهینه سازی محلی را بر روی رابطه ها اعمال می کنیم و آنها را بر اساس عبارتیکه صفتهای رتبه بندی آنها در تابع رتبه بندی دارند، مرتب می کنیم، سپس ورودی های مورد نیاز برای ورودی ها را برای

بدست آوردن K جواب بهتر تعیین می نماییم، هزینه های انتقال را بررسی کرده و میزان اطلاعاتی از رابطه ها را می بایست منتقل شود به سیستمی با

کمترین هزینه ارسال می نماییم، در نهایت بر روی رابطه های نهایی عمل اتصال

را انجام داده و نتایج نهایی را بدست می آوریم یا در این حالت به جای عمل اتصال با الهام گرفتن از الگوریتمهای جستجوی آگاهانه، مسئله بهینه سازی را تبدیل به جستجوی آگاهانه کرده سپس توسط این رابطه های نهایی گراف را برای جستجو بر اساس صفتها و تابع رتبه بندی تشکیل داده و K جواب بهتر را بدست می آوریم.

۲- چالشها
برخی مشکلات برای انجام این تحقیق شامل موارد زیر می باشند:

۱- تعیین اندازه ورودی N رابطه بر اساس اندازه خروجی مورد نظر آنها: تا به حال روشهای ارائه شده الگوریتمی را برای N رابطه ارائه نداده اند فقط الگوریتمها برای تعیین اندازه ورودی دو رابطه می باشد.

۲- اعمال الگوریتمی برای سیستم توزیع شده: روشهای بررسی شده برای بهینه

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

پارامترهایی که در انتقال اطلاعات بین سیستمها موثرند بر روی روش پیشنهادی تاثیر می گذارند. کنترل ارسال و دریافت اطلاعات و نوع پروتکل نیز در الگوریتم کلی تاثیر گذارند.
۳- برای تبدیل مسئله بهینه سازی تقاضا به جستجوی آگاهانه : در این حالت البته روشهای کارایی ارائه شده است که چالش اصلی در آنها ساختن شاخصها بر روی رابطه ها بر اساس عبارتی که صفتهای رتبه بندی آنها در تابع رتبه بندی دارند و در نهایت ایجاد گراف حاصل از تمامی شاخصها بر اساس تابع رتبه بندی و جستجو بر روی آن می باشد. در ایجاد گراف و جستجو بر روی آن می بایست شرایط جستجوی آگاهانه را در نظر گرفت…………………………………

 

 

نقد وبررسی

نقد بررسی یافت نشد...

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

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

0 نقد و بررسی
وضعیت کالا : موجود است.
شناسه محصول : 2354

قیمت : تومان99,000