دانلود ‫پروژه بهینه سازی تقاضا تحت رتبه بندی در سیستمهای مدیریت پایگاه داده

بهینه سازی تقاضا یکی از مسائل مهم در سیستمهای مدیریت پایگاه داده می باشد. در سالهای اخیر بهینه سازی تقاضا از جنبه های مختلفی مورد بررسی قرار گرفته است که به تفصیل در فصل 2 بیان شده است. مقوله ای که مورد بررسی انجام دادیم بهینه سازی تقاضا تحت رتبه بندی می باشد که برای بدست آوردن Kجواب بهتر در یک تقاضا است که K توسط تقاضا تعیین می شود.
1- انگیزه تحقیق
پدیدار شدن برنامه های کاربردی که وابسته به تقاضاهای رتبه بندی هستند، پشتیبانی کارای تقاضاهای رتبه بندی را در سیستم های مدیریت پایگاه داده در دنیای واقعی طلب می کنند. پشتیبانی تقاضاهای رتبه بندی به سیستم های پایگاه داده توانایی پاسخ دادن کارا به تقاضاهای بازیابی اطلاعات را می دهد.
در سالهای اخیر، ترکیب مزایای سیستم های بازیابی اطلاعات و پایگاه داده یک هدف اصلی برای خیلی از محققان بوده است. سیستم های پایگاه داده، مدیریت داده را با جامعیت قوی و تضمین سازگاری فراهم می آورند. از طرف دیگر سیستم های بازیابی اطلاعات مکانیزم هایی برای بازیابی کارا و رتبه بندی فازی که برای کاربر مطلوب است، فراهم می نمایند.
موضوع مهم در این زمینه تعیین اندازه مورد نیاز ورودی ها در N رابطه برای پاسخگویی به تقاضای تحت رتبه بندی می باشد تا بدین وسیله بتوان TOP K مورد نظر را بدست آورد. درمجتمع سازی اطلاعات در مقیاس بالا، انتخاب جوابهای رتبه بندی TOP K ازچندین منبع خیلی حیاتی می باشد و در کمینه کردن هزینه انتقال نقش اساسی دارد. زیرا هر چه اندازه رابطه ها کوچکتر باشد، هزینه کمتری برای انتقال صرف می گردد. علاوه براین انتخاب روش مناسب برای تعیین اندازه ورودی مورد نیاز رابطه ها تاثیر چشم گیری در هزینه کل پردازش دارد بر اساس این مزیت روشهای مختلفی برای بهینه سازی تحت رتبه بندی ارائه شده است که مهمترین آنها را در فصل 2 مورد بررسی قرار دادیم. روشهای بیان شده در زمینه بهینه سازی تقاضا تحت رتبه بندی غالبا در مقوله سیستمهای شخصی بیان شده اند، در حالیکه کاربرد عملی این تقاضاها در سیستمهای تحت وب و توزیع شده می باشد. بر این اساس تصمیم گرفتیم این روشها را برای سیستم توزیع شده بسط دهیم.


2- تشریح مسئله
هنگامیکه یک تقاضا تحت رتبه بندی داریم که هدف بدست آوردن TOP K می باشد، در این حالت به تمامی رکورد های جدول نیاز نداریم، بر اساس مقدار K تعدادی از رکوردها در رابطه ها که امتیاز کمی دارند در نتیجه نهایی نقشی ندارند و بهتر است آنها هرس شوند و برای محاسبات و انتقال اطلاعات زمانی را برای این رکوردها تلف نکنیم. ابتدا تعریفی از یک تقاضای تحت رتبه بندی را در زیر بیان می کنیم.
در تقاضای تحت رتبه بندی، تقاضا بر روی M صفت A1، A2، ... ، AN و N رابطه به صورت R1، R2، ... ، RN تعریف می شود که هر Ai(i=1:M) متعلق به یک رابطه Rj (j=1:N) می باشد. هر یک از صفتها نسبت به نوع شان دارای دامنه خاصی می باشند. R1، R2، ... ، RN در M سیستم به صورت توزیع شده قرار دارند به صورتیکه هر رابطه به طور کامل بر روی یک سیستم قرار دارد به عبارت دیگر عمل partitioning بر روی رابطه ها را در پایگاه توزیع شده بین سیستمها را در این تحقیق نداریم.
با توجه به تقاضا یکسری از صفتهای این رابطه ها برای عمل پرتو بکار می روند که به عنوان صفتهایی می باشند که در رکوردهای حاصل مورد استفاده قرار می گیرند یکسری از صفتهای این رابطه ها برای عمل انتخاب بکار می روند که در واقع شرط های منطقی هستند که بر روی رکوردهای رابطه ها اعمال می شوند و رکودهایی دارای این محدودیتها می باشند می توانند برای مراحل بعدی مورد استفاده قرار بگیرند.برخی از صفتها برای عمل اتصال مورد استفاده قرار می گیرد، هنگامیکه چند رابطه داریم برای اینکه عمل اتصال بین آنها را بر قرار کنیم می بایست صفتهای اتصال را برای هر یک از روابط تعیین نماییم، اگر برای دو رابطه Ri و Rj صفتی برای اتصال وجود نداشته باشد، SQL به جای عمل اتصال، ضرب دکارتی را بین این دو رابطه انجام می دهد. در تقاضا ها ی تحت رتبه بندی بخشی برای رتبه بندی داریم که برخی از صفتهای رابطه ها به صورت یک عبارت رتبه بندی بیان می شود که به آن تابع رتبه بندی گفته می شود.
تابع رتبه بندی f به صورت ترکیبی از M' صفت تشکیل شده است که درآن M'<=m می="" باشد.="" فرضی="" که="" برای="" تابع="" رتبه="" بندی="" f="" داریم="" این="" است="" که="" تغییرات="" تابع="" رتبه="" بندی="" نسبت="" به="" کل="" رابطه="" ها="" یکنواخت="" باشد.="" البته="" در="" تابع="" رتبه="" بندی="" مورد="" نظر="" تغییرات="" تابع="" نسبت="" به="" هر="" رابطه="" می="" تواند="" غیر="" یکنواخت="" باشد="" علاوه="" براین="" در="" تقاضاها="" ی="" تحت="" رتبه="" بندی="" تعداد="" جوابهای="" مطلوب="" نیز="" تعیین="" می="" شود="" که="" همان="" top="" k="" می="" باشد.="" نمونه="" ای="" از="" یک="" تقاضای="" تحت="" رتبه="" بندی="" در="" مثال="" 1="" بیان="" شده="">

