گراف تقدم

یک گراف تقدم که به نام گراف مغایرت و گراف توالی پذیر شناخته می‌شود، در زمینه کنترل همزمانی در پایگاه داده مورد استفاده قرار می‌گیرد.

گراف تقدم برای برنامه S شامل:

• یک گره برای هر یال جهت دار در S
• یک قوس از T_j به Ti اگر یک عمل از T_من قبل و درگیری با یکی از T_j's اقدامات است.

مثال‌های گراف تقدم

مثال ۱

مثال ۱

${\displaystyle }$

مثال ۲

مثال ۲

${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$

گراف تقدم برنامه D با ۳ یال وجود دارد. به عنوان یک چرخه (۲ یال؛ با دو جهت متفاوت) از راس T1 و T2 است. رقابتی سریالی نیست. توجه کنید که یال‌های جهت دار به این دو راس به معنی ایجاد یک گراف تقدم نیست.

امتحان توالی پذیری با گراف تقدم

تست Serializability مثال

الگوریتم برای تست توالی پذیری برنامه S همراه با یک برنامه مثال.

${\displaystyle }$

یا

${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$

1. برای هر راس T_x موجود در برنامه S ایجاد یک گره برچسب Ti در گراف تقدم؛ بنابراین گراف تقدم شامل T₁T₂T₃.
2. برای هر مورد در S که در آن T_j اجرا می‌شود آیتم (x)رامی خواند پس از اجرای Ti آیتم (x) را می‌نویسد ایجاد یک لبه (T_i → T_j) در گراف تقدم. ایناتفاقدر مثال بالا به هیچ عنوان خوانده شدن پس از نوشتن انجام نمی‌شود.
3. برای هر مورد در S که در آن T_j نوشتن آیتم (x) را پس از آنکه Ti اجرا می‌شود خواندن آیتم(x) را اجرا می‌کند یال (T_i → T_j) در گراف تقدم. این نتایج در یک گراف جهت دار از _{T1 به T2 (به عنوان T1 دارای (R(A می‌باشد پیش از آنکه (T2 W(A را داشته باشد)}.
4. برای هر مورد در S که در آن Tj نوشتن آیتم (x) را پس از آنکه Ti اجرا می‌شود خواندن آیتم(x) را اجرا می‌کند یال (Ti → Tj) در گراف تقدم. این نتایج در گراف جهت دار T₂ T₁T₂ T₃ و T₁ T₃.
5. برنامه S توالی پذیر است اگر و تنها اگر گراف تقدم هیچ چرخه ای نداشته باشد. همانظور که T₁ و T₂ یک چرخه را مانند مثال بالا تشکیل می‌دهند نباشد.

پیوند به بیرون

• اصول سیستم‌های پایگاه داده، 5th Edition, استفاده از اولویت نمودار مورد بحث قرار گرفته‌است در فصل ۱۷ به عنوان آنها مربوط به آزمون برای درگیری serializability.
• Abraham Silberschatz, هنری Korth و S. Sudarshan. 2005. پایگاه داده سیستم مفاهیم (5 ed.), PP. 628–630. McGraw-Hill, Inc. , نیویورک، نیویورک، ایالات متحده است.
• ترجمه شده توسط مصطفی صفائی.