انجام پایان نامه

درخواست همکاری انجام پایان نامه  بانک مقالات رایگان انجام پایان نامه

سفارش پایان نامه

|

انجام پایان نامه ارشد

 پایان نامه 

پایان نامه‏ کامپیوتر

انجام پایان نامه‏ ارشد کامپیوتر

مقدمه
در اواسط دهه 1980، با نزول قيمت DRAM، اين ايده مطرح شد که کامپيوترهاي آتي با داشتن حافظه اصلي با ظرفيت بالا، مي توانند بسياري از پايگاه داده ها را درحافظه اصلي داشته باشند. در اين شرايط مي توان همه I/O ها (که بسيار هزينه بر مي باشند) را از پردازش DBMS حذف نمود. بنابراين معماري DBMS دستخوش تغييرات جدي مي شود و در يک MAIN MEMORY DBMS(MMDBMS)، مديريت I/O ديگر نقشي نخواهد داشت.
نکته مهم در يک MMDB، چگونگي انجام تراکنشها و recovery بصورت کارا است. برخي از الگوريتمهاي پيشنهادي براساس اين فرض عمل مي کنند که قسمت کوچکي از حافظه اصلي بصورت ماندگار وجود دارد که اطلاعاتش توسط باطري در صورت قطع برق از بين نخواهد رفت. اين قسمت از حافظه اصلي براي نگهداري redo log ها استفاده مي شود.
تعداد ديگري از الگوريتمهاي پيشنهادي پيش فرض حافظه ماندگار را ندارند و همچنان از عمليات I/O براي نوشتن اطلاعات تراکنش در حافظه ماندگار استفاده مي کنند. بنابراين در اين الگوريتمها عمليات I/O بطور کامل حذف نمي شود، بلکه تعدادشان بسيار کمتر مي شود زيرا  I/Oمربوط به نوشتن اطلاعات صفحات buffer ها، حذف خواهد شد.
در يک MMDBMS، ساختارداده هاي ساده مانند T-Tree و همچنين bucket-chained hash جايگزين ساختارداده هايي چون B-Tree و linear hash در DBMS هاي مبتني بر ديسک مي شوند. بنابراين سرعت اجراي پرس و جو(پرس و جو) و بهنگام سازي بسيار افزايش مي يابد و هزينه index lookup و نگهداري ،فقط مربوط به  پردازنده و دسترسي به حافظه اصلي خواهد شد.
يکي از مشکلات اصلي در MMDBMS ها بهينه کردن درخواستهاست. عدم وجود I/O به عنوان فاکتور اصلي در هزينه ها به معناي پيچيدگي بيشتر مدل کردن هزينه در يک MMDBMS است زيرا در اينجا يکسري فاکتورهاي فازي از قبيل هزينه اجراي  پردازنده ، بايد در نظر گرفته شوند. در اين حالت بايد با استفاده از تعامل روش coding، عوامل سخت افزاري مانند  پردازنده و معماري حافظه و پارامترهاي پرس و جو، به يک مدل قابل اطمينان از هزينه اجرا در حافظه اصلي رسيد.
در دهه 1990، MMDBMS ها با افزايش سايز ديسکها و سايز مسائل همراه با افزايش ظرفيت DRAM ها، به اوج محبوبيت خود رسيدند. MMDBMS ها اغلب براي برنامه هايي که به پايگاه داده Real Time نياز دارند (مانند سيستمهاي embedded سوئيجهاي تلفن) ، استفاده مي شود. از آنجايط که سايز حافظه اصلي در کامپيوترها روز به روز در حال افزايش است، اين اميد وجود دارد که براي بسياري از پايگاه داده هايي که امروزه امکان قرارگفتن آنها بصورت کامل در حافظه اصلي وجود ندارد، اين شرايط مهيا شود.



مدلهاي هزينه حافظه اصلي
متاسفانه تا کنون تلاشهاي اندکي جهت مدل کردن هزينه کارايي MMDBMSها صورت گرفته است. تحقيقات اوليه روي طراحي ماشينهاي پايگاه داده ها، بيشتر در زمينه وابستگيهاي ميان الگوريتمها و دسترسي حافظه صورت مي گرفت.در صورتيکه امروزه به دليل محدود شدن استفاده از MMDBMS ها به کاربرد در پايگاه داده هاي Real Time(به صورت پرس وجوهاي ساده، مانند يک hash lookup در يک جدول)، اينگونه تحقيقات از اهميت کمتري برخوردارند.
در تحقيقات اخير در زمينه MMDBMS ها دو نمونه تحقيقاتي Office-By-Example (OBE) مربوط به شرکت IBM و Smallbase مربوط به شرکت HP مسائل ارزشمندي را درمورد بهينه سازي پرس وجو ها و مدلسازي هزينه حافظه اصلي مطرح کرده اند که در ادامه به بررسي اين دو نمونه مي پردازيم.

