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

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

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

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

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

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

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

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

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

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

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

* اجرای عمل انتخاب حتی الامکان هر چه زودتر.

* اجرای عمل پرتو حتی الامکان هر چه زودتر.

* تعیین اینک کدام عمل انتخاب و پرتو، رابطه ای کوچکتر تولید می کنند.

* پردازش زیر عبارتهای مشترک در درخت، حتی الامکان یکبار و ...