الگوریتم های تخصیص داده پویا در سیستم های پایگاه داده توزیعی

n

nمقدمه

nالگوریتم های استاتیک

qالگوریتم ژنتیک

qالگوریتم Simulated Evolution

qالگوریتم The Mean Field Annealing (MFA)

qالگوریتم تخصیص داده جستجوی تصادفی همسایگی

q

nالگوریتمهای تخصیص پویا

qالگوریتم شمارنده ساده

qالگوریتم Load Sensitive counter

qالگوریتم Incremental

qالگوریتم optimal

qالگوریتم Threshold

n

q

• دغدغه اصلی سیستم های پایگاه داده توزیع شده قطعه قطعه کردن و تخصیص پایگاه داده اصلی می باشد واحد قطعه داده می تواند یک فایل باشد که در این حالت موضوع تخصیص همان تخصیص فایل خواهد بود مشکل تخصیص داده یک مسئله NP-complete می باشد
• نیاز به هیوریستیکهای سریع برای تولید راه حل های موثر می باشد
• تخصیص بهینه اشیا پایگاه داده به طور شدید بستگی به استراتژی اجرای پرس وجو که به وسیله پایگاه داده توزیع شده پیاده سازی شده دارد
• nهزینه اصلی در اجرای پرس و جو در سیستمهای پایگاه داده توزیع شده هزینه انتقال داده هنگام انتقال یک رابطه در موقع درخواست پرس و جو از یک سایت و انتقال آن از یک سایت متفاوت میباشد.

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

  n الگوریتم تخصیص داده پارامترهای زیر را به عنوان ورودی می گیرد :

  qگراف وابستگی قطعه داده

  qهزینه انتقال واحد داده ای بین سایتها

  qمحدودیتهای تخصیص روی تعداد قطعه داده که می تواند به سایت تخصیص داده شود

  qتعداد تکرار اجرای پرس و جو از سایتها