مثال1: یک خانواده مایل به خرید خانه‌ای در نزدیکی یک مدرسه می‌باشد و هدف آنها کاهش هزینه‌های کلی‌شان می‌باشد. یک تابع رتبه بندی ساده که مجموع قیمت خانه و هزینه شهریه 5 سال مدرسه را برآورد می کند در نظر بگیرید. می بایست عمل جستجو در دو رابطه خانه‌ و مدرسه در پایگاه داده، بر اساس تقا ضای زیر صورت گیرد.
SELECT *
FROM House, School
( WHERE ( DISTANCE (House.Location , School.Location) <>
ORDER BY ( House.Price + 5 * School.Tuition )
Top 10
رابطه های House و School می توانند در یک سیستم توزیع شده بر روی یک یا دو سیستم وجود داشته باشند. البته از هر رابطه فقط یک نمونه وجود دارد یعنی عمل Replication نیز در سیستم مورد بررسی نداریم. در این تقاضا خانواده تنها حداکثر به 10 نتیجه بجای همه نتایج ممکن احتیاج دارد که از بین این 10 نتیجه تصمیم گیری نماید و خانه مطلوب را انتخاب نماید. راه حل سنتی این است که ابتدا همه رابطه های مورد نیاز تقاضا در صورت عدم وجود به سیستم اجرا کننده تقاضا به طور کامل ارسال می شوند سپس عمل اتصال بر روی دو رابطه انجام می شود، کلیه جوابها محاسبه شده و در نهایت بر اساس تابع رتبه بندی جوابها مرتب شده و 10 تای اول انتخاب می شوند. در حالتیکه رابطه ها بزرگ و تعداد جوابها زیاد باشد، هزینه محاسبات و انتقال اطلاعات نسبتا زیاد می باشد. البته برای K های بزرگ روش سنتی هزینه محاسباتی کمتری نسبت به روشهایی که اندازه ورودی را تخمین می زنند، دارد اما در این حالت نیز مشکل هزینه انتقال اطلاعات نسبتا زیاد می باشد.
در این تحقیق به جای اینکه در ابتدا رابطه ها را به طور کامل به سیستم تقاضا کننده ارسال کنیم، ابتدا بهینه سازی محلی را بر روی رابطه ها اعمال می کنیم و آنها را بر اساس عبارتیکه صفتهای رتبه بندی آنها در تابع رتبه بندی دارند، مرتب می کنیم، سپس ورودی های مورد نیاز برای ورودی ها را برای بدست آوردن K جواب بهتر تعیین می نماییم، هزینه های انتقال را بررسی کرده و میزان اطلاعاتی از رابطه ها را می بایست منتقل شود به سیستمی با کمترین هزینه ارسال می نماییم، در نهایت بر روی رابطه های نهایی عمل اتصال را انجام داده و نتایج نهایی را بدست می آوریم یا در این حالت به جای عمل اتصال با الهام گرفتن از الگوریتمهای جستجو آگاه، مسئله بهینه سازی را تبدیل به جستجوی آگاه کرده سپس توسط این رابطه های نهایی گراف را برای جستجو بر اساس صفتها و تابع رتبه بندی تشکیل داده و K جواب بهتر را بدست می آوریم.


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