View source for सकर्मक समापन

{{Short description|Smallest transitive relation containing a given binary relation}}
{{About|एक द्विआधारी संबंध का सकर्मक समापन|एक सेट का सकर्मक समापन|सकर्मक समुच्चय #सकर्मक समापन}}
  
गणित में, समुच्चय {{mvar|X}} पर [[द्विआधारी संबंध]] {{mvar|R}} का '''सकर्मक समापन''', ''X'' पर सबसे लघु [[संबंध (गणित)]] है इसमें ''R'' सम्मिलित होते है और यह [[सकर्मक संबंध]] होते है। परिमित समुच्चयों के लिए, "सबसे लघु" को उसके सामान्य अर्थ में लिया जा सकता है, जिसमें सबसे कम संबंधित जोड़े होते हैं | अनंत समुच्चयों के लिए यह ''R'' का अद्वितीय [[न्यूनतम तत्व|न्यूनतम अवयव]] सकर्मक '''[[सुपरसेट|उपसम्मुच्य]]''' है।

इस प्रकार से उदाहरण के लिए, यदि {{mvar|X}} हवाई अड्डों का समूह है और {{mvar|x R y}} का अर्थ है "हवाई अड्डे {{mvar|X}} से हवाई अड्डे {{mvar|y}} के लिए सीधी उड़ान है" और ({{mvar|x}} में {{mvar|X}} और {{mvar|y}} के लिए) हैं, तब उस {{math|''x'' ''R''{{sup|+}} ''y''}} का अर्थ है "एक या अधिक उड़ानों में {{mvar|X}} से {{mvar|y}} तक उड़ान भरना संभव होता है"। अनौपचारिक रूप से, ट्रांजिटिव क्लोजर आपको उन सभी स्थानों का समुच्चय देता है जहां आप किसी भी प्रारंभिक स्थान से पहुंच सकते हैं। 

अधिक औपचारिक रूप से, द्विआधारी संबंध का सकर्मक समापन {{mvar|R}} समुच्चय {{mvar|X}} पर सकर्मक संबंध होता है समुच्चय {{math|''R''{{sup|+}}}} पर {{mvar|X}} ऐसा है कि {{math|''R''{{sup|+}}}} रोकना {{mvar|R}} और {{math|''R''{{sup|+}}}} न्यूनतम है | देखना {{harvtxt|लिडल |पिल्ज़|1998|p=337}} हैं. यदि द्विआधारी संबंध स्वयं सकर्मक है, तब सकर्मक समापन वही द्विआधारी संबंध है | अन्यथा, सकर्मक समापन भिन्न संबंध होता है।

इसके विपरीत, [[सकर्मक कमी|संक्रमणीय कमी]] न्यूनतम संबंध {{mvar|S}} से जोड़ती है किन्तु किसी दिए गए संबंध {{mvar|R}} से जैसे कि उनका समापन {{math|1=''S''{{sup|+}} = ''R''{{sup|+}}}} ही है | चूंकि, अनेक भिन्न {{mvar|S}} इस संपत्ति के साथ उपस्तिथ हो सकता है।

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

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

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

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

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

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

अतः परिमित समुच्चयों के लिए, हम ''R'' से प्रारंभ करके और संक्रमणीय किनारों को जोड़कर चरण दर चरण संक्रमणीय समापन का निर्माण कर सकते हैं। चूंकि यह सामान्य निर्माण के लिए अंतर्ज्ञान देता है। किसी भी समुच्चय ''X'', के लिए, हम यह प्रमाणित कर सकते है कि सकर्मक समापन निम्नलिखित अभिव्यक्ति द्वारा दिया गया है |
:<math>R^{+}=\bigcup_{i = 1}^{\infty} R^i.</math>
जहाँ <math>R^i</math> R की ''i''-th पावर है, जिसे आगमनात्मक रूप से परिभाषित किया गया है |
:<math>R^1 = R</math>
और के लिए <math>i>0</math>,
:<math>R^{i+1} = R \circ R^i</math>
जहाँ यह <math>\circ</math> [[संबंधों की संरचना]] को दर्शाता है |

इस प्रकार से यह दर्शाने के लिए कि ''R<sup>+</sup>'' की उपरोक्त परिभाषा ''R'' युक्त सबसे कम सकर्मक संबंध है, हम दिखाते हैं कि इसमें ''R'' सम्मिलित होता है, कि यह सकर्मक है, और यह उन दोनों विशेषताओं के साथ सबसे लघु समुच्चय होता है।

* <math>R \subseteq R^{+}</math>: <math> R^+</math> सभी सम्मिलित हैं <math> R^i</math>, इसलिए विशेष रूप से <math> R^+</math> रोकना <math> R</math>.
* <math> R^{+}</math> सकर्मक है | यदि <math>(s_1, s_2), (s_2, s_3)\in R^+</math>, तब <math>(s_1, s_2)\in R^j</math> और <math>(s_2, s_3)\in R^k</math> कुछ के लिए <math>j,k</math> की परिभाषा के अनुसार <math>R^+</math>. चूँकि रचना साहचर्य है, <math>R^{j+k} = R^j \circ R^k</math>; इस तरह <math>(s_1, s_3)\in R^{j+k} \subseteq R^+</math> की परिभाषा के अनुसार <math>\circ</math> और <math>R^+</math> 
* <math>R^{+}</math> न्यूनतम है, अर्थात यदि <math>T</math> कोई सकर्मक संबंध युक्त है <math>R</math>, तब <math>R^{+} \subseteq T</math> हैं | ऐसा कोई दिया गया <math>T</math>, [[गणितीय प्रेरण]] पर <math>i</math> दिखाने के लिए उपयोग किया जा सकता है <math>R^i\subseteq T</math> सभी के लिए <math>i</math> इस प्रकार: आधार: <math>R^1 = R \subseteq T</math> अनुमान से चरण: यदि <math>R^i\subseteq T</math> धारण करता है, और <math>(s_1, s_3)\in R^{i+1} = R \circ R^i</math>, तब <math>(s_1, s_2) \in R</math> और <math>(s_2, s_3)\in R^i</math> कुछ के लिए <math>s_2</math>, की परिभाषा के अनुसार <math>\circ</math>. इस तरह, <math>(s_1, s_2), (s_2, s_3)\in T</math> धारणा द्वारा और प्रेरण परिकल्पना द्वारा होती हैं। इस तरह <math>(s_1, s_3)\in T</math> की परिवर्तनशीलता द्वारा <math>T</math> हैं | यह प्रेरण पूरा करता है। इस प्रकार से , <math>R^i\subseteq T</math> सभी के लिए <math>i</math> तात्पर्य <math>R^{+} \subseteq T</math> की परिभाषा <math>R^{+}</math> के अनुसार .

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

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

== ग्राफ़ सिद्धांत में ==
[[File:Transitive-closure.svg|thumb|right|alt=Transitive closure constructs the output graph from the input graph.|ट्रांसिटिव क्लोजर इनपुट ग्राफ से आउटपुट ग्राफ का निर्माण करता है।]]इस प्रकार से [[कंप्यूटर विज्ञान]] में, ट्रांजिटिव क्लोजर की अवधारणा को डेटा संरचना के निर्माण के रूप में विचार किया जा सकता है जोकी [[गम्यता]] प्रश्नों का उत्तर देना संभव बनाता है। अर्थात , क्या कोई या अधिक हॉप्स में नोड ''A'' से नोड ''d'' तक पहुंच सकता है? द्विआधारी संबंध आपको केवल यह बताता है कि नोड ''A'' नोड ''b'' से जुड़ा है, और वह नोड ''b'' नोड सी से जुड़ा है, आदि। ट्रांजिटिव क्लोजर के निर्माण के पश्चात , जैसा कि निम्नलिखित चित्र में दर्शाया गया है,O(1) में ) ऑपरेशन यह निर्धारित कर सकता है कि नोड ''d'' नोड ''a'' से पहुंच योग्य है। डेटा संरचना को सामान्यतः बूलियन आव्युह के रूप में संग्रहीत किया जाता है, इसलिए यदि आव्युह [1] [4] = सत्य है, तब यह स्तिथि है कि नोड 1 या अधिक हॉप्स के माध्यम से नोड 4 तक पहुंच सकता है।

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

[[File:Equivalentie.svg|thumb|[[क्लस्टर ग्राफ़]], अप्रत्यक्ष ग्राफ़ का सकर्मक समापन]][[अप्रत्यक्ष ग्राफ]] का सकर्मक समापन क्लस्टर ग्राफ़ उत्पन्न करता है, जोकी क्लिक (ग्राफ़ सिद्धांत) के ग्राफ़ का असंयुक्त संघ है। ट्रांजिटिव क्लोजर का निर्माण ग्राफ के [[घटक (ग्राफ सिद्धांत)]] को खोजने की समस्या का समतुल्य सूत्रीकरण है।<ref>{{citation
 | last1 = McColl | first1 = W. F.
 | last2 = Noshita | first2 = K.
 | doi = 10.1016/0166-218X(86)90020-X
 | issue = 1
 | journal = [[Discrete Applied Mathematics]]
 | mr = 856101
 | pages = 67–73
 | title = On the number of edges in the transitive closure of a graph
 | volume = 15
 | year = 1986}}</ref>
== तर्क और कम्प्यूटेशनल स्पष्टतामें ==
इस प्रकार से किसी द्विआधारी संबंध का सकर्मक समापन, सामान्य तौर पर, [[प्रथम-क्रम तर्क]] (एफओ) में व्यक्त नहीं किया जा सकता है।

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

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

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

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

== डेटाबेस क्वेरी भाषाओं में ==
{{further|SQL में पदानुक्रमित और पुनरावर्ती क्वेरीज़}}

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

इस प्रकार से [[ संगणक वैज्ञानिक |संगणक वैज्ञानिक]] ट्रांजिटिव क्लोजर गणनाओं को भी प्रयुक्त करता है। <ref>(Silberschatz et al. 2010:C.3.6)</ref>

[[MariaDB|मारियाडीबी]] रिकर्सिव कॉमन टेबल एक्सप्रेशन प्रयुक्त करता है, जिसका उपयोग ट्रांजिटिव क्लोजर की गणना करने के लिए किया जा सकता है। यह सुविधा अप्रैल 2016 की रिलीज़ 10.2.2 में उपस्तिथ की गई थी। <ref>{{cite web| title=पुनरावर्ती सामान्य तालिका अभिव्यक्तियाँ अवलोकन| url=https://mariadb.com/kb/en/recursive-common-table-expressions-overview/| publisher=mariadb.com}}</ref>
== एल्गोरिदम ==
इस प्रकार से ग्राफ़ के आसन्न संबंध के सकर्मक समापन की गणना के लिए कुशल एल्गोरिदम यहां पाए जा सकते हैं | यह {{harvtxt|नुउटिला|1995}}. आसन्न आव्युह के गुणन की समस्या को कम करने से न्यूनतम उपलब्धि प्राप्त होती है समय जटिलता, अर्थात। [[मैट्रिक्स गुणन|आव्युह गुणन]] ({{harvnb|मुनरो|1971}}, {{harvnb|फिशर|मेयेर|1971}}) हैं, जो <math>O(n^{2.3728596})</math> {{as of|2020|12|lc=y}}. चूंकि , यह दृष्टिकोण व्यावहारिक नहीं है क्योंकि विरल ग्राफ़ के लिए स्थिर कारक और मेमोरी खपत दोनों अधिक होता हैं | यह {{harv|नुउटिला|1995|pp=22–23|loc=sect.2.3.3}} हैं. समस्या का फ़्लॉइड-वॉर्शल एल्गोरिथम <math>O(n^3)</math>, द्वारा भी समाधान किया जा सकता है या ग्राफ़ के प्रत्येक नोड से प्रारंभ होने वाली बार-बार चौड़ाई-पहली खोज या [[गहराई-पहली खोज]] द्वारा किया गया था।

इस प्रकार से निर्देशित ग्राफ़ के लिए, पर्डोम का एल्गोरिदम पहले इसके संक्षेपण डीएजी और इसके संक्रमणीय समापन की गणना करके, पुनः इसे मूल ग्राफ़ पर उठाकर समस्या का समाधान करता है। इसका रनटाइम <math>O(m+\mu n)</math> है , जहाँ <math>\mu</math> इसके कठोरता से जुड़े घटकों के मध्य किनारों की संख्या है।<ref name=Purdom>{{cite journal | doi=10.1007/BF01940892 | url= | first=Paul |last=Purdom Jr. | title=एक सकर्मक समापन एल्गोरिथ्म| journal=[[BIT Numerical Mathematics]] | volume=10 | number=1 | pages=76&ndash;94 | date=Mar 1970 }}</ref><ref>{{cite report | url=https://minds.wisconsin.edu/handle/1793/57514 | author=Paul W. Purdom Jr. | title=एक सकर्मक समापन एल्गोरिथ्म| institution=[[University of Wisconsin-Madison]] | type=Computer Sciences Technical Report | volume=33 | date=Jul 1968 }}</ref><ref>{{cite web
| url=https://algowiki-project.org/algowiki/en/index.php?title=Purdom%27s_algorithm&oldid=10286
| title="Purdom's algorithm" on AlgoWiki}}</ref><ref>{{cite web
| url=https://algowiki-project.org/algowiki/en/index.php?title=Transitive_closure_of_a_directed_graph&oldid=1475
| title="Transitive closure of a directed graph" on AlgoWiki}}</ref>

वर्तमान में शोध ने [[MapReduce|मैपरेडइयूस]] प्रतिमान के आधार पर वितरित सिस्टम पर ट्रांजिटिव क्लोजर की गणना करने के कुशल विधियों का पता लगाया है।<ref>(Afrati et al. 2011)</ref>
== यह भी देखें ==
*[[पैतृक संबंध]]
* [[निगमनात्मक समापन]]
* [[ प्रतिवर्ती समापन ]]
* [[सममित समापन]]
* सकर्मक कमी ( सबसे लघु संबंध जिसमें ''R'' का सकर्मक समापन इसके सकर्मक समापन के रूप में होता है)

== संदर्भ ==
{{Reflist}}
* Foto N. Afrati, Vinayak Borkar, Michael Carey, Neoklis Polyzotis, Jeffrey D. Ullman, [https://web.archive.org/web/20140810063150/http://www.edbt.org/Proceedings/2011-Uppsala/papers/edbt/a1-afrati.pdf Map-Reduce Extensions and Recursive Queries], EDBT 2011, March 22–24, 2011, Uppsala, Sweden, {{isbn|978-1-4503-0528-0}}
* {{Cite book | last1 = Aho | first1 = A. V. | last2 = Ullman | first2 = J. D. | doi = 10.1145/567752.567763 | chapter = Universality of data retrieval languages | title = Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of programming languages - POPL '79 | pages = 110–119 | year = 1979 }}
* {{Cite book | last1 = Benedikt | first1 = M. | last2 = Senellart | first2 = P. | doi = 10.1007/978-1-4614-1168-0_10 | chapter = Databases | title = Computer Science. The Hardware, Software and Heart of It| pages = 169–229| year = 2011 | isbn = 978-1-4614-1167-3 | editor1-last = Blum| editor1-first = Edward K.| editor2-last = Aho| editor2-first = Alfred V. }}
* {{cite book|author1=Heinz-Dieter Ebbinghaus|author2=Jörg Flum|title=Finite Model Theory|url=https://archive.org/details/finitemodeltheor0000ebbi|url-access=registration|year=1999|publisher=Springer|isbn=978-3-540-28787-2|edition=2nd|pages=[https://archive.org/details/finitemodeltheor0000ebbi/page/123 123]–124, 151–161, 220–235}}
* {{cite conference | doi=10.1109/SWAT.1971.4 | contribution-url=http://mercury.pr.erau.edu/~siewerts/cs332/documents/Papers/Transitive-Closure/Transitive-Closure-with-Boolean-Matrices.pdf | author=M.J. Fischer and A.R. Meyer | contribution=Boolean matrix multiplication and transitive closure | editor=Raymond E. Miller and John E. Hopcroft | title=Proc. 12th Ann. Symp. on Switching and Automata Theory (SWAT) | publisher=IEEE Computer Society | pages=129&ndash;131 | date=Oct 1971 }} 
* {{cite book|author1=Erich Grädel|author2=Phokion G. Kolaitis|author3=Leonid Libkin |author4=Maarten Marx |author5=Joel Spencer |author6=Moshe Y. Vardi |author7=Yde Venema |author8=Scott Weinstein|title=Finite Model Theory and Its Applications|year=2007|publisher=Springer|isbn=978-3-540-68804-4|pages=151–152}}
* Keller, U., 2004, ''[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.127.8266 Some Remarks on the Definability of Transitive Closure in First-order Logic and Datalog]'' (unpublished manuscript)* {{citation|first=Leonid|last=Libkin|author-link=Leonid Libkin|title=Elements of Finite Model Theory|year=2004|publisher=Springer|isbn=978-3-540-21202-7|url-access=registration|url=https://archive.org/details/elementsoffinite00libk}}
* {{citation|last1=Lidl|first1= R.|last2=Pilz|first2=G.|year=1998|title=''Applied abstract algebra''|edition=2nd|series= [[Undergraduate Texts in Mathematics]]|publisher= Springer|isbn=0-387-98290-6}}
* {{cite journal|last=Munro| first=Ian | doi=10.1016/0020-0190(71)90006-8 | url=   | title=Efficient determination of the  transitive closure of a directed graph | journal=Information Processing Letters | volume=1 | number=2 | pages=56&ndash;58 | date=Jan 1971 }} 
* {{Cite book|last=Nuutila|first=Esko|url=http://worldcat.org/oclc/912471702|title=Efficient transitive closure computation in large digraphs|date=1995|publisher=Finnish Academy of Technology|isbn=951-666-451-2|oclc=912471702}}
* {{cite book|author1=Abraham Silberschatz|author2=Henry Korth|author3=S. Sudarshan|title=Database System Concepts|year=2010|edition=6th|publisher=McGraw-Hill|isbn=978-0-07-352332-3|title-link=Database System Concepts}} [http://codex.cs.yale.edu/avi/db-book/db6/appendices-dir/c.pdf Appendix C] (online only)

== बाहरी संबंध ==
* "[http://www.cs.sunysb.edu/~algorith/files/transitive-closure.shtml Transitive closure and reduction]", The Stony Brook Algorithm Repository, Steven Skiena.

[[Category:All articles containing potentially dated statements]]
[[Category:Articles containing potentially dated statements from December 2020]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:Created On 27/06/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:ग्राफ़ एल्गोरिदम]]
[[Category:द्विआधारी संबंध]]
[[Category:बंद करने वाले ऑपरेटर]]