تعداد تراکنش‌های وارد شونده به سیستم

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

پیاده‌سازی در مقیاس کوچک

(Hedayati, Kamali, Shakerian and Rahmani, 2010)

اندازه هر تراکنش (تعداد دستورات هر تراکنش)

الگوریتم مرتب‌سازی زمان‌مهر پایه‌ای

مدل‌سازی توسط مدل مارکف

(Singhal, 1991) و
(روحانی رانکوهی، ۱۳۸۶)

تعداد داده‌های مشترک و غیر مشترک تراکنش‌ها

یک مکانیزم بر اساس قفل دو مرحله‌ای

پیاده‌سازی در مقیاس کوچک

(Al-Jumah, Hossam, and El-Sharkawi, 2000)

تعداد داده‌های مشترک در تراکنش‌هایی بدون داده غیر مشترک

یک مکانیزم بر اساس قفل دو مرحله‌ای

پیاده‌سازی در مقیاس کوچک

(Al-Jumah, et al., 2000)

در هنگام مدل‌سازی یک مطالعه موردی ساده به عنوان مثال برای درک بهتر ارائه گردیده است. مثال ذکر شده شامل سه تراکنش و دو منبع است.
مدل‌سازی‌ها با بهره گرفتن از پتری رنگی و نرم‌افزار CPN Tools ارائه شده‌اند. در نهایت به ارزیابی هر سه الگوریتم پرداخته شده است و الگوریتم‌ها با معیارهای بیان شده در فوق مورد بررسی قرار داده شده‌اند. آزمایش‌ها چندین بار تکرار گردیده و از مقادیر میانگین‌گیری به عمل آمده است. نمودارهای لازم نیز جهت مقایسه‌ی آسان‌تر ترسیم و بررسی گردیده‌اند.
ساختار پایان‌نامه
این پایان‌نامه به فرم زیر سازماندهی شده است.
در فصل دوم پیشینه‌ تحقیق و مطالب مرتبط آورده شده است. در این فصل یک مرور کلی بر کلیات مطلب، اهداف، پیشینه‌ تحقیق و سایر کارهای انجام شده در این زمینه خواهیم داشت. در پیشینه تحقیق، می‌پردازیم به این که تا کنون چه الگوریتم‌هایی ارائه شده، ارزیابی از طریق چه روش‌هایی صورت گرفته است و مانند آن‌ها. همچنین تعدادی از پارامترها و معیارهای ارزیابی الگوریتم‌های کنترل همروندی را بررسی خواهیم نمود. علاوه بر آن بعضی روش‌های پیاده‌سازی و شبیه‌سازی‌ موجود مانند پیاده‌سازی در مقیاس کوچک، شبیه‌سازی از طریق مدل مارکف، شبیه‌سازی از طریق شبکه‌های پتری و مانند آن‌ها را بررسی می‌کنیم و به مزایا و معایب آن‌ها اشاره‌ای خواهیم داشت. همچنین روش تجزیه و تحلیل از طریق صف نیز بطور مختصر مورد بررسی قرار می‌گیرد.
در فصل سوم انواع الگوریتم‌های کنترل همروندی پایه‌ای موجود را بررسی خواهیم کرد. در این میان تعدادی از الگوریتم‌های کنترل همروندی مانند پروتکل قفل ۲PL که احتمال بن‌بست در آن وجود دارد و تکنیک‌های WW و WD که تکنیک‌های پیش‌گیری از بن‌بست هستند را مورد مطالعه قرار می‌دهیم. مزایا و معایب هر یک از این الگوریتم‌های کنترل همروندی پایه‌ای را نیز تا حدودی بررسی خواهیم نمود.
در فصل چهارم نیز به بررسی شبکه‌های پتری، مخصوصاً شبکه‌های پتری رنگی که یکی از ابزارهای بسیار مفید برای شبیه‌سازی الگوریتم‌های کنترل همروندی هستند، پرداخته می‌شود.
در فصل پنجم نحوه‌ی مدل‌سازی الگوریتم‌های مورد نظر با بهره گرفتن از شبکه‎های پتری بیان شده است؛ که شامل تعریف مجموعه‌های رنگ، نشانه‌گذاری‌های اولیه، متغیرهای موجود در مدل، شرح عملکرد توابع مدل و تعیین اولویت برای فایر^[۷] شدن گذار مورد نظر از بین گذارهای فعال می‌باشد.
در فصل ششم که همان بخش پایانی است مدل‌ها بر اساس پارامترهای متفاوت بررسی و با هم مقایسه شده‌اند. آزمایش‌های مورد نیاز صورت گرفته و هرکدام چندین بار تکرار گردیده‌اند. نتایج میانگین‌گیری شده و نمودارهای لازم جهت مقایسه ترسیم شده‌اند. در نهایت نیز نتیجه‌گیری کلی از مباحث بیان شده مشاهده می‌شود و پیشنهاداتی برای کارهای آینده ارائه خواهد شد.
فصل دوم
پیشینه‌ تحقیق
مقدمه
در این فصل پیشینه‌ تحقیق و مطالب مرتبط آورده شده است. یک مرور کلی بر کلیات مطلب، اهداف، پیشینه‌ تحقیق و سایر کارهای انجام شده در این زمینه خواهیم داشت. ابتدا اهمیت الگوریتم‌های کنترل همروندی پایگاه داده‌ها، از دید سایر تحقیقات انجام شده تا کنون بررسی می‌شود. سپس بعضی از انواع پایگاه داده‌هایی که در تحقیقات گذشته بیشتر مورد بررسی قرار گرفته بوده‌اند و نام آن‌ها در این فصل ذکر شده، تعریف و بررسی گردیده‌اند. علاوه بر آن بعضی روش‌های پیاده‌سازی و شبیه‌سازی‌ موجود مانند پیاده‌سازی در مقیاس کوچک، شبیه‌سازی از طریق مدل مارکف، شبیه‌سازی از طریق شبکه‌های پتری و مانند آن‌ها نیز بررسی شده و به مزایا و معایب آن‌ها اشاره‌ای شده است. همچنین روش تجزیه و تحلیل از طریق صف نیز بطور مختصر مورد بررسی قرار می‌گیرد. علاوه بر آن تعدادی از پارامترها و معیارهای ارزیابی الگوریتم‌های کنترل همروندی و آزمایش‌هایی که تا کنون صورت گرفته‌اند مورد مطالعه قرار گرفته است. در نهایت نیز برخی از مزایا و معایب روش‌های مدل‌سازی توضیح داده می‌شوند.
اهمیت الگوریتم‌های کنترل همروندی پایگاه داده‌ها
مدت زمان زیادی است که حفظ ثبات و سازگاری داده‌های به اشتراک گذاشته شده در سیستم پایگاه داده‌ها‌، مورد مطالعه قرار گرفته است (Shu, and Young, 2002). مطالعاتی که در زمینه‌ی ارزیابی الگوریتم‌های کنترل همروندی پایگاه داده‌ها صورت می‌گیرند، نه تنها در پایگاه داده‌های معمولی و پایگاه داده‌های بلادرنگ^[۸]، بلکه در سیستم پایگاه داده‌ی توزیع شده‌، پایگاه داده مبتنی بر وب، سیستم‌های بلادرنگ سخت^[۹] و مانند آن‌ها نیز کاربردهای اساسی دارند. نشان داده شده است که الگوریتم‌های قفل متمرکز و توزیع شده در اغلب مواقع، رفتارهایی مشابه در مواجه شدن با سیستم، مدل و مفروضات مشخص شده‌ انجام می‌دهند (Sarkar, and Nabendu, 2009). همچنین در (Shu, and Young, 2002) پروتکل کنترل همروندی چند نسخه‌ای به گونه‌ای بیان شده است که برای سیستم پایگاه داده متمرکز و توزیع شده مشابه است. تنها برخی موارد جزیی باید در یک محیط توزیع شده، به صورت اضافه‌تر از حالت متمرکز در نظر گرفته شوند. این موارد شامل افزودن تعدادی فیلد محدود است. این فیلدها شامل تخصیص ورژن داده، اطمینان از تثبیت^[۱۰] شدن و تجزیه‌ناپذیری^[۱۱] است.
برخی از انواع پایگاه داده‌ها
در اینجا لازم است به تعریف جزیی برخی از پایگاه داده‌های نام برده شده در این بخش بپردازیم.
الف) پایگاه داده‌ی بلادرنگ: همان پایگاه داده‌ی معمولی است که رخدادها و دستورات در همان لحظه پردازش می‌شوند.
ب) پایگاه داده‌ی توزیع شده‌: در طول سال‌های اخیر، توزیع شدگی به عنوان یک مسئله‌ی مهم برای پایگاه داده‌ها مورد بررسی قرار گرفته است (Ozsu, 1985). این مسئله دلایل منطقی بسیاری مانند توزیع طبیعی سازمان‌ها دارد. پایگاه داده توزیع شده مجموعه‌ای از قطعات مختلف است. به بیان دیگر بیش از یک شبکه از کامپیوترهای متصل، با یکدیگر ارتباط منطقی دارند. در یک پایگاه داده توزیع شده، مجموعه‌ای از داده‌ها می‌توانند در سراسر چندین مکان فیزیکی توزیع شوند. از آنجا که این پایگاه داده به صورت توزیع شده است، کاربران مختلف می‌توانند بدون تداخل با یکدیگر، به آن دسترسی داشته باشند. اهمیت ارزیابی الگوریتم‌های پایه‌ای کنترل همروندی پایگاه داده‌ها در جایی مشخص می‌شود که سیستم مدیریت پایگاه داده‌ها (DBMS)^[12] باید همروندی را در پایگاه داده‌ها برقرار کند و به صورت دوره‌ای پایگاه داده‌های پراکنده را همگام‌سازی کند تا مطمئن شود که همه آن‌ها دارای داده‌های سازگار هستند (Mousavi, Naji, and Ebrahimi, 2013). سیستم‌های پایگاه داده توزیع شده (DDBS)^[13] در سال‌های اخیر مورد توجه بیشتری قرار گرفته اند. به نظر می‌رسد که این زمینه برای برخی از کارهای تجزیه و تحلیل و مقایسه‌ای آماده است (Sarkar, and Nabendu, 2009) و (Ozsu, 1985).
ج) پایگاه داده مبتنی بر وب: سیستم پایگاه داده‌ی مبتنی بر وب سیستمی است که هم ویژگی‌های پایگاه داده‌ی توزیع شده و هم ویژگی‌های پایگاه داده‌ی بلادرنگ را دارد. البته، مشکلات کنترل همروندی در پایگاه داده‌ی مبتنی بر وب، پیچیده‌تر و دشوارتر از پایگاه داده‌های توزیع شده معمولی می‌باشد (Han, Jiang, and Luo, 2004).