Office-By-Example (OBE)
OBE يک پايگاه داده در حافظه اصلي است که بسياري از مفاهيمQuery-by-example(QBE)، را گسترش مي دهد. براي بهينه سازي پرس و جو، مبتني بر هزينه، OBE يک مدل کامل از هزينه را ارائه مي دهد. باتوجه به اين پيش فرض که داده هايي که پردازش مي شوند در حافظه اصلي قرار گرفته اند، عامل اصلي هزينه در پايگاه داده هاي متداول که همان دسترسي I/O است حذف خواهد شد.
در اين صورت هزينه محاسبات  پردازنده از اهميت بالايي برخوردار خواهد شد. اين در حاليست که مدلسازي هزينه  پردازنده بسياردشوار است و پارامترهاي زيادي از قبيل طراحي نرم افزار، معماري سخت افزار و حتي روش برنامه نويسي، در مدلسازي هزينه  پردازنده دخيل هستند. بعلاوه تحليل دقيق سيستمهاي بزرگ به منظور شمارش تعداد سيکلهاي  پردازنده غير ممکن مي باشد.
راه حل پيشنهادي، استفاده از روشهاي تجربي و روشهاي تحليلي در کنار يکديگر است.
در ابتدا، bottleneck هاي سيستم با استفاده از يک تحليلگرِ اجرا شناسايي مي شوند. در اين روش تنها bottleneck ها، براي مدلسازي هزينه پردازنده بکار مي روند.
البته در اين مرحله، بسيار مهم است که bottleneck ها تا حد ممکن توسط تلاشهاي معقول اصلاح شوند.
مرحله بعد پيدا کردن وزن نسبي هريک از bottleneck ها و مشخص سازي واحد هزينه آنها توسط روشهاي تجربي است.
براي OBE، bottleneck ها و واحدهاي هزينه بصورت زير مشخص مي شوند :
•    ارزيابي expression هايي که در predicate ها آمده اند. (واحد هزينه = C1)
•    عمليات قياسي که براي مشخص کردن خروجي نهايي predicate ها لازم است. (واحد هزينه = C2)
•    بازيابي يک tuple از يک رابطه موجود در حافظه اصلي. (واحد هزينه = C3)
•    واحد عملياتِ ساختن شاخص (index) ( ساختن شاخص روي رابطه اي که n تا tuple دارد، nLog2n برابر واحد هزينه دارد. واحد هزينه = C4)
•    واحد عمليات در مرتب سازي ،که در شرايط شاخصهاي چند ستوني(multi-column index) مورد نياز است. (واحد هزينه = C5)
جالبترين نتيجه بدست آمده از آزمايشات اين است که، هزينه ارزيابي expression هاي سيستم، بيشترين هزينه از ميان هزينه هاي مطرح شده در OBE مي باشد.در حاليکه C2 تا C5 تقريبا يکسان مي باشند، C1 به ميزان قابل توجهي بيشتر از آنهامي باشد.
در ادامه به بررسي نمونه Smallbase مي پردازيم.


Smallbase
در smallbase، مدل هزينه حافظه اصلي به سه گروه تقسيم مي شود:
1.     Hardware-based  
اين مدل بسيار شبيه مدل هزينه مبتني بر I/O در پايگاه داده هاي متداول است. به جاي شمارش عمليات I/O،  تعداد سيکلهاي پردازنده شمارش مي شود. عليرغم اينکه اين روش بسيار ساده به نظر مي رسد، از جهت پياده سازي مشکلات عمده اي وجود دارد.بعلاوه، portability بسيار محدود خواهد شد زيرا اين سياستها ميان معماريهاي سخت افزار، متفاوت است. در هر حال اين مدل بسيار دقيق و قابل لطمينان مي باشد.

2.     Application-based
در اين روش هزينه ها بر اساس هزينه bottleneck هاي سيستم بيان مي شود.عليرغم اينکه اين روش از جهت پياده سازي بسيار ساده تر از روش hardware-based است، اين نوع مدل از عموميت کمتري برخوردار است.
Bottleneck ها بسيار وابسته به workload ِمورد استفاده براي شناسايي آنها، دارد و بنابراين نمي توان از اين روش براي نمايش هزينه هاي همه انواع پرس و جو استفاده کرد.
در اصل،اين مدل نسبت به مدل hardware-based از portability بالاتري (توسط توليد دوباره پروفيل) برخوردار است. به هر حال، اين روش نه تنها باعث تفاوت در واحدهاي هزينه مي شود بلکه مجموعه bottleneck ها هم متفاوت خواهد شد.در اين حالت اگر مدل، دستخوش تغييرات شود، هزينه توابعِ هزينه مربوط به عمليات پايگاه داده، بايد دوباره بر اساس bottleneck هاي جديد فرمولسازي شود.

