بستار تعدی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در ریاضیات بستار تعدی یک رابطه دوتایی R در مجموعه کوچکترین رابطه از شامل R که متعدی باشد.

برای مثال اگر X یک مجموعه‌ای از فرودگاه‌ها و x R y به معنی "یک پرواز مستقیم از فرودگاه x به فرودگاه y وجود دارد" (برای x و y در X) باشد، سپس بستار تعدی R در رابطه 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 روزهای هفته‌اند")

اثبات و شرح[ویرایش]

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

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

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

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

و برای

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

برای نشان دادن تعریف بالا که R+ کوچکترین رابطهٔ متعدی حاوی R است، نشان می‌دهیم که آن شامل 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 بسته شدن
  • اجدادی ارتباط

منابع[ویرایش]

پیوند به بیرون[ویرایش]

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