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

  • رتبه2 از 5
  • دوشنبه ۲۲ مهر ۱۳۹۸
  • الگوريتم هاي تخصيص داده پويا

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

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

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

    الگوريتمSimulated Evolution

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

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

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

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

    الگوريتمLoad Sensitive counter

    الگوريتمIncremental

    الگوريتمoptimal

    الگوريتمThreshold

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

    مقدمه

    § نياز به هيوريستيکهاي سريع براي توليد راه حل هاي موثر مي باشد

    § تخصيص بهينه اشيا پايگاه داده به طور شديد بستگي به استراتژي اجراي پرس وجو که به وسيله پايگاه داده توزيع شده پياده سازي شده دارد

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

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

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

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

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

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

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

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

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

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

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

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

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

    q Population را ارزيابي کن.

    q تعداد generation=0

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

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

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

    q Population را ارزيابي کن

    q تعداد generation را يکي اضافه کن

    q اتمام حلقه While

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

    الگوريتم Simulated Evolution

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

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

    q الگوريتم Simulated Evolution از mutation به عنوان مکانيزم جستجوي اوليه استفاده مي کند

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

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

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

    n تعداد generation=0

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

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

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

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

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

    n تعداد generation ها را يکي اضافه کن

    n پايان حلقه While

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

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

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

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

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

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

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

    n Mean field ، spin ها را در رديف i محاسبه کن براي مثال : Φi j , j

    n مجموع روبرو را محاسبه کن: ∑eΦij/T

    n


    ارائه شده توسط : سعید زمانی

    در وب سایت : پرشین جم


    تحقیق آماده | | بازدید | : persiangem

    ارسال دیدگاه برای پست : الگوريتم هاي تخصيص داده پويا - پایگاه داده

  • نرگس در مورد :مهم ترین فایده حجاب چیست میگه :

    نمیدونم

    پنجشنبه ۱۳ خرداد ۱۴۰۰ 1 ماه پیش

  • حسام در مورد :انواع تصمیم گیری را نام ببرید تفکر هشتم میگه :

    تصمیم گیری آنی

    پنجشنبه ۲۰ خرداد ۱۴۰۰ 1 ماه پیش

  • Rahil در مورد :میتوکندری چیست علوم هفتم میگه :

    عالی هر سوالی بخوای هست و به راحتی به جواب میرسی

    سه شنبه ۱۱ خرداد ۱۴۰۰ 1 ماه پیش

  • بنیامین در مورد :مهم ترین محصول کشاورزی آسیا میگه :

    مهپ ترین محصول کشاورزی اسیا چیست

    دوشنبه ۱۰ خرداد ۱۴۰۰ 2 ماه پیش

  • النا در مورد :من یک نوجوان ایرانی هستم که تصمیم دارم میگه :

    خوب

    پنجشنبه ۱۳ خرداد ۱۴۰۰ 1 ماه پیش

    • ...

    به نظر تان در پرشین جم چه مطالبی درج شود؟