کاربر گرامی  خوش آمدید ... 

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

مشخص نشده
مشخص نشده
19
مشخص نشده
227 KB
20771
قیمت: ۲,۰۰۰ تومان
دانلود مقاله
  • خلاصه
  • فهرست و منابع
  • خلاصه تحقیق مقاله الگوریتم های تخصیص داده پویا در سیستم های پایگاه داده توزیعی

    مقدمه

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

    دغدغه اصلی سیستم های پایگاه داده توزیع شده قطعه قطعه کردن[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 یک راه حل عمومی است که می تواند برای حل مسئله های بهینه سازی ترکیبی مختلف استفاده شود.

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

    فهرست:

    ندارد.
     

    منبع:

    [1]L. C. John, A Generic Algorithm for Fragment Allocation in Distributed Database Systems, ACM, 1994

     

    [2] Ahmad, I., K. Karlapalem, Y. K. Kwok and S. K. Evolutionary Algorithms for Allocating Data in Distributed Database Systems, International Journal of Distributed and Parallel Databases, 11: 5-32, The Netherlands, 2002.

     

    [3] A. Brunstroml, S. T. Leutenegger and R. Simhal, Experimental Evaluation of Dynamic Data Allocation Strategies in a Distributed Database with changing Workloads, ACM Transactions on Database Systems, 1995

     

    [4] A. G. Chin, Incremental Data Allocation and ReAllocation in Distributed Database Systems, Journal of Database Management; Jan-Mar 2001

    ; 12, 1; ABI/INFORM Global pg. 35

     

    [5] T. Ulus and M. Uysal, Heuristic Approach to Dynamic Data Allocation in Distributed Database Systems, Pakistan Journal of Information and Technology 2 (3): 231-239, 2003

    , ISSN 1682-6027

     

    [6] S. Voulgaris, M.V. Steen, A. Baggio, and G. Ballintjn, Transparent Data Relocation in Highly Available Distributed Systems. Studia Informatica Universalis. 2002

     

    [7] Navathe, S.B., S. Ceri, G. Wiederhold and J. Dou, Vertical Partitioning Algorithms for Database Design, ACM Transaction on Database Systems, 1984

    , 9: 680-710.

     

    [8] P.M.G. Apers, “Data allocation in distributed database systems,” ACM Transactions on Database Systems, vol. 13, no. 3, pp. 263–304, 1988.

     

    [9] Y. F. Huang and J. H. Chen, Fragment Allocation in Distributed Database Design

    Journal of Information Science and Engineering 17, 491-506, 2001

     

    [10] I. O. Hababeh , A Method for Fragment Allocation Design in the Distributed Database Systems, The Sixth Annual U.A.E. University Research Conference, 2005

     

    [11] R. Baseda, S. Tasharofi, M. Rahgozar, Near Neighborhood Allocation: A Novel Dynamic Data Allocation Algorithm in DDB, CSICC 2006.

کلمات کلیدی:  N/A
تحقیق در مورد تحقیق مقاله الگوریتم های تخصیص داده پویا در سیستم های پایگاه داده توزیعی, مقاله در مورد تحقیق مقاله الگوریتم های تخصیص داده پویا در سیستم های پایگاه داده توزیعی, تحقیق دانشجویی در مورد تحقیق مقاله الگوریتم های تخصیص داده پویا در سیستم های پایگاه داده توزیعی, مقاله دانشجویی در مورد تحقیق مقاله الگوریتم های تخصیص داده پویا در سیستم های پایگاه داده توزیعی, تحقیق درباره تحقیق مقاله الگوریتم های تخصیص داده پویا در سیستم های پایگاه داده توزیعی, مقاله درباره تحقیق مقاله الگوریتم های تخصیص داده پویا در سیستم های پایگاه داده توزیعی, تحقیقات دانش آموزی در مورد تحقیق مقاله الگوریتم های تخصیص داده پویا در سیستم های پایگاه داده توزیعی, مقالات دانش آموزی در مورد تحقیق مقاله الگوریتم های تخصیص داده پویا در سیستم های پایگاه داده توزیعی
امتیاز کاربران: 

دریافت لینک دانلود به صورت خودکار بلافاصله پس از پرداخت

امکان پرداخت آنلاین از طریق کلیه کارت های عضو شتاب

ثبت سفارش
تعداد
عنوان محصول