सकर्मक समापन

This article is about the transitive closure of a binary relation. For the transitive closure of a set, see transitive set § Transitive closure.

गणित में, द्विआधारी संबंध का सकर्मक समापन R सेट पर (गणित) X पर सबसे छोटा संबंध (गणित) है X उसमें सम्मिलित है R और सकर्मक संबंध है. परिमित समुच्चयों के लिए, सबसे छोटे को उसके सामान्य अर्थ में लिया जा सकता है, जिसमें सबसे कम संबंधित जोड़े होते हैं; अनंत सेटों के लिए यह अद्वितीय न्यूनतम तत्व सकर्मक सुपरसेट है R.

उदाहरण के लिए, यदि Xहवाई अड्डों का समूह है और x R yमतलब एयरपोर्ट से सीधी फ्लाइट है x हवाई अड्डे के लिए y (के लिए x और y में X), फिर का सकर्मक समापन R पर Xसंबंध है R⁺ ऐसा है कि x R⁺ y यानी इससे उड़ान भरना संभव है x को y या अधिक उड़ानों में। अनौपचारिक रूप से, ट्रांजिटिव क्लोजर आपको उन सभी स्थानों का सेट देता है जहां आप किसी भी शुरुआती स्थान से पहुंच सकते हैं।

अधिक औपचारिक रूप से, द्विआधारी संबंध का सकर्मक समापन R सेट पर X सकर्मक संबंध है R⁺ सेट पर X ऐसा है कि R⁺ रोकना R और R⁺ न्यूनतम है; देखना Lidl & Pilz (1998, p. 337). यदि द्विआधारी संबंध स्वयं सकर्मक है, तो सकर्मक समापन वही द्विआधारी संबंध है; अन्यथा, सकर्मक समापन अलग संबंध है।

इसके विपरीत, सकर्मक कमी न्यूनतम संबंध जोड़ती है S किसी दिए गए संबंध से R जैसे कि उनका समापन ही है, अर्थात, S⁺ = R⁺; हालाँकि, कई भिन्न S इस संपत्ति के साथ मौजूद हो सकता है।

सकर्मक समापन और सकर्मक कमी दोनों का उपयोग ग्राफ सिद्धांत के निकट से संबंधित क्षेत्र में भी किया जाता है।

सकर्मक संबंध और उदाहरण

समुच्चय X पर संबंध R सकर्मक है यदि, X में सभी x, y, z के लिए, जब भी x R y और y R z तब x R z. सकर्मक संबंधों के उदाहरणों में किसी भी सेट पर समानता संबंध, किसी भी रैखिक रूप से आदेशित सेट पर कम या बराबर संबंध, और सभी लोगों के सेट पर संबंध x का जन्म y से पहले हुआ था। प्रतीकात्मक रूप से, इसे इस प्रकार दर्शाया जा सकता है: यदि x < y और y < z तब x < z.

गैर-संक्रमणीय संबंध का उदाहरण यह है कि शहर x तक सभी शहरों के सेट पर शहर y से सीधी उड़ान के माध्यम से पहुंचा जा सकता है। सिर्फ इसलिए कि शहर से दूसरे शहर के लिए सीधी उड़ान है, और दूसरे शहर से तीसरे शहर के लिए सीधी उड़ान है, इसका मतलब यह नहीं है कि पहले शहर से तीसरे शहर के लिए सीधी उड़ान है। इस संबंध का सकर्मक समापन अलग संबंध है, अर्थात् सीधी उड़ानों का क्रम है जो शहर x से शुरू होता है और शहर y पर समाप्त होता है। प्रत्येक संबंध को सकर्मक संबंध के समान ही बढ़ाया जा सकता है।

कम सार्थक सकर्मक समापन के साथ गैर-संक्रमणीय संबंध का उदाहरण है x, y के बाद सप्ताह का दिन है। इस संबंध का सकर्मक समापन कैलेंडर पर दिन y के बाद आने वाला कोई दिन है, जो सप्ताह के सभी दिनों x और y के लिए तुच्छ रूप से सत्य है (और इस प्रकार कार्टेशियन उत्पाद के बराबर है, जो कि x और y दोनों दिन हैं) सप्ताह )।

अस्तित्व और विवरण

किसी भी संबंध R के लिए, R का सकर्मक समापन हमेशा मौजूद रहता है। इसे देखने के लिए, ध्यान दें कि सकर्मक संबंधों के किसी भी अनुक्रमित परिवार का प्रतिच्छेदन (सेट सिद्धांत) फिर से सकर्मक है। इसके अलावा, आर युक्त कम से कम सकर्मक संबंध मौजूद है, अर्थात् तुच्छ एक: एक्स × एक्स। आर का सकर्मक समापन तब आर युक्त सभी सकर्मक संबंधों के प्रतिच्छेदन द्वारा दिया जाता है।

परिमित सेटों के लिए, हम आर से शुरू करके और संक्रमणीय किनारों को जोड़कर चरण दर चरण संक्रमणीय समापन का निर्माण कर सकते हैं। यह सामान्य निर्माण के लिए अंतर्ज्ञान देता है। किसी भी सेट एक्स के लिए, हम यह साबित कर सकता है कि सकर्मक समापन निम्नलिखित अभिव्यक्ति द्वारा दिया गया है

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

कहाँ $R^{i}$ R की i-वीं शक्ति है, जिसे आगमनात्मक रूप से परिभाषित किया गया है

$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^{+}$ सकर्मक है: यदि $(s_{1},s_{2}),(s_{2},s_{3})\in R^{+}$, तब $(s_{1},s_{2})\in R^{j}$ और $(s_{2},s_{3})\in R^{k}$ कुछ के लिए $j,k$ की परिभाषा के अनुसार $R^{+}$. चूँकि रचना साहचर्य है, $R^{j+k}=R^{j}\circ R^{k}$; इस तरह $(s_{1},s_{3})\in R^{j+k}\subseteq R^{+}$ की परिभाषा के अनुसार $\circ$ और $R^{+}$.
• $R^{+}$ न्यूनतम है, अर्थात यदि $T$ कोई सकर्मक संबंध युक्त है $R$, तब $R^{+}\subseteq T$: ऐसा कोई दिया गया $T$, गणितीय प्रेरण पर $i$ दिखाने के लिए उपयोग किया जा सकता है $R^{i}\subseteq T$ सभी के लिए $i$ इस प्रकार: आधार: $R^{1}=R\subseteq T$ अनुमान से. चरण: यदि $R^{i}\subseteq T$ धारण करता है, और $(s_{1},s_{3})\in R^{i+1}=R\circ R^{i}$, तब $(s_{1},s_{2})\in R$ और $(s_{2},s_{3})\in R^{i}$ कुछ के लिए $s_{2}$, की परिभाषा के अनुसार $\circ$. इस तरह, $(s_{1},s_{2}),(s_{2},s_{3})\in T$ धारणा द्वारा और प्रेरण परिकल्पना द्वारा। इस तरह $(s_{1},s_{3})\in T$ की परिवर्तनशीलता द्वारा $T$; यह प्रेरण पूरा करता है। आखिरकार, $R^{i}\subseteq T$ सभी के लिए $i$ तात्पर्य $R^{+}\subseteq T$ की परिभाषा के अनुसार $R^{+}$.

गुण

दो सकर्मक संबंधों का प्रतिच्छेदन (सेट सिद्धांत) सकर्मक है।

दो सकर्मक संबंधों का मिलन (सेट सिद्धांत) सकर्मक होना आवश्यक नहीं है। सकर्मकता को संरक्षित करने के लिए, व्यक्ति को सकर्मक समापन लेना होगा। ऐसा तब होता है, उदाहरण के लिए, जब दो समतुल्य संबंधों या दो पूर्व-आदेशों का मिलन होता है। नया तुल्यता संबंध या पूर्व आदेश प्राप्त करने के लिए व्यक्ति को ट्रांजिटिव क्लोजर (रिफ्लेक्सिविटी और समरूपता - तुल्यता संबंधों के मामले में - स्वचालित हैं) लेना होगा।

ग्राफ़ सिद्धांत में

ट्रांसिटिव क्लोजर इनपुट ग्राफ से आउटपुट ग्राफ का निर्माण करता है।

कंप्यूटर विज्ञान में, ट्रांजिटिव क्लोजर की अवधारणा को डेटा संरचना के निर्माण के रूप में सोचा जा सकता है जो गम्यता प्रश्नों का उत्तर देना संभव बनाता है। यानी, क्या कोई या अधिक हॉप्स में नोड ए से नोड डी तक पहुंच सकता है? द्विआधारी संबंध आपको केवल यह बताता है कि नोड ए नोड बी से जुड़ा है, और वह नोड बी नोड सी से जुड़ा है, आदि। ट्रांजिटिव क्लोजर के निर्माण के बाद, जैसा कि निम्नलिखित चित्र में दर्शाया गया है, Big_O_notation#Orders_of_common_functions|O(1) में ) ऑपरेशन यह निर्धारित कर सकता है कि नोड डी नोड ए से पहुंच योग्य है। डेटा संरचना को आम तौर पर बूलियन मैट्रिक्स के रूप में संग्रहीत किया जाता है, इसलिए यदि मैट्रिक्स [1] [4] = सत्य है, तो यह मामला है कि नोड 1 या अधिक हॉप्स के माध्यम से नोड 4 तक पहुंच सकता है।

