بستار تعدی

در ریاضیات بستار تعدی یک رابطه دوتایی R در مجموعه X، کوچکترین رابطه از X، شامل R که متعدی باشد.
برای مثال اگر X یک مجموعه‌ای از فرودگاه‌ها و x R y به معنی "یک پرواز مستقیم از فرودگاه x به فرودگاه y وجود دارد" (برای x و y در X) باشد، سپس بستار تعدی R در X، رابطه R⁺ است به طوری که x R⁺ y به معنی آن است که "ممکن است برای پرواز از x به y یک یا چند پرواز انجام شود". به عبارت دیگر بستار تعدی مجموعه‌ای از تمام نقاطی را به شما می‌دهد که می‌توانید از هر نقطهٔ شروع به آن‌ها برسید.
به صورت دقیق تر، بستار تعدی رابطه باینری R در مجموعه X، کوچکترین رابطه متعدی روی مجموعه X است به طوری که R⁺ شامل R باشد (Lidl & Pilz (1998)). اگر رابطهٔ دودویی به خودی خود متعدی باشد بسطار تعدی آن خود رابطه می‌شود؛ در غیر این صورت بستار تعدی رابطه‌ای دیگر می‌شود.

روابط متعدی و نمونه‌ها

رابطه R در مجموعه X متعدی است، اگر برای تمام x و y و zهای موجود در Xکه x R y و y R z ،نتیجه بدهد x R z. نمونه‌هایی از روابط متعدی عبارتند از:
رابطهٔ برابری در هر مجموعه‌ای، رابطهٔ "کوچکتر یا مساوی " در هر مجموعهٔ مرتب خطی، و رابطهٔ "x قبل از y متولد شده" در مجموعهٔ همه مردم. این روابط را می‌توان به صورت نمادین نشان داد: اگر x <y و y <z آنگاه x <z است.
یک مثال از یک رابطهٔ غیر متعدی:
«میتوان از شهر y با پرواز مستقیم به شهر x رسید» در مجموعهٔ تمام شهرها.
تنها به دلیل وجود یک پرواز مستقیم از شهری به شهر دوم و یک پرواز مستقیم از شهر دوم به سوم، پرواز مستقیم از شهر اول به شهر دوم وجود ندارد. بستار تعدی این رابطه متفاوت است، یعنی «دنباله‌ای از پروازهای مستقیم که در شهر X شروع می‌شود و در شهر y به پایان می‌رسد». هر رابطه‌ای را می‌توان بسط داد در یک روش مشابه به یک رابطهٔ متعدی.
به عنوان مثال یک رابطهٔ غیر تعدی که نسبت به تعدی بودن بسته نیست «روز x بعد از روز y در هفته هست».
این بستار تعدی این رابطه است:
"چند روز x می‌آید بعد از y"
که بدیهی است برای تمام روزهای هفته x و y (این معادل یک دستگاه دکارتی است که"x , y روزهای هفته‌اند")

خواص

اشتراک دو رابطهٔ متعدی، متعدی است.
اجتماع دو رابطهٔ متعدی حتماً متعدی نیست. برای حفظ حالت متعدی یکی باید بستار تعدی باشد. این اتفاق زمانی می‌افتد برای مثال که اتحاد دو روابط هم‌ارزی یا دو preorders. برای به دست آوردن رابطه هم‌ارزی جدید یا preorder یکی باید بستار تعدی (یازتابی و تقارن در مورد روابط هم‌ارزی—خودکار هستند) باشد.

در نظریه گراف

