بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
بررسی استراتژیهای دسترسی بهینه برای تکه تکه شدن ژنتیکی پایگاه داده توزیع شده
چکیده
مجموعه ای از تکه تکه شدنها ،تخصیص و فرایندهای تکراری را توزیع شدن داده میگویند. یک پایگاه داده توزیع شده مجموعه ای از داده های منطقی هستند که به یک سیستم یکسان تعلق دارنداما در بیش از سایتهای یک شبکه کامپیوتری گسترش پیدا می کنند. سایتهایی از پایگاه داده توزیع شده می توانند آدرس شبکه یکسان داشته باشند و ممکن است در اتاق یکسانی هم باشند اما روابط بین آنها روی شبکه انجام می شود در عوض اینکه روی حافظه مشترک انجام شود.ارتباط با شبکه فقط منبع اشتراکی برای سیستم مدیریت پایگاه داده می باشد .
تکه تکه شدن یک تکنیک طراحی است که یک رابطه ساده یا کلاسی از پایگاه داده را به 2پارتیشن یا بیشتر تقسیم میکند که تر کیب میشوند از پارتیشنهایی که پایگاه داده اصلی را بدون هیچ کم و کاستی از اطلاعات که فراهم میکند .
زمانی که داده تخصیص داده میشود ممکن است یک کپی ساده از آن تکثیر یا نگهداری شود.
در این مقاله الگوریتم ژنتیکی ارائه داده ام که از ترکیب 3 الگوریتم ژنتیک: -1یک شبیه ساز تصادفی از استراتژیهای دسترسی بهینه برای یک طراحی یک پایگاه داده توزیع شده -.2استراتژیهای دسترسی بهینه برای طراحی پایگاه داده توزیع شده با استفاده از تکه تکه شدن ژنتیکی -3 استراتژیهای در دسترس بهینه برای طراحی یک پایگاه داده توزیع شده ،می باشد .برای بهبود ترتیبی تخصیص زیر پرس و جو روی سایتهای شبکه همراه با پیدا کردن برنامه تکه تکه شدن نزدیک های مطلوب برای گرههای مختلف یا سایتهایی برای جایگزینی صفات داده می باشد.
مقدمه
پرس و جو بهینه پایگاه داده توزیع شده از طریق بسیاری از زیر عملیات پیچیده روی روابط سایتهای شبکه، امکانات فرایند محلی و سیستم پایگاه داده ای خودشان بدست می آید||۳||روشهای قطعی با اکتشاف پایگاه داده توزیع شده، پرس و جو بهینه، تکه تکه شدن داده، تخصیص عمل، تکه تکه شدن ژنتیکی خاص و روشهای شمارش جامع شبیه سازی برنامه نویسی پویا ، تکنیکهای حریصانه، استرتژیهای تصادفی و .... روشهایی هستند در که حوزه بهبود از نظر تعداد سایت یا تعداد ارتباط دامنه، مشکل را افزایش می دهند ۱].
۲- کارهای تحقیقاتی مرتبط
یک جز کلیدی از هر رابطه بهینه پرس و جو پایگاه داده توزیع شده جدولهای تکه تکه شده و داده های تکه تکه شده توزیع شده روی
سایتهایی از شبکه است.[۲]
طراحی سیستمهای پایگاه داده و پرس و جو بهینه توزیع شده است و به عنوان یک فعالیت تحقیقاتی برای طک مدت زمان زیادی خواهد ماند. فعالیتهای تحقیقاتی در زمینه دسترسی بهینه یک پایگاه داده توزیع شده می تواند تقسیمات گسترده ای داشته باشد و برای مقایسه کارهای اولیه در سه طبقه می توان آنها را نام برد.: ۱
- تکنیکهای قطعی: شمارش جامع با کشفها (برنامه نویسی پویا)، خوشه و بسته، حریصانه، برنامه نویسی پویای تکرای
-2تکنیکهای به صورت تصادفی:بهبود تکرار،شبیه ساز loo mlasoa،بهبود مرحله دوم
-3تکنیهای تکاملی:الگوریتمهای ژنتیک،برنامه نویسی ژنتیکی هدف چند گانه
-1-2 شمارش جامع
روش اولیه در سیستمtc njmmpاز MBIو استفاده بعد برای بهبود پرس وجو بوسیله بیشتر فروشندگان S BIDاست.برنامه در دسترس ساخته میشود برای هر رابطه در مرحله اولیه و سپس الگوریتم میشمارد همه برنامهای در دسترس مورد استفاده پیوند دوگانه که بلوکهایی را در مرحله دوم میسازند فاز سوم که برنامه ریزی میشود به وسیله اتصال عملیاتی که یک برنامه کامل را می سازند .
SIMULATED ANNEALING-2-2
یک فرایند مشابه بازپختی از کریستالهاست که درجه نزدیک به نقطه فریز دارند.
به طور کلی بهینه کردن هر وضعیت بوسیله یک راه حل ممکن بوسیله قیمتی از یک راه حل پیشنهادی جایگزین میشود.[4]
این روش است پالایشی از بهبود تکرارالگوریتم تصادفی اولیه که رنج می برد برای پیداکردن عجولانه مینیمم قیمت محلی ،در عوض پیدا کردن یک مینیمم عمومی.
بیشتر کارها متمرکز شده اند روی دو جنبه :
-1تخصیص داده (برنامه ای از تخصیص تکه تکه شدنها روی سایتهای مختلف)
-2تخصیص عمل (چگونه تولید می شود یک دنباله از پرس وجوهای سایتهای مختلف )
آزمایشات شبیه سازی شده برای مقایسه از روش شاخه و بسته وبازپخت شبیه سازی و روشهای حریصانه برای مشکل تخصیص عمل استفاده می شود.
[3] یک مدل قیمت عالی برای کم کردن قیمتهایO/Mمحلی و UPC یارتباط در استراتژی تخصیص عمل ارائه میدهند.
[6] با توجه به فرایند موازی سازی و موازنه کردن بار داده و تخصیص عمل کارهایشان توسعه یافتند.
[7] در مورد جزئیات مشکل تخصیص و تکه تکه شدن آنها بحث می کند
-3 مدل قیمت
مشکل تخصیص زیر پرس وجو شامل پیدا کردن قیمت پرس و جو مینیمم بهینه ممکن توزیع شده iاز Rمیباشد.[3]
OSDCیک مدل برای جمع قطمت از کل تابع قیمت که دو جز دارد ارائه میدهد:[3]
-1 فرایند پرس وجو
-2 قیمت ذخیره شده
مجموعه ای از تکه تکه شدنها میباشد:R = {r1,r2,…,rn} یک شبکه از سایتها میباشد:S = {s1,s2,…,sm}
مجموعه ای از زیر پرس وجوهامی باشد:Q = {q1,q2,…,qn}
ما انتخاب می کنیم OSDCرا از قیمت پرس و جو که تابعی از مجموعه قیمتهای فرایند محلی و قیمتهای انتقال است.
با نادیده گرفتن قیمتهای به روز و نادیده گرفتن قیمتهای کنترل همزمانی قیمتهای OZSu مدلی را برای تراکنشهای بازیابی ارائه داد .دراین مدل اجزاء sMI+UUs را دور می اندازند. ما یک مدل ساده ازپرس وجو های بازیابی را نشان می دهیم.
جمع آنها می دهد کل اعداد از دسترسی تکه تکه شدنهای رجوع شده بهs q .اکنون kjjانتخاب میشود. در حالی که فقط ورودیهای ولوم قیمت را برای سایتهایی که تکه تکه شدند ودر حقیقت ذخیره شده اند.
-4 قیمتهای فرایند محلی
شروع
معادله (1) نشان می دهد قیمتهای فرایند محلی را از رابطه ورودی انتقال از یک دیسک به حافظه و زمان mtiبرای پردازش یک انتخاب یا پرتویی از سایتهای مدل nsi i نادیده میگیرد.جزئیات قیمت فرایند محلی را برای آن توسعه داده ایم این مدل با اضافه کردن جزئیات قیمتهای پیوند محلی که در زیر امده است
معادله l نشان میدهد قیمتهای خروجی ورودی در نتاطج متوسط ذخیره شده از عملیات قبلی از سایت از عملیات پیوند جاری می باشد.
معاله s نشان می دهد که قیمتهای /MO وبرای UPCکارائی عملیات پیوند جاری از سایت D می باشد.
-5 الگوریتم ژنتیک
الگورتیم ژنتیک تکنیک جستجویی در علم کامپیوتربرای یافتن راه حل تقریبی برای بهینه سازی و مسائل جستجو است.
بیشتر جمعیتها تولید می شود با استفده از اصول استاندارد AGبه عنوان مثال:انتخاب،متقاطع،جهش[2]
انتخاب: تابع هدف بهتر (کمترین قیمت ) که یک کروموزوم هست را میگیرد و شانس بیشتری را به او می دهد در دوباره تولید کردن در جمعیت بعدی.
-1-5 الگوریتم ژنتیک ارائه شده:
-1دادن مقدار اولیه ژن با رشته دودوئی تصادفی از کروموزمهای والد بین جایی کهi بزرگترین اتاi عدد صحیح از سایتها نباشد.
-2خواندن فایل داده ورودی شامل تراکنشهای مختلف و فرکانسهای صفات مورد نیاز
-3خواندن ویژگی خوشه ای ،محدود کردن ویژگیها و شاخصهای در دسترس
-4تکرارمرحله 1تا 3 برای استحکام جمعیت اولیه ژنها تا ژنها برابرNنشوند. (ژنها(N-1=
-5تولید یک استخر جمعیت اولیه از کروموزمهای پایه مختلف با کپی های متناسب با تناسب اندام که نیمی از عضوهای استخر تولید شده از پروفایلهای تراکنش ،پروفایلهای تخصیص داده و دیگر انتخابهای تصادفی روی هر سایتی هستند.
-6 انتخاب مدل باقیمانده تصادفی و دادن شانس بیشتر به عضوهای نصب شده برای ورود به استخر جفت گیری بر اساس نسبت بالاترین میانگین احتمال ارزش تناسب اندام
-7توانایی نخبه گرایی:ورود هر چه بیشتر عضو نصب شده به نسل بعدی از تولید قبلی در استخر جفت گیری بوسیله جایگزینی آن با نصب کمتر
-8در خواست تقاطع (0,6)وجهش (0,2)که استخر جمعیت جدید را تولید می کند.
-9 ارزیابی ارزشهای تناسب اندام متغیرها برای اینکه
-10قیمت ارزیابی شده هر عضواز هر برنامه تخصیص هدف برای کاهش قیمت کل از پرس و جو (بوسیله
-11 تولید کروموزمهای باقیمانده N-1از جمعیت جدید
