افزایش كارایی پرس و جوهای پایگاه داده تحلیلی با نگاشت مكعب مفهومی به فضای دوبعدی

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

مکعب داده

پایگاه داده تحلیلی

پردازش تحلیلی برخط

مدل داده‌ی چند بعدی

 
 
 
1- مقدمه
پایگاه داده‌ی تحلیلی، ابزاری برای پشتیبانی تصمیم است كه از منابع داده‌ی سازمان‌ها و ارگان‌های متفاوت تهیه می‌شود. این پایگاه داده بستر مناسبی فراهم می‌آورد كه داده‌های بایگانی شده در پایگاه‌های داده‌ی عملیاتی، به صورت مجتمع و سازمان یافته درآیند و برای استخراج دانش مناسب باشند. تعریف ارائه شده توسط اینمون (Inmon) برای پایگاه داده تحلیلی به صورت زیر است: "پایگاه داده تحلیلی، یك مجموعه موضوع-گرا، یكپارچه، متكی بر بازه‌های زمانی متفاوت (متغیر با زمان) ، و تغییرناپذیر از داده‌ها است كه برای پشتیبانی مدیریت پردازش تصمیم‌گیری (تصمیم‌یاری) به كار می‌رود."[12]
 
پایگاه‌های داده تحلیلی با توجه به اینکه اطلاعات مجتمع شده از چندین پایگاه داده عملیاتی را در خود دارند  شامل حجم عظیمی از داده هستند. این مساله سبب بروز مشکلاتی در نگهداری و به کارگیری پایگاه‌های مزبور می‌شود. برای اینکه بتوان به صورت کارا به پرس‌وجوهایی که از پایگاه داده تحلیلی می‌شود پاسخ داد، باید از روشهایی کارا برای دستیابی به داده و پردازش پرس‌وجو استفاده کرد. به این منظور الگوریتم‌های فراوانی ارائه شده‌اند که هدف آنها انجام پرس و جوها به نحوی است که زمان لازم برای پاسخگویی کمینه باشد و در عین حال فضای حافظه مورد نیاز برای انجام پردازش ها بهینه و یا دست کم قابل قبول باشد.
 
پایگاه های داده تحلیلی را می توان از دیدگاه مفهومی به صورت مجموعه ای چند بعدی از داده ها دید. این دیدگاه چند بعدی را مکعب داده می نامند. مكعب داده در [6] ارائه شده و برخی از ویژگی‌های مفید محاسبه مكعب بیان شده است. منظور از محاسبه مکعب داده، پاسخگویی به پرس و جوهای تحلیلی است که از پایگاه داده تحلیلی متناظر با آن می شود.  چون این پرس وجوها تحلیلی هستند و به بررسی داده ها در بعد کلان می پردازند، نیاز به مجموع سازی داده ها در ابعاد مختلف مکعب دارند.سه نوع تابع برای انجام عملیات مجموع‌سازی تعریف می‌شوند [1]. مجموعه‌ای مانند T از چندگانه‌ها (ركوردها) را در نظر بگیرید. فرض كنید كه مجموعه‌ی  یك مجموعه‌ی كامل از زیر مجموعه‌های جدا از هم T باشد یعنی  و . 
 
• تابع مجموع‌ساز F، تابع توزیعی خوانده می‌شود اگر تابعی مانند G وجود داشته باشد طوریكه  . توابع SUM، MIN، و MAX همگی توابعی توزیعی هستند كه در آنها G=F است. تابع COUNT نیز یك تابع توزیعی است كه در آن G=SUM است.
• تابع مجموع‌ساز F جبری است اگر تابع M-مقداری G و تابع H موجود باشند طوریكه   كه در آن مقدار M برخلاف مقادیر |T| و n ثابت است. همه‌ی تابع‌های توزیعی توابعی جبری نیز هستند. علاوه بر آنها توابعی نظیر میانگین، انحراف معیار استاندارد، MaxN و MinN نیز توابعی جبری هستند. به عنوان مثال، در تابع میانگین (Average)، تابع G مقادیر SUM و COUNT را به دست می‌آورد و تابع H نتایج به دست آمده از تابع G را بر هم تقسیم می‌نماید.
• یك تابع مجموع‌ساز نظیر F را هولیستیك می‌نامند اگر جبری نباشد. برای مثال توابع میانه (Median) و رتبه (Rank) نمونه‌ای از توابع هولیستیك هستند. 
 
 
فهرست مطالب
افزایش كارایی پرس و جوهای پایگاه داده تحلیلی با نگاشت مكعب مفهومی به فضای دوبعدی 1
چكیده 1
كلید واژه 1
1- مقدمه 2
2- پرس و جوهای آستانه ای 3
3- الگوریتم  Ex-Cube 5
3-1- تعاریف و نمادها 5
3-2- ساختار ابرگراف 6
3-3- ذخیره سازی دوبعدی Ex-Graph 6
3-4- فضای لازم برای ذخیره سازی Ex-Graph 7
4- شبیه‌سازی و نتایج به دست آمده 8
4-1- تاثیر افزایش حجم پایگاه داده بر روی شمای ثابت بر سرعت محاسبات 8
4-2- تغییرات زمان با افزایش کاردینالیتی ابعاد 8
4-3- افزایش تعداد ابعاد 8
4-4- افزایش تعداد ابعاد 9
5- نتیجه 9
مراجع 9
 
 
 OLAP
Data Cube
Data Warehouse
On-Line Analytical Processing
Multi-dimensional Data Model