گراف تقدم
یک گراف تقدم که به نام گراف مغایرت و گراف توالی پذیر شناخته میشود، در زمینه کنترل همزمانی در پایگاه داده مورد استفاده قرار میگیرد.
گراف تقدم برای برنامه S شامل:
- یک گره برای هر یال جهت دار در S
- یک قوس از Tj به Ti اگر یک عمل از Tمن قبل و درگیری با یکی از Tj's اقدامات است.
مثالهای گراف تقدم ویرایش
مثال ۱ ویرایش
مثال ۲ ویرایش
گراف تقدم برنامه D با ۳ یال وجود دارد. به عنوان یک چرخه (۲ یال؛ با دو جهت متفاوت) از راس T1 و T2 است. رقابتی سریالی نیست. توجه کنید که یالهای جهت دار به این دو راس به معنی ایجاد یک گراف تقدم نیست.
امتحان توالی پذیری با گراف تقدم ویرایش
الگوریتم برای تست توالی پذیری برنامه S همراه با یک برنامه مثال.
- یا
- برای هر راس Tx موجود در برنامه S ایجاد یک گره برچسب Ti در گراف تقدم؛ بنابراین گراف تقدم شامل T1T2T3.
- برای هر مورد در S که در آن Tj اجرا میشود آیتم (x)رامی خواند پس از اجرای Ti آیتم (x) را مینویسد ایجاد یک لبه (Ti → Tj) در گراف تقدم. ایناتفاقدر مثال بالا به هیچ عنوان خوانده شدن پس از نوشتن انجام نمیشود.
- برای هر مورد در S که در آن Tj نوشتن آیتم (x) را پس از آنکه Ti اجرا میشود خواندن آیتم(x) را اجرا میکند یال (Ti → Tj) در گراف تقدم. این نتایج در یک گراف جهت دار از T1 به T2 (به عنوان T1 دارای (R(A میباشد پیش از آنکه (T2 W(A را داشته باشد).
- برای هر مورد در S که در آن Tj نوشتن آیتم (x) را پس از آنکه Ti اجرا میشود خواندن آیتم(x) را اجرا میکند یال (Ti → Tj) در گراف تقدم. این نتایج در گراف جهت دار T2 T1T2 T3 و T1 T3.
- برنامه S توالی پذیر است اگر و تنها اگر گراف تقدم هیچ چرخه ای نداشته باشد. همانظور که T1 و T2 یک چرخه را مانند مثال بالا تشکیل میدهند نباشد.
پیوند به بیرون ویرایش
- اصول سیستمهای پایگاه داده، 5th Edition, استفاده از اولویت نمودار مورد بحث قرار گرفتهاست در فصل ۱۷ به عنوان آنها مربوط به آزمون برای درگیری serializability.
- Abraham Silberschatz, هنری Korth و S. Sudarshan. 2005. پایگاه داده سیستم مفاهیم (5 ed.), PP. 628–630. McGraw-Hill, Inc. , نیویورک، نیویورک، ایالات متحده است.
- ترجمه شده توسط مصطفی صفائی.