بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
یک مدل توسعه یافته از استراتژی بخش بندی برای بهینه سازی پرس و جوها
چکیده
در یک سیستم توزیع شده، پایگاه داده توزیع شده، در سراسر شبکه، توزیع شده است، یعنی به طور منطقی، داده - ها به یک سیستم یکسان تعلق دارند، اما به طور فیزیکی، بر روی سایتهای شبکه، پخش شدهاند. هدف از توزیع کردن دادهها، بدست آوردن قابلیت اطمینان، در دسترس بودن اطلاعات و کارایی می باشد. بنابراین، انجام یک پرس و جو از دیدگاه کاربر، بدین صورت است که جدول ها در پایگاه دادهها، باید در یک جا جمع باشند. برای انجام این کار، با استفاده از روشهای بهینه سازی پرس و جو، سعی می کنند که این دید کاربر را حفظ تمایند، یعنی شفافیت را بالا ببرند و این کار، نیازمند آن است که زمان پاسخ به کاربر، به حد قابل قبول برسد و به تبع آن، هزینه انتقال در سطح شبکه و هزینه الحاق رابطه ها، کاهش یابد. در این مقاله، ابتدا روشهای موجود شامل تکنیک بخش بندی - تکرار سازی و تکنیک بخش بندی درهم به صورت اجمالی شرح داده شده اند و سپس ما روشی را پیشنهاد می کنیم که به موجب آن، ابتدا روش بخش بندی درهم را توسعه می دهیم و با توجه به ویژگیهای استراتژی بخش بندی درهم، در مییابیم که سرعت دستیابی به چند تایی های یک بخش کاهش و سرعت انتقال در سطح شبکه، تا حد زیادی افزایش مییابد و همچنین مشاهده خواهد شد که هزینه الحاق پرس و جوهای انجام شده از طرف کاربر، با توجه به معیاری که ما برای بخش بندی درنظر می گیریم، کاهش می یابد و چون عملگر الحاق، پرهزینه ترین عملگر در بین عملگرهای رابطه ای می باشد، به بهینه سازی این عملگر می پردازیم،
۱ - مقدمه
امروزه، ما با سیل عظیمی از اطلاعات مواجه هستیم، به طوری که ما، به یک شیوه مناسب برای سازماندهی این اطلاعات، نیازمندیم. به همین دلیل، سیستمهای پایگاه داده، توسعه داده شدهاند...در یک سیستم پایگاه داده متمرکز، همه اطلاعات، در یک مجموعه از جداول و رابطه ها، قرار می گیرند که در آنها، دادهها در ردیفها و ستون ها، قرار گرفته و در یک محل، ذخیره می شوند. همانطور که می دانیم، در پایگاه داده توزیع شده، اطلاعات جداول و رابطه ها، در سایتهای مختلف و در مکانهای متفاوت از نظر جغرافیایی، پخش شده اند و به دلایل گوناگون، جمع شدن اطلاعات در یک سایت، قابل قبول نیست، یا اینکه شرایط محیط به گونه ای است که این امر، میسر نیست، اگر هم اطلاعات، در یک سایت، جمع شود، هزینه انتقال و زمان پاسخ، آنقدر زیاد میباشد که اقتصادی و عقلانی نمی باشد. هدف از بهینه سازی پرس و جو" ، است که با وجود پراکندگی اطلاعات در سایتهای مختلف، زمان پردازش پرس و جو و هزینه انتقال را کاهش دهیم. البته، راهکارهایی که برای بخش بندی رابطه ها، وجود دارد، می تواند تا حد زیادی، برای رسیدن به هدفهای ذکر شده در بالا، کمک کند.
در ادامه، در بخش دوم، بهینه سازی پرس و جو را شرح می دهیم. در بخش سوم، درباره تکنیکهای بخش بندی، صحبت می کنیم و به مزایا و معایب آنها میپردازیم. در بخش چهارم، طرح پیشنهادی خود را برای تعداد محدودی از تجزیه رابطه به بخش ها، به طور مختصر شرح داده و در بخش پنجم، این روش را برای n بخش، توسعه می دهیم و در بخش آخر، نتیجهگیری را بیان می کنیم.
۲- بهینه سازی پرس وجوها | ۱ |
بهینه سازی پرس و جو، از این مساله، آغاز شد که ما چگونه می توانیم اطلاعات مورد نظر خود را در بین کل اطلاعات ذخیره شده در جداول پیدا کنیم است. برای پاسخ به این امر، قسمتی به نام بهینه ساز پرس و جو، به سیستم مدیریت پایگاه دالاه، اضافه شده است که این وظیفه را به عهده توجه به اینکه، این جستجو، از نظر زمانی، بسیار با اهمیت دارد. با اضافه شدن بهینه ساز پرس وجو، مسماری سیستم مدیریت پایگاه داده، تغییر کرد که می توان آن را در شکل (۱) مشاهده کرد:
پردازش پرس و جوی توزیع شده، یک مجموعه از اعمال رابطه ای و مراحل انتقالی شبکه، میباشد. در نتیجه، چالشها و تکنیکهای موجود در بهینه سازی پرس وجوی توزیع شده را می توان به دو دسته تقسیم کرد: ه هزینه انتقال شبکه : که تکنیکهای استفاده شده در این دسته و مقدار انتقال اطلاعات در شبکه را کاهش میدهند. • زمان پاسخ پرس وجو: که تکنیکهای استفاده شده در این دسته، از پردازش موازی، برای بهینه سازی زمان پردازش استفاده میکنند. تکنیکهایی، به منظور بخش بندی برای پردازش پرس و جوهای توزیع شده وجود دارند که هدف آنها، افزایش موازی سازی و بالا بردن کارایی بین قسمتهای مورد پردازش است و زمان پاسخ نیز تا حدی کاهش مییابد. بسته به الگوریتم بخش بندی، یک یا چند رابطه، انتخاب شده و با توجه به تعداد سایتهای پردازشی با اندازه یکسان یا متفاوت برای تعادل بار، به تعدادی پارتیشن، تقسیم و توزیع میشوند و سپس، سایر رابطه های شرکت کننده در الحاق، در این سایت ها، تکرار شده و پردازش، به طور موازی انجام می شود.
۳- تکنیکهای بخش بندی||۵|
در این بخش دو تکنیکا مهم بخش بندی که در حال حاضر استفاده می شود، ارائه می گردد.
۱-۳ - تکنیک بخش بندی و تکرار سازی
در این الگوریتم، یکی از رابطه ها، انتخاب شده و به چند بخش تقسیم می شود. سپس، این بخش، بین سایتهای مختلف، توزیع می شود، به طوری که پرس وجو، بتواند به صورت موازی انجام شود و سایر رابطه ها تکرار می شوند. به عنوان مثال، فرض کنید پرس وجو، دو رابطه RI و R2 را با مشخصاتی که در جدول (۱) آمده است، مورد ارجاع قرار دهد. با فرض این که هر دو سایت، از سرعت پردازشی یکسانی برخوردار هستند، اR، به دو بخش به نامهای با F و FI2 با اندازه یکسان، تقسیم میشود، سپس، FI2 به سایت ۲ و R2 به سایت ۱ فرستاده می شود، سپس، دو الحاق R2ہF11Cو oR2لاہ12 F به صورت موازی، در دو سایت انجام می شود. اجتماع این دو الحاق، جواب رR1 coR می - باشد. از معایب این روش، این است که چون سایتهای متفاوت، سرعت پردازش متفاوتی دارند تعادل بار، تضمین نمی شود و دوم اینکه اگر تعداد مراجعات به رابطه ها، توسط یک پرس و جو زیاد باشد تاثیر چندانی در بهبود این روش ندارد.
۳- ۲- تکنیک بخش بندی درهم
اگر در مثال قبلی، دامنه صفت الحاق، اعداد صحیح باشد، ما می توانیم R1را به دو قسمت و F ، حاوی همه تاپلها با مقدار صفت الحاق فرد و ۴ ، حاوی همه تاپلها با مقدار صفت الحاق زوج، تقسیم کنیم. به طور مشابه، R نیز می تواند به دو قسمت با چنین خصوصیاتی، تقسیم شود. بدیهی است که شرطهای زیر همواره برقرار است
بنابراین ROR می تواند به وسیله فرستادن و F به سایت ۲ و FI به سایت ۱، پردازش شود. مزیت این کار آن است که هزینه الحاق در هر سایت، کمتر خواهد بود، به این دلیل که به جای کل رابطه، فقط، یک قسمت از R ، در الحاق، به کار گرفته می شود. به - علاوه، هزینه انتقال نیز کاهش می یابد، به این دلیل که فقط نیاز است تا F به جای R ، از سایت ۲ به سایت ۱، منتقل شود. در این روش، از تابع درهم، برای بخش بندی یک رابطه به قسمت کوچکتر، استفاده می کنیم.
معایب
زبه زمان بخش بندی داریم و در صورتی که تعداد رکوردهای جدول، بسیار زیاد باشد، با زوج و فرد کردن آن نیز، حجم انتقال کاهش یافته، تاثیر چندانی در زمان پاسخ ایجاد نکرده و ما، با مشکل روبرو هستیم .
۶- طرح پیشنهادی
