الگوریتم های تخصیص داده پویا در سیستم های پایگاه داده توزیعی
مقدمه
دغدغه اصلی سیستم های پایگاه داده توزیع شده قطعه قطعه کردن و تخصیص پایگاه داده اصلی می باشد واحد قطعه داده می تواند یک فایل باشد که در این حالت موضوع تخصیص همان تخصیص فایل خواهد بود مشکل تخصیص داده یک مسئله NP-complete می باشد
نیاز به هیوریستیکهای سریع برای تولید راه حل های موثر می باشد
تخصیص بهینه اشیا پایگاه داده به طور شدید بستگی به استراتژی اجرای پرس وجو که به وسیله پایگاه داده توزیع شده پیاده سازی شده دارد
هزینه اصلی در اجرای پرس و جو در سیستمهای پایگاه داده توزیع شده هزینه انتقال داده هنگام انتقال یک رابطه در موقع درخواست پرس و جو از یک سایت و انتقال آن از یک سایت متفاوت میباشد.
هدف اصلی الگوریتم های تخصیص داده تعیین نسبت دادن فرگمنتها به سایتهای مختلف برای کمینه کردن هزینه انتقال داده در اجرای یک مجموعه از پرس و جو ها می باشد
الگوریتم های استاتیک :
الگوریتم تخصیص داده پارامترهای زیر را به عنوان ورودی می گیرد :
گراف وابستگی قطعه داده
هزینه انتقال واحد داده ای بین سایتها
محدودیتهای تخصیص روی تعداد قطعه داده که می تواند به سایت تخصیص داده شود
تعداد تکرار اجرای پرس و جو از سایتها
الگوریتم ژنتیک
فرض کنید ri,j نشان دهنده نیازمندی سایت i به قطعه داده j می باشد
الگوریتم ژنتیک برای مسئله تخصیص داده به صورت زیر می باشد :
population را مقداردهی اوایه کن هر کدام از population های انفرادی اتصال نمایش دودویی تخصیص تصادفی اولیه هر قطعه داده می یاشد.
Population را ارزیابی کن.
تعداد generation=0
تا وقتی که no of generation < MAX GENERATION انجام بده
Individual ها را از population بعدی انتخاب کن
Crossover و Mutation را برای Individual ها انتخاب شده انجام بده
Population را ارزیابی کن
تعداد generation را یکی اضافه کن
اتمام حلقه While
تخصیص نهایی را با انتخاب fittest individual مشخص می کند اگر تخصیص نهایی قابل امکان نباشد سایتی که از نظر قطعه داده بار اضافی دارد بار آن را به سایتی منتقل می کند که کمترین هزینه انتقال را دارد .
فهرست مطالب
مقدمه
الگوریتم های استاتیک
الگوریتم ژنتیک
الگوریتم Simulated Evolution
الگوریتم The Mean Field Annealing (MFA)
الگوریتم تخصیص داده جستجوی تصادفی همسایگی
الگوریتمهای تخصیص پویا
الگوریتم شمارنده ساده
الگوریتم Load Sensitive counter
الگوریتم Incremental
الگوریتم optimal
الگوریتم Threshold
منابع و مراجع: