إغلاق متعدٍ

العلاقات الثنائية المتعدية  v ت هـ
متماثل مضاد للتناظر متصل مؤسس بشكل جيد لديه روابط لديه لقاءات انعكاسي غير انعكاسي غير متماثل توتال، سيميكونكس مضاد للانعكاس علاقة التكافؤ Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ طلب مسبق (طلب شبه رسمي) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ طلب جزئي ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ إجمالي الطلبات المسبقة ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ إجمالي الطلب ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ الطلب المسبق ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ ترتيب شبه جيد ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ ترتيب جيد ✗ Y Y Y ✗ ✗ Y ✗ ✗ شعرية ✗ Y ✗ ✗ Y Y Y ✗ ✗ الانضمام إلى شبه الشبكة ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ شبكة اللقاءات ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ ترتيب جزئي صارم ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y ترتيب ضعيف صارم ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y إجمالي الطلب الصارم ✗ Y Y ✗ ✗ ✗ ✗ Y Y متماثل مضاد للتناظر متصل مؤسس بشكل جيد لديه روابط لديه لقاءات انعكاسي غير انعكاسي غير متماثل التعريفات، للجميع${\displaystyle a,b}$و${\displaystyle S\neq \varnothing$ :} ${\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}aRb{\text{ و }}&bRa\\\Rightarrow a={}&b\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\vee b\\{\text{يوجد}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}}$ ${\displaystyle aRa}$ ${\displaystyle {\text{not }}aRa}$ ${\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}}$
يشير الرمز Y إلى أن خاصية العمود صحيحة دائمًا بالنسبة لعنصر الصف (في أقصى اليسار)، بينما يشير الرمز ✗ إلى أن الخاصية غير مضمونة بشكل عام (قد تكون صحيحة أو خاطئة). على سبيل المثال، يُشار إلى أن كل علاقة تكافؤ متناظرة، ولكن ليس بالضرورة مضادة للتناظر، بالرمز Y في عمود "متناظر" والرمز ✗ في عمود "مضاد للتناظر". تتطلب جميع التعريفات ضمنيًا العلاقة المتجانسة${\displaystyle R}$يكون متعدياً : للجميع${\displaystyle a,b,c,}$لو${\displaystyle aRb}$و${\displaystyle bRc}$ثم${\displaystyle aRc.}$ قد يتطلب تعريف المصطلح خصائص إضافية غير مدرجة في هذا الجدول.

في الرياضيات ، يُعرف الإغلاق المتعدي R ⁺ لعلاقة ثنائية متجانسة R على مجموعة X بأنه أصغر علاقة على X تحتوي على R وتكون متعدية . بالنسبة للمجموعات المنتهية، يمكن فهم "الأصغر" بمعناها المعتاد، أي امتلاك أقل عدد من الأزواج المرتبطة؛ أما بالنسبة للمجموعات غير المنتهية، فإن R + ^هي المجموعة الفائقة المتعدية الدنيا الوحيدة لـ R.

على سبيل المثال، إذا كانت X مجموعة من المطارات و x R y تعني "هناك رحلة طيران مباشرة من المطار x إلى المطار y " (لـ x و y في X )، فإن الإغلاق المتعدي لـ R على X هو العلاقة R ⁺ بحيث x R ⁺ y تعني "من الممكن السفر من x إلى y في رحلة واحدة أو أكثر".

More formally, the transitive closure of a binary relation R on a set X is the smallest (w.r.t. ⊆) transitive relation R⁺ on X such that R ⊆ R⁺; see Lidl & Pilz (1998, p. 337). We have R⁺ = R if, and only if, R itself is transitive.

Conversely, transitive reduction reduces a minimal relation S from a given relation R such that they have the same closure, that is, S⁺ = R⁺; however, many different S with this property may exist.

Both transitive closure and transitive reduction are also used in the closely related area of graph theory.

A relation R on a set X is transitive if, for all x, y, z in X, whenever x R y and y R z then x R z. Examples of transitive relations include the equality relation on any set, the "less than or equal" relation on any linearly ordered set, and the relation "x was born before y" on the set of all people. Symbolically, this can be denoted as: if x < y and y < z then x < z.

One example of a non-transitive relation is "city x can be reached via a direct flight from city y" on the set of all cities. Simply because there is a direct flight from one city to a second city, and a direct flight from the second city to the third, does not imply there is a direct flight from the first city to the third. The transitive closure of this relation is a different relation, namely "there is a sequence of direct flights that begins at city x and ends at city y". Every relation can be extended in a similar way to a transitive relation.

مثال على علاقة غير متعدية ذات إغلاق متعدٍ أقل دلالة هو " س هو يوم الأسبوع الذي يلي ص ". الإغلاق المتعدي لهذه العلاقة هو "يوم ما س يأتي بعد يوم ص في التقويم"، وهو صحيح بشكل بديهي لجميع أيام الأسبوع س و ص (وبالتالي فهو مكافئ للمربع الديكارتي ، الذي ينص على أن " س و ص كلاهما يومان من أيام الأسبوع").

لأي علاقة R ، يوجد دائمًا إغلاق متعدٍّ لـ R. ولإثبات ذلك، لاحظ أن تقاطع أي مجموعة من العلاقات المتعدية هو أيضًا علاقة متعدية. علاوة على ذلك، توجد على الأقل علاقة متعدية واحدة تحتوي على R ، وهي العلاقة التافهة: X × X. وبالتالي ، يُعطى الإغلاق المتعدي لـ R بتقاطع جميع العلاقات المتعدية التي تحتوي على R.

بالنسبة للمجموعات المنتهية، يمكننا بناء الإغلاق المتعدي خطوة بخطوة، بدءًا من R وإضافة الحواف المتعدية. وهذا يعطينا فكرة عامة عن كيفية بنائه. لأي مجموعة X ، يمكننا إثبات أن الإغلاق المتعدي يُعطى بالصيغة التالية

${\displaystyle R^{+}=\bigcup _{i=1}^{\infty }R^{i}.}$

أين${\displaystyle R^{i}}$هي القوة i من R ، المعرفة استقرائيًا بواسطة

${\displaystyle R^{1}=R}$

و، لـ${\displaystyle i>0}$،

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

أين${\displaystyle \circ }$يشير إلى تكوين العلاقات .

لإظهار أن التعريف أعلاه لـ R ⁺ هو أصغر علاقة متعدية تحتوي على R ، نوضح أنها تحتوي على R ، وأنها متعدية ، وأنها أصغر مجموعة تتمتع بكلتا هاتين الخاصيتين.

• ${\displaystyle R\subseteq R^{+}}$:${\displaystyle R^{+}}$يحتوي على كل${\displaystyle R^{i}}$لذلك على وجه الخصوص${\displaystyle R^{+}}$يتضمن${\displaystyle R}$.
• ${\displaystyle R^{+}}$فعل متعدٍ: إذا${\displaystyle (s_{1},s_{2}),(s_{2},s_{3})\in R^{+}}$، ثم${\displaystyle (s_{1},s_{2})\in R^{j}}$و${\displaystyle (s_{2},s_{3})\in R^{k}}$بالنسبة للبعض${\displaystyle j,k}$بحسب تعريف${\displaystyle R^{+}}$بما أن التركيب ترابطي،${\displaystyle R^{j+k}=R^{j}\circ R^{k}}$؛ لذلك${\displaystyle (s_{1},s_{3})\in R^{j+k}\subseteq R^{+}}$بحسب تعريف${\displaystyle \circ }$و${\displaystyle R^{+}}$.
• ${\displaystyle R^{+}}$يكون الحد الأدنى، أي إذا${\displaystyle T}$أي علاقة متعدية تحتوي على${\displaystyle R}$، ثم${\displaystyle R^{+}\subseteq T}$: بالنظر إلى أي من هذا القبيل${\displaystyle T}$، الحث على${\displaystyle i}$يمكن استخدامها لإظهار${\displaystyle R^{i}\subseteq T}$للجميع${\displaystyle i}$كما يلي: القاعدة:${\displaystyle R^{1}=R\subseteq T}$بافتراض. الخطوة: إذا${\displaystyle R^{i}\subseteq T}$يحمل، و${\displaystyle (s_{1},s_{3})\in R^{i+1}=R\circ R^{i}}$، ثم${\displaystyle (s_{1},s_{2})\in R}$و${\displaystyle (s_{2},s_{3})\in R^{i}}$بالنسبة للبعض${\displaystyle s_{2}}$، بحسب تعريف${\displaystyle \circ }$. لذلك،${\displaystyle (s_{1},s_{2}),(s_{2},s_{3})\in T}$بالافتراض وبالاستقراء. ومن ثم${\displaystyle (s_{1},s_{3})\in T}$عن طريق التعدي${\displaystyle T}$وبهذا يكتمل الاستقراء. وأخيرًا،${\displaystyle R^{i}\subseteq T}$للجميع${\displaystyle i}$يشير إلى${\displaystyle R^{+}\subseteq T}$بحسب تعريف${\displaystyle R^{+}}$.

تقاطع علاقتين متعديتين هو علاقة متعدية .

لا يشترط أن يكون اتحاد علاقتين متعديتين علاقة متعدية. وللحفاظ على التعدي، يجب أخذ الإغلاق المتعدي. يحدث هذا، على سبيل المثال، عند اتحاد علاقتي تكافؤ أو علاقتي ترتيب جزئي . وللحصول على علاقة تكافؤ أو علاقة ترتيب جزئي جديدة، يجب أخذ الإغلاق المتعدي (حيث يكون الانعكاس والتناظر - في حالة علاقات التكافؤ - تلقائيين).

في علم الحاسوب ، يُمكن اعتبار مفهوم الإغلاق المتعدي بمثابة بناء بنية بيانات تُتيح الإجابة على أسئلة إمكانية الوصول . أي، هل يُمكن الانتقال من العقدة أ إلى العقدة د في قفزة واحدة أو أكثر؟ تُخبرنا العلاقة الثنائية فقط أن العقدة أ متصلة بالعقدة ب ، وأن العقدة ب متصلة بالعقدة ج ، وهكذا. بعد بناء الإغلاق المتعدي، كما هو موضح في الشكل التالي، يُمكن تحديد إمكانية الوصول إلى العقدة د من العقدة أ في عملية زمنية ثابتة O(1) . تُخزّن بنية البيانات عادةً كمصفوفة منطقية، فإذا كانت matrix[1][4] = true، فهذا يعني أن العقدة 1 يُمكنها الوصول إلى العقدة 4 عبر قفزة واحدة أو أكثر.

إن الإغلاق المتعدي لعلاقة التجاور للرسم البياني الموجه غير الدوري (DAG) هو علاقة الوصول للرسم البياني الموجه غير الدوري وترتيب جزئي صارم .

ينتج عن الإغلاق المتعدي للرسم البياني غير الموجه رسم بياني عنقودي ، وهو اتحاد منفصل من الزمر . ويُعد بناء الإغلاق المتعدي صياغة مكافئة لمسألة إيجاد مكونات الرسم البياني. ^{[ 1 ]}

لا يمكن ، بشكل عام، التعبير عن الإغلاق المتعدي لعلاقة ثنائية في منطق الرتبة الأولى . هذا يعني أنه لا يمكن كتابة صيغة باستخدام رمزي المسند R و T بحيث تتحقق في أي نموذج إذا وفقط إذا كان T هو الإغلاق المتعدي لـ R. في نظرية النماذج المحدودة ، يُطلق على منطق الرتبة الأولى المُوسّع بعامل الإغلاق المتعدي عادةً اسم منطق الإغلاق المتعدي ، ويُختصر إلى FO(TC) أو TC. يُعد TC نوعًا فرعيًا من منطق النقطة الثابتة . اكتشف رونالد فاجين في عام 1974 أن FO(TC) أكثر تعبيرًا من FO، ثم أعاد ألفريد أهو وجيفري أولمان اكتشاف هذه النتيجة في عام 1979، حيث اقترحا استخدام منطق النقطة الثابتة كلغة استعلام لقواعد البيانات . ^{[ 2 ]} مع المفاهيم الأحدث لنظرية النماذج المحدودة، يُستنتج مباشرةً أن FO(TC) أكثر تعبيرًا من FO من حقيقة أن FO(TC) ليس محليًا وفقًا لـ Gaifman . ^{[ 3 ]}

في نظرية التعقيد الحسابي ، تتوافق فئة التعقيد NL تمامًا مع مجموعة الجمل المنطقية القابلة للتعبير عنها في TC. ويعود ذلك إلى أن خاصية الإغلاق المتعدي ترتبط ارتباطًا وثيقًا بمسألة STCON ، وهي مسألة كاملة في NL تتعلق بإيجاد المسارات الموجهة في الرسم البياني. وبالمثل، فإن الفئة L هي منطق من الدرجة الأولى مع خاصية الإغلاق التبادلي والمتعدي. وعند إضافة خاصية الإغلاق المتعدي إلى منطق من الدرجة الثانية ، نحصل على PSPACE .

منذ ثمانينيات القرن الماضي، طبّقت قاعدة بيانات أوراكل امتدادًا خاصًا بلغة SQLCONNECT BY... START WITH يسمح بحساب الإغلاق المتعدي كجزء من الاستعلام التصريحي. أضاف معيار SQL 3WITH RECURSIVE (1999) بنيةً أكثر عمومية تسمح أيضًا بحساب الإغلاقات المتعدية داخل معالج الاستعلام؛ اعتبارًا من عام 2011، تم تطبيق هذه الميزة في IBM Db2 و Microsoft SQL Server و Oracle و PostgreSQL و MySQL (الإصدار 8.0 وما بعده). أصدرت SQLite دعمًا لهذه الميزة في عام 2014.

تُنفذ لغة Datalog أيضًا حسابات الإغلاق المتعدي. ^{[ 4 ]}

تُطبّق MariaDB تعابير الجداول المشتركة المتكررة، والتي يمكن استخدامها لحساب الإغلاقات المتعدية. أُضيفت هذه الميزة في الإصدار 10.2.2 الصادر في أبريل 2016. ^{[ 5 ]}

يمكن إيجاد خوارزميات فعالة لحساب الإغلاق المتعدي لعلاقة التجاور في الرسم البياني في نوتيلا (1995) . ويؤدي اختزال المشكلة إلى ضرب مصفوفات التجاور إلى تحقيق التعقيد الزمني لخوارزميات ضرب المصفوفات السريعة ، ^{[ 6 ]}${\displaystyle O(n^{2.3728596})}$ومع ذلك، فإن هذا النهج غير عملي نظرًا لارتفاع كل من العوامل الثابتة واستهلاك الذاكرة للرسوم البيانية المتفرقة ( نوتيلا 1995 ، الصفحات 22-23، القسم 2.3.3) . ويمكن أيضًا حل المشكلة باستخدام خوارزمية فلويد-وارشال . ${\displaystyle O(n^{3})}$أو عن طريق البحث المتكرر بالعرض أولاً أو البحث بالعمق أولاً بدءاً من كل عقدة من الرسم البياني.

بالنسبة للرسوم البيانية الموجهة، تحل خوارزمية بوردوم المشكلة عن طريق حساب الرسم البياني الموجه المختصر وإغلاقه المتعدي أولاً، ثم رفعه إلى الرسم البياني الأصلي. زمن تشغيلها هو${\displaystyle O(m+\mu n)}$، أين${\displaystyle \mu }$يمثل عدد الحواف بين مكوناتها المتصلة بقوة . ^{[ 7 ] [ 8 ] [ 9 ] [ 10 ]}

وقد استكشفت الأبحاث الحديثة طرقًا فعالة لحساب الإغلاق المتعدي على الأنظمة الموزعة استنادًا إلى نموذج MapReduce . ^{[ 11 ]}