3.     Engine-based
اين مدل هزينه، مابين مدل hardware-based - که دقيق و پيچيده است- و مدل application-based -که عليرغم سادگي از عموميت کمتري برخوردار است-، قرار دارد. اين مدل بر اساس هزينه عمليات ابتدايي که موتور اجرايي MMDBMS تامين مي کند، عمل مي کند.
در يک پروسه دو مرحله اي اين مدل توضيح داده مي شود:
در اين مدل عمومي ابتدا عوامل اصلي هزينه شناخته مي شوند و هزينه پردازش پرس و جو بر اساس عوامل شناخته شده بيان مي گردد. سپس مدل با مشخص کردن مقادير مربوط به اين عوامل، مقداردهي اوليه شده و سپس ارزيابي مي شود.
مرحله اول نياز به اطلاعات کامل در مورد اجزاي داخلي موتور اجرايي دارد و عموماً توسط دست انجام مي شود. در مورد اينکه مدل تا چه حد بايد جزئي و دقيق باشد، اين پاسخ مطرح مي شود که مدل بايد تا آنجايي که به feasibility سيستم خدشه اي وارد نشود، بصورت جزئي مدل شود. يکسري ساده سازيها و بهبود و دوباره نگري در طي مرحله ارزيابي قابل انجام است.
براي سيستم smallbase ، هزينه هاي ابتدايي زيرشناسايي شده اند :
•    Fetch کردن يک ستون ويا مقدار يک پارامتر
•    انجام عمليات رياضي و منطقي
•    اجراي يک عمل مقايسه
•    اجراي  expression  ايي که  like  داشته باشد
•    scan کردن جدول، T-tree index، hash index، جدول موقت
•    ساخت و از بين بردن T-tree index، hash index، جدول موقت
•    مرتب سازي tuple ها
•    انتخاب tuple هاي مشخص
•    انجام عمل join (nested loop join، merge join)
به وابستگيهاي هزينه به فاکتورهايي از قبيل سايز جداول، نوع داده ها و ... در مرحله دوم پرداخته مي شود.
در مرحله دوم يک برنامه تست ،وظيفه مقداردهي اوليه و ارزيابي مدل را بصورت اتوماتيک برعهده دارد. براي هر واحد هزينه دو پرس و جو که هزينه اجرايشان، فقط در آن مقدار متفاوت باشد، در نظر گرفته مي شود. بعلاوه فرمولهايي که وابستگي هر واحد هزينه را به سايز جدولها نشان مي دهند، بايد مشخص شوند.
برنامه تست هزينه سپس پارامترهاي مربوطه و ارزيابي مدل را با اجراي هر زوج پرس و جو به تعداد مکرر با سايزهاي متفاوت جداول انجام مي دهد.   

ساختارهاي شاخص در حافظه اصلي
ساختارهاي شاخصِ طراحي شده براي حافظه اصلي، متفاوت از طراحي هاي رايج براي سيتم هاي مبتني بر ديسک مي باشند.اهداف اصلي در طراحي يک شاخص مبتني برديسک عبارتند از : به حداقل رساندن تعداد دستيابي ها به ديسک و به حداقل رساندن فضاي ديسک.در حالي که يک شاخص مبتني بر حافظه اصلي ،در حافظه اصلي قرار گرفته واصلا دستيابي به ديسک وجود ندارد که حداقل شود از اين رو، هدف اصلي از طراحي يک ساختار شاخص مبتني بر حافظه اصلي ،کاهش زمان کلي محاسبات و در عين حال ، به کار گيري حداقل حافظه ممکن مي باشد.
در يک پايگاه داده مبتني بر حافظه اصلي، رابطه ها در حافظه قرار مي گيرند،بنابراين،نيازي نخواهد بود که شاخص، مقادير واقي صفات را ذخيره کند، در عوض مي توان از اشاره گر هايي به tupleها استقاده نمود و با استفاده از اين اشاره گرها ، مقادير واقعي صفات را در هنگام لازم ، بازيابي نمود.
چنين روشي جندين مزيت دارد:
    با استقاده از اشاره گرِ tuple،شاخص، هم به مقادير صفات آن tuple دسترسي دارد و هم به خود tuple ،بنابراين اندازه شاخص کاهش مي يابد.








انجام پایان نامه

انجام پایان نامه کامپیوتر، انجام پایان نامه ارشد کامپیوتر، انجام پایان نامه، پایان نامه

برای دیدن ادامه مطلب از لینک زیر استفاده نمایید

  دانلود مقاله | انجام پایان نامه

سفارش پایان نامه