تخصیص عمودی سلسله مراتبی با استفاده از الگوریتم انرژی (مقاله ترجمه شده)

چکیده

طراحی یک سیستم پایگاه داده توزیع شده موثر (DDBS) به عنوان یکی از چالش برانگیز ترین مشکلات در نظر گرفته می شود به دلیل عوامل متعدد وابسته که بر روی عملکرد آن تاثیر گذار هستند . تخصیص و تکه تکه شدن دو فرآیند هستند که کارآیی و صحت آنها می تواند عملکرد DDBS را تحت تاثیر قرار دهد . بنابراین ، تکه تکه شدن کارآمد داده ها و تخصیص قطعات در سراسر قسمت های شبکه به عنوان یک حوزه مهم پژوهشی در طراحی پایگاه داده های توزیع شده به شمار می آید . در این مقاله ما یک روشی را ارائه می دهیم که در آن به طور همزمان به تکه تکه شدن داده ها و تخصیص قطعات مناسب در سراسر شبکه خواهیم پرداخت . الگوریتم انرژی پیوندی (BEA) با اندازه وابستگی بهتری برای بهبود خوشه های تولید شده از این ویژگی ها مورد استفاده قرار می گیرد . این الگوریتم به طور همزمان خوشه هایی از این ویژگی ها را تولید می کند، هزینه تخصیص هر خوشه به هر کدام از این محل ها را مورد محاسبه قرار می دهد و هر کدام از این خوشه ها را به مناسب ترین محل تخصیص می دهد.

مقدمه

پایگاه داده های توزیع شده سبب کاهش هزینه و افزایش کارایی و در دسترس بودن می شوند ، اما طراحی سیستم های مدیریتی پایگاه داده های توزیع شده (DDBMS) پیچیده است . برای امکان پذیر شدن این فرآیند ، آن را به دو مرحله تقسیم می کنیم : تکه تکه شدن و تخصیص . در مرحله تکه تکه شدن سعی می کنیم که داده ها را به تکه هایی تقسیم کنیم ، که باید به محل هایی در طول شبکه در مرحله تخصیص اختصاص داده شود. فرآیند تکه تکه شدن به دو دسته تقسیم می شود : تکه تکه شدن عمودی و تکه تکه شدن افقی . تکه تکه شدن عمودی (VF) از لحاظ پارتیشن بندی رابطه R در مجموعه های متلاشی شده(disjoint) از روابط کوچکتر است در حالیکه تکه تکه شدن افقی (HF) پارتیشن بندی مجموعه R به چندتایی های متلاشی شده است . مشکل تخصیص شامل پیدا کردن توزیع بهینه از تکه تکه شدن مجموعه F در محل مجموعه S است . چهار نوع استراتژی قابل اجرا برای تخصیص داده در رابطه با یک پایگاه داده توزیع شده وجود دارد : متمرکز شده ، تکه تکه شده (پارتیشن)، تکرار کامل و تکرار جزئی (انتخابی) [10]. زمانی که داده ها اختصاص داده شده است ، ممکن است از آنها کپی گرفته شود یا اینکه کپی گرفته نشود . برای همین ، تخصیص قطعه می تواند به صورت فاقد افزونه و با افزونه باشد . در طی طرح تخصیص فاقد افزونه ، دقیقا یک کپی از هر قطعه در سراسر تمامی سایت ها وجود دارد ، در حالیکه در طرح تخصیص افزونه ، بیشتر از یک کپی از هر قطعه در سراسر تمامی سایت ها وجود خواهد داشت [12] . در این کار ، ما تکه تکه شدن را با تکرار جزئی برخی از خوشه های ویژگی ها را انجام می دهیم.

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

روش ها

تخصیص و تکه تکه شدن مشکلاتی مرتبط به یکدیگر هستند که حل آنها به طور همزمان دشوار می باشد ولی منجر به عملکرد بهتر در نرم افزار ها خواهد شد . برای بهترین دانش ما ، BEA به طور همزمان بر روی تخصیص و تکه تکه شدن اعمال نمی شود . زیرا در پارتیشن بندی عمودی ویژگی هایی که معمولا با هم دیده می شوند معمولا در یک قطعه قرار می گیرند ، و اندازه گیری دقیق آنها با یکدیگر ضروری می باشد .BEA از وابستگی ویژگی ها برای ایجاد خوشه هایی از ویژگی ها استفاده می کند که بیشتر شبیه هم هستند . آن را با استفاده از ویژگی (AU) و دسترسی به کوئری (QA) ماتریس ویژگی های وابستگی (AFF) و در نهایت خوشه های ماتریس وابستگی (CA) به وسیله در موقعیت قرار دادن و مجددا در موقعیت قرار دادن ستون ها و سطر هایی از ویژگی ها صورت می پذیرد . اندازه گیری وابستگی ها بسیار ساده است . اندازه گیری این وابستگی ارائه شده در BEA اصولا بر اساس دسترسی همزمان به ویژگی مبتنی برAi و ویژگی Aj از رابطه R(A1,A2,…,An) با کوئری qk برای هر کوئری در Q=(q1,q2,…,qn) است . به عبارت دیگر ، دو ویژگی زمانی شبیه به هم در نظر گرفته می شوند که اگر با یک کوئری بتوان هر دوی آنها را دید . این موضوع را با AU به وسیله Aij=1 و Aik=1 به طور همزمان برای ویژگی j و k که به وسیله کوئری i دیده شده است می باشد و با در نظر گیری تمایلات ویژگی های Ai و Aj به عنوان aff(Ai,Aj) صورت می پذیرد ، تعداد تکرار دسترسی به کوئری K بر سایت I را به شکل Freq1(qk) نشان می دهیم ، و دسترسی به اجرای کوئری K بر سایت I را به شکل acc1(qk) نشان می دهیم.