در علوم کامپیوتر، مفهوم بستار تعدی را می‌توان به عنوان ساخت یک ساختار داده که امکان پاسخ به پرسش قابل دسترسی در نظر گرفت.
یعنی که می‌تواند یکی از گره a به گره d در یک یا چند گره است؟ یک رابطهٔ دوتایی فقط به شما می‌گوید که گره a به گره b متصل است و گره b به گره c متصل است، پس از ساخته شدن بستار تعدی، همان‌طور که در شکل زیر نشان داده شده‌است، در O(1) عملیات یکی می‌تواند تعیین کند که گره d قابل دسترسی است از گره یک. داده ساختارها معمولاً به عنوان یک ماتریس ذخیره می‌شوند، بنابراین اگر ماتریس[۱][۴] = ۱ و یعنی که گره ۱ می‌تواند برود به گره ۴ از طریق یک یا چند گره.
این بستار تعدی یک گراف جهت‌دار غیرمدور (DAG) رابطهٔ دسترسی و از و مجموعهٔ مرتب جزیی است.

در منطق و محاسبات پیچیده

این بستارهای تعدی باینری رابطه به‌طور کلی نمی‌تواند بیان شود در مرتبه اول منطق(FO).
این به این معنی است که کسی نمی‌تواند فرمولی بنویسد با استفاده از گزاره نمادهای R و T که راضی خواهد بود در
هر مدل اگر و تنها اگر T بستار تعدی از Rاست.
در محدود مدل تئوریبرای اولین بار-سفارش منطق (FO) تمدید با یک متعدی بسته شدن اپراتور است که معمولاً به نام متعدی بسته شدن منطقو به صورت مختصر FO(TC) یا فقط TC. TC یک زیر نوع fixpoint را از دست منطق. این واقعیت است که FO(TC) است که به شدت رسا تر از FO کشف شد توسط رونالد Fagin در سال ۱۹۷۴; نتیجه شد و سپس کشف توسط Alfred Aho و جفری آلمن در سال ۱۹۷۹ که به پیشنهاد به استفاده از fixpoint را از دست منطق به عنوان یک پایگاه داده پرس و جو زبان (Libkin 2004:vii). با مطلب اخیر مفاهیم محدود مدل تئوری اثبات این که FO(TC) است که به شدت رسا تر از FO شرح زیر است بلافاصله از این واقعیت است که FO(TC) است Gaifman-محلی (Libkin 2004:49).
در نظریه پیچیدگی محاسباتیاین پیچیدگی کلاس NL دقیقاً مربوط به مجموعه‌ای از منطقی جملات expressible در TC. دلیل این است که متعدی بسته شدن اموال است یک رابطه نزدیک با NL-کامل مشکل STCON برای پیدا کردن کارگردانی مسیر در یک گراف. به‌طور مشابه کلاس L is first-order logic با مبادلهای‌های متعدی بسته شدن. زمانی که متعدی بسته اضافه شده‌است به مرتبه دوم منطق به جای ما به دست آوردن PSPACE.

در پایگاه داده‌های پرس و جو زبان

از سال 1980s پایگاه داده اوراکل اجرا کرده‌است اختصاصی SQL فرمت اتصال... شروع با که اجازه می‌دهد تا محاسبه متعدی بسته شدن به عنوان بخشی از یک اعلانی پرس و جو. این SQL 3 (1999) استاندارد اضافه شده کلی تر با بازگشتی ساخت نیز اجازه می‌دهد متعدی تعطیلی به محاسبه در داخل query processor; به عنوان از ۲۰۱۱ دومی است به اجرا در آی بی ام DB2های مایکروسافت SQL سرورهای Oracleو PostgreSQL واگر چه نه در MySQL (بندیکت و Senellart 2011:189).
Datalog نیز پیاده‌سازی متعدی بسته شدن محاسبات (Silberschatz et al. 2010:C. 3.6).

الگوریتم

الگوریتم‌های کارآمد برای محاسبه بستار تعدی یک گراف را می‌توان در Nuutila (1995) پیدا کرد. سریعترین و بدترین روش که عملی نیست، تبدیل مسئله به ضرب ماتریس است. این مشکل نیز حل می‌شود با الگوریتم وارشال یا با تکرار breadth-first search یا جستجو ی اول عمق با شروع از هر گره از گراف است.
بیشتر تحقیقات اخیر به راه‌های مؤثر محاسبهٔ بستار تعدی در سیستم‌های توزیع شده بر اساس MapReduce پارادایم (Afrati et al. 2011) اشاره می‌کند.