• صلة القرابة
• الاستنتاج المنطقي
• إغلاق انعكاسي
• إغلاق متناظر
• الاختزال المتعدي (أصغر علاقة يكون إغلاقها المتعدي هو الإغلاق المتعدي لـ R )

• فوتو ن. أفراتي ، فيناياك بوركار، مايكل كاري ، نيوكليس بوليزوتيس، جيفري د. أولمان ، امتدادات MapReduce والاستعلامات المتكررة ، EDBT 2011، 22-24 مارس 2011، أوبسالا، السويد، ISBN 978-1-4503-0528-0
• أهو، أ. ف .؛ أولمان، ج. د. (1979). "عالمية لغات استرجاع البيانات". وقائع الندوة السادسة لجمعية آلات الحوسبة SIGACT-SIGPLAN حول مبادئ لغات البرمجة - POPL '79 . الصفحات 110-119 . doi : 10.1145/567752.567763 . 
• بينيديكت، م.؛ سينيلارت، ب. (2011). "قواعد البيانات". في: بلوم، إدوارد ك.؛ أهو، ألفريد ف. (محرران). علوم الحاسوب: المكونات المادية والبرمجية وجوهرها . ص 169-229 . doi : 10.1007/978-1-4614-1168-0_10 . ISBN  978-1-4614-1167-3.
• هاينز ديتر إبنجهاوس؛ يورج فلوم (1999). نظرية النموذج المحدود (  الطبعة الثانية). سبرينغر. الصفحات 123 – 124، 151 – 161، 220 – 235. ISBN  978-3-540-28787-2.
• فيشر، إم جيه؛ ماير، إيه آر (أكتوبر 1971). "ضرب المصفوفات البوليانية والإغلاق المتعدي" (ملف PDF) . في: ريموند إي. ميلر وجون إي. هوبكروفت (محرران). وقائع الندوة السنوية الثانية عشرة حول نظرية التبديل والأتمتة (SWAT) . جمعية مهندسي الكهرباء والإلكترونيات (IEEE). الصفحات 129-131 . doi : 10.1109/SWAT.1971.4 . 
• إريك غرادل؛ فوكيون ج. كولايتيس؛ ليونيد ليبكين؛ مارتن ماركس؛ جويل سبنسر؛ موشيه ي. فاردي؛ يدي فينيما؛ سكوت واينشتاين (2007). نظرية النموذج المحدود وتطبيقاتها . سبرينغر. ص 151-152 . ISBN  978-3-540-68804-4.
• كيلر، يو، 2004، بعض الملاحظات حول إمكانية تعريف الإغلاق المتعدي في منطق الرتبة الأولى و Datalog (مخطوطة غير منشورة)
• ليبكين، ليونيد (2004)، عناصر نظرية النموذج المحدود ، سبرينغر، ISBN 978-3-540-21202-7
• ليدل، ر.؛ بيلز، ج. (1998)،الجبر المجرد التطبيقينصوص جامعية في الرياضيات (الطبعة الثانية  )، سبرينغر، رقم ISBN 0-387-98290-6
• مونرو، إيان (يناير 1971). "تحديد فعال للإغلاق المتعدي للرسم البياني الموجه". رسائل معالجة المعلومات . 1 (2): 56-58 . doi : 10.1016/0020-0190(71)90006-8 .
• نوتيلا، إيسكو (1995). حساب الإغلاق المتعدي الفعال في الرسوم البيانية الموجهة الكبيرة . الأكاديمية الفنلندية للتكنولوجيا. ISBN 951-666-451-2. OCLC 912471702 . 
• أبراهام سيلبرشاتز؛ هنري كورث؛ إس. سودارشان (2010). مفاهيم نظم قواعد البيانات (الطبعة السادسة  ). ماكجرو هيل. ISBN 978-0-07-352332-3.الملحق ج (متوفر عبر الإنترنت فقط)

• " الإغلاق والاختزال المتعدي "، مستودع خوارزميات ستوني بروك، ستيفن سكينا.