میهن داکیومنت بزرگترین مرجع و مرکز دانلود پایان نامه (متن کامل فرمت ورد) فروش پایان نامه - خرید پایان نامه (کاردانی ، کارشناسی)همه رشته ها
حقوق اقتصاد مدیریت روانشناسی ریاضی تربیت بدنی کامپیوتر نرم افزار و سخت افزار عمران معماری برق صنایع غذایی علوم اجتماعی هنر علوم سیاسی فیزیک مکانیک حسابداری

تبلیغات کلیکی - افزایش رتبه گوگل

اگهی رایگان

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


کد محصول : 1000859 نوع فایل : word تعداد صفحات : 21 صفحه قیمت محصول : 2000 تومان تعداد بازدید 977

فهرست مطالب و صفحات نخست


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

مقدمه

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

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

 
شکل 1 : گراف وابستگي قطعه داده

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

فرض کنيد ri,j نشان دهنده نيازمندي سايت i به قطعه داده j مي باشد ، و هر قطعه داده i بوسيله اندازه اش مشخص مي شود که با si نشان داده مي شود و ti,j نشان دهنده هزينه اي است که سايت i متحمل مي شود تا به قطعه داده که در سايت j وجود دارد دسترسي پيدا کند مشکل تخصيص در سيستم هاي پايگاه داده توزيع شده پيدا کردن راه حلي است که داده ها طوري در سايت هاي موجود استقرار يابند که براي دسترسي به آنها کمترين هزينه را متحمل شويم . اين بدين معناست که ما عمل جايگزيني
 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 مي باشد.
الگوريتم ژنتيک يک تکنيک جستجوي تطابقي مي باشد که بر پايه اصول و مکانيزمهاي انتخاب طبيعي  و survival of the fittest از سير تکاملي تدريجي مي باشد با شبيه سازي سير تکاملي طبيعي  الگوريتم ژنتيک مي تواند به طور موثر حوزه مسئله را جستجو کند و به راحتي مسائل مشکل را حل کند . الگوريتم ژنتيک با توليد يک population اوليه شروع به کار مي کند ، P (t = 0) ، و هر کدام از اعضاي خود را با تابع هدف ارزيابي مي کند تا موقعي که شرايط پاياني  فراهم نشود يک قسمت از population انتخاب ، ارزيابي و برگردانده ميشود به population.[12]
الگوريتم ژنتيک براي مسئله تخصيص داده به صورت زير مي باشد :
1-    population را مقداردهي اوايه کن هر کدام از population هاي انفرادي اتصال  نمايش دودويي تخصيص تصادفي اوليه  هر قطعه داده مي ياشد.
2-    Population را ارزيابي کن.
3-    تعداد generation=0
4-    تا وقتي که no of generation < MAX GENERATION انجام بده
5-    Individual ها را از population بعدي انتخاب کن
6-    Crossover و Mutation را براي Individual ها انتخاب شده انجام بده
7-    Population  را ارزيابي کن
8-    تعداد generation را يکي اضافه کن
9-    اتمام حلقه While
10-    تخصيص نهايي را با انتخاب fittest individual مشخص مي کند اگر تخصيص نهايي قابل امکان نباشد سايتي که از نظر قطعه داده بار اضافي دارد بار آن را به سايتي منتقل مي کند که کمترين هزينه انتقال را دارد .
الگوريتم ژنتيک نسبت به استفاده از هيوريستيک حريصانه  روي مسئله اختصاص قطعه داده با سايزهاي مختلف کارايي  بيشتري دارد . هيوريستيک حريصانه زمان و تلاش زيادي براي پياده سازي نياز دارد در حاليکه الگوريتم عمومي ساده مي باشد .[12]

الگوريتم Simulated Evolution :
تفاوت اصلي الگوريتم ژنتيک با الگوريتم Simulated Evolution اين است که اولي روي crossover دارد که يک مکانيزم احتمالي مي باشد و که براي تبادل اطلاعات بين راه حلها  براي شناسايي بهترين راه حل مناسب مي باشد در حاليکه دومي از mutation به عنوان مکانيزم جستجوي اوليه استفاده مي کند. علاوه بر اينها در شماي مطرح شده نمايش  chromosomal بر پايه مشکل داده مي باشد و راه حل با استفاده از هيوريستيک کدگذاري  ( هيوريستيک نگاشت ) به منظور نگاشت از حوزه مسئله به حوزه راه حل توليد شده است . اين الگوريتم به صورت زير است :[7]
1-    اولين chromosome را براساس مسئله داده  توليد کن و اين chromosome را براي توليد population اوليه تغيير بده.
2-    از هيوريستيک نگاشت براي توليد راه حل براي هر chromosome استفاده کن.
3-    راه حل بدست آمده را ارزيابي کن
4-    تعداد generation=0
5-    تا وقتي که no of generations < MAX GENERATION انجام بده
6-    Chromosome ها را براي population بعدي انتخاب کن
7-    براي اين مجموعه کروموزوم ها crossover و mutation انجام بده
8-    از هيوريستيک نگاشت براي توليد راه حل براي هر chromosome استفاده کن.
9-    راه حل بدست آمده را ارزيابي کن
10-    تعداد generation ها را يکي اضافه کن
11-    پايان حلقه While
12-    بهترين راه حل پيدا شده تاکنون را به خروجي ببر