الگوریتم

الگوریتم 1 با هزینه ارتباطی بین شبکه سایت ها ، ماتریس QA ، ماتریس AU ، و ویژگی هایی که به عنوان ورودی به حساب می آیند کار می کند و درختی از ویژگی های خوشه شده به همراه تخصیص آنها به سایت ها را تولید می کند. این الگوریتم به شکل سلسله مراتبی کار می کند و به تدریج یک درخت خوشه ای ایجاد می کند . در هر بار تکرار آن دو مجموعه از ویژگی ها تولید می شود . مجموعه ای بزرگتر از ویژگی های مشابه که ما آن را به عنوان تکرار خوشه ورودی (IIC) می نامیم به عنوان ورودی برای تکرار بعدی مورد استفاده قرار می گیرد . سایر مجموعه های کوچک را با نام خوشه های برگ می شناسیم (LC) زیرا جداسازی شده است و به عنوان گره های برگ در درخت قرار می گیرند . در مرحله اول DM به وسیله ماتریس بهینه سازی هزینه های ارتباطاتی با استفاده از کار وایتن و همکارانش [25] صورت می پذیرد . سپس MQA به وسیله ضربت QA در ماتریس DM تولید می شود . قدم بعدی مقدار دهی اولیه IIC به وسیله ماتریس AU است . این الگوریتم با تکرار الگوریتم BEA اصلاح شده ادامه پیدا می کند ، که بعدا توضیح داده خواهد شد ، تا زمانی که ویژگی هایی که در IIC شمارش می شود برابر با 3 باشد . از آنجایی که هر تکرار دارای بیشترین شباهت باشد در یک گروه IIC قرار می گیرد ، ما فرض می کنیم پس از این تعداد تکرار ، IIC نتیجه شده شامل بیشترین ویژگی های مشابه از تمامی موارد است به همین دلیل نیازی نیست که از این بیشتر برویم . سپس ، هزینه ذخیره سازی برای هر ویژگی در هر سایت مورد محاسبه قرار می گیرد و در نهایت بر اساس این هزینه ها ، هر خوشه از ویژگی ها به مناسب ترین سایت تخصیص پیدا می کند. آخرین IIC به تمامی سایت ها تخصیص پیدا کرده است.

مورد مطالعاتی

برای تخمین میزان بهبودی و دقت الگوریتم ما ، ما هم BEA کلاسیک و هم الگوریتم خودمان را بر روی پایگاه داده ای از سیستم مدیریتی ترمینال (TMS) اعمال کردیم . TMS یک سروری است که به فروشگاه ها (یا سوپرمارکت ها) متصل شده است ، این ترمینال دارای شماره سریال منحصر به فردی است . بستگی به نوع ترمینال، اطلاعات ترمینالی یا اطلاعات سیستم عامل را می توان دانلود یا به روز رسانی کرد . از آنجایی که این فروشگاه ها در سایت های مختلفی واقع شده است ، TMS مسلما با پایگاه داده های توزیع شده بهتر می تواند عمل کند . هر ترمینال دارای یک شماره سریال منحصر به فرد است ، یکی از وظایف تعریف این شماره برای هر گروه ترمینال است . این وظایف شامل یک یا تعداد بیشتری از فایل ها است که می توانند همراه یک گروه پایانه باشند . هر ترمینال ، شامل گروهی از ترمینال و وظیفه است که دارای یک جدول است . یک نمای نمونه از جداول و روابط آنها در شکل 4 به تصویر کشیده شده است . پس از بررسی تراکنش ها ، هشت مورد از رایج ترین تراکنش ها و روابط آنها در TMS در نظر گرفته شده است ، 8 ویژگی (در جدول 2 به تصور کشیده شده است) برای توزیع در هفت سایت انتخاب شده است .

جمع بندی

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

برای کارهای آینده می توان به بهینه سازی تابع هزینه برای تخصیص داده و با در نظر گیری بازیابی و بروزرسانی های مکرر برای هر ویژگی و اعمال روشی بهتر جهت محاسبه وزن هایی برای اندازه گیری شباهت ها است .

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