خلاصه درس پایگاه داده پیشرفته – دکتر شیری ۹۳/۰۲/۲۹

خلاصه درس پایگاه داده پیشرفته – دکتر شیری ۹۳/۰۲/۲۹
انواع بن بست
بن بست حالتی است که دو یا بیش از دو تراکنش هر کدام منتظر پایان دیگریست

دو راه حل برای بن بست وجود دارد
۱- روشهای کشف بن بست
۲- روشهای جلوگیری از بن بست

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

۲- استفاده از مهر زمانی برای حل مشکل بن بست

مهر زمانی مقدار منحصر به فردی است که سیستم برای هر تراکنش در نظر می گیرد که می تواند ترکیبی از ID و زمان شروع تراکنش باشد

هر زمانی تراکنش Ti را با Ts(Ti) نشان می دهیم

دو الگوریتم در این رابطه مطرح می کنیم

۱- الگوریتم منتظر گذاشتن و پس راندن :
اگر Ts(Ti)<Ts(Tj) و Ti خواهان قفل کردن داده ای Tj ۀنرا قفل کرده و منتظر می ماند که کار Tj تمام شود . در غیر اینصورت طرد می شود

 

۲- الگوریتم زخمی کردن و منتظر گذاشتن :
اگر Ts(Ti)<Ts(Tj) و Ti خواهان قفل کردن داده ای است که Tj قفل کرده ، Ti زخمی می شود ( طرد می شود ) و داده از آن گرفته می شود و در اختیار Ti قرار می گیرد . در غیر اینصورت باید منتظر بماند

۳- عدم انتظار :
اگر ترامنشی ، داده مورد نیاز خود را نتواند قفل کند ، بدون درنگ ( بدون انتظار ) طرد می شود

۴- انتظار محتاطانه :
اگر تراکنش Ti خواهان قفل کردن داده ای است که Tj آنرا قفل کرده اگر Tj خود منتظر باز شده قفلی داده ای نباشد Ti منتظر می ماند ، در غیر اینصورت طرد می شود
————————————–
روشهای کشف مشکل بن بست

این روش های خوشبینانه هستند
فرض می کنند بن بست به ندرت رخ میدهد و اجازه می دهند تراکنش ها آزادانه اعمال خود را انجام دهند و اگر احساس کردند که لن بست رخ داده آنرا کشف و برطرف می کنند

۱- مهلت زمانی :
سیستم یک مهلت زمانی تعیین می کند و اگر تراکنش نتوانست در این مهلت زمانی به داده مورد نظر خود را قفل کند ، طرد می شود

۲- بررسی متناوب درخواست های قفل گذاری
در این روش سیستم به منظور کشف بن بست به طور متناوب درخواستهای قفل گذاری تراکنش ها را بررسی می کند
این کار را با رسم گراف انتظار انجام میدهد

گراف انتظار یک گراف جهت دار است که رئوس آن تراکنش ها هستند و یال جهت دار Ti–>Tj در این گراف وجود دارد .
اگر Ti خواهان قفل داده ای باشد که Tj قفل کرده باشد

اگر در این سیکل یا دور وجود داشته باشد یعنی بن بست رخ داده و سیستم باید بن بست را رفع کند (با طرد بعضی از تراکنش ها )

——————————-
سیاست های مختلفی برای طرد تراکنش هست
– تراکنشی که کمترین کار را انجام داده، طرد شود
– تراکنشی که زمان بیشتری تا پایان آن مانده، طرد شود
– تراکنشی که باعت loop شده
– تراکنشی که بیشترین داده را قفل کرده

——————
روش مهر زمانی
برای کنترل همروندی
در این روش غیر از مهر زمانی تراکنش ها که با Ts (T) نشان میدهیم برای هر فقره داده مانند D دو نوع مهر زمانی داریم

مهر زمانی خواندن Ts-r (D) که برابر است با بزرگترین مهر زمانی تراکنش ها مه داده D را خواندن

مهر زمانی نوشتن : Ts-W(D) برابر است با بزرگترین مهر زمانی که تراکنش هایی که داده D را تغییر داده یا نوشته
پروتکل To
۱- در عمل خواندن ، تراکنش Ti دستور R(D) صادر می کند آنگاه

الف ) اگر زمان مهر این تراکنش کوچکتز ار زمان مهر نوشتن داده D بود
Ts(Ti)>Ts-W(D) درخواست رد می شود و تراکنش طرد می شود
ب) در غیر اینصورت درخواست به سایت می شود
Ts-R(D)=Max{Ts-R(D),Ts(Ti){

۲- در عمل نوشتن ترانش Ti دستور W(D) را صادر می کند
در این حالت
الف ) Ts(Ti)<Ts-RD) درخواست رد می شود و تراکنش طرد می شود
ب) اگر Ts(Ti)<Ts-W(D) درخواست رد می شود و تراکنش طرد می شود چون نتیجه از دست رفته رخ میدند
ج) در غیر اینصورت درخواست اجابت می شود و قرار میدهیم

Ts-W(D)=Max {Ts-W(D), Ts(Ti)}
کتاب روحانی رانکوهی جلد دوم سیستم های مدیریت پایگاه داده ، یا حق جو – جلد دوم ، یا دیت – جلد دوم را بخوانید
سوال در این روش کدام یک از مشکلاتی ک مطرح شد رخ می دهد
۱- تضعیف همروندی
۲- طرد تسلسلی
۳- مشکل بن بست
۴- مشکل گرسنگی یا قحطی زدگی

۵- آیا این روش همروندی را تضمین می کند ؟
پروتکل مهر زمانی نوع دوم برای همروندی
یک زمان مهر ساختگی برای تراکنش با کمی اختلاف ایجاد کنیم
در اینصورت ممکن است خیلی از طرد شدن ها برطرف شود مشکل این اختلاف چقدر بگیریم
پروتکل مهر زمانی شدید برای همروندی
در عمل نوشتن دیدیم که اگر Ts(Ti)>Ts-R(D) عمل توشتن اجرا می شود
در این پروتکل این اجازه را وقتی می دهد که تراکنش داده را خوانده به ترتیب برسد