هيوريستيک نگاشت
براي هر کروموزوم يک راه حل با تخصيص قطعه داده j با الويت بالا براي سايت i پيدا مي کنيم طوريکه u’i j  براي تمام u’x j, 1<x <m کوچکترين باشد. اگر حد تخصيص موثر براي يک ژن موجود در قسمت a کروموزوم براي يک سايت فراتر رود ما اين قطعه داده را به سايتي اختصاص مي دهيم که u’ij اش کمترين مقدار بعدي ( هزينه تخصيص قطعه داده j به سايت i ) براي تمام u’yj, 1< y <m, y ≠ x باشد.اين واقعيت که هر قطعه داده به يک سايت تخصيص داده مي شود گارانتي مي شود براي اينکه هر بار چک مي شود حد تخصيص کلي بزرگتر يا مساوي تعداد قطعه هاي داده براي هر نسل   از کروموزوم ها باشد. سپس مي توانيم اين فرايند را براي هر قطعه داده با الويت بالا بين قطعه داده هاي ديگر که هنوز به سايتي تخصيص داده نشده ادامه پيدا مي کند.[9]

الگوريتم The Mean Field Annealing (MFA) :
تکنيک Mean Field Annealing  ويژگي محاسباتي بهم پيوسته  شبکه عصبي Hopfield را با 
simulated annealing ترکيب مي کند .MFA ابتدا براي حل مشکل فروشنده دوره گرد به جاي استفاده از الگوريتم HHN  که نمي توانست مسئله با اندازه بزرگ را حل کند مطرح گرديد MFA يک راه حل عمومي است که مي تواند براي حل مسئله هاي بهينه سازي ترکيبي مختلف استفاده شود.

 
شبکه عصبي Hopfield


الگوريتم MFA به صورت زير است :
1.    temperature اوليه را بدست آور قرار بده T=T0
2.    ميانگين spin ها را مقداردهي اوليه کن s = [s00, s01, . . . , sk−1,m−1 هر si j  با يک عدد تصادفي بين 0 و 1 مقداردهي اوليه مي شود
3.    تا وقتي که temperature در بازه cooling مي باشد انجام بده
4.    تا وقتي که E کاهش مي يابد انجام بده
5.    قطعه داده i را به صورت تصادفي انتخاب کن
6.    Mean field ، spin ها را در رديف i محاسبه کن براي مثال : Φi j , ∀ j
7.    مجموع روبرو را محاسبه کن: ∑eΦij/T
8.    مقدار spin جديد را در رديف i محاسبه کن
9.    تغييرات انرژي را به خاطر اين بروزرساني هاي جديد محاسبه کن
10.    پايان حلقه While
11.    temperature ، T را مطابق با زمانبندي cooling بروز کن
12.    پايان حلقه While
13.    تخصيص نهايي را با تخصيص هر قطعه داده به سايت با توجه به مقدار spin بزرگ مشخص کن . اگر تخصيص نهايي قابل امکان نباشد سايتي که قطعه داده اضافي دارد اين قطعه داده را به سايتي منتقل کن که کمترين هزينه را داشته باشد.[3]


الگوريتم تخصيص داده جستجوي تصادفي همسايگي
ايده اصلي در الگوريتم جستجوي همسايگي توليد يک راه حل اوليه با کيفيت مناسب  مي باشد سپس الگوريتم به طور احتمالي مطابق با برخي همسايگي هاي از قبل تعريف شده ، راه حل هاي مجاور  در فضاي جستجو را انتخاب و آزمايش مي کند که آيا از حالت قبل بهتر است يا نه ، اگر راه حل جديد بهتر باشد الگوريتم از اين راه حل اقتباس مي کند و جستجو را در همسايگي جديد آغاز مي کند در غير اينصورت الگوريتم نقطه جديدي را انتخاب مي کند الگوريتم کار خود را موقعي به اتمام مي رساند که يا تعداد قدمهاي جستجوي آن به يک مقدار مشخص برسد و يا اينکه بعد از تعدادي قدم بهبودي حاصل نشود کيفيت راه حل در الگوريتم جستجوي همسايگي بطور شديدي بستگي به راه حل همسايگي دارد الگوريتم براي مسئله تخصيص داده به صورت زير مي باشد:
1.    از Divisive-Clustering براي پيدا کردن تخصيص اوليه Initial Alloc استفاده کن
2.    Best Alloc = Initial Alloc
3.    New Alloc = Best Alloc; iteration = 0
تکرار کن
4.    searchstep = 0; counter = 0
تکرار کن
5.    به طور تصادفي دو سايت از Initial Alloc انتخاب کن
6.    به طور تصادفي دو قطعه داده از هر سايت انتخاب کن
7.    اين دو قطعه داده را با هم تبادل کن
8.    اگر هزينه کاهش پيدا کرد آنگاه
خود را با اين تبادل انطباق بده و counter را مساوي صفر قرار بده
در غير اين صورت undo کن و counter  را يکي اضافه کن
تا وقتي که ++searchstep > MAXSTEP OR counter > MARGIN
9.    اگر cost(New Alloc) < cost(Best Alloc) آنگاه
Best Alloc = New Alloc
10.    دو قطعه داده از دو سايت مجزا که به طور تصادفي از New Alloc انتخاب شده اند را با هم تبادل کن
تا وقتي که iteration > MAXITERATION [10]
به طور کلي SE و GA راه حلهاي بهتري نسبت به RS و MFA توليد مي کنند الگوريتم RS پيچيدگي زماني کمتري دارد بنابراين الگوريتم سريعي مي باشد ولي الگوريتم SE کند مي باشد براي حوزه هايي که بايستي سريع عمل کنيم و جواب بهينه مدنظر نمي باشد الگوريتم RS گزينه مناسبي مي باشد ولي اگر کارايي و کيفيت راه حل اهميت داشته باشد الگوريتم GA گزينه مناسب مي باشد بنابراين داشتن همه اين الگوريتم ها در سيستم پايگاه داده توزيع شده باعث مي شود که راه حلهاي متنوع داشته باشيم و اين راه حلها يک trade-off بين پيچيدگي و کيفيت مي باشد.
در [10] براي تخصيص قطعه داده يک متدي طراحي شده که نيازمنديهاي خوشه کردن  سايتها و تعيين تخصيص قطعه داده در سيستمهاي پايگاه داده توزيع شده را برطرف مي کند علاوه بر اينها هزينه ارتباط بين سايتها را کاهش مي دهد و کارايي را در محيط سيستمي شبکه غيرمتجانس  افزايش مي دهد . متد خوشه بندي به اين دليل استفاده شد که سايتها را در يک خوشه گروه بندي کنند که اين کار باعث کاهش هزينه ارتباط بين سايتها در فرآيند تخصيص داده مي شود . متد تخصيص قطعه داده با افزايش قابليت در دسترس بودن و قابليت اطمينان ( کپي هاي چندگانه از  قطعه هاي داده وجود دارد ) کارايي سيستم را افزايش مي دهد.

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

الگوريتم شمارنده ساده 
در اين الگوريتم با استفاده از يک شمارنده که تعداد دسترسي از هر سايت به هر بلاک را نگهداري مي کند استفاده مي شود براي اينکه مشخص شود کي تخصيص مجدد مورد نياز مي باشد شمارنده براي هر بلاک فقط در يکي از سايتهاي موجود در سيستم پايگاه داده توزيع شده نگهداري مي شود
براي مثال فرض کنيد پارتيشن A در سايت 1 قرار دارد در سيستمي با تعداد سايتهاي N ، سايت 1 N شمارنده براي پارتيشن A نگهداري مي کند . الگوريتم شمارنده ساده سايتهايي که به اين قطعه داده دسترسي پيدا مي کنند را رتبه بندي مي کند و بهترين سايت را انتخاب مي کند اين الگوريتم به صورت زير مي باشد:[3]

الگوريتم شمارنده ساده :
1.    يک فرايند state در بازه هاي زماني منظم شمارنده ها را براي هر بلاک چک ميکند
2.    سطرهاي يک بلاک در صورتي که شمارنده مربوط به آن بلاک در يک سايت بيشتر از سايتي باشد که بلاک هم اکنون در آن قرار دارد به آن سايت منتقل مي شود
3.    بعد از چک کردن شمارنده بلاک ها ، فرايند state قبل از چک کردن دوباره شمارنده ها براي تعداد t-check از تراکنشها که قرار است کامل شوند صبر مي کند

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

در اين الگوريتم فرايند وضعيت  فرايندي مي باشد که براي هر تراکنش   اطلاعات آماري مانند توان عملياتي و ميانگين زمان پاسخ و قسمتي از تراکنش کهنيازمند دسترسي به داده اي که در سايت ديگر ذخيره شده را نگهداري مي کند بايستي توجه داشته باشيم که مقدار t-check به اندازه کافي کوچک باشد تا سيستم در مقابل تغييرات بار واکنش سريع نشان دهد همچنين بايد به اندازه کافي بزرگ باشد تا اين تعداد تکرار دسترسي به يک بلاک که در يک سايت مشخص قرار دارد به يک مقدار ثابت برسد و بتوان از روي آن تصميم گيري کرد که بلاک بايد به کدام سايت منتقل شود . مشخص کردن اينکه آيا يک بلاک بايستي به سايت ديگر منتقل شود يا نه يک تصميم محلي   مي باشد به همين دليل شمارنده هر بلاک در سايتي قرار داده مي شود که بلاک هم در همان سايت قرار دارد . اين الگوريتم بر الگوريتم هاي تخصيص داده استاتيک برتري دارد.[3]

 


منابع :


 



 [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.

 

 

 
طراحی سایت : سایت سازان