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

بخشی از پاورپوینت

اسلاید 1 :

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

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

الگوريتم Load Se sitive cou ter

الگوريتم I creme tal

الگوريتم optimal

الگوريتم Threshold

اسلاید 2 :

مقدمه

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

اسلاید 3 :

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

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

اسلاید 4 :

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

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

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

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

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

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

اسلاید 5 :

الگوريتم ژنتيک

فرض کنيد ri,j نشان دهنده نيازمندي سايت i به قطعه داده j مي باشد

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

  populatio را مقداردهي اوايه کن هر کدام از populatio هاي انفرادي اتصال  نمايش دودويي تخصيص تصادفي اوليه  هر قطعه داده مي ياشد.

  Populatio را ارزيابي کن.

  تعداد ge eratio =0

  تا وقتي که o of ge eratio < MAX GE ERATIO انجام بده

  I dividual ها را از populatio بعدي انتخاب کن

اسلاید 6 :

Crossover و Mutatio را براي I dividual ها انتخاب شده انجام بده

  Populatio   را ارزيابي کن

  تعداد ge eratio را يکي اضافه کن

  اتمام حلقه While

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

اسلاید 7 :

تفاوت اصلي الگوريتم ژنتيک با الگوريتم Simulated Evolutio  :

الگوريتم ژنتيک روي crossover دارد که يک مکانيزم احتمالي مي باشد و که براي تبادل اطلاعات بين راه حلها براي شناسايي بهترين راه حل مناسب مي باشد

الگوريتم Simulated Evolutio  از mutatio به عنوان مکانيزم جستجوي اوليه استفاده مي کند

اسلاید 8 :

اولين chromosome را براساس مسئله داده توليد کن و اين chromosome را براي توليد populatio اوليه تغيير بده.

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

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

تعداد ge eratio =0

تا وقتي که o of ge eratio s < MAX GE ERATIO انجام بده

Chromosome ها را براي populatio بعدي انتخاب کن

اسلاید 9 :

براي اين مجموعه کروموزوم ها crossover و mutatio انجام بده

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

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

تعداد ge eratio ها را يکي اضافه کن

پايان حلقه While

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

اسلاید 10 :

اوليه را بدست آور قرار بده T=T0

ميانگين spi ها را مقداردهي اوليه کن s = [s00, s01, . . . , sk−1,m−1 هر si j  با يک عدد تصادفي بين 0 و 1 مقداردهي اوليه مي شود

تا وقتي که temperature در بازه cooli g مي باشد انجام بده

تا وقتي که E کاهش مي يابد انجام بده

قطعه داده i را به صورت تصادفي انتخاب کن

Mea field ، spi ها را در رديف i محاسبه کن براي مثال : Φi j , ∀ j