एक निर्देशित अचक्रीय ग्राफ (डीएजी) के आसन्न संबंध का सकर्मक समापन डीएजी का पहुंच योग्यता संबंध और सख्त आंशिक आदेश है।

एक क्लस्टर ग्राफ़, अप्रत्यक्ष ग्राफ़ का सकर्मक समापन

एक अप्रत्यक्ष ग्राफ़ का सकर्मक समापन क्लस्टर ग्राफ़ उत्पन्न करता है, जो क्लिक (ग्राफ़ सिद्धांत) के ग्राफ़ का असंयुक्त संघ है। ट्रांजिटिव क्लोजर का निर्माण ग्राफ के घटक (ग्राफ सिद्धांत) को खोजने की समस्या का समतुल्य सूत्रीकरण है।

तर्क और कम्प्यूटेशनल जटिलता में

किसी द्विआधारी संबंध का सकर्मक समापन, सामान्य तौर पर, प्रथम-क्रम तर्क (एफओ) में व्यक्त नहीं किया जा सकता है।

इसका मतलब यह है कि कोई भी विधेय प्रतीकों आर और टी का उपयोग करके सूत्र नहीं लिख सकता है जो संतुष्ट हो जाएगा कोई भी मॉडल यदि और केवल यदि T, R का सकर्मक समापन है।

परिमित मॉडल सिद्धांत में, ट्रांजिटिव क्लोजर ऑपरेटर के साथ विस्तारित प्रथम-क्रम तर्क (एफओ) को आमतौर पर 'ट्रांसिटिव क्लोजर लॉजिक' कहा जाता है, और संक्षिप्त रूप से एफओ (टीसी) या सिर्फ टीसी कहा जाता है। टीसी फिक्सप्वाइंट लॉजिक्स का उप-प्रकार है। तथ्य यह है कि एफओ (टीसी) एफओ की तुलना में सख्ती से अधिक अभिव्यंजक है, इसकी खोज रोनाल्ड फागिन ने 1974 में की थी; परिणाम को 1979 में मैं अल्फ्रेड हूं और जेफरी उलमन द्वारा फिर से खोजा गया, जिन्होंने डेटाबेस क्वेरी भाषा के रूप में फिक्सपॉइंट तर्क का उपयोग करने का प्रस्ताव रखा। परिमित मॉडल सिद्धांत की नवीनतम अवधारणाओं के साथ, यह प्रमाण कि एफओ (टीसी) एफओ की तुलना में सख्ती से अधिक अभिव्यंजक है, इस तथ्य से तुरंत पता चलता है कि एफओ (टीसी) गैफमैन-स्थानीय नहीं है। कम्प्यूटेशनल जटिलता सिद्धांत में, जटिलता वर्ग एनएल (जटिलता) टीसी में व्यक्त तार्किक वाक्यों के सेट से सटीक रूप से मेल खाती है। ऐसा इसलिए है क्योंकि ट्रांज़िटिव क्लोजर प्रॉपर्टी का ग्राफ़ में निर्देशित पथ खोजने के लिए एनएल-पूर्ण समस्या STCON के साथ घनिष्ठ संबंध है। इसी प्रकार, वर्ग एल (जटिलता) क्रमविनिमेय, सकर्मक समापन के साथ प्रथम-क्रम तर्क है। जब इसके बजाय दूसरे क्रम के तर्क में ट्रांजिटिव क्लोजर जोड़ा जाता है, तो हमें PSPACE प्राप्त होता है।

डेटाबेस क्वेरी भाषाओं में

Further information: Hierarchical and recursive queries in SQL

1980 के दशक से Oracle डेटाबेस ने मालिकाना SQL एक्सटेंशन लागू किया है CONNECT BY... START WITH यह घोषणात्मक क्वेरी के भाग के रूप में सकर्मक समापन की गणना की अनुमति देता है। SQL 3 (1999) मानक ने और अधिक सामान्य जोड़ा WITH RECURSIVE निर्माण क्वेरी प्रोसेसर के अंदर ट्रांजिटिव क्लोजर की गणना करने की भी अनुमति देता है; 2011 तक बाद वाले को IBM Db2, Microsoft SQL Server, Oracle डेटाबेस, PostgreSQL और MySQL (v8.0+) में लागू किया गया है। SQLite ने 2014 में इसके लिए समर्थन जारी किया।

