چکیده
در یک سیستم مدیریت بانک اطلاعاتی توزیع شده قبل از طرح یک پرسجو، جهت کم کردن هزینه های ارتباطی در پرسجوهایی که در آینده مطرح خواهند شد و یا به عبارت دیگر تولید یک بستر بهینه مسئله تخصیص داده ها به سایت های مختلف مطرح می شود که جزو مسائل NP می باشد. اما وقتی پرسجویی در یکی از سایت ها مطرح می شود، جهت استخراج اطلاعات مربوط که در سایت های دیگر قرار دارند، طرح های اجرایی مختلف، مدل های انتقالی مختلفی مطرح می شوند که نتیجه یکسان ولی هزینه اجرایی متفاوتی دارند. اما سوال اینجاست که برای اجرای بهینه یک پرسجو در یک سیستم توزیع شده با توجه به مسائل فوق چه باید کرد. در این تحقیق سعی شده روشهای تخصیص داده در یک سیستم توزیع شده بررسی گردد، سپس به بیان روشهای تولید طرح بهینه و الگوریتم های موجود پرداخته شود.
فهرست مطالب
فصل 1: مقدمه 6
1-1 مقدمه 7
1-2 سیستم های پایگاه داده توزیع شده. 7
1-3 پایگاه اطلاعات توزیع شده 8
1-4 قوانین Date برای پایگاه داده توزیع شده 9
1-4-1 خود مختاری محلی 10
1-4-2 عدم وابستگی به یک سایت مرکزی 10
1-4-3 پیوستگی عملیات 10
1-4-4 نامرئی بودن مکان 10
1-4-5نامرئی بودن تکه تکه کردن 10
1-4-6 نامرئی بودن نسخه سازی 11
1- 4-7پردازش پرسش توزیع شده 11
1-4-8 مدیریت تراکنش توزیع شده: 11
1-4-9 نامرئی بودن سخت افزار: 11
1-4-10 نامرئی بودن سیستم عامل: 11
1-4-11نامرئی بودن شبکه 11
1-4-12 نامرئی بودن سیستم مدیریت پایگاه داده توزیع شده 11
1-5 روشهای توزیع داده 12
1-5-1 روش استخراج دستی یا متمرکز 12
1-5-2 تکه تکه کردن داده 12
1-5-2-1 تکه تکه کردن افقی 12
1-5-2-2 تکه تکه کردن عمودی 12
1-5-2-3 تکه تکه کردن مختلط 12
1-6 نسخه سازی از داده ها 13
1-6-1 نسخه سازی کامل 13
1-6-2 نسخه سازی جزئی 13
1-6-3 تصویر فرار 13
1-7 معماری سیستم پایگاه داده توزیع شده 14
فصل 2: بهینه سازی پرسجو 16
2-1 بهینه سازی پرس و جو 17
2-2 روشهای بهینه سازی پرسجو در بانک های اطلاعاتی توزیع شده 18
2-2-1 تخصیص داده 18
2-2-1-1 الگوریتم های استاتیک 19
2-2-1-1-1 الگوریتم ژنتیک 20
2-2-1-1-2 الگوریتم Simulated Evolution 22
2-2-1-1-3 هیوریستیک نگاشت 23
2-2-1-1-4 الگوریتم The Mean Field Annealing (MFA) 23
2-2-1-1-5 الگوریتم تخصیص داده جستجوی تصادفی همسایگی 25
2-2-1-2 الگوریتم تخصیص پویا 26
2-2-1-2-1 الگوریتم شمارنده ساده 27
2-2-1-2-2- الگوریتم Load Sensitive counter 28
2-2-1-2-3 الگوریتم Incremental 29
2-2-1-2-4 الگوریتم Threshold 30
2-2-1-2-5 الگوریتم Near Neighborhood Allocation با حد آستانه نسبی(RTNNA) 35
2-2-1-2-6 الگوریتم Revise Relative Threshold Near Neighborhood Allocation 37
2-2-2 تولید طرح اجرای بهینه 37
2-2-2-1 گراف پیوند 38
2-2-2-2 الگوریتم های قطعی 39
2-2-2-2-1 برنامه ریزی دینامیکی 39
2-2-2-2-2 الگوریتم دایجسترا 40
2-2-2-2-3 الگوریتم جستجوی A* 42
2-2-2-3 الگوریتم های غیر قطعی 43
2-2-2-3-1 گردش تصادفی 43
2-2-2-3-2 نزدیکترین همسایگی در درخت پرپشت 43
2-2-2-3-3 شبیه سازی سرد شدن فلزات 44
2-2-2-3-4 تپه نوردی 44
2-2-2-3-5 الگوریتم ژنتیک 45
2-2-2-3-6 الگوریتم اصلاح مکرر 45
2-2-2-3-7 اتوماتهای یادگیر 46
2-2-2-3-8 ترکیب الگوریتم ژنتیک و آتاماتای یادگیر 47
2-2-2-3-8-1 ژن و کروموزوم 48
2-2-2-3-8-2تابع برازندگی 50
فصل 1: مقدمه
1-1 مقدمه
در این بخش اطلاعاتی در رابطه با کلیت سیستم های پایگاه داده توزیع شده آورده شده است.
1-2 سیستم های پایگاه داده توزیع شده.
بانک های اطلاعاتی به منظور ذخیره سازی و ساماندهی حجم زیادی از اطلاعات برای استفاده توسط کاربر یا کاربران مختلف به کار می روند. اما سوال این است که برای این حجم زیاد از اطلاعات چه مرزی وجود دارد و اینکه تا چه تعداد کاربر می توانند همزمان از این اطلاعات استفاده کنند؟
اگر از توانایی سیستم مدیریت پایگاه داده توزیع شده 1در ذخیره سازی و ساماندهی حجم زیاد داده ها و تعداد کاربران صرفنظر کنیم، بدیهی است که نگهداری یک فایل اطلاعاتی در یک رایانه با محدودیت منابع ذخیره سازی( مثلا محدودیت گنجایش دیسک) و مدیریت درخواست همزمان کاربران با محدودیت منابع پردازشی مواجه خواهد شد. حتی اگر ظرفیت ذخیره سازی و توان پردازشی یک رایانه را نیز افزایش دهیم، باز هم مشکل در طولانی مدت حل نخواهد شد،. ضمن اینکه مشکلات دیگر در زمینه پهنای باند مصرفی در زمان تبادل اطلاعات در شبکه نیز بوجود خواهد آمد. بنابراین سیستم مدیریت پایگاه داده توزیع شده باید به گونه ای باشد که این مشکلات را برای طولانی مدت حل کند.
از طرفی می توان ادعا کرد در هر لحظه میلیونها کاربر در حال استفاده از اینترنت و وب هستند و علت اینکه پاسخگویی به این تعداد کاربر با مشکل مواجه نمی شود این است که سایت های وب و خدمات اینترنتی بین رایانه های مختلف توزیع شده است. وب دید روشنی از یک سیستم توزیع شده را به ما می دهد. این سیستم کاملا شفاف عمل می کند به این صورت که کاربر بدون نگرانی از اینکه یک سایت در کجا و در چه رایانه ای قرار دارد، می تواند به سایت های مختلف دسترسی پیدا کند. همچنین وب به گونه ای است که اگر در لحظه ای برخی از رایانه های متصل به آن از کار بیفتند یا از شبکه خارج شوند، باز هم به کار خود ادامه می دهد.
به نظر می رسد که برای حل مشکلات مربوط به پایگاه داده یک راه حل ممکن توزیع اطلاعات در بین سیستم های مختلف و سازماندهی و مدیریت آنها تحت یک سیستم متمرکز و به صورت یکپارچه است. این سیستم نیز می بایست علاوه بر رفع موارد اشاره شده (نظیر حجم زیاد داده و کاربر و نیز استفاده از پهنای باند) به صورتی کاملا شفاف عمل کند به طوریکه کاربر نگران این توزیع اطلاعات نباشد و براحتی بتواند سیستم اطلاعاتی توزیع شده را بمانند یک سیستم واحد در نظر بگیرد.
1-3 پایگاه اطلاعات توزیع شده
پایگاه اطلاعات توزیع شده از مفاهیم پیشرفته در زمینه مدیریت پایگاه داده است که می بایست برای پیاده سازی پروژه های گسترده و بزرگ که در سطح استانی و یا کشوری و یا حتی بیشتر اجرا می شوند، مورد استفاده قرار گیرد. در این سیستم اطلاعات می توانند از نظر فیزیکی در مکان های مختلف قرار گیرند. برای مثال در تصویر 1-1 که یک سیستم غیر توزیع شده را نشان می دهد، مشاهده می کنید که یک سرور مرکزی وجود دارد که کلیه اطلاعات یک دانشگاه فرضی در آن قرار گرفته است. و اطلاعات همه گروه ها نظیر اطلاعات دانشجویان هر گروه، اطلاعات نمرات هر ترم و اطلاعات دروس در آن نگهداری می شود. در تصویر 1-2 یک طرح توزیع شده از همان پایگاه داده است که این بار اطلاعات مربوط به دانشجویان و نمرات مستقلا در پایگاه داده هر گروه نگهداری شده است و فقط اطلاعات مربوط به دروس در سرور مرکزی قرار دارد.
شکل 1-1 یک پایگاه داده غیر توزیع شده شکل 1-2: نمونه ای از پایگاه داده توزیع شده
در تصویر 1-1 مشاهده می کنید حجم زیادی از اطلاعات در شبکه بوجود آمده است ولی در تصویر 1-2 این ترافیک به شکل مطلوبی کاهش پیدا کرده است. در تصویر 1-3 نشان داده شده است که در صورت توسعه شبکه، احتمالا با مشکل کمبود منابع و یا پهنای باند مواجه خواهیم شد. اما در تصویر 1-4 این مسئله تعدیل شده است.
شکل 1-3: مشکلات توسعه پایگاه داده غیر توزیع شده شکل 1-4: توسعه پایگاه داده توزیع شده
اگر مسئله را از دید امنیتی بررسی کنید، یک گروه نباید بتواند به اطلاعات گروهی دیگر دسترسی داشته باشد. حال یک مهاجم در تصویر 1-5 صرف نظر از اینکه امنیت سیستم های هر گروه در چه حد باشد، تنها با نفوذ به سرور مرکزی کلیه اطلاعات را در اختیار خواهد داشت. اما در تصویر 1-6 نشان داده شده است که با نفوذ به سرور مرکزی نمی توان به اطلاعات گروه ها دسترسی پیدا کرد، ضمن اینکه حتی اگر مهاجم بتواند از دیوارهای آتش یک سیستم عبور کند، سایر اطلاعات در معرض خطر نخواهند بود.
شکل 1-5: یک پایگاه داده غیر توزیع شده شکل 1-6: نمونه ای از پایگاه داده توزیع شده
اصل مهم در معماری سیستم پایگاهی توزیع شده این است که سیستم باید چنان عمل کند که کاربران دقیقا مثل محیط پایگاه داده ای متمرکز معمولی از آن استفاده کنند. برای رعایت این اصل مهم ، در هر سیستم پایگاهی توزیع شده قواعد زیر باید رعایت شوند.
1-4 قوانین Date برای پایگاه داده توزیع شده [1]
آقای Date که از اولین پیشگامان طرح مبحث پایگاه داده رابطه ای هستند برای پایگاه های داده توزیع شده 12 قانون و یا بهتر بگوییم هدف را تعیین کرده اند. در کتابهای مختلف از این 12 مورد با نام قانون نام برده اند ولی خود Date در کتابش از آنها با نام هدف یاد کرده است. وقتی بیشتر دقیق می شویم می بینیم که نام هدف شایسته تر است چرا که قانون چیزی است که باید رعایت شود و این در حالی است که تا به امروز هیچ سیستم مدیریت پایگاه داده توزیع شده ای نتوانسته است این 12 هدف را با هم رعایت کند. Date می گوید این 12 هدف هرگز از یکدیگر کاملا مستقل نیستند ولی یکسان نیز نیستند و بستگی به محیط و شرایط هر کدام از آنها ممکن است پر رنگ تر شود.
تعریف پایگاده داده این بود که کاربر از توزیع شدگی مطلع نشود و این در شرایطی قابل دسترسی است که به این 12 هدف برسیم در غیر این صورت کاربر کم و بیش دور بودن داده را احساس خواهد کرد. در ادامه این 12 هدف شرح داده شده اند.
1-4-1 خود مختاری محلی2:
به این معناست که هر سایتی دارای یک سری داده محلی است که توسط خود آن مدیریت می شود، به عبارتی یک سری داده متعلق به پایگاه داده محلی هستند چه از طریق سایت های دیگر قابل دسترسی باشند یا خیر. یک سایت نباید برای انجام عملیات محلی وابسته به سایت دیگری باشد. بدیهی است که برآورده کردن این هدف به صورت کامل غیر ممکن است و دقیق تر این است که گفته شود هر سایتی تا حداکثر ممکن باید خود مختار باشد.
1-4-2 عدم وابستگی به یک سایت مرکزی3:
در پایگاه داده توزیع شده همه سایتها با هم، هم ارز می باشند. اگر هدف قبلی برآورده شود خود به خود این هدف نیز برآورده می شود. ولی ذکر این هدف به این دلیل ارزشمند است که می توان این هدف را تامین کرد در حالی که خود مختاری محلی حداکثر نداشته باشیم. به دو دلیل برآوردن این هدف مهم است:
الف) سایت مرکزی ممکن است گردنه بطری شود و از سرعت سیستم بکاهد.
ب) اگر سایت مرکزی خراب شود کل سیستم از کار می افتد.
1-4-3 پیوستگی عملیات:
یک مزیت سیستم های پایگاه داده توزیع شده این است که قابلیت اتکا و قابلیت برقراری بیشتری از سیستم های متمرکز دارند. قابلیت اتکا به این دلیل بیشتر است که این سیستم ها به صورت همه یا هیچ نیستند. با خرابی یک سایت بقیه می توانند به کار خود ادامه دهند.
1-4-4 نامرئی بودن مکان:
این هدف می گوید که کاربر نباید بداند که داده به صورت فیزیکی کجا ذخیره شده است و وقتی از سیستم استفاده می کند احساس کند همه داده در سایت محلی ذخیره شده است.
1-4-5نامرئی بودن تکه تکه کردن:
می گوید که کاربر از نخوه تکه تکه شدن نباید آگاهی داشته باشد.
1-4-6 نامرئی بودن نسخه سازی:
کاربر نباید از نحوه نسخه سازی داده آگاهی داشته باشد. در ادامه در این رابطه و مورد قبل بیشتر بحث خواهد شد.
1- 4-7پردازش پرسش توزیع شده:
اولا سیستم باید قابلیت پردازش یک پرسش که داده مورد نیاز آن در سطح سیستم توزیع شده است را داشته باشد. ثانیا سیستم باید تا آنجا که ممکن است روش بهینه پاسخگویی را انتخاب کند که زمان کمتری طول بکشد.
1-4-8 مدیریت تراکنش توزیع شده:
از پیچیده ترین و پرهزینه ترین مشکلات پایگاه توزیع شده مدیریت تراکنش هاست. مدیریت تراکنش ها شامل دو بحث کلی کنترل همروندی در پایگاه توزیع شده و مقابله با بن بست ها می شود. در پایگاه توزیع شده کنترل همروندی توسط روش هایی مانند قفل کردن داده، برچسب زمان، چند گانگا، معتبر بودن و … استفاده می شود. یکی از روشهای پر کاربرد در سیستمهای توزیع شده برای مقابله با بن بست ها، روش کشف و ترمیم بن بست است.
1-4-9 نامرئی بودن سخت افزار:
یعنی هر سایت می تواند یک سخت افزار متفاوت داشته باشد. مثلا یک سایت یک کامپیوتر بزرگ IBM باشد و یک سایت یک کامپیوتر کوچک HP. در واقع سیستم از نوع سخت افزار مستقل است.
1-4-10 نامرئی بودن سیستم عامل:
مانند مورد قبل است. تمایل وجود دارد که یک سیستم مدیریت پایگاه داده توریع شده نه تنها روی سخت افزارهای مختلف قابل اجرا باشد بلکه روی سیستم عامل های گوناگون نیز کار کند. مثلا یک سیستم مدیریت پایگاه داده توزیع شده نسخه ای برای LINUX، نسخه ای برای WINDOWS و نسخه ای برای MVS داشته باشد.
1-4-11نامرئی بودن شبکه:
یعنی سیستم باید بتواند روش های ارتباطی مختلفی را حمایت کند.
1-4-12 نامرئی بودن سیستم مدیریت پایگاه داده توزیع شده:
این شاید یکی از مهمترین این 12 اصل است. به خصوص وقتی که چندین سیستم متمرکز قبلا داشتیم و سپس تصمیم گرفتیم آنها را به یک سیستم پایگاه داده توزیع شده تبدیل کنیم. DBMS های مختلف باید بتوانند با هم ارتباط برقرار کنند.
1-5 روشهای توزیع داده [2]
یکی از مهمترین گام ها در طراحی سیستم های توزیع شده، تعیین روش قرار دادن داده در سایت هاست. در ادامه بحث روش هایی ذکر می شود.
1-5-1 روش استخراج دستی یا متمرکز
واقعا نمی توان این را یک روش برای سیستمهای توزیع شده دانست و با این روش یک پایگاه داده توزیع شده نداریم. اما در مراجع مختلف از آن به عنوان یکی از روشهای توزیع داده در سیستمهای توزیع شده یاد شده است. در این روش یک پایگاه داده و یک DBMS بر روی یک سیستم داریم و کاربرها به صورت توزیع شده در شبکه قرار گرفته اند. در واقع دیدهای4 توزیع شده بر روی شبکه داریم. کاربرها بسته به دیدشان مقداری از داده ها را از سایت اصلی می گیرند. در این روش تمام سایت ها به جز سایت اصلی برای هر پرسش کاربر نیاز به شبکه دارند در نتیجه زمان زمان پاسخگویی به پرسشها بالا می رود. همچنین ایجاد خرابی در سایت اصلی سبب از کار افتادن کل سیستم می شود.
1-5-2 تکه تکه کردن داده
داده های موجود در پایگاهمان را تکه تکه کرده و هر تکه را در یک سایت قرار می دهیم. برای تقسیم کردن داده ها بین سایت ها روش هایی وجود دارد.
1-5-2-1 تکه تکه کردن افقی: در مورد یک رابطه تکه تکه کردن افقی بدین معناست که یک زیر مجموعه از تاپل ها را انتخاب و در یک سایت قرار می دهیم. می توان این کار را با یک شرطی روی یکی از صفات رابطه انجام داد. مثلا برای صفت قد در یک رابطه در مورد افراد می گوییم افراد با قد کمتر از 170 سانتیمتر در یک سایت و افراد با قد بیشتر از 170 سانتیمتر در یک سایت دیگر قرار بگیرند. دلیلی ندارد که حتما بخش ها از هم جدا باشند و می توانند اشتراک هم داشته باشند ولی معمولا این کار را انجام نمی دهند چرا که عملیات بهنگام سازی پایگاه داده بسیار پیچیده می شود.
1-5-2-2 تکه تکه کردن عمودی: یک تکه عمودی از یک رابطه، یک سری صفات خاص از آن رابطه می باشد. برای این که با چند تکه که در سایت های مختلف قرار دارند دوباره رابطه بسازیم می توانیم از دستور ساده پیوند5 استفاده کنیم.
1-5-2-3 تکه تکه کردن مختلط: در این روش از هر دو روش بالا به صورت همزمان استفاده می شود. مثلا یک جدول را ابتدا افقی تکه تکه می کنیم و در ادامه هر تکه را عمودی تقسیم می کنیم و الی آخر. در تکه تکه کردن با توجه به اینکه باید بتوان دوباره رابطه ها را بازسازی کرد در کاتالوگ سیستم (که بستگی به روش پیاده سازی می تواند در همه سایت ها یا در یک سایت و یا چند سایت باشد) نحوه تقسیم شدن رابطه ها ذخیره می شود که به آن شمای تکه تکه شدن می گویند.
1-6 نسخه سازی از داده ها
این روش نیز انواع مختلف دارد. در طی این روش از یک رابطه چند نسخه تهیه می شود و در جند سایت ذخیره می گردد. نسخه سازی سبب افزایش برقراری پایگاه می شود چرا که اگر داده ای در سایتی از بین برود می توان از طریق سایتهای دیگر به آن دسترسی داشت.
1-6-1 نسخه سازی کامل: در این روش تمام داده ها را در همه سایت ها قرار می دهیم. یعنی هر سایت کل پایگاه داده را در خود دارد. این باعث حداکثر شدن دسترسی پذیری پایگاه داده می شود. چون حتی وقتی که هنوز یک سایت هم خراب نشده باشد داده های ما از بین نرفته اند. همچنین باعث بالا رفتن کارایی برای پرسشهای محلی می شود. ولی معایب فراوان نیز دارد. مهمتریم عیب آن بالا رفتن هزینه بهنگام سازی است چرا که در هر بار بهنگام سازی، داده در همه سایتها باید بهنگام شود. به طبع بر عکس این روش این است که اصلا نسخه سازی نداشته باشیم. در این روش تمام تکه ها از هم جدا هستند و تنها اشتراک آنها با هم در کلید اصلی است. به این روش جایدهی بدون افزونگی می گویند. میتوان گفت اگر سیستم ما سیستمی است که بهنگام سازی کمی می خواهد بهتر است از نسخه سازی کامل استفاده کنیم ولی اگر بهنگام سازی در آن فراوان است نسخه سازی کمتر بکنیم.
1-6-2 نسخه سازی جزئی: بین دو روش نسخه سازی کامل و عدم نسخه سازی روش نسخه سازی نسبی وجود دارد. که در آن یک سری تکه از رابطه نسخه سازی می شود و یک سری نه. تعداد نسخه سازی می تواند از یک تا تعداد سایت ها باشد. در کاتالوگ سیستم توصیفات نحوه نسخه سازی ذخیره می شود. مانند همان توصیفاتی که برای تکه تکه کردن ذخیره می شود.
1-6-3 تصویر فرار
از این روش در خلال روشهای توضیح داده شده در بالا استفاده می شود. تصویر فرار یک کپی از داده ها در یک زمان داده شده است. این کپی به صورت متناوب بهنگام می شود. که زمان تناوب متناوب است. زمان تناوب می تواند چند ساعت یا چند هفته باشد. از تصویر فرار معمولا برای دیدها استفاده می شود. و کپی تهیه شده تنها حق خواندن دارد. این یک روش سریع است و برای سیستم هایی که میزان خواندن در آنها زیاد است و بهنگام سازی دیر به دیر مثلا روزی یک بار انجام می شود بسیار مناسب است. مثلا یک پایگاه داده شامل ساعت پروازها در روز.
سخن کوتاه اینکه در طراحی جایدهی فیزیکی داده در سایت ها یک طیف گسترده از انتخاب ها وجود دارد و طراح پایگاه داده توزیع شده از مهمترین کارهایی که پیش رو دارد این است که این جایدهی را طراحی کند. در طراحی جایدهی داده در سایت ها باید نکاتی در نظر گرفته شود از جمله:
محل قرار گرفتن سایت ها از لحاظ جغرافیایی و فاصله آنها از یکدیگر
پهنای باند شبکه
هزینه و پیچیدگی مدیریت داده ها و همروندی
هزینه نامرئی سازی
هزینه تکه تکه کردن و نسخه سازی داده از یک سایت
هزینه نرم افزار مورد نیاز برای مدیریت سیستم
1-7 معماری سیستم پایگاه داده توزیع شده [3]
سیستم داده های توزیعی قبلا به شکل سیستم مشتری مداری بوده است به گونه ای که مشتری6 و سرور7 با هم در فرایند شرکت می کردند. در یک نظام اینچنینی فاصله مشخصی بین مسولیت های مشتری و سرور وجود دارد. به گونه ای که اطلاعات در سایت های سرور ذخیره می شود و با اجرای سرور دسترسی به اطلاعات محلی برای مشتریان فراهم می شود. از طرفی سایت های مشتریان فرایندهای مربوط به خودشان را به گونه ای انجام می دهند که یک همبستگی بین کاربران و اطلاعات به وجود امده فراهم شود.
در یک سیستم سروری پیچیده همان معماری قبلی را داریم با این تفاوت که شبکه به صورت P2P عمل می کند یعنی هر سایت در سیستم می تواند هم به عنوان مشتری عمل کند و هم به عنوان سرور. در این صورت داده ها در همه گره ها 8ذخیره می شوند و این امکان برای هر گره وجود دارد که بتواند درخواست انتقال داده هایی را که در آن گره ذخیره نشده اند را داشته باشد. اگر یک سایت در خواست انتقال داده داشته باشد و بخواهد از داده های سایت های دیگر استفاده کند، این سایت با سایت مورد نظر ارتباط برقرار کرده و منجر به نتیجه خواهد شد هر چند ممکن است گاهی اوقات منجر به نتیجه مطلوب نگردد. به عنوان مثال یک سیستم p2p شامل 4 سایت (s1, s2, s3, s4)می باشد که در شکل 1-7 نشان داده شده اند. این سیستم شامل 3 رابطه R1, R2, R3 می باشد که در چند سایت تکه تکه شده اند. در این سیستم چنانچه سایت 1 درخواست داده در مورد رابطه R1 داشته باشد مجبور خواهد بود با سایر سایت هایی که شامل این نوع رابطه هستند ارتباط برقرار کند.
شکل 1-7: شبکه P2P
فصل 2: بهینه سازی پرسجو
2-1 بهینه سازی پرس و جو9
بهینه سازی پرس و جو، فرایند انتخاب کاراترین طرح ارزیابی پرس و جو از میان استراتژی های بسیاری است که اغلب برای پردازش یک پرس و جوی ممکن است، مخصوصا برای مواردی که پرس و جو پیچیده باشد[4].
یک جنبه از بهینه سازی در سطح جبر رابطه ای رخ می دهد که در آن سیستم تلاش می کند عبارتی بیابد که معادل با عبارت داده شده ولی برای اجرا کاراتر باشد. جنبه دیگر انتخاب یک استراتژی جزئی برای پردازش است مثل انتخاب الگوریتم مورد استفاده برای اجرای عملیات، اندیس خاص و….
کار بهینه ساز پرس و جو این است که یک طرح برای ارزیابی پرس و جو ارائه کند که همان نتایج پرس و جوی اولیه را با کمترین هزینه ممکن ( و یا حداقل با اختلاف هزینه کم نسبت به کمترین هزینه ممکن ) ایجاد کند.
برای انتخاب از میان طرحهای ارزیابی پرس و جوی متفاوت، بهینه ساز باید هزینه طرحها را تخمین بزند زیرا محاسبه هزینه دقیق ارزیابی یک طرح معمولا بدون ارزیابی واقعی آن ممکن نیست. در عوض بهینه ساز با استفاده از اطلاعات آماری در مورد روابط( مانند اندازه رابطه و عمق اندیس ها ) تخمین خوبی از هزینه طرح ارائه می کند و عمدتا میزان دستیابی به دیسک هزینه پردازش را تعیین می کند. بنابراین وقتی مسئله بهینه سازی در پایگاه داده توزیع شده مطرح می شود عمده ترین عاملی که مسئله طرح بهینه رو تحت الشعاع قرار می دهد هزینه ارتباطی بین سایتهای مختلف است که جداول در بین آنها توزیع شده اند. پس در این نوع بانک های اطلاعاتی تولید طرح بهینه از یک پرس و جو بر مبنای هزینه ارتباطی سایت های مختلف می باشد. ولی در این نوع بانک های اطلاعاتی علاوه بر مسئله تولید طرح بهینه از یک پرس و جو مسئله تخصیص داده ها نیز مطرح می شود، به عبارت دیگر ایجاد یک بستر بهینه برای اجرای یک پرس و جو می باشد.
به طور کلی می توان گفت انجام بهینه سازی پرس و جو در 4 مرحله به ترتیب ذیل صورت می پذیرد.
* قالب ریزی پرس و جو به شکل داخلی ( تبدیل پرس و جو اصلی به نمایش درونی که برای عملیات ماشین مناسب تر است. مانند درخت نحو مجرد و درخت پرس و جو )
* تبدیل به شکل متعارف (بهینه ساز، بدون درنظر گرفتن مقادیر داده واقعی و مسیرهای دستیابی فیزیکی موجود در پایگاه داده، بهینه سازی هایی انجام می دهد یعنی تبدیل نمایش درونی به شکل معادل با کارایی بیشتر)
* انتخاب رویه های سطح پایین کاندید(کار اصلی آن درنظرگرفتن پرس و جو به عنوان مجموعه ای از عملیات سطح پایین است. برای هر عملیات سطح پایین چندین رویه پیاده سازی درنظرگرفته شده است و برای هر رویه فرمول هزینه متناظر با آن تعریف می شود. معمولا برحسب I/O دیسک یا بهره وری CPU)
* تولید طرحهای پرس و جو و انتخاب ارزان ترین طرح ( هر ترکیب مجموعه ای از رویه های پیاده سازی کاندید ساخته می شود به نحوی که هر عملیات توسط یک رویه پیاده سازی می شود)
2-2 روشهای بهینه سازی پرسجو در بانک های اطلاعاتی توزیع شده
در بانک های اطلاعاتی توزیع شده عمده ترین بحث مربوط به هزینه ارتباطی بین سایت های مختلف می باشد و بر خلاف بانک های اطلاعاتی متمرکز عمده ترین هزینه مربوط به زمان و حافظه لازم جهت اجرای یک پرسجوست. از این رو در بانک اطلاعاتی توزیع شده مسئله بهینه سازی می تواند در دو فاز کلی و یک بخش جزئی مطرح شود که هر کدام از این سه بخش می تواند به عنوان یک مسئله مجزا بررسی شود. این بخش های کلی عبارت است از مسئله تخصیص داده که موضوع بحث آن اختصاص داده ها به سایت های مختلف جهت کاهش هزینه های ارتباطی با به حداقل رساندن مبادلات در یک سیستم توزیع شده می باشد و بخش دوم مربوط به مسئله تولید طرح بهینه اجرایی یک پرسجو می باشد. یک پرسجوی پیوند گرا که از چندین و چند عمل پیوند تشکیل شده، می تواند در طرح های مختلف اجرا شود که هزینه اجرایی متفاوت ولی نتیجه یکسان دارد. و سومین بخش سیاست اجرای یک طرح پرسجو در یک سیستم توزیع شده می باشد که کدام داده ها از سایتی به سایت دیگر انتقال داده شوند تا هزینه اجرای یک پرسجو کمینه شود.
2-2-1 تخصیص داده
پیشرفت در تکنولوژیهای شبکه و پایگاه داده در دهه های اخیر منجر به ایجاد سیستم های پایگاه داده توزیع شده گشته است .یک سیستم پایگاه داده توزیع شده مجموعه ای از سایتها می باشد که از طریق شبکه به هم متصل شده اند که هر کدام از سایت ها پایگاه داده مخصوص به خود دارد اما می توانند با یکدیگر کار کنند بنابراین هر کاربری در هر سایتی می تواند به همه داده های موجود در شبکه دسترسی داشته باشد درست مانند اینکه همه داده ها در سایت کاربر ذخیره شده است .
دغدغه اصلی سیستم های پایگاه داده توزیع شده قطعه قطعه کردن10 و تخصیص11 پایگاه داده اصلی می باشد واحد قطعه داده می تواند یک فایل باشد که در این حالت موضوع تخصیص همان تخصیص فایل خواهد بود مشکل تخصیص داده یک مسئله NP-complete می باشد بنابراین نیاز به هیوریستیکهای سریع برای تولید راه حل های موثر می باشد علاوه بر اینها تخصیص بهینه اشیا پایگاه داده به طور شدید بستگی به استراتژی اجرای پرس وجو 12 که به وسیله پایگاه داده توزیع شده پیاده سازی شده دارد .
هزینه اصلی در اجرای پرس و جو در سیستمهای پایگاه داده توزیع شده هزینه انتقال داده هنگام انتقال یک رابطه در موقع درخواست پرس و جو از یک سایت و انتقال آن از یک سایت متفاوت می باشد [5]. هدف اصلی الگوریتم های تخصیص داده تعیین نسبت دادن فرگمنتها به سایتهای مختلف برای کمینه کردن هزینه انتقال داده در اجرای13 یک مجموعه از پرس و جو ها می باشد که معادل کمینه کردن زمان متوسط اجرای پرس و جو می باشد که اهمیت اصلی در محیط های توزیع شده و پایگاه داده چند رسانه ای دارد .
2-2-1-1 الگوریتم های استاتیک :
مسئله تخصیص داده به طور کلی یک مسئله NP-complete می باشد و نیازمند هیوریستکهایی میباشد که راه حل سریع و با کیفیت بالا تولید کند. گسترش یک هیوریستیک موثر بستگی به استراتژی اجرای پرس و جویی دارد که توسط سیستمهای پایگاه داده توزیع شده بکار گرفته می شود که به این دلیل است که استراتژی مختلف اجرای پرس و جو الگو های مختلف انتقال داده متفاوت دارند [6]. الگوریتم تخصیص داده پارامترهای زیر را به عنوان ورودی می گیرد : 1 – گراف وابستگی قطعه داده 2- هزینه انتقال واحد داده ای بین سایتها 3 – محدودیتهای تخصیص روی تعداد قطعه داده که می تواند به سایت تخصیص داده شود 4 – تعداد تکرار اجرای پرس و جو از سایتها [7]
گراف وابستگی14 قطعه داده یک گراف بدون سیکل جهت دار می باشد که در ریشه15 آن سایت اجرای پرس و جو قرار دارد و سایر نودها نودهای قطعه داده می باشد که ممکن است توسط پرس و جو مورد دسترسی قرار گیرد و این گراف وابستگی قطعه داده وابستگی بین قطعه داده و مقدار داده ای که بایستی موقع اجرای پرس و جو منتقل شود را مدل می کند .
شکل 2-1 : گراف وابستگی قطعه داده
2-2-1-1-1 الگوریتم ژنتیک 16
فرض کنید ri,j نشان دهنده نیازمندی سایت i به قطعه داده j می باشد ، و هر قطعه داده i بوسیله اندازه اش مشخص می شود که با si نشان داده می شود و ti,j نشان دهنده هزینه ای است که سایت i متحمل می شود تا به قطعه داده که در سایت j وجود دارد دسترسی پیدا کند مشکل تخصیص در سیستم های پایگاه داده توزیع شده پیدا کردن راه حلی است که داده ها طوری در سایت های موجود استقرار یابند که برای دسترسی به آنها کمترین هزینه را متحمل شویم . این بدین معناست که ما عمل جایگزینی17
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 می باشد.
الگوریتم ژنتیک یک تکنیک جستجوی تطابقی می باشد که بر پایه اصول و مکانیزمهای انتخاب طبیعی18 و survival of the fittest از سیر تکاملی تدریجی می باشد با شبیه سازی سیر تکاملی طبیعی19 الگوریتم ژنتیک می تواند به طور موثر حوزه مسئله را جستجو کند و به راحتی مسائل مشکل را حل کند . الگوریتم ژنتیک با تولید یک population اولیه شروع به کار می کند ، P (t = 0) ، و هر کدام از اعضای خود را با تابع هدف ارزیابی می کند تا موقعی که شرایط پایانی20 فراهم نشود یک قسمت از population انتخاب ، ارزیابی و برگردانده میشود به population.[8]
الگوریتم ژنتیک برای مسئله تخصیص داده به صورت زیر می باشد :
population را مقداردهی اولیه کن هر کدام از population های انفرادی اتصال21 نمایش دودویی تخصیص تصادفی اولیه22 هر قطعه داده می باشد.
Population را ارزیابی کن.
تعداد generation=0
تا وقتی که no of generation < MAX GENERATION انجام بده
Individual ها را از population بعدی انتخاب کن
Crossover و Mutation را برای Individual ها انتخاب شده انجام بده
Population را ارزیابی کن
تعداد generation را یکی اضافه کن
اتمام حلقه While
تخصیص نهایی را با انتخاب fittest individual مشخص می کند اگر تخصیص نهایی قابل امکان نباشد سایتی که از نظر قطعه داده بار اضافی دارد بار آن را به سایتی منتقل می کند که کمترین هزینه انتقال را دارد .
الگوریتم ژنتیک نسبت به استفاده از هیوریستیک حریصانه23 روی مسئله اختصاص قطعه داده با سایزهای مختلف کارایی24 بیشتری دارد . هیوریستیک حریصانه زمان و تلاش زیادی برای پیاده سازی نیاز دارد در حالیکه الگوریتم عمومی ساده می باشد .[8]
2-2-1-1-2 الگوریتم Simulated Evolution :
تفاوت اصلی الگوریتم ژنتیک با الگوریتم Simulated Evolution این است که اولی روی crossover دارد که یک مکانیزم احتمالی می باشد و که برای تبادل اطلاعات بین راه حلها25 برای شناسایی بهترین راه حل مناسب می باشد در حالیکه دومی از mutation به عنوان مکانیزم جستجوی اولیه استفاده می کند. علاوه بر اینها در شمای مطرح شده نمایش chromosomal بر پایه مشکل داده می باشد و راه حل با استفاده از هیوریستیک کدگذاری26 ( هیوریستیک نگاشت ) به منظور نگاشت از حوزه مسئله به حوزه راه حل تولید شده است . این الگوریتم به صورت زیر است :[9]
اولین chromosome را براساس مسئله داده27 تولید کن و این chromosome را برای تولید population اولیه تغییر بده.
از هیوریستیک نگاشت برای تولید راه حل برای هر chromosome استفاده کن.
راه حل بدست آمده را ارزیابی کن
تعداد generation=0
تا وقتی که no of generations < MAX GENERATION انجام بده
Chromosome ها را برای population بعدی انتخاب کن
برای این مجموعه کروموزوم ها crossover و mutation انجام بده
از هیوریستیک نگاشت برای تولید راه حل برای هر chromosome استفاده کن.
راه حل بدست آمده را ارزیابی کن
تعداد generation ها را یکی اضافه کن
پایان حلقه While
بهترین راه حل پیدا شده تاکنون را به خروجی ببر
2-2-1-1-3 هیوریستیک نگاشت28
برای هر کروموزوم یک راه حل با تخصیص قطعه داده j با الویت بالا برای سایت i پیدا می کنیم طوریکه u'i j برای تمام u'x j, 1<x <m کوچکترین باشد. اگر حد تخصیص موثر برای یک ژن موجود در قسمت a کروموزوم برای یک سایت فراتر رود ما این قطعه داده را به سایتی اختصاص می دهیم که u'ij اش کمترین مقدار بعدی ( هزینه تخصیص قطعه داده j به سایت i ) برای تمام u'yj, 1< y <m, y ≠ x باشد.این واقعیت که هر قطعه داده به یک سایت تخصیص داده می شود گارانتی می شود برای اینکه هر بار چک می شود حد تخصیص کلی بزرگتر یا مساوی تعداد قطعه های داده برای هر نسل 29 از کروموزوم ها باشد. سپس می توانیم این فرایند را برای هر قطعه داده با الویت بالا بین قطعه داده های دیگر که هنوز به سایتی تخصیص داده نشده ادامه پیدا می کند.[10]
2-2-1-1-4 الگوریتم The Mean Field Annealing (MFA) :
تکنیک Mean Field Annealing ویژگی محاسباتی بهم پیوسته30 شبکه عصبی Hopfield را با
simulated annealing ترکیب می کند .MFA ابتدا برای حل مشکل فروشنده دوره گرد به جای استفاده از الگوریتم HHN31 که نمی توانست مسئله با اندازه بزرگ را حل کند مطرح گردید MFA یک راه حل عمومی است که می تواند برای حل مسئله های بهینه سازی ترکیبی مختلف استفاده شود.
شکل 2-2: شبکه عصبی Hopfield
الگوریتم MFA به صورت زیر است :
temperature اولیه را بدست آور قرار بده 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
مجموع روبرو را محاسبه کن: ∑eΦij/T
مقدار spin جدید را در ردیف i محاسبه کن
تغییرات انرژی را به خاطر این بروزرسانی های جدید محاسبه کن
پایان حلقه While
temperature ، T را مطابق با زمانبندی cooling بروز کن
پایان حلقه While
تخصیص نهایی را با تخصیص هر قطعه داده به سایت با توجه به مقدار spin بزرگ مشخص کن . اگر تخصیص نهایی قابل امکان نباشد سایتی که قطعه داده اضافی دارد این قطعه داده را به سایتی منتقل کن که کمترین هزینه را داشته باشد.[11]
2-2-1-1-5 الگوریتم تخصیص داده جستجوی تصادفی همسایگی32
ایده اصلی در الگوریتم جستجوی همسایگی تولید یک راه حل اولیه با کیفیت مناسب33 می باشد سپس الگوریتم به طور احتمالی مطابق با برخی همسایگی های از قبل تعریف شده ، راه حل های مجاور34 در فضای جستجو را انتخاب و آزمایش می کند که آیا از حالت قبل بهتر است یا نه ، اگر راه حل جدید بهتر باشد الگوریتم از این راه حل اقتباس می کند و جستجو را در همسایگی جدید آغاز می کند در غیر اینصورت الگوریتم نقطه جدیدی را انتخاب می کند الگوریتم کار خود را موقعی به اتمام می رساند که یا تعداد قدمهای جستجوی آن به یک مقدار مشخص برسد و یا اینکه بعد از تعدادی قدم بهبودی حاصل نشود کیفیت راه حل در الگوریتم جستجوی همسایگی بطور شدیدی بستگی به راه حل همسایگی دارد الگوریتم برای مسئله تخصیص داده به صورت زیر می باشد:
از 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 [6]
به طور کلی SE و GA راه حلهای بهتری نسبت به RS و MFA تولید می کنند الگوریتم RS پیچیدگی زمانی کمتری دارد بنابراین الگوریتم سریعی می باشد ولی الگوریتم SE کند می باشد برای حوزه هایی که بایستی سریع عمل کنیم و جواب بهینه مدنظر نمی باشد الگوریتم RS گزینه مناسبی می باشد ولی اگر کارایی و کیفیت راه حل اهمیت داشته باشد الگوریتم GA گزینه مناسب می باشد بنابراین داشتن همه این الگوریتم ها در سیستم پایگاه داده توزیع شده باعث می شود که راه حلهای متنوع داشته باشیم و این راه حلها یک trade-off بین پیچیدگی و کیفیت می باشد.
در [6] برای تخصیص قطعه داده یک متدی طراحی شده که نیازمندیهای خوشه کردن35 سایتها و تعیین تخصیص قطعه داده در سیستمهای پایگاه داده توزیع شده را برطرف می کند علاوه بر اینها هزینه ارتباط بین سایتها را کاهش می دهد و کارایی را در محیط سیستمی شبکه غیرمتجانس36 افزایش می دهد . متد خوشه بندی به این دلیل استفاده شد که سایتها را در یک خوشه گروه بندی کنند که این کار باعث کاهش هزینه ارتباط بین سایتها در فرآیند تخصیص داده می شود . متد تخصیص قطعه داده با افزایش قابلیت در دسترس بودن و قابلیت اطمینان ( کپی های چندگانه از قطعه های داده وجود دارد ) کارایی سیستم را افزایش می دهد.
2-2-1-2 الگوریتم تخصیص پویا :
در محیط استاتیک یعنی جایی که دسترسی به قطعه داده هایی که در سایتها وجود دارد از جانب سایتهای دیگر تغییر نمی کند تخصیص قطعه داده استاتیک بهترین راه حل می باشد در حالیکه در محیط پویا37 این احتمالات دسترسی که در طول زمان و به کررات عوض می شود ، تخصیص قطعه داده استاتیک کارایی پایگاه داده را کاهش می دهد . در زیر ما الگوریتم های مختلف تخصصیص قطعه داده پویا را بررسی می کنیم:
2-2-1-2-1 الگوریتم شمارنده ساده 38
در این الگوریتم با استفاده از یک شمارنده که تعداد دسترسی از هر سایت به هر بلاک را نگهداری می کند استفاده می شود برای اینکه مشخص شود کی تخصیص مجدد مورد نیاز می باشد شمارنده برای هر بلاک فقط در یکی از سایتهای موجود در سیستم پایگاه داده توزیع شده نگهداری می شود
برای مثال فرض کنید پارتیشن A در سایت 1 قرار دارد در سیستمی با تعداد سایتهای N ، سایت 1 N شمارنده برای پارتیشن A نگهداری می کند . الگوریتم شمارنده ساده سایتهایی که به این قطعه داده دسترسی پیدا می کنند را رتبه بندی می کند و بهترین سایت را انتخاب می کند این الگوریتم به صورت زیر می باشد:[11]
الگوریتم شمارنده ساده :
یک فرایند state در بازه های زمانی منظم شمارنده ها را برای هر بلاک چک میکند
سطرهای یک بلاک در صورتی که شمارنده مربوط به آن بلاک در یک سایت بیشتر از سایتی باشد که بلاک هم اکنون در آن قرار دارد به آن سایت منتقل می شود
بعد از چک کردن شمارنده بلاک ها ، فرایند state قبل از چک کردن دوباره شمارنده ها برای تعداد t-check از تراکنشها که قرار است کامل شوند صبر می کند
شکل 2-3 : الگوریتم شمارنده ساده
در این الگوریتم فرایند وضعیت39 فرایندی می باشد که برای هر تراکنش 40 اطلاعات آماری مانند توان عملیاتی و میانگین زمان پاسخ و قسمتی از تراکنش کهنیازمند دسترسی به داده ای که در سایت دیگر ذخیره شده را نگهداری می کند بایستی توجه داشته باشیم که مقدار t-check به اندازه کافی کوچک باشد تا سیستم در مقابل تغییرات بار واکنش سریع نشان دهد همچنین باید به اندازه کافی بزرگ باشد تا این تعداد تکرار دسترسی به یک بلاک که در یک سایت مشخص قرار دارد به یک مقدار ثابت برسد و بتوان از روی آن تصمیم گیری کرد که بلاک باید به کدام سایت منتقل شود . مشخص کردن اینکه آیا یک بلاک بایستی به سایت دیگر منتقل شود یا نه یک تصمیم محلی 41 می باشد به همین دلیل شمارنده هر بلاک در سایتی قرار داده می شود که بلاک هم در همان سایت قرار دارد . این الگوریتم بر الگوریتم های تخصیص داده استاتیک برتری دارد.[11]
2-2-1-2-2- الگوریتم Load Sensitive counter :
الگوریتم شمارنده ساده وقتی که توزیع قطعه های داده در سایتها متعادل باشد خوب کار می کند ولی اگر یک سایت به تعداد بلاک های زیادی دسترسی پیدا کند این الگوریتم همه این بلاکها را در این سایت قرار می دهد و باعث می شود بخاطر بار اضافی پردازنده و دیسک موجود در این سایت کارایی پایین بیاید الگوریتم Load Sensitive counter با در نظر گرفتن شرایط بار این مشکل را حل می کند بدون این الگوریتم اگر بلاکهای زیادی در یک سایت قرار گیرد همزمانی اجرای بین تراکنشها کاهش پیدا می کند و توان عملیاتی کاهش پیدا می کند . این الگوریتم بر الگوریتم شمارنده ساده و الگوریتم های استاتیک برتری دارد و به صورت زیر می باشد: [12]
الگوریتم Load Sensitive counter :
هم بر تعداد دسترسی ها و هم بر بار (توازن داده) در سیستم نظارت کن
اینکه بلاک داده بایستی منتقل شود یا نه مانند الگوریتم شمارنده ساده می باشد با این تفاوت که بلاک ها در صورتی منتقل می شوند که مقدار بلاک ذخیره شده در آن سایت از یک مقدار آستانه ای42 بالاتر نرود . پارامترهای الگوریتم عبارتند از : مقدار بلاک داده بیشینه ای که یک سایت می تواند در خود ذخیره کن و مقدار آستانه ای بار
شکل 2-4 : الگوریتم Load Sensitive counter
2-2-1-2-3 الگوریتم Incremental
چهارچوب رشد افزایشی43 موقعی فراخوانی می شود که کارایی سیستم از یک آستانه ای که توسط مدیر سیستم پایگاه داده مشخص می شود بالاتر رود . در این الگوریتم برای اینکه به یک وضعیت قابل قبول برسیم سرورهای جدیدی در سیستم پایگاه داده توزیع شده معرفی می شود با معرفی هر سرور جدید تخصیص مجدد داده44 جدید برای سیستم محاسبه می شود این فرایند به طور تکراری اجرا می شود تا موقعی که به یک کارایی قابل قبول برسیم یا اینکه تعداد سرور ها با تعداد رابطه ها در سیستم پایگاه داده توزیع شده یکسان باشد .
در یک سیستم پایگاه داده توزیع شده با افزایش بار کاری45 به سرورهای جدیدی نیاز پیدا می شود الگوریتم Incremental هیوریستیکهای تخصیص دوباره پر46 و تخصیص مجدد جزئی 47 برای تخصیص داده موثر بکار می برد . هر دو این الگوریتم ها هیوریستیک های تکراری48 حریصانه و تپه نوردی49 می باشند که از مسیر دو بار عبور نمی کند [13]. در هر تکرار یا راه حل با کمترین هزینه را پیدا می کنند و یا تمام می شوند هر دو این الگوریتم ها اینها را به عنوان ورودی نیاز دارند : تخصیص داده کنونی ، رابطه ها ، و پرس وجوها در سیستم پایگاه داده توزیع شده . با معرفی سرورهای جدید در سیستم پایگاه داده توزیع شده هزینه کاهش پیدا می کند و علاوه براین می توان پیچیدگی را کنترل کرد . این هیوریستیک ها به خاطر پچیدگی خطی شان می توانند مسائل بزرگ ، کوچک و پیچیده را بر اساس نیازهای سازمانی حل کنند . این الگوریتم مسئله فضای جستجو را کاهش می دهد و بنابراین هزینه به طور کلی کاهش پیدا می کند [13].
شکل 2-5 :چهارچوب incremental growth
2-2-1-2-4 الگوریتم Threshold
در این روش قطعه داده افقی ، عمودی یا ترکیبی از اینها می تواند استفاده شود و واحدهای تخصیص می تواند به اندازه رکورد یا صفت50 باشد.
همانطور که قبلاً گفتیم در سیستم های پایگاه داده توزیع شده با قرار دادن قطعه داده ها در سایتهایی که بیشترین دسترسی به این قطعه داده دارند کارایی افزایش پیدا می کند . مشکل اساسی ما این است که برای یک قطعه داده بتوانیم سایت مناسب را پیدا کنیم یک راه حل این مشکل این است که برای یک قطعه داده خاص تعداد دسترسی تمام سایتها را بشماریم آن سایتی که بیشترین دسترسی به این قطعه داده را داشته باشد اولین کاندید برای ذخیره سازی آن می باشد. برای این کار یک ماتریس m*n در نظر می گیریم که m نشان دهنده تعداد قطعه های داده و n نشان دهنده تعداد سایتها می باشد که در این ماتریس هر عنصر sij از S نشان دهنده تعداد دسترسی های سایت j به نود i می باشد [14].
ابتدا همه قطعه های داده با استفاده از یکی از روشها بین نودها توزیع می شوند سپس هر نود j الگوریتم optimal را برای هر قطعه داده i که در آن نود ذخیره شده اجرا می کند.
الگوریتم optimal به صورت زیر می باشد:
الگوریتم optimal :
برای هر قطعه داده که به صورت محلی51 ذخیره شده سطر شمارنده دسترسی را برابر 0 قرار بده ( Sik=0 که k=1,2,…,n )
درخواست دسترسی به قطعه داده ذخیره شده را پراسس کن
شمارنده دسترسی نودی که به این قطعه داده دسترسی پیدا کرده را یکی افزایش بده ( اگر نود x به قطعه داده i دسترسی پیدا کند قرار بده six=six+1 )
اگر نودی که به آن دسترسی شده همان نود جاری باشد که قطعه داده در آن قرار دارد برو به مرحله 2 ( دسترسی محلی )
اگر شمارنده نود دور52 بیشتر از نودی باشد که قطعه داده در آن قرار دارد مالکیت این قطعه داده همراه با آرایه مربوط به آن را به نود دور منتقل کن ( اگر نود x به قطعه داده i دسترسی پیدا کند و six>sij باشد قطعه داده i را به نود x بفرست )
برو به مرحله 2
شکل 2-6 : الگوریتم Optimal
مزیت الگوریتم Optimal استقلال نود مرکزی می باشد بدین معنا که چون هر نود الگوریتم را به طور خودکار اجرا می کند هیچ وابستگی به نود مرکزی وجود ندارد و تمامی نودها اهمیت یکسان دارند. هر زمان که یک نود خراب53 شود الگوریتم می تواند به عملیات خود به عملیات خود البته بدون وجود قطعه داده موجود در این سایت ادامه دهد [13].
الگوریتم optimal دارای دو عیب می باشد : اول اینکه مشکل ذخیره سازی بالقوه54 وجود دارد با کاهش اندازه قطعه داده یا افزایش تعداد نودها اندازه ماتریس شمارنده دسترسی افزایش پیدا می کند و این افزایش سایز ماتریس باعث می شود که به فضای ذخیره سازی زیادی نیاز داشته باشیم. مشکل دوم مشکل مقیاس بندی55 برای نوع داده ای است که مقادیر شمارنده دسترسی را ذخیره می کنند . چون مقدار شمارنده دسترسی بطور مداوم افزایش پیدا می کند ممکن است موجب ناهنجاری شود . مشکل بالقوه وقت یعنی زمان انتقال قطعه های داده از یک سایت به سایت دیگر نیز وجود دارد و ممکن است به صورت نمایی افزایش پیدا کند . در الگوریتم Threshold فقط یک شمارنده برای برای هر قطعه داده ذخیره می شود در مقایسه با الگوریتم Optimal این الگوریتم فضای ذخیره سازی کمتری نیاز دارد چون برای هر قطعه داده فقط یک شمارنده ذخیره می شود دو استراتژی برای انتخاب سایت ای که قرار است یک قطعه داده در آن قرار گیرد وجود دارد : یا این به صورت تصادفی انتخاب شود و یا نودی که آخرین دسترسی را داشته است انتخاب شود در استراتژی اولین نودی که انتخاب می شود ممکن است نودی باشد که قبلاً هرگز به این قطعه داده دسترسی نداشته بود بنابراین استفاده از استراتژی دوم منطقی تر می باشد .
در ابتدا قطعه های داده به طور تصادفی با استفاده از یک متد در بین نودها توزیع می شود. یک مقدار آستانه t انتخاب می شود ، سپس هر نود j برای هر قطعه داده i که در آن ذخیره شده است الگوریتم Threshold را اجرا می کند این الگوریتم به صورت زیر می باشد:[7]
الگوریتم Threshold :
برای هر قطعه داده که به صورت محلی ذحیره شده مقدار شمارنده را برابر صفر قرار بده ( برای هر قطعه داده i قرار بده si=0 )
درخواست دسترسی به قطعه داده را پراسس کن.
اگر این دسترسی یک دسترسی محلی باشد مقدار شمارنده این قطعه داده را دوباره صفر کن ( اگر نود j به قطعه داده i دسترسی پیدا کند قرار بده si=0 ) برو به مرحله 2
اگر این دسترسی یک دسترسی دور باشد شمارنده مربوط به این قطعه داده را یکی افزایش بده ( اگر قطعه داده i به صورت دور دسترسی شود قرار بده si=si+1
اگر شمارنده این قطعه داده از مقدار حد آستانه بیشتر باشد این شمارنده را صفر کن و آن را به نود دور منتقل کن ( اگر si>t قرار بده si=0 و قطعه داده را به نود دور منتقل کن)
برو به مرحله 2
شکل 2-7 : الگوریتم Threshold
نکته مهم در این الگوریتم انتخاب حد آستانه می باشد که روی انتقال قطعه های داده تاثیر می گذارد از الگوریتم بالا واضح است که اگر مقدار حد آستانه زیاد باشد قطعه داده تمایل دارد که برای مدت طولانی در نود بماند و اگر مقدار حد آستانه کم باشد این قطعه داده در نودهای گوناگونی مستقر خواهد شد. نکته دیگری توزیع احتمالات دسترسی 56 می باشد اگر احتمالات دسترسی همه نودها برای یک قطعه داده یکسان باشد این قطعه داده همه نودها را ملاقات خواهد کرد [8].
در این الگوریتم قطعه داده تمایل دارد که در نودی باقی بماند که بیشترین احتمال دسترسی دارد با افزایش احتمال دسترسی یک نود تمایل برای باقی ماندن قطعه داده در این نود افزایش پیدا می کند همچنین در این الگوریتم با افزایش حد آستانه قطعه داده تمایل دارد که در نودی که بیشترین احتمال دسترسی دارد باقی بماند.
2-2-1-2-5 الگوریتم Near Neighborhood Allocation با حد آستانه نسبی57(RTNNA):
الگوریتمNNA حالت خاصی از الگوریتم Optimal می باشد در الگوریتم optimal تمام قطعه های داده با استفاده از یک متد استاتیک بین تمام سایتها توزیع می شود سپس هر نود j برای قطعه داده i الگوریتم optimal را مطابق شکل 4 اجرا می کند . مشکل این الگوریتم ( optimal ) این است که اگر الگوهای تکرار دسترسی به قطعه های داده زیاد باشد زمان زیادی برای انتقال قطعه های داده به نودهای مختلف صرف می شود بنابراین زمان پاسخ و تاخیر افزایش پیدا می کند در الگوریتم NNA این مشکل حل می شود در الگوریتم NNA شرایط لازم برای اینکه قطعه داده منتقل شود درست مانند الگوریتم optimal می باشد اما مقصد یعنی محلی که قرار است داده به آن منتقل شود فرق می کند در این روش توپولوژی شبکه و مسیریابی58 برای مشخص کردن مقصد در نظر گرفته می شود به عبارت دیگر مقصد قطعه داده ای که می خواهد منتقل شود نودی می باشد که همسایه نود مبدا است و این نود همسایه یعنی نودی که قرار است قطعه داده به آن منتقل شود در مسیری قرار دارد که نودهای موجود در این مسیر بیشترین دسترسی به این قطعه داده را دارند در این الگوریتم ( NNA ) از الگوریتم link state برای مسیربابی استفاده شده است با استفاده از این روش انتقال مکرر قطعه های داده به دلیل اینکه این قطعه های داده در نودی قرار می گیرد که برای همه نودهایی که به این قطعه داده دسترسی دارند هزینه دسترسی میانگین دارد کاهش مییابد بنابراین تاخیر این انتقالات کاهش می یابد و زمان پاسخ59 بهتر می شود [15] در الگوریتم NNA یک حد آستانه ای که مقدار آن برابر 5 بود برای انتقال قطعه های داده در نظر گرفته می شد یعنی اگر شمارنده مربوط به یک قطعه داده که توسط نودهای دیگر دسترسی می شد مساوی 5 می شد این قطعه داده با استفاده از الگوریتم های مسیر یابی به یکی از نودهای همسایه منتقل می شد در حالیکه در الگوریتم RTNNA این مقدار آستانه نسبی می باشد بدین معنا که با توجه به مرحله دوم الگوریتم شمارنده ساده ( Simple Counter Algorithm ) تصمیم گیری درباره انتقال قطعه داده به این صورت انجام می شود که سطرهای یک بلاک در صورتی که شمارنده مربوط به آن بلاک در یک سایت بیشتر از سایتی باشد که بلاک هم اکنون در آن قرار دارد تصمیم گیری درباره انتقال قطعه داده با استفاده از الگوریتم های مسیر یابی انجام می شود که در این پروژه ما مانند الگوریتم NNA از الگوریتم link state استفاده کردیم برای اینکه مشخص کنیم که قطعه داده بایستی در کدام نود قرار گیرد که میانگین دسترسی نودهای دیگر به این قطعه داده کمترین مقدار را داشته باشد در این الگوریتم ( RTNNA ) بهبود قابل ملاحظه ای نسبت به الگوریتم NNA حاصل شد که نتایج آن در ادامه آورده شده است .
با توجه به شکل 6 فرض کنید نود G ،H ،I وE به طور مکرر برای قطعه داده i که در نود A قرار دارد درخواست می فرستند با توجه به الگوریتم RTNNA هنگامی که شمارنده مربوط به یکی از این نودها بالاتر از بقیه نودها و نود مبدا باشد قطعه داده i به نود C منتقل می شود اگر این درخواستها بعد از انتقال قطعه داده ادامه پیدا کند قطعه داده به نود B منتقل می شود این روش ادامه پیدا می کند تا وقتی که قطعه داده به نود G منتقل شود . با قرار گرفتن این قطعه داده در نود G ، درخواستها از نودهای G ،H ،I و E با کمترین تاخیر و نه تاخیر کمینه جواب داده می شود در این مرحله داده در یک وضعیت پایدار قرار می گیرد بعد از این مرحله اگر یکی از نودهای H ،G وE بیشتر از دیگران درخواست قطعه داده بدهند این قطعه داده در این نود قرار می گیرد .
شکل 2-8 : توپولوژی آزمایش
در آزمایشات انجام شده ما دو فاکتور در نظر می گیریم : تاخیر متوسط برای دریافت پاسخ از درخواست یک قطعه داده ( زمان پاسخ 60 ) و زمان سپری شده برای انتقال داده از یک نود به نود دیگر ( زمان انتقال قطعه داده61 ) .
2-2-1-2-6 الگوریتم Revise Relative Threshold Near Neighborhood Allocation
در این الگوریتم تصمیم گیری برای انتقال قطعه داده از سایتی که در آن قرار دارد به سایت دیگر به این صورت انجام می شود که ابتدا مجموع شمارنده مربوط به یک قطعه داده که توسط تمامی سایتهای موجود در شبکه به آن دسترسی شده محاسبه می شود سپس این مجموع بر تعداد نودها منهای نودهایی که به این قطعه داده دسترسی پیدا نکرده اند تقسیم می شود از این معادله یک نتیجه حاصل می شود اگر این مقدار از مقدار شمارنده این قطعه داده مربوط به سایتی که در آن قرار دارد بیشتر باشد انتقال قطعه داده انجام می شود و داده یک مرحله با توجه به الگوریتم مسیریابی link state یک قدم منتقل می شود و در سایت دیگری قرار می گیرد.
2-2-2 تولید طرح اجرای بهینه
در این مرحله سیستم مدیریت پایگاه داده از بین تعدادی طرح اجرا، بهترین طرح را بر می گزیند به گونه ای که اجرای پرسجوی داده شده توسط کاربر با استفاده از این طرح دارای کمترین هزینه، بویژه هزینه عملیات ورودی/خروجی 62می باشد. ورودی بهینه ساز، نمایش داخلی پرسجوی Q می باشد که توسط کاربر به سیستم مدیریت پایگاه داده، وارد شده است. هدف کلی از بهینه سازی پرسجو، انتخاب کاراترین طرح اجرایی برای دستیابی به داده مناسب و پاسخ به پرسجوی داده شده می باشد. به بیان دیگر در صورتی که مجموعه همه طرح های اجرایی اختصاص داده شده برای پاسخ به پرس و جوی Q را با S نشان دهیم هر عضو qep متعلق به مجموعه S دارای هزینه Cost(qep) می باشد (این هزینه شامل زمان پردازشیو زمان ورودی/خروجی می باشد). هدف هر الگوریتم بهینه سازی یافتن عضوی مانند qep0 متعلق به مجموعه S می باشد به نحوی که [16]:
طرح اجرایی برای پاسخ به یک پرسجو، دنباله ای از عملگرهای جبری رابطه ای می باشد که بر روی روابط پایگاه داده شده اعمال می شود و جواب لازم برای آن پرسجو را تولید می کند. از بین عملگرهای رابطه ای موجود، پردازش و بهینه سازی عملگر پیوند63 که بوسیله نماد ∞ نمایش داده می شود، جزو مشکلترین عملگرها می باشد. اساسا عملگر پیوند دو رابطه را به عنوان ورودی می گیرد و تاپل های آنها را یک به یک بر اساس معیار مشخصی، ترکیب کرده و یک رابطه جدید را به عنوان خروجی تولید می نماید. از آنجا که عملگر پیوند دارای خاصیت انجمنی 64جابجایی65 می باشد، تعداد طرح های اجرایی موجود برای پاسخ دهی به یک پرسجو با افزایش تعداد پیوندهای بین روابط، به صورت نمایی رشد پیدا می کند. علاوه بر این موارد، معمولا یک سیستم مدیریت پایگاه داده، انواع روشهای پیاده سازی عملگر پیوند را برای پردازش پیوندها و انواع اندیس ها را برای دسترسی به روابط پشتیبانی می کند. بطوریکه این موارد، گزینه های لازم برای پاسخ دهی به یک پرسجو را هر چه بیشتر می کند. گر چه تمامی طرح های اجرایی موجود برای پاسخ دهی به یک پرسجوی مشخص، دارای خروجی یکسان می باشند، اما از آنجا که کاردینالیتی روابط میانی ایجاد شده یکسان نیستند، طرح های اجرایی بوجود آمده دارای هزینه متفاوتی خواهند بود. بنابراین، انتخاب ترتیب مناسب برای اجرای عمل پیوند در هزینه کلی تاثیرگذار است. مسئله بهینه سازی پرسجو، که اغلب از آن بعنوان مسئله انتخاب ترتیب مناسب برای اجرای عملگرهای پیوند 66یاد می شود یک مسئله NP-hard می باشد [17].
شایان ذکر است روشهای تولید طرح بهینه به دو دسته مبتنی بر هزینه و مبتنی بر قاعده تقسیم می شوند. بر این اساس الگوریتمهایی در این دو شاخه مطرح و بررسی می شوند. در روش مبتنی بر قاعده اساسا نتایج اجرای یک طرح در گراف پیوند بهترین منظور شده و جستجویی برای فضای بزرگتر وجود ندارد، بنابراین روش سریعی هستند. طرح بهتر در بسیاری از موارد نمی شود و الگوریتمها به وسیله یک بار اجرا، یک طرح بهتر را پیدا می کنند. در روش مبتنی بر هزینه اصل بر بکارگیری رابطه آماری در محاسبه برآوردها و هزینه هاست. دارای فضای جستجوی نمایی بوده و استفاده از متدهای شایستگی برای جستجو و پیدا کردن بهترین طرح برای روابط کوچک و عدم وجود امکان برای پیدا کردن طرح برای تعداد زیادی از رابطه ها از ویژگی های آن می باشد [18].
2-2-2-1 گراف پیوند
اساس روش های بهینه سازی پرسجو بر این اصل استوار است که هر پایگاه داده را می توان به صورت یک گراف پیوند در نظر گرفت به طوری که هر گره نشان دهنده یک جدول و هر لبه نشان دهنده وجود ارتباط بین آن جداول می باشد. هر دو دسته از الگوریتم ها با توجه به این گراف پیوند عمل می کنند [19].
شکل 2-9: گراف پیوند
الگوریتم های مبتنی بر قاعده روشی با انعطاف پذیری پایین و اغلب با کارایی پایین می باشند و اغلب اصلا طرح بهینه ای بدست نمی آید، ولی با توجه به اینکه در یک بار اجرا یک طرح را به عنوان طرح بهینه انتخاب می کنند، روش سریعی هستند. از جمله می توان به الگوریتم های پریم و کروسکال اشاره کرد. این روش ها فقط برای پایگاه داده های کوچک با ظرفیت محدود کارایی داشته و در عمل کارایی چندانی ندارند.
در الگوریتم های مبتنی بر هزینه از روابط آماری و اطلاعات موجود در کاتالوگ سیستم در محاسبه برآوردها و هزینه ها استفاده می شود و فضای جستجو نمایی بوده و از متدهای شایستگی برای جستجو استفاده می شود. با توجه به این ویژگی ها این الگوریتم ها دارای انعطاف پذیری و تنوع زیادی بوده و نتایج بهتری تولید می کنند الگوریتم های مبتنی بر هزینه خود به دو دسته الگوریتم های قطعی و الگوریتم های غیر قطعی تقسیم می شوند [20].
الگوریتم های قطعی فقط یک الگوریتم جستجوی فراگیر و مهم دینامیکی می باشند و در مقابله با سوالات بزرگ واقعی ناتوان می باشند. اما الگوریتم های غیر قطعی به وسیله جستجوی یک نمودار که گرههای آن تمام طرحهای اجرایی متناوب می باشند و می توانند برای پاسخ به سوال به کار برده شوند، عمل می کنند. هر گره دارای یک هزینه به همراه آن می باشد و هدف الگوریتم کشف یک گره به همراه هزینه های حداقل آن می باشد. الگوریتمهای تصادفی یک روند تصادفی در نمودار از طریق یک مجموعه حرکتی اجرا می کنند [18].
2-2-2-2 الگوریتم های قطعی
حال با توجه مطالب بیان شده به بررسی الگوریتم های زیر مجموعه الگوریتم های قطعی می پردازیم.
2-2-2-2-1 برنامه ریزی دینامیکی [21]
در این روش با توجه به اطلاعات موجود در کاتالوگ سیستم مدیریت پایگاه داده به اجرای الگوریتم پرداخته می شود:
شکل 2-10: الگوریتم برنامه ریزی دینامیکی
چک کردن همه سبک های ممکن از رابطه، اجرایی شدن تعداد محدودی از رابطه ها، استفاده شده به وسیله IBM در برنامه های بانک اطلاعاتی، ایجاد و محاسبه هزینه ها بصورت تکراری برای تمامی ترکیبات روابط، استفاده از یک رابطه ساده و قابل دسترس برای شروع کار، محاسبه هزینه برای ترکیب روابط بصورت دو به دو و تکرار بترتیب همین عمل برای ترکیبات با تعداد بیشتر روابط از ویژگی های این الگوریتم است [21] بطور مثال شکل 2-11:
شکل 2-11: چهار رابطه که با هم ترکیب می شوند
2-2-2-2-2 الگوریتم دایجسترا
توصیف: یک الگوریتم که بر روی گراف عمل می کند و کوتاه ترین طرح برای رسیدن از یک گره مبدا تا یک گره مقصد را در یک گراف وزن دار پیدا می کند. نکته ای که در این الگوریتم بایستی مد نظر قرار گیرد این است که یک گراف نباید دارای لبه های با وزن منفی باشد. (وزن برای یک طرح یعنی جمع وزن های لبه های استفاده شده در یک طرح)
اما سوال اینجاست که چگونه می توان انجام طرح های مختلف بین گره ها و روابط در گراف ترکیب را مدیریت کرد. برای پاسخ به این سوال، یک طرح بطور مستقیم در یک گراف ترکیب جستجو می شود. اما برای کوتاه ترین مسیر در یک گراف دیگر نیز جستجو می شود. در عبارات فوق منظور از گره ها یعنی تمام زیر مجموعه های ممکن از روابط برای ترکیب کردن و منظور از لبه ها یعنی امکان ایجاد ارتباط هر گره با گره دیگر با توجه به اینکه امکان رفتن با اجرای درست یک ترکیب یا پیوند به گره دیگر وجود دارد یا نه. وجود یک گره در یک طرح به این معنی است که روابط بصورت یک به یک ترکیب می شوند و رفتن از یک گره به گره دیگر به این معنی است که ترکیب انجام می شود.
شکل 2-12: ترکیب چهار رابطه A, B, C , D
حال با رعایت نکات زیر به جزئیات الگوریتم پرداخته می شود:
برای هر گره V موارد زیر مورد توجه قرار می گیرد:
کمترین هزینه C(V) که قبلا از یک طرح برای رسیدن به یک گره مورد نظر به دست آمده
حالت گره از لحاظ باز یا بسته بودن
یک مجموعه از گره ها در یک M نگهداری می شود که به عنوان گره باز هستند که قبلا از یک طرح برای رسیدن به یک گره مورد نظر به دست آمده اند.
گام های الگوریتم.
گره های آغازی را در مجموعه خالی{} قرار بده از مجموعه M با هزینه صفر
گره V را از مجموعه M بردار بشرطی که هزینه آن یعنی V(C) کوچکترین مقدار باشد.
برای تمام لبه های خارج شونده از گره V، هزینه را برای تمام طرح هایی که به گره مقصد دیگر از گره V می روند، محاسبه کن.
تمام گره های باز را که لبه ای از آن خارج می شودرا در مجموعه M قرار بده اگر قبلا در آن نبوده باشد.
اگر مجموعه M خالی نباشد و ما گره ی داشته باشیم که هنوز به عنوان مقصد انتخاب نشده به مرحله دوم برگرد [21] .
2-2-2-2-3 الگوریتم جستجوی A*
(بهبود یافته الگوریتم دایجسترا) معرفی یک تابع اکتشافی H(v) که یک کران پایین از هزینه طرح از گره v تا گره مقصد را محاسبه می کند. یک مرحله از الگوریتم دایجسترا تغییر داده شده و V(c) یک گره با کمترین مقدار V(c)+H(v) جایگزین کرده و به عنوان گره بسته علامت گذاری می شود. اگر یک تابع اکتشافی بهتر موجود باشد، اجباری خواهد بود که به تمام فضای جستجو رجوع شود.
تابع اکتشافی: اگر هنوز خواسته شود تا گره ها به عنوان بسته بندی علامت گذاری شود تابع اکتشافی به ارضای دنباله
شرایط زیر است:
C(y)-C(x)< H(x)-H(y) (2)
اگر شرایط شکست نقض شد نمی توان گره ها را به عنوان بسته علامت گذاری کرد و اجباراٌ برخی گره ها برای چندین بار
پردازش می شود.
توابع مکاشفه ای ممکن:
۱- تعداد چندتایی ها در گره ها یا منحنی مورد نظر
۲-کاهش مسیرهایی که از تعداد زیادی چند تایی بوجود آمده است. (فقط قابل اجرا در گرهها یا منحنیهای قابل تجسم)
۳-تعداد چند تایی هایی که نیاز به بازیابی دستورات از روابط باقی دارد. یک کران پایین واقعی که وضعیت را جبران می کند و اجازه به نشانه گذاری گره های بسته می دهد.
۴-احتمالا برای رسیدن به کران پایین اتصالات باقی مانده توسعه پیدا کند. یا هر تخمین و تقریب دیگر[22].
2-2-2-3 الگوریتم های غیر قطعی
حال با توجه به ویژگیهای غیر قطعی الگوریتم هایی که در این مجموعه قرار دارند مورد بررسی قرار می گیرد.
2-2-2-3-1 گردش تصادفی
به طور تصادفی به میان فضای جستجو می رود.
-1 بیشترین مقدار را به عنوان بهترین مسیرمشخص تنظیم می شود.
-2 یک مسیر اتفاقی را انتخاب می شود
-3 اگر ارزش مسیر بهتر از ارزش مسیر حال حاضر است بدانید که آن مسیر بهترین مسیر است
-4 به مرحله دوم برگرد.
روش فوق بسیار ساده ولی نه قابل استفاده در تمرینات. ولی می توان در مقایسه با الگوریتم های دیگر بکار برد.
نزدیکترین همسایگی (مجاورت)
* از اولین گره آغاز می شود
* لبه ای انتخاب می شود که پایین ترین هزینه را برای رسیدن به گره دست نخورده داشته باشد
*مرحله قبلی تکرار می شود تا اینکه هیچ گره ملاقات نشده وجود نداشته باشد
*اگر مسیر پیدا شده هزینه پایین تری نسبت به بهترین مسیر دارد جای آنها با هم عوض می شود
*گره بعدی انتخاب شود در حالیکه از یک شروع می شود و با مرحله دوم ادامه داده می شود
بررسی کردن تمام مسیرهای ثابت بجای تنها یک لبه امکان پذیر است [22].
2-2-2-3-2 نزدیکترین همسایگی در درخت پرپشت
۱- یک مجموعه از گره ها را که امکان دست یابی به همه ارتباطات را دارد بسازد.
۲- کم ارزشترین پیوند را از بین ترکیبات پیوندی موجود که بین دو رابطه وجود دارد انتخاب می شود.
۳- گره خروجی یا همان گره نتیجه به دسته روابط که قرار است به هم پیوند یابند اضافه می شود.
۴- منشاء نسبت ها از دسته حذف می شود.
به مرحله دوم رجوع می شود، اگر بیش از دو تا نسبت وجود دارد ممکن است یک یا پیوند های بیشتری داشته باشید [22].
2-2-2-3-3 شبیه سازی سرد شدن فلزات
این روش شبیه سازی پدیده فیزیکی سرد شدن فلزات است. یک کریستال دارای بیشترین انرژی و کمترین تغییرات تصادفی در ساختارش می باشد. این تغییرات کوچک به پایداری بیشتر می رسند در هنگامی که کریستال از خودش انرژی پخش می کند. یک مسیر در هنگام اجرا در بار اول دارای بیشترین هزینه است، در هر بار تکرار اجرای یک پروسس یک تغییر تصادفی اتفاق می افتد. تغیرات در هزینه مستقل از تغییرات احتمال خواه تغییرات حفظ شوند یا دور انداخته شوند محاسبه میشود. تغییرات با محاسبه احتمالات نگه داشته می شود.
شکل 2-13: الگوریتم شبیه سازی سرد شدن فلزات
2-2-2-3-4 تپه نوردی
بیان الگوریتم:
۱- از یک مسیر تصادفی شروع می شود.
۲- تمام مسیرهای مجاور بررسی می شود و یکی با نازلترین ارزش پیدا می شود.
۳- اگر ارزش بهترین مسیر مجاور از مسیر واقعی کمتر باشد مسیر واقعی با مسیر مجاور عوض می شود.
۴-به مرحله دوم برگرد اگر در مرحله قبلی مسیر بهتری پیدا شد [23].
2-2-2-3-5 الگوریتم ژنتیک:
برای اجرای الگوریتم ژنتیک در این رابطه ابتدا پرسجو ها به فرم بهینه در آورده می شود. سپس برای بهینه کردن یک پرسجو که ترکیبی از چند جدول است آنها را از فضای واقعی مسئله به فضای کدهای قابل پردازش می بریم. سپس مراحل زیر انجام می شود.
جمعیت اولیه آرایه ای از ژن ها در نظر گرفته می شود که تشکیل کروموزم را می دهند. نسل های بعدی حاصل ترکیبی از عملگرهای های زیر است:
انتخاب: مناسب ترین افراد برای باقی ماندن به نسل بعدی انتخاب می شوند.
برش (ترکیب): بهترین اعضای انتخاب شده با هم ترکیب می شوند و زاد و ولد می کنند
جهش: کسر مشخصی از مردم جهت ایجاد تنوع ژنتیکی بصورت تصادفی عوض می شوند [24و25].
این مراحل بصورت تکراری انجام می شوند تا زمانی که
– جمعیت به کیفیت دلخواه برسند (به بهینه ترین پرسجو برسیم)
– تعداد جمعیت از پیش تعیین بوجود آید (برای تعداد مشخصی از نسل ها صورت گیرد)
– هیچ پیشرفتی برای نسلهای مختلف حاصل نشود (جمعیت تقریباٌ مثل هم شوند)
الگوریتم برای زمانی مشخص اجرا می شود.
2-2-2-3-6 الگوریتم اصلاح مکرر
استراتژی شبیه الگوریتم تپه نوردی می باشد که از روش تقسیم وغلبه برای یافتن مینیمم محلی استفاده می کند.
شکل 2-14: الگوریتم اصلاح مکرر
مراحل الگوریتم:
۱-نقطه شروع تصادفی انتخاب می شود
۲- مجاورت یا همسایگی تصادفی انتخاب می شود اگر ارزش آن کمتر از گره جاری است کپی برداری می شود.
۳-مرحله دوم تکرار می شود تا اینکه حداقل محلی بدست آید.
۴-تمام مراحل تکرار می شود تا زمانی که شرایط توقف احراز شود.
۵-به مینیمم محلی با پایین ترین ارزش بر می گردیم.
شرایط توقف ممکن است براساس یک شماره شمارنده با یک مقدر ثابت باشد و یا براساس یک بازه زمانی باشد [23].
2-2-2-3-7 اتوماتهای یادگیر
یکی دیگر از الگوریتمهای غیر قطعی که پیاده سازی شده اند اتوماتهای یادگیر می باشند. یادگیری در آتاماتهای یادگیری، انتخاب یک اقدام بهینه از آتاماتا بوسیله یک پاسخ تصادفی از مجموعه پاسخ های مجاز جواب می دهد. پاسخ محیط به صورت آماری به اقدام آتاماتا وابست هاست. اصطلاح محیط شامل اجتماع تمام شرایط خارجی و تاثیرات آنها روی عملکرد آتاماتا می باشد [26].
شکل 2-15: زیر برنامه مربوط به اتومات یادگیر
شکل 2-16: روال مربوط به جریمه
شکل 2-17: روال مربوط به پاداش
2-2-2-3-8 ترکیب الگوریتم ژنتیک و آتاماتای یادگیر [27]
با ترکیب الگوریتم ژنتیکی و آتاماتای یادگیر و تلفیق مفاهیم ژن ، کروموزوم ، اقدام و عمق ، سابقه تاریخی تکامل راه حل مساله، به شکل کار ا استخراج شده و در روند جستجو مورد استفاده قرار می گیرد . خاصیت مهم الگوریتم ترکیبی، مقاومت آن در مقابل تغییرات سطحی جواب هاست ، به عبارتی دیگر تعادلی انعطاف پذیر بین کارایی الگور یتم ژنتیکی و پایداری آتاماتای یادگیر در الگوریتم ترکیبی وجود دارد. خودترمیمی ، تولید مثل، جریمه و پاداش (هدایت) از ویژگی های الگوریتم ترکیبی است. در ادامه پارامترهای اصلی این الگوریتم توضیح داده شده است.
2-2-2-3-8-1 ژن و کروموزوم:
در الگوریتم پیشنهادی برخلاف الگوریتم های ژنتیکی کلاسیک، از کدگذاری دودویی یا نمایش جایگشت طبیعی برای کروموزوم ها استفاده نمی شود . هر کروموزوم توسط یک آتاماتای یادگیر از نوع مهاجرت اشیا نشان داده می شود. بطوریکه هر کدام از ژنها در کروموزوم به یکی از اقدامهای آتاماتا نسبت داده می شود و در یک عمق مشخصی از آن اقدام قرار می گیرد . در این آتاماتا مجموعه اقدا مهای مجاز برای آتاماتای یادگیر است . این آتاماتا k اقدام دارد (تعداد اقدام های این آتاماتا با تعداد اعمال پیوند برابر است). اگر پیوند شماره u از پرس وجوی داده شده در اقدام m قرار گرفته باشد، در اینصورت پیوندu ، m امین پیوندی از پرس وجو خواهد بود که اجرا می شود. مجموعه وضعیت ها وN عمق حافظه برای آتاماتا می باشد . مجموعه وضعیت های این آتاماتا به k زیر مجموعه و و … و افراز می شود و عملگرهای پیوند بر اساس این که در کدام وضعیت قرار داشته باشند دسته بندی می گردند. اگر پیوند شماره u از پرس وجو در مجموعه وضعیت قرار داشته باشد در اینصورت پیوند u، j امین پیوندی خواهد بو د که اجرا می شود. در مجموعه وضعیت های اقدام j، به وضعیت ، وضعیت داخلی و به وضعیت وضعیت مرزی گفته می شود. گره ای که در وضعیت قرار دارد گره با اهمیت بیشتر و گره ای در وضعیت با اهمیت کمتر نامیده می شود. در اثر پاداش دادن یا جریمه کردن یک اقدام ، وضعیت پیوند وابسته به آن اقدام ، تغییر می کند که بعد از ایجاد شدن چند نسل از آتاماتاها توسط الگوریتم ژنتیکی می توان به یک جایگشت بهینه رسید که همان بهترین راه حل مسئله است . اگر پیوندی در وضعیت مرزی یک اقدام قرار داشته باشد ، جریمه شدن آن باعث تغییر اقدامی که پیوند به آن وابسته است، می شود و در نتیجه باعث ایجاد جایگشت جدیدی می گردد. حال پرس وجوی زیر را در نظر بگیرید:
(A∞C) and (B∞C) and (C∞D) and (D∞E)
هر عمل پیوند دارای یک شرط برای انجام پیوند می باشد که جهت سادگی نمایش حذف شده است و مشخص می کند که کدام تاپلها از روابط پیوند یافته در نتیجه ظاهر می شوند. همان گونه که در قسمت های قبلی ذکر گردید این پرس وجوینیز می تواند به صورت گراف شکل 2-18 نمایش داده شود. حروف بزرگ را برای نشان دادن رابطه ها و pi را برای نمایش عملگرهای پیوند بکار می بریم.
شکل 2-18: گراف پرسجو
مجموعه عملگرهای پیوند p1,p2,p3,p4 را در نظر می گیریم تا جایگشتی از ترتیب اجرای عملیات پیوند را با آتاماتای مهاجرت اشیاء مبتنی بر اتصالات آتاماتای ستلین نشان دهیم. این آتاماتای یادگیر دارای 4 اقدام {a1,a2,a3,a4}( به تعداد پیوندهای پر سوجو) و عمق 5 می باشد. مجموعه وضعیت های}١،۶،١١،١۶،٢١،٢۶{ وضعیتهای داخلی و مجموعه وضعیتهای }5،١٠،١۵،٢٠،٢۵،٣٠{ وضعیتهای مرزی آتاماتای یادگیر هستند. در ابتد ا هر یک از پیوندهای پرس وجو در وضعیت مرزی اقدام مربوطه قرار دارند . در الگوریتم ترکیبی هر ژن از کروموزوم معادل یک اقدام آتاماتا می باشد و لذ ا می توان در ادامه این دو واژه را به جای یکدیگر بکار برد . این آتاماتای یادگیر(کروموزوم) دارای 4 اقدام (ژن) می باشد و هر اقدام دارای 5 وضعیت داخلی می باشد. فرض کنید در اولین جایگشت ابتدا پیوند 3 و سپس پیوند 2 و پیوند 1 و در انتها پیوند4 ترتیب اجرای عملگرهای پیوند ما باشند . نحوه نمایش این ترتیب اجرا با آتاماتای مهاجرت اشیای مبتنی بر اتصالات آتاماتای ستلین67 بصورت شکل 2-19 است. در ابتدا هر یک از پیوندها در وضعیت مرزی اقدام مربوطه قرار دارند.
شکل 2-19: نمایش جایگشت پیوندهای p1,p2,p3,p4 توسط آتاماتای یادگیر مبتنی بر اتصالات آتاماتای ستلین
2-2-2-3-8-2تابع برازندگی:
در الگوریتم.های ژنتیکی، تابع برازندگی شاخص زنده ماندن کروموزوم ها است. هدف جستجوی ترتیب بهینه پیوندهای پرس وجو، یافتن جایگشتی از عملگرهای پیوند می باشد که کل هزینه اجرای پر سوجو در این جایگشت کمینه باشد. نکته ای که در محاسبه تابع برازندگی مهم است، تعداد رجوعات به دیسک می باشد. لذا می توانیم تابع برازندگی F را برای یک طرح اجرایی qep بصورت زیر تعریف نماییم
. F(qep)=1/ تعداد رجوعات به دیسک
برای محاسبه تعداد رجوعات به دیسک (هزینه) یک طرح اجرایی، هر طرح اجرایی را متناسب با یک درخت پردازشی در نظر می گیریم. هزینه هر گره بصورت بازگشتی (پایین به بالا و از راست به چپ) با جمع هزینه های بدست آمده از دو گره فرزند و هزینه لازم جهت پیوند آنها برای بدست آوردن نتیجه نهایی، محاسبه می شود [21]. برای نمونه، پیوند R1∞R2 را در نظر می گیریم:
در این صورت هزینه ارزیابی برابر با مقدار زیر خواهد بود:
که در آن C(Rk) هزینه بدست آوردن گره فرزند می باشد و از رابطه زیر قابل محاسبه است:
بعنوان یک حالت خاص اگر R1 و R2 هر دو رابطه پایه ای باشند هزینه Ctotal برابر با C(R1∞R2) خواهد بود و باتوجه به اینکه نوع پیاده سازی بکار رفته برای عمل پیوند در پرس وجوها را از نوع حلقه های تودر تو 68در نظر گرفته ایم، هزینه محاسبه عمل پیوند در این نوع پیاده سازی برابر C(R1∞R2 ) = bR1 + bR2 است که bRk تعداد بلاکهای رابطه Rkمی باشد.
عملگرها: با توجه به اینکه در الگوریتم ترکیبی هر کرومو زوم بصورت یک آتاماتای یادگیر نمایش داده می شود عملگرهای جابجایی و جهش با مشابه این عملگرها در الگوریتمهای ژنتیکی متفاوت میباشند.
عملگر انتخاب69: عملگر انتخاب بکار رفته برای این الگوریتم، از نوع چرخ رولت 70می باشد.
عملگر ترکیب یا جابجایی71: عملگرهای جابجایی پیاده سازی شده برای الگوریتم ترکیبی عبارتند از:
Ordered: این روش ترتیب نسبی ژنها درکروموزوم را تا حد ممکن حفظ می کند. با در نظر گرفتن جایگشت های والد اول و والد دوم ، دو جایگشت فرزند به وسیله انتخاب دو نقطه برش در جایگشتهای والدین و کپی کردن الما نهای بین دو نقطه برش در فرزندان، و پر کردن باقیمانده جایگشت های فرزندان با الما نهای استفاده نشده از والد دیگر با شروع از نقطه برش دوم به بعد، ایجاد می شوند.
:Reverse این نوع عملگر جابجایی شبیه روش Ordered است با این تفاوت که در این روش ژنهای خارج از دو نقطه برش در فرزندان کپی می شوند بر خلاف روش Ordered که ژنهای بین دو نقطه برش در فرزندان کپی می شوند.
:Partially Mapped در این نوع عملگر جابجایی، دوجایگشت فرزند به وسیله انتخاب دو نقطه برش درجایگشت های والدین و کپی کردن الما نهای بین دو نقطه برش در فرزندان و پر کردن باقیمانده جایگشت های فرزندان با المان های متناظر آنها از والدین، ایجاد می شوند. توجه کنید که اگر یکی از المانهای خارج از ناحیه جابجایی فرزندی با یکی از المان های ناحیه جابجایی خود یکسان باشد آن المان به عنوان حفره در نظر گرفته می شود و باید مقدار آن عوض شود. نحوه پر کردن یک حفره به این صورت است که مثلا اگر حفره در فرزند اول باشد، ابتدا موقعیت ژنی از والد دوم را که دارای مقدار مساوی با مقدار حفره است پیدا می کنیم. سپس از والد اول مقدار ژنی را که در موقعیت یکسانی با ژن پیدا شده قرار دارد را به عنوان مقدارحفره در نظر می گیریم.
:Cycle در این عملگر جابجایی ، دو جایگشت فرزند بوسیله شکل دادن یک سیکل در بین والدین ایجاد می شوند .
به عنوان مثال برای ا یجاد فرزند اول، با شروع از اولین المان والد 1، آن را به اولین ژن در والد دوم نگاشت می کنیم.سپس اولین ژن والد دوم را در فرزند اول پیدا کرده و به ژن هم مکان خود در والد دوم نگاشت می دهیم و این کار تا کامل شدن سیکل کامل ادامه می یابد. المان هایی از سیکل را که در والد 1 هستند در فرزند اول قرار می دهیم. سپس مکان های خالی فرزند اول را با المان های متناظر در والد 2 پر می کنیم. فرزند دوم نیز به همین ترتیب ایجاد می شود.
:Exchange در این عملگر جابجایی، دو کروموزوم والد انتخاب می شوند و به صورت تصادفی دو ژن j و i در یکی از دو کروموزوم والد انتخاب می شوند. سپس همین دو ژن در کروموزوم دیگر انتخاب می شوند. مجموعه ژنهای با شماره های بین j و i را مجموعه جابجایی می نامیم. سپس ژن های هم شماره در دو مجموعه جابجایی با یکدیگر جابجا می شوند (مثلا ژن شماره i از مجموعه جابجایی اول با ژن شماره i از مجموعه جابجایی دوم، ژن شماره i+1 از مجموعه جابجایی اول با ژن شماره i+1 از مجموعه جابجایی دوم و …). با این عمل دو کروموزوم جدید حاصل می شوند که اصطلاحاً فرزندان دو آتاماتای والد خوانده می شوند.
:Smart Exchange این عملگر جابجایی دقیقا مانند روش Exchange است با این تفاوت که مثلا ژن شماره iاز مجموعه جابجایی اول با ژن شماره i از مجموعه جابجایی دوم زمانی جابجا می شود که هزینه اجرای پیوند مشخص شده با ژن i در مجموعه جابجایی اول کمتر از مجموعه دوم باشد. در نهایت هر کروموزوم مجموعه ژنهای j تا i خود را در صورتی که هزینه شان بیشتر از ژنهای کروموزوم دیگر باشد از او کپی می کند . شبه کد این عملگر به عنوان مثال در شکل 2-20 نشان داده شده است.
شکل 2-20: شبه کد عملگر جابجایی
از آنجا که در این الگوریتم از n کروموزوم (آتاماتا) استفاده می شود و هر آتاماتا دارای مشخصه های اختصاصی مربوط به خود (وضعیت ، اقدام و شئ متناظر هر اقدام) می باشد، جهت خوانایی بیشتر شبه کد ، این مشخصه ها را با پیشوند نام آتاماتا و جداساز نقطه نشان می دهیم . مثلا برای نشان دادن وضعیت پیوند u از آتاماتای i از نمایش LAi.State(u) استفاده شده است. در الگوریتم مذکور costi(LA1)، هزینه )تعداد رجوعات به دیسک) برای پیوند موجود در اقدام i ام آتاماتای یادگیر 1 می باشد. به عنوان مثال دو آتامات ا از جمعیت تشکیل شده به صورت تصادفی انتخاب می شوند . سپس با انتخاب تصادفی دو محل a2,a3 مجموعه جابجایی {a2,a3} حاصل می شود. در نهایت مطابق شکل 2-21 با جابجایی اقدام های متناظر در فاصله جابجایی، دو کروموزوم جدید حاصل می شود عملگر جهش72: برای انجام دادن این عملگر از ر وشهای مختلفی که برای کار با جایگشت ها مناسب هستند استفاده شده است .
روش های پیاده سازی شده برای عملگر جهش عبارتند از:
:Order Based (Swap) این عملگر، دو اقدام (ژن) از یک آتاماتا (کروموزوم) را به صورت تصادفی انتخاب نموده و جابجا می کند.
:SubList Based دو ژن از کروموزوم را بطور تصادفی انتخاب کرده و ترتیب آنها را معکوس می کند.
:Insertion ژن یا بلوکی از ژنها را بطور تصادفی درکروموزوم انتخاب کرده و آنرا در نقطه تصادفی دیگری درج می کند.
:Scramble یک بلوک از ژنها را بطور تصادفی انتخاب کرده و آنها را بصورت تصادفی دوباره مرتب می کند.
شکل 2-21: نحوه عملگر جابجایی
به عنوان نمونه شکل 2-22 مثالی از عملگر جهش Swap Mutation و شکل 2-23 نیز شبه کد این عملگر را نشان می دهد.
شکل 2-22: نحوه عملگر جهش
شکل 2-23: شبه کد عملگر جهش
عملگر جریمه و پاداش : در هر یک از کروموزوم ها پس از بررسی میزان برازندگی یک ژن که به صورت تصادفی انتخاب شده است، به آن ژن پاداش یا جریمه داده می شود . در اثر پاداش دادن یا جریمه کردن یک ژن، عمق ژن تغییر می کند .شکل2-24 شبه کد عملگر پاداش را نشان می دهد.
شکل 2-24: شبه کد عملگر پاداش
به عنوان مثال در آتاماتای با اتصال های مشابه آتاماتای ستلین اگر پیوند p2در مجموعه وضعیت های }١٠،9،8،7،6{ قرار داشته باشد و هزینه برای پیوند p2 موجود در اقدام دوم از متوسط هزینه های پیوندهای موجود در کروموزوم، کمتر باشد، به این پیوند پاداش داده می شود و اهمیت پیوند افزایش می یابد و به سمت وضعیت های داخلی تر این اقدام حرکت می کند. اگر پیوند p2 در وضعیت داخلی 6 قرار داشته و پاداش بگیرد، در همان وضعیت باقی می ماند. این مورد در شکل2-25 نشان داده شده است.
شکل 2-25: نحوه پاداش پیوند p2
همچنین اگر هزینه پیوندی از متوسط هزینه پیوندهای موجود در کروموزوم، بیشتر باشد، در اینصورت محل قرارگیری این پیوند مناسب نبوده و جریمه می شود شبه کد عملگر جریمه در شکل 2-26 نشان داده شده است.
شکل 2-26: شبه کد عملگر جریمه
نحوه حرکت چنین پیوندی برای دو حالت مختلف در زیر آمده است.
الف) پیوند در وضعیتی غیر از وضعیت مرزی قرار داشته باشد: جریمه نمودن این راس سبب کم اهمیت شدن این راس می شود. نحوه حرکت چنین راسی در شکل 2-27 نشان داده شده است.
شکل 2-27: نحوه جریمه کردن یک راس که در وضعیتی غیر از وضعیت مرزی قرار داشته باشد
ب) پیوند در وضعیت مرزی قرار دارد. در این حالت پیوندی از پرس وجو ر ا پید ا می کنیم بطوریکه اگر در طرح اجرایی مربوطه جای دو راس عوض شوند بیشترین کاهش در مقدار هزینه حاصل گردد در اینصورت اگر پیوند پید ا شده در وضعیت مرزی قرار داشته باشد جای دو پیوند عوض می شود و در غیر اینصورت ابتدا پیوند مشخص شده به وضعیت مرزی اقدام خود منتقل و سپس جابجایی صورت می پذیرد . نحوه حرکت چنین پیوندی در شکل 2-28 نشان داده شده است . در شکل2-29 نیز شبه کد الگوریتم ترکیبی تعیین ترتیب پیوندها در پرس وجو نشان داده شده است.
شکل 2-28: نحوه جریمه کردن یک راس که در وضعیت مرزی قرار داشته باشد
شکل 2-29: شبه کد الگوریتم ترکیبی
مراجع
[1] DATE C.J, An Introduction to Database Systems, Seventh Edition, 2000
[2] CONNOLY, Thomas, BEGG, CAROLYNS, STRACHAN, ANNE, Database Systems, Second Edition, 1999.
[3] G. RAMAKRISHNAN, Database Management Systems, Third Edition , 2003.
[4] S. Kirkpatrick, C. D. Gelatt, Jr., M. P. Vecchi, Optimization by simulated annealing, Science, 220 (4598) (1983) 671-680.
[5] 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.
[6] I. O. Hababeh , A Method for Fragment Allocation Design in the Distributed Database Systems, The Sixth Annual U.A.E. University Research Conference, 2005.
[7] 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
[8] ISHFAQ AHMAD, Evolutionary Algorithms for Allocating Data in Distributed Database Systems, Distributed and Parallel Databases, 11, 5-32, 2002.
[9] 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.
[10] Y. F. Huang and J. H. Chen, Fragment Allocation in Distributed Database Design Journal of Information Science and Engineering 17, 491-506, 2001.
[11] 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.
[12] 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.
[13] S. Voulgaris, M.V. Steen, A. Baggio, and G. Ballintjn, Transparent Data Relocation in Highly Available Distributed Systems. Studia Informatica Universalis. 2002.
[14] P.M.G. Apers, "Data allocation in distributed database systems," ACM Transactions on Database Systems, vol. 13, no. 3, pp. 263-304, 1988.
[15] R. Baseda, S. Tasharofi, M. Rahgozar, Near Neighborhood Allocation: A Novel Dynamic Data Allocation Algorithm in DDB, CSICC 2006.
[16] K. Bennet, M. C. Ferris, Y. E. Ioannidis, A genetic algorithm for database query optimization, In Proc. Of the Fourth Intl. Conf. on Genetic Algorithms, San Diego, USA (1991) 400-407.
[17] T. Ibaraki and T. Kameda, Optimal nesting for computing N- relational joins, ACM Trans. on Database Systems, 9 (3) (1984) 482-502.
[18] Yannis E. Ioannidis, Query OptimizationT, Computer Sciences Department University of Wisconsin Madison, WI 53706.
[19] Surajit Chaudhuri, An Overview of Query Optimization in Relational Systems, Redmond, Microsoft Research, 1998, WA 98052.
[20] سید محمد تقی روحانی رانکوهی، سیستم مدیریت پایگاه داده ها، انتشارات جلوه تهران، 1383.
[21] Michael Steinbrunn, Guido Moerkotte, Alfons Kemper, Heuristic and Randomized Optimization for the Join Ordering Problem. 1998
[22] Zehai Zhou, Using Heuristics and Genetic Algorithms for Large-scale Database Query Optimization, Journal of Information and Computing Science Vol. 2, No. 4, 2007.
[23] Kristina Zelenay, ETH Zürich, Query ptimization, Seminar Algorithmen for Datenbase systeme, June 2005.
[24] Rocıo L. Cecchini, Carlos M. Lorenzetti, Nelida Beatrız Brignole, Using genetic algorithms to evolve a population of topical queries, elsevier,1 April 2008.
[25] Stoyan Vellev, an adaptive genetic algorithm with dynamic population size for optimizing join queries, INFOS 2008, Varna, Bulgaria, June-July 2008.
[26] Kayvan Asghari, Ali Safari Mamaghani and Mohammad Reza Meybodi, An Evolutionary Approach for Query Optimization Problem in Database, springer,2007.
[27] کیوان اصغری و همکاران، بهینه سازی اجرای پرس و جوها در پایگاه داده رابطه ای با الگوریتم تکاملی ترکیبی، مجله کامپیوتر و رباتیک 1، 37-25، 1387.
1 Distributed data base management system
2 Local autonomy
3 no reliance on a central site
4 views
5 Join
6 Client
7 Server
8 Nodes
9 Query optimization
10 Fragmentation
11 Allocation
12 Query
13 Static
14 Dependency Graph
15 Root
16 Generic Algorithm
17 Placement
18 Natural Selection
19 Natural Evolution
20 Terminator
21 Concatation
22 Initial Random Allocation
23 Greedy
24 Performance
25 Solution
26 Decoding
27 Data Problem
28 Mapping Heuristic
29 Generation
30 Collective Computation Property
31 Hopfield Neural Network
32 Random Neighborhood Search (RS) Data Allocation Algorithm
33 Moderate
34 Nearby Solution
35 Clustering
36 heterogeneous
37 Dynamic
38 Simple Counter Algorithm
39 State Process
40 Transaction
41 Local Decision
42 Threshold
43 incremental growth framework
44 data reallocation
45 Workload
46 Full REALLOCATE heuristics
47 Partial REALLOCATE
48 Iterative
49 hill-climbing
50 Attribute
51 locally
52 Remote Node
53 Crash
54 Potential
55 Scaling
56 Access Probabilities
57 Relative Threshold
58 Routing
59 Response Time
60 Response Time
61 Fragment Data Migration Time
62 Input/Output
63 Join
64 Associative
65 Commutative
66 Join Ordering Problem
67 Tsetlin
68 Nested Loop
69 Selection
70 roulette wheel
71 Crossover
72 Mutation
—————
————————————————————
—————
————————————————————
53