إغلاق متعد

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

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

وبشكل أكثر رسمية، فإن الإغلاق المتعدي لعلاقة ثنائية R على مجموعة X هو أصغر (wrt ⊆) علاقة متعدية R ⁺ على X بحيث R ⊆ R ⁺ ؛ انظر Lidl & Pilz (1998، ص 337). لدينا R ⁺ = R إذا، وفقط إذا، كانت R نفسها متعدية.

وعلى العكس من ذلك، يؤدي الاختزال المتعدي إلى استخلاص علاقة دنيا S من علاقة معينة R بحيث يكون لهما نفس الإغلاق، أي S ⁺ = R ⁺ ؛ ومع ذلك، قد توجد العديد من S المختلفة التي لها هذه الخاصية.

يتم أيضًا استخدام كل من الإغلاق الانتقالي والاختزال الانتقالي في المجال ذي الصلة الوثيقة بنظرية الرسم البياني .

تكون العلاقة R في المجموعة X متعدية إذا كان لكل x و y و z في X ، كلما كان x R y و y R z فإن x R z . تشمل أمثلة العلاقات المتعدية علاقة المساواة في أي مجموعة، وعلاقة "أقل من أو يساوي" في أي مجموعة مرتبة خطيًا، والعلاقة " وُلِد x قبل y " في مجموعة كل الأشخاص. يمكن الإشارة إلى ذلك رمزيًا على النحو التالي: إذا كان x < y و y < z فإن x < z .

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

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

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

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

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

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

${\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]

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

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

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

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

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

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

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

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

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

• الصورة: ن. أفراتي ، فيناياك بوركار، مايكل كاري ، نيوكليس بوليزوتيس، جيفري د. أولمان ، امتدادات Map-Reduce والاستعلامات المتكررة، مؤتمر EDBT 2011، 22-24 مارس 2011، أوبسالا، السويد، رقم ISBN 978-1-4503-0528-0 
• Aho, AV ; Ullman, JD (1979). "عالمية لغات استرجاع البيانات". وقائع ندوة ACM 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) . جمعية الحاسبات بمعهد مهندسي الكهرباء والإلكترونيات. ص 129-131. doi :10.1109/SWAT.1971.4.
• إريك جرايدل؛ فوكيون ج. كولايتيس؛ ليونيد ليبكين؛ مارتن ماركس؛ جويل سبنسر؛ موشيه ي. فاردي؛ يدي فينيما؛ سكوت وينشتاين (2007). نظرية النموذج المحدود وتطبيقاتها . سبرينغر. ص 151-152. ISBN 978-3-540-68804-4.
• Keller, U., 2004, Some Remarks on the Definability of Transitive Closure in First-order Logic and Datalog (مخطوطة غير منشورة)* Libkin, Leonid (2004), Elements of Finite Model Theory , Springer, 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.الملحق ج (متاح على الإنترنت فقط)

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