چکیده
پردازش پرس و جو مفهوم مهمی در حوزه ی پایگاه داده ی توزیع شده میباشد. که در همین راستا پردازش پرس و جوی توزیع شده با توجه به اینکه هدف کم کردن یا به حداقل رساندن هزینهی عملیاتی میباشد، فاکتور مهمی در کل کارایی سیستم پایگاه دادهی توزیع شده می-باشد.ما در این مقاله از معماری شبکه توزیعی متمرکز استفاده می کنیم، براساس این نوع معماری سرور باید تصمیم گیری کند چگونه پرس وجو را شکسته و به کدام کلاینت با کمترین هزینه ی عملیاتی فرستاده و زمان پاسخ کمینه را دریافت نماید. هدف از این مقاله نحوهی تخصیص زیر پرس وجو ها به سایت ها مختلف با شایستگی بهترمیباشد. با مدل کردن ویرگی های سایت به کروموزم ها که هر ژن کروموزم یکی از ویژگی سایت میباشد که بصورت پویا مثل ترافیک شبکه، تاخیر، پردازش محلی در حال تغییر است باعث میشود تخصیص زیرپرش وجوها هوشمندانه شود در نتیجه زمان پاسخ کمینه شود. که الگوریتم فرهنگی با روشهای شمارشی و الگوریتم ژنتیک مقایسه شده که نتایج قابل توجهی داشته است.

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

-۱ مقدمه

پایگاه دادهها در این نوع معماری بر حسب کاربری به دو بخش Back-end و Front-end تقسیم میشود، Back-end وظیفه بررسی و کنترل دسترسیها، بررسی و بهینه سازی پرس و جوها و کنترل همزمانی ها و سالم بودن پایگاه داده ها را به عهده دارد، Front-end شامل ابزارهایی برای نمایش و زیبا سازی نتایج پرس و جو ها مثل ابزارهای تولید فرمها و ابزار های گزارش گیری می باشد.[۱] برای ایجاد ارتباط درست میان دو قسمت فوق نیازمند یک لایه و بستر می باشیم. این بستر می تواند از دو طریق دستورات SQL و یا API ها برقرار شود.

در مقایسه این نوع معماری با معماری متمرکز با استفاده از پردازنده-های مرکزی می توان افزایش میزان کاربری سیستم با توجه به هزینه، آسان تر شدن گسترش و توزیع منابع، تولید واسط های کاربر بهتر و راحت تر شدن نگهداری سیستم را نام برد.

در این نوع معماری، سرورها از لحاظ عملکردی به دو بخش تقسیم می شوند، یکی سرورهای داده ای که این نوع سرور ها بیشتر در سیستمهای شیگرا مورد استفاده قرار میگیرند و دیگری سرورهای تراکنشی که این نوع سرورها بیشتر در سیستمهای رابطهای مورد استفاده قرار میگیرند. در سرورهای تراکنشی که به آنها سرورهای پرس و جو هم گفته می شود روش کار بدین صورت است که درخواست های کاربران به این سیستمها ارسال میشود و نتیجه در این سرورها تولید و به کاربر ارسال میشود. درخواستهای کاربران به صورت دستورات RPC و دستورات SQL ارسال میشود. برای ارسال و دریافت نیاز به نرم افزارهایی مانند ODBC و JDBC هست که وظیفه ارتباط با سرور و ارسال پرس و جوها و دریافت نتایج را به عهده دارد. برای پیاده سازی سرورهای تراکنشی از تعدادی پردازه که حافظه مشترک دارند استفاده می شود که معمولا برای بهبود پردازهها از چندنخی مورد استفاده قرار میگیرند.

برای بهینه سازی پرس و جو در یک محیط کلاینت/سرور باید اطلاعات کافی در مورد مکان های دادهها داشته باشیم تا بتوانیم با توجه به آن بهترین روش را برای دسترسی به داده ها پیدا کنیم. مهمترین مسئله در اینجا تجزیه کردن پرس و جوها می باشد. پردازش پرس و جوی توزیع شده در سه مرحله ی فاز پردازش محلی، فاز ساده سازی و فاز پردازش انجام می گیرد، در فاز پردازش محلی گزینش ها و انتخاب انجام می گیرد و در فاز ساده سازی از یک کاهنده برای کم کردن اندازهی رابطهها استفاده می شود و در فاز پردازش نهایی نتایج رابطهها در یک جا جمع شده و نتیجهی نهایی پرس و جو ایجاد و فرستاده می شود. در اینجا به این خاطر که از موازی سازی کمتری استفاده می شود پدیده ی سربار زیاد انتقال را داریم.[۲] در پردازش پرس وجو ی توزیع شده، یکسری عملیات تحت عنوان عملیات عمومی نیز وجود دارد که این عملیات شامل قسمت بندی یک رابطه در داخل قطعهها، اجتماع قطعه ها از کل رابطه و انتقال یک رابطه / قطعه از یک پایگاه داده به دیگر پایگاه داده می باشد.[۳] برای ساده سازی انتقال داده و برای مرحله ی پردازش پرس و جو ی توزیع شده از نیم پیوند و پیوند متوالی استفاده میشود، در نیم پیوند عملیات پیوند برای کاهش پردازش پرس و جو استفاده می شوند و با استفاده از احیا کننده ی پیوند یک پرس و جو در داخل پیوند های متوالی ترجمه میشود و هر پیوند بوسیله ی یک عملگر رابطه ای به طور محلی با توجه به محل عملگر های دیگر پیاده سازی میشود. همچنین میتوان از ترکیب پیوندها و نیم پیوندها برای بهبود پردازش پرس و جوی توزیع شده استفاده کرد.[۴,۵]

-۲ جزئیات مدل های هزینه ی پردازش پرس وجو

Valduriez یک متدلوژی پردازش پرس وجو توزیع شده شرح داده است که در شکل ۱ نشان داده شده است.[۶]

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