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

مقدمه

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

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

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

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

مسئله تخصیص داده به طور کلی یک مسئله NP-complete می باشد و نیازمند هیوریستکهایی میباشد که راه حل سریع و با کیفیت بالا تولید کند. گسترش یک هیوریستیک موثر بستگی به استراتژی اجرای پرس و جویی دارد که توسط سیستمهای پایگاه داده توزیع شده بکار گرفته می شود که به این دلیل است که استراتژی مختلف اجرای پرس و جو الگو های مختلف انتقال داده متفاوت دارند[10] . الگوریتم تخصیص داده پارامترهای زیر را به عنوان ورودی می گیرد : 1 – گراف وابستگی قطعه داده 2- هزینه انتقال واحد داده ای بین سایتها 3 – محدودیتهای تخصیص روی تعداد قطعه داده که می تواند به سایت تخصیص داده شود 4 -  تعداد تکرار اجرای پرس و جو از سایتها[4]

گراف وابستگی[5] قطعه داده یک گراف بدون سیکل جهت دار می باشد که در ریشه[6] آن سایت اجرای پرس و جو قرار دارد و سایر نودها نودهای قطعه داده می باشد که ممکن است توسط پرس و جو مورد دسترسی قرار گیرد و این گراف وابستگی قطعه داده وابستگی بین قطعه داده و مقدار داده ای که بایستی موقع اجرای پرس و جو منتقل شود را مدل می کند .

(تصاویر در فایل اصلی موجود است)

الگوریتم ژنتیک [7]

فرض کنید ri,j نشان دهنده نیازمندی سایت i به قطعه داده j می باشد ، و هر قطعه داده i بوسیله اندازه اش مشخص می شود که با si نشان داده می شود و ti,j نشان دهنده هزینه ای است که سایت i متحمل می شود تا به قطعه داده که در سایت j وجود دارد دسترسی پیدا کند مشکل تخصیص در سیستم های پایگاه داده توزیع شده پیدا کردن راه حلی است که داده ها طوری در سایت های موجود استقرار یابند که برای دسترسی به آنها کمترین هزینه را متحمل شویم . این بدین معناست که ما عمل جایگزینی[8]

 P = {p1, p2, p3,..,pj, ...,pn}  ( که pj=i نشان دهنده قطعه داده j است که در سایت i واقع شده است)  برای n قطعه داده پیدا می کنیم بنابراین هر سایتی از ظرفیت خودش سرریز نمی شود و

 åri,j sj <= ci,j  "i |  1<=i<=m و ååri,j ti,pj    کمینه می شود.

با محدود کردن استفاده از نیازمندیهای ماتریس و هزینه انتقال صفر مسئله تخصیص پایگاه داده توزیع شده به مسئله bin packing تبدیل می شود که یک مسئله NP-complete می باشد.

الگوریتم ژنتیک یک تکنیک جستجوی تطابقی می باشد که بر پایه اصول و مکانیزمهای انتخاب طبیعی[9] و survival of the fittest از سیر تکاملی تدریجی می باشد با شبیه سازی سیر تکاملی طبیعی[10] الگوریتم ژنتیک می تواند به طور موثر حوزه مسئله را جستجو کند و به راحتی مسائل مشکل را حل کند . الگوریتم ژنتیک با تولید یک population اولیه شروع به کار می کند ، P (t = 0) ، و هر کدام از اعضای خود را با تابع هدف ارزیابی می کند تا موقعی که شرایط پایانی[11] فراهم نشود یک قسمت از population انتخاب ، ارزیابی و برگردانده میشود به population.[12]

الگوریتم ژنتیک برای مسئله تخصیص داده به صورت زیر می باشد :

population را مقداردهی اوایه کن هر کدام از population های انفرادی اتصال[12] نمایش دودویی تخصیص تصادفی اولیه[13] هر قطعه داده می یاشد.

Population را ارزیابی کن.

تعداد generation=0

تا وقتی که no of generation < MAX GENERATION انجام بده

Individual ها را از population بعدی انتخاب کن

Crossover و Mutation را برای Individual ها انتخاب شده انجام بده

Population  را ارزیابی کن

تعداد generation را یکی اضافه کن

اتمام حلقه While

تخصیص نهایی را با انتخاب fittest individual مشخص می کند اگر تخصیص نهایی قابل امکان نباشد سایتی که از نظر قطعه داده بار اضافی دارد بار آن را به سایتی منتقل می کند که کمترین هزینه انتقال را دارد .

الگوریتم ژنتیک نسبت به استفاده از هیوریستیک حریصانه[14] روی مسئله اختصاص قطعه داده با سایزهای مختلف کارایی[15] بیشتری دارد . هیوریستیک حریصانه زمان و تلاش زیادی برای پیاده سازی نیاز دارد در حالیکه الگوریتم عمومی ساده می باشد .[12]

الگوریتم Simulated Evolution :

تفاوت اصلی الگوریتم ژنتیک با الگوریتم Simulated Evolution این است که اولی روی crossover دارد که یک مکانیزم احتمالی می باشد و که برای تبادل اطلاعات بین راه حلها[16] برای شناسایی بهترین راه حل مناسب می باشد در حالیکه دومی از mutation به عنوان مکانیزم جستجوی اولیه استفاده می کند. علاوه بر اینها در شمای مطرح شده نمایش  chromosomal بر پایه مشکل داده می باشد و راه حل با استفاده از هیوریستیک کدگذاری[17] ( هیوریستیک نگاشت ) به منظور نگاشت از حوزه مسئله به حوزه راه حل تولید شده است . این الگوریتم به صورت زیر است :[7]

اولین chromosome را براساس مسئله داده[18] تولید کن و این chromosome را برای تولید population اولیه تغییر بده.

از هیوریستیک نگاشت برای تولید راه حل برای هر chromosome استفاده کن.

راه حل بدست آمده را ارزیابی کن

تعداد generation=0

تا وقتی که no of generations < MAX GENERATION انجام بده

Chromosome ها را برای population بعدی انتخاب کن

برای این مجموعه کروموزوم ها crossover و mutation انجام بده

از هیوریستیک نگاشت برای تولید راه حل برای هر chromosome استفاده کن.

راه حل بدست آمده را ارزیابی کن

تعداد generation ها را یکی اضافه کن

پایان حلقه While

بهترین راه حل پیدا شده تاکنون را به خروجی ببر

هیوریستیک نگاشت[19]

برای هر کروموزوم یک راه حل با تخصیص قطعه داده j با الویت بالا برای سایت i پیدا می کنیم طوریکه u’i j  برای تمام u’x j, 1

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

تکنیک Mean Field Annealing  ویژگی محاسباتی بهم پیوسته[21] شبکه عصبی Hopfield را با  

simulated annealing ترکیب می کند .MFA ابتدا برای حل مشکل فروشنده دوره گرد به جای استفاده از الگوریتم HHN[22] که نمی توانست مسئله با اندازه بزرگ را حل کند مطرح گردید MFA یک راه حل عمومی است که می تواند برای حل مسئله های بهینه سازی ترکیبی مختلف استفاده شود.