بستار تعدی

در ریاضیات بستار تعدی (تراگذری) یک رابطه دوتایی 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 باشد (الگو:Harvard citation text). اگر رابطهٔ دودویی به خودی خود متعدی باشد بسطار تعدی آن خود رابطه می‌شود؛ در غیر این صورت بستار تعدی رابطه‌ای دیگر می‌شود.

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

رابطه R در مجموعه X متعدی است، اگر برای تمام x و y و zهای موجود در Xکه x R y و الگو:Nowrap ،نتیجه بدهد الگو:Nowrap. نمونه‌هایی از روابط متعدی عبارتند از:

رابطهٔ برابری در هر مجموعه‌ای، رابطهٔ "کوچکتر یا مساوی " در هر مجموعهٔ مرتب خطی، و رابطهٔ "x قبل از y متولد شده" در مجموعهٔ همه مردم. این روابط را می‌توان به صورت نمادین نشان داد: اگر الگو:Nowrap و الگو:Nowrap آنگاه الگو:Nowrap است.

یک مثال از یک رابطهٔ غیر متعدی:

«میتوان از شهر y با پرواز مستقیم به شهر x رسید» در مجموعهٔ تمام شهرها.

تنها به دلیل وجود یک پرواز مستقیم از شهری به شهر دوم و یک پرواز مستقیم از شهر دوم به سوم، پرواز مستقیم از شهر اول به شهر دوم وجود ندارد. بستار تعدی این رابطه متفاوت است، یعنی «دنباله‌ای از پروازهای مستقیم که در شهر X شروع می‌شود و در شهر y به پایان می‌رسد». هر رابطه‌ای را می‌توان بسط داد در یک روش مشابه به یک رابطهٔ متعدی.

به عنوان مثال یک رابطهٔ غیر تعدی که نسبت به تعدی بودن بسته نیست «روز x بعد از روز y در هفته هست».

این بستار تعدی این رابطه است:

"چند روز x می‌آید بعد از y"

که بدیهی است برای تمام روزهای هفته x و y (این معادل یک دستگاه دکارتی است که"x , y روزهای هفته‌اند")

اثبات و شرح

برای هر رابطه R، بستار تعدی R همیشه وجود دارد. برای دیدن این، توجه داشته باشید که اشتراک هر خانواده از روابط متعدی، متعدی است.

بعلاوه حداقل یک رابطه متعدی حاوی R وجود دارد از جمله: X × X. بستار تعدی R اشتراک همه روابط متعدی حاوی رابطهٔ R است.

برای مجموعه‌های متناهی ما می‌توانیم ساخت بستار تعدی را با شروع از R و اضافه کردن لبه‌های متعدی پیش ببریم. این شهود کلی برای ساخت است. برای هر مجموعه X ما می‌توانیم ثابت کنیم که بستار تعدی توسط عبارت زیر به دست می‌آید:

R^{+} = ⋃_{i \in {1, 2, 3, \dots}} R^{i} .

که در آن $R^{i}$ توان i از R به شکل زیر تعریف شده:

R^{1} = R

و برای $i > 0$

R^{i + 1} = R \circ R^{i}

که در آن $\circ$ نشان دهنده ترکیب روابط است.

برای نشان دادن تعریف بالا که R+ کوچکترین رابطهٔ متعدی حاوی R است، نشان می‌دهیم که آن شامل R است و آن متعدی است و کوچکترین مجموعه‌ای است که با هر دو این ویژگی‌ها را داراست.

$R \subseteq R^{+}$ : $R^{+}$ شامل تمام $R^{i}$ ، به‌طور خاص $R^{+}$ $R$ .
$R^{+}$ متعدی است: تمامی اعضای $R^{+}$ در یکی از $R^{i}$ ، بنابراین $R^{+}$ باید با استدلال زیر متعدی می‌شود:
اگر $(s_{1}, s_{2}) \in R^{j}$ و $(s_{2}, s_{3}) \in R^{k}$ ، سپس از خاصیت شرکت پذیری، $(s_{1}, s_{3}) \in R^{j + k}$ (و در $R^{+}$ ) به خاطر تعریف $R^{i}$ .
$R^{+}$ کوچکترین است: $G$ مجموعهٔ روابط متعدی حاوی $R$ ، ما باید نشان دهیم $R^{+} \subseteq G$ . کافی است نشان دهیم که برای هر $i > 0$ ، $R^{i} \subseteq G$ . خب، از آنجایی که $G$ شامل $R$ ، $R^{1} \subseteq G$ . و چون $G$ متعدی است، هر گاه $R^{i} \subseteq G$ ، $R^{i + 1} \subseteq G$ با توجه به ساختار $R^{i}$ و تعریف متعدی بودن، بنابراین، $G$ $R^{i}$ ، و بنابراین هست $R^{+}$ .

خواص

اشتراک دو رابطهٔ متعدی، متعدی است.

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

در نظریه گراف

Transitive closure constructs the output graph from the input graph. — متعدی بسته شدن سازه خروجی گراف از ورودی گراف.

در علوم کامپیوتر، مفهوم بستار تعدی را می‌توان به عنوان ساخت یک ساختار داده که امکان پاسخ به پرسش قابل دسترسی در نظر گرفت. یعنی که می‌تواند یکی از گره 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) اشاره می‌کند.

جستارهای وابسته

قیاسی بسته شدن
متعدی کاهش (کوچکترین ارتباط داشتن متعدی بسته شدن R به عنوان آن متعدی بسته شدن)
متقارن بسته شدن
Reflexive بسته شدن
اجدادی ارتباط

منابع

الگو:پانویس

Lidl, R. and Pilz, G. , 1998, Applied abstract algebra, 2nd edition, Undergraduate Texts in Mathematics, Springer, ISBN 0-387-98290-6
Keller, U. , 2004, Some Remarks on the Definability of Transitive Closure in First-order Logic and Datalog (unpublished manuscript)
الگو:یادکرد کتاب
الگو:Citation
الگو:یادکرد کتاب
الگو:یادکرد کتاب
الگو:یادکرد کتاب
Nuutila, E. , Efficient Transitive Closure Computation in Large Digraphs. Acta Polytechnica Scandinavica, Mathematics and Computing in Engineering Series No. 74, Helsinki 1995, 124 pages. Published by the Finnish Academy of Technology. ISBN 951-666-451-2، الگو:ISSN، UDC 681.3.
الگو:یادکرد کتاب Appendix C (online only)
Foto N. Afrati, Vinayak Borkar, Michael Carey, Neoklis Polyzotis, Jeffrey D. Ullman, Map-Reduce Extensions and Recursive Queries, EDBT 2011, March 22–24, 2011, Uppsala, Sweden, ISBN 978-1-4503-0528-0

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

"متعدی بسته شدن و کاهش"استونی بروک الگوریتم مخزن استیون Skiena.
"Apti Algoritmi الگو:Webarchive"یک مثال و برخی از C++ پیاده‌سازی از الگوریتم‌های که محاسبه متعدی بسته شدن یک داده باینری ارتباط Vreda Pieterse.