सकर्मक समापन

This article is about एक द्विआधारी संबंध का सकर्मक समापन. For एक सेट का सकर्मक समापन, see सकर्मक समुच्चय § सकर्मक समापन.

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

इस प्रकार से उदाहरण के लिए, यदि X हवाई अड्डों का एक समूह है और x R y का अर्थ है "हवाई अड्डे X से हवाई अड्डे y के लिए सीधी उड़ान है" (x में X और y के लिए), तो उस 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 के पश्चात सप्ताह का दिन है"। इस संबंध का सकर्मक समापन "कुछ दिन x कैलेंडर पर एक दिन y के पश्चात आता है" है, जो सप्ताह के सभी दिनों x और y के लिए तुच्छ रूप से सत्य है (और इस प्रकार कार्टेशियन वर्ग के समान है, जो कि "x और y हैं सप्ताह के दोनों दिन")।

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

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

अतः परिमित समुच्चयों के लिए, हम R से प्रारंभ करके और संक्रमणीय किनारों को जोड़कर चरण दर चरण संक्रमणीय समापन का निर्माण कर सकते हैं।

चूंकि यह सामान्य निर्माण के लिए अंतर्ज्ञान देता है। किसी भी समुच्चय X, के लिए, हम

यह प्रमाणित कर सकता है कि सकर्मक समापन निम्नलिखित अभिव्यक्ति द्वारा दिया गया है

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

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

$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^{+}$ के अनुसार .

गुण

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

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

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

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

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

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

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

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

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

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

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

कोई भी मॉडल यदि और केवल यदि T, R का सकर्मक समापन है।

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

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

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

Further information: SQL में पदानुक्रमित और पुनरावर्ती क्वेरीज़

1980 के दशक से आकाशवाणी डेटाबेस ने मालिकाना एसक्यूएल एक्सटेंशन प्रयुक्त किया है CONNECT BY... START WITH यह घोषणात्मक क्वेरी के भाग के रूप में सकर्मक समापन की गणना की अनुमति देता है। एसक्यूएल 3 (1999) मानक ने और अधिक सामान्य जोड़ा WITH RECURSIVE निर्माण क्वेरी प्रोसेसर के अंदर ट्रांजिटिव क्लोजर की गणना करने की भी अनुमति देता है; 2011 तक पश्चात वाले को आईबीएम डीबी2, माइक्रोसॉफ्ट एसक्यूएल सर्वर, आकाशवाणी डेटाबेस, पोस्टग्रेएसक्यूएल और माई एसक्यूएल (v8.0+) में प्रयुक्त किया गया है। और एसक्यूलाइट ने 2014 में इसके लिए समर्थन उपयोग किया गया था ।

इस प्रकार से संगणक वैज्ञानिक ट्रांजिटिव क्लोजर गणनाओं को भी प्रयुक्त करता है।

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

एल्गोरिदम

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

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

वर्तमान में शोध ने मैपरेडइयूस प्रतिमान के आधार पर वितरित सिस्टम पर ट्रांजिटिव क्लोजर की गणना करने के कुशल विधियों का पता लगाया है।

यह भी देखें

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

संदर्भ

• 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.