संगणक वैज्ञानिक ट्रांजिटिव क्लोजर गणनाओं को भी लागू करता है। MariaDB रिकर्सिव कॉमन टेबल एक्सप्रेशन लागू करता है, जिसका उपयोग ट्रांजिटिव क्लोजर की गणना करने के लिए किया जा सकता है। यह सुविधा अप्रैल 2016 की रिलीज़ 10.2.2 में पेश की गई थी।

एल्गोरिदम

ग्राफ़ के आसन्न संबंध के सकर्मक समापन की गणना के लिए कुशल एल्गोरिदम यहां पाए जा सकते हैं Nuutila (1995). आसन्न मैट्रिक्स के गुणन की समस्या को कम करने से न्यूनतम उपलब्धि प्राप्त होती है समय जटिलता, अर्थात। मैट्रिक्स गुणन (Munro 1971, Fischer & Meyer 1971), जो है $O(n^{2.3728596})$ as of December 2020. हालाँकि, यह दृष्टिकोण व्यावहारिक नहीं है क्योंकि विरल ग्राफ़ के लिए स्थिर कारक और मेमोरी खपत दोनों अधिक हैं (Nuutila 1995, pp. 22–23, sect.2.3.3). समस्या को फ़्लॉइड-वॉर्शल एल्गोरिथम द्वारा भी हल किया जा सकता है $O(n^{3})$, या ग्राफ़ के प्रत्येक नोड से शुरू होने वाली बार-बार चौड़ाई-पहली खोज या गहराई-पहली खोज द्वारा।

निर्देशित ग्राफ़ के लिए, Purdom का एल्गोरिदम पहले इसके संक्षेपण DAG और इसके संक्रमणीय समापन की गणना करके, फिर इसे मूल ग्राफ़ पर उठाकर समस्या का समाधान करता है। इसका रनटाइम है $O(m+\mu n)$, कहाँ $\mu$ इसके मजबूती से जुड़े घटकों के बीच किनारों की संख्या है। हाल के शोध ने MapReduce प्रतिमान के आधार पर वितरित सिस्टम पर ट्रांजिटिव क्लोजर की गणना करने के कुशल तरीकों का पता लगाया है।

यह भी देखें

• पैतृक संबंध
• निगमनात्मक समापन
• प्रतिवर्ती समापन
• सममित समापन
• सकर्मक कमी (आर के सकर्मक समापन के रूप में इसके सकर्मक समापन वाला सबसे छोटा संबंध)

संदर्भ

• 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
• Aho, A. V.; Ullman, J. D. (1979). "Universality of data retrieval languages". Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of programming languages - POPL '79. pp. 110–119. doi:10.1145/567752.567763.
• Benedikt, M.; Senellart, P. (2011). "Databases". In Blum, Edward K.; Aho, Alfred V. (eds.). Computer Science. The Hardware, Software and Heart of It. pp. 169–229. doi:10.1007/978-1-4614-1168-0_10. ISBN 978-1-4614-1167-3.
• Heinz-Dieter Ebbinghaus; Jörg Flum (1999). Finite Model Theory (2nd ed.). Springer. pp. 123–124, 151–161, 220–235. ISBN 978-3-540-28787-2.
• M.J. Fischer and A.R. Meyer (Oct 1971). "Boolean matrix multiplication and transitive closure" (PDF). In Raymond E. Miller and John E. Hopcroft (ed.). Proc. 12th Ann. Symp. on Switching and Automata Theory (SWAT). IEEE Computer Society. pp. 129–131. doi:10.1109/SWAT.1971.4.
• Erich Grädel; Phokion G. Kolaitis; Leonid Libkin; Maarten Marx; Joel Spencer; Moshe Y. Vardi; Yde Venema; Scott Weinstein (2007). Finite Model Theory and Its Applications. Springer. pp. 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 (unpublished manuscript)* Libkin, Leonid (2004), Elements of Finite Model Theory, Springer, ISBN 978-3-540-21202-7
• Lidl, R.; Pilz, G. (1998), Applied abstract algebra, Undergraduate Texts in Mathematics (2nd ed.), Springer, ISBN 0-387-98290-6
• Munro, Ian (Jan 1971). "Efficient determination of the transitive closure of a directed graph". Information Processing Letters. 1 (2): 56–58. doi:10.1016/0020-0190(71)90006-8.
• Nuutila, Esko (1995). Efficient transitive closure computation in large digraphs. Finnish Academy of Technology. ISBN 951-666-451-2. OCLC 912471702.
• Abraham Silberschatz; Henry Korth; S. Sudarshan (2010). Database System Concepts (6th ed.). McGraw-Hill. ISBN 978-0-07-352332-3. Appendix C (online only)

बाहरी संबंध

• "Transitive closure and reduction", The Stony Brook Algorithm Repository, Steven Skiena.