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

. الگوريتم هاي تخصيص داده پويا در سيستم هاي پايگاه داده توزيعي رئوس مطالب مقدمه الگوريتم هاي استاتيک الگوريتم ژنتيک الگوريتم Simulated Evolution الگوريتم )The Mean Field Annealing (MFA الگوريتم تخصيص داده جستجوي تصادفي همسايگی 2 رئوس مطالب الگوريتمهای تخصيص پويا الگوريتم شمارنده ساده الگوريتم Load Sensitive counter الگوريتم Incremental الگوريتم optimal الگوريتم Threshold 3 مقدمه دغدغ..ه اص..لي سيس..تم ه..اي پايگ..اه داده توزي..ع ش..ده قطع..ه قطع..ه ک..ردن و تخص.يص پايگ.اه داده اص.لي مي باش.د واح.د قطع.ه داده مي توان.د ي.ک فاي.ل باش.د ک.ه در اين ح.الت موض.وع تخص.يص هم.ان تخص.يص فاي.ل خواه.د ب.ود مش.کل تخص.يص داده يک مسئله NP-completeمي باشد ‏نياز به هيوريستيکهاي سريع براي توليد راه حل هاي موثر مي باشد ‏تخص.يص بهين.ه اش.يا پايگ.اه داده ب.ه ط.ور ش.ديد بس.تگي ب.ه اس.تراتژي اج.راي پ.رس وجو که به وسيله پايگاه داده توزيع شده پياده سازي شده دارد 4 مقدمه هزينه اصلي در اجراي پرس و جو در سيستمهاي پايگاه داده توزيع شده هزينه انتقال داده هنگام انتقال يک رابطه در موقع درخواست پرس و جو از يک سايت و انتقال آن از يک سايت متفاوت ميباشد. هدف اصلي الگوريتم هاي تخصيص داده تعيين نسبت دادن فرگمنتها به سايتهاي مختلف براي کمينه کردن هزينه انتقال داده در اجراي يک مجموعه از پرس و جو ها مي باشد 5 الگوريتم هاي استاتيک : الگوريتم تخصيص داده پارامترهاي زير را به عنوان ورودي مي گيرد : گراف وابستگي قطعه داده هزينه انتقال واحد داده اي بين سايتها محدوديتهاي تخصيص روي تعداد قطعه داده که مي تواند به سايت تخصيص داده شود تعداد تکرار اجراي پرس و جو از سايتها 6 الگوريتم ژنتيک فرض کنيد ri,jنشان دهنده نيازمندي سايت iبه قطعه داده j مي باشد الگوريتم ژنتيک براي مسئله تخصيص داده به صورت زير مي باشد : population را مقداردهي اوايه کن هر کدام از populationهاي انفرادي اتصال نمايش دودويي تخصيص تصادفي اوليه هر قطعه داده مي ياشد. Population را ارزيابي کن. تعداد generation=0 تا وقتي که no of generation < MAX GENERATIONانجام بده Individual ها را از populationبعدي انتخاب کن 7 الگوريتم ژنتيک Crossover و Mutationرا براي Individualها انتخاب شده انجام بده Population را ارزيابي کن تعداد generationرا يکي اضافه کن اتمام حلقه While تخصيص نهايي را با انتخاب fittest individualمشخص مي کند اگر تخصيص نهايي قابل امکان نباشد سايتي که از نظر قطعه داده بار اضافي دارد بار آن را به سايتي منتقل مي کند که کمترين هزينه انتقال را دارد . 8 الگوريتم Simulated Evolution تفاوت اصلي الگوريتم ژنتيک با الگوريتم : Simulated Evolution الگوريتم ژنتيک روي crossoverدارد که يک مکانيزم احتمالي مي باشد و که براي تبادل اطالعات بين راه حلها براي شناسايي بهترين راه حل مناسب مي باشد الگوريتم Simulated Evolutionاز mutationبه عنوان مکانيزم جستجوي اوليه استفاده مي کند 9 الگوريتم Simulated Evolution ‏ ‏ ‏ ‏ ‏ ‏ 10 اولين chromosomeرا براساس مسئله داده توليد کن و اين chromosomeرا براي توليد population اوليه تغيير بده. از هيوريستيک نگاشت براي توليد راه حل براي هر chromosomeاستفاده کن. راه حل بدست آمده را ارزيابي کن تعداد generation=0 تا وقتي که no of generations < MAX GENERATIONانجام بده Chromosomeها را براي populationبعدي انتخاب کن الگوريتم Simulated Evolution براي اين مجموعه کروموزوم ها crossoverو mutationانجام بده از هيوريستيک نگاشت براي توليد راه حل براي هر chromosomeاستفاده کن. راه حل بدست آمده را ارزيابي کن تعداد generationها را يکي اضافه کن پايان حلقه While بهترين راه حل پيدا شده تاکنون را به خروجي ببر 11 الگوريتم The Mean Field )Annealing (MFA ‏ ‏ ‏ ‏ ‏ ‏ 12 اوليه را بدست آور قرار بده T=T0 ميانگين spinها را مقداردهي اوليه کن s = [s00, s01, . . . , sk−1,m−1هر si jبا يک عدد تصادفي بين 0و 1 مقداردهي اوليه مي شود تا وقتي که temperatureدر بازه coolingمي باشد انجام بده تا وقتي که Eکاهش مي يابد انجام بده قطعه داده iرا به صورت تصادفي انتخاب کن Mean field ، spinها را در رديف iمحاسبه کن براي مثال Φi j , ∀ j : الگوريتم The Mean Field )Annealing (MFA مجموع روبرو را محاسبه کنeΦij/T∑ : مقدار spinجديد را در رديف iمحاسبه کن تغييرات انرژي را به خاطر اين بروزرساني هاي جديد محاسبه کن پايان حلقه While temperature ، T را مطابق با زمانبندي coolingبروز کن پايان حلقه While تخصيص نهايي را با تخصيص هر قطعه داده به سايت با توجه به مقدار spinبزرگ مشخص کن .اگر تخصيص نهايي قابل امکان نباشد سايتي که قطعه داده اضافي دارد اين قطعه داده را به سايتي منتقل کن که کمترين هزينه را داشته باشد 13 الگوريتم تخصيص داده جستجوي تصادفي همسايگی ‏ ‏ ‏ ‏ ‏ ‏ ‏ ‏ 14 از Divisive-Clusteringبراي پيدا کردن تخصيص اوليه Initial Allocاستفاده کن ‏Best Alloc = Initial Alloc ‏New Alloc = Best Alloc; iteration = 0 تکرار کن ‏searchstep = 0; counter = 0 تکرار کن به طور تصادفي دو سايت از Initial Allocانتخاب کن به طور تصادفي دو قطعه داده از هر سايت انتخاب کن الگوريتم تخصيص داده جستجوي تصادفي همسايگی اين دو قطعه داده را با هم تبادل کن اگر هزينه کاهش پيدا کرد آنگاه خود را با اين تبادل انطباق بده و counterرا مساوي صفر قرار بده در غير اين صورت undoکن و counterرا يکي اضافه کن تا وقتي که searchstep > MAXSTEP OR counter >++ ‏MARGIN اگر ) cost(New Alloc) < cost(Best Allocآنگاه ‏Best Alloc = New Alloc  دو قطعه داده از دو سايت مجزا که به طور تصادفي از New Allocانتخاب شده اند را با هم تبادل کن تا وقتي که iteration > MAXITERATION 15 الگوريتمهای تخصيص پويا : الگوريتم شمارنده ساده الگوريتم Load Sensitive counter الگوريتم Incremental الگوريتم : optimal الگوريتم : Threshold 16 الگوريتم شمارنده ساده ‏ ‏ ‏ 17 يک فرايند stateدر بازه هاي زماني منظم شمارنده ها را براي هر بالک چک ميکند سطرهاي يک بالک در صورتي که شمارنده مربوط به آن بالک در يک سايت بيشتر از سايتي باشد که بالک هم اکنون در آن قرار دارد به آن سايت منتقل مي شود بعد از چک کردن شمارنده بالک ها ،فرايند state قبل از چک کردن دوباره شمارنده ها براي تعداد t- checkاز تراکنشها که قرار است کامل شوند صبر مي کند الگوريتم Load Sensitive ‏counter هم بر تعداد دسترسي ها و هم بر بار (توازن داده) در سيستم نظارت کن اينکه بالک داده بايستي منتقل شود يا نه مانند الگوريتم شمارنده ساده مي باشد با اين تفاوت که بالک ها در صورتي منتقل مي شوند که مقدار بالک ذخيره شده در آن سايت از يک مقدار آستانه اي باالتر نرود .پارامترهاي الگوريتم عبارتند از : مقدار بالک داده بيشينه اي که يک سايت مي تواند در خود ذخيره کن و مقدار آستانه اي بار 18 الگوريتم Incremental وروديها: سرورهاي پايگاهداده توپولوژي شبکه رابطه هاي پايگاه داده پرسوجوها و حد آستانه ( تخصيصداده ) معرفي سرور جديد الگوريتم تخصيصمجدد ‏Yes هزينه کنوني> هزينه آستانه ‏No بهينه محلي خروجيها : سرورهاي پايگاه داده تخصيصدادهجديد 19 الگوريتم : optimal براي هر قطعه داده که به صورت محلي ذخيره شده سطر شمارنده دسترسي را برابر 0قرار بده ( Sik=0که ) k=1,2,…,n درخواست دسترسي به قطعه داده ذخيره شده را پراسس کن شمارنده دسترسي نودي که به اين قطعه داده دسترسي پيدا کرده را يکي افزايش بده ( اگر نود xبه قطعه داده iدسترسي پيدا کند قرار بده ) six=six+1 20 الگوريتم : optimal اگر نودي که به آن دسترسي شده همان نود جاري باشد که قطعه داده در آن قرار دارد برو به مرحله ( 2دسترسي محلي ) اگر شمارنده نود دور بيشتر از نودي باشد که قطعه داده در آن قرار دارد مالکيت اين قطعه داده همراه با آرايه مربوط به آن را به نود دور منتقل کن ( اگر نود xبه قطعه داده iدسترسي پيدا کند و six>sijباشد قطعه داده iرا به نود xبفرست ) برو به مرحله 2 21 الگوريتم : Threshold ‏ ‏ ‏ 22 براي هر قطعه داده که به صورت محلي ذحيره شده مقدار شمارنده را برابر صفر قرار بده ( براي هر قطعه داده iقرار بده ) si=0 درخواست دسترسي به قطعه داده را پراسس کن. اگر اين دسترسي يک دسترسي محلي باشد مقدار شمارنده اين قطعه داده را دوباره صفر کن ( اگر نود jبه قطعه داده iدسترسي پيدا کند قرار بده ) si=0برو به مرحله 2 الگوريتم : Threshold اگر اين دسترسي يک دسترسي دور باشد شمارنده مربوط به اين قطعه داده را يکي افزايش بده ( اگر قطعه داده iبه صورت دور دسترسي شود قرار بده si=si+1 اگر شمارنده اين قطعه داده از مقدار حد آستانه بيشتر باشد اين شمارنده را صفر کن و آن را به نود دور منتقل کن ( اگر si>tقرار بده si=0و قطعه داده را به نود دور منتقل کن) 23 منابع و مراجع           [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 I)ata 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. 24 منابع و مراجع         [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. [12] Ceri, S., Pernici, B., and Wiederhold, G., Optimization Problems and Solution Methods in the Design of Data Distribution, Information Systems, 14, 1989, 261-272. [13] Ceri, S., Navathe, S. B., and Wiederhold, G., Distribution Design of Logical Database Schemas, IEEE Transactions on Software Engineering, 9 , 1983, 487503. [14] Zhang, Y., and Orlowska, M. E., On Fragmentation Approaches for Distributed Database Design, Information Sci., 1, 1994, 117-132. 25 Thanks for you Attention 26