ग्राफ समस्याएं: SQL सर्वर में NOCYCLE पूर्व प्रतिस्थापन से कनेक्ट करें?

Question

प्रश्न:

मैं निम्नलिखित (निर्देशित) ग्राफ है:

और इस तालिका:

CREATE TABLE [dbo].[T_Hops](
    [UID] [uniqueidentifier] NULL, 
    [From] [nvarchar](1000) NULL, 
    [To] [nvarchar](1000) NULL, 
    [Distance] [decimal](18, 5) NULL 
) ON [PRIMARY] 

GO 

और यह सामग्री:

 INSERT INTO [dbo].[T_Hops]    ([UID]    ,[From]    ,[To]    ,[Distance])  VALUES    (newid()    ,'A'    ,'E'    ,10.00000    ); 
     INSERT INTO [dbo].[T_Hops]    ([UID]    ,[From]    ,[To]    ,[Distance])  VALUES    (newid()    ,'E'    ,'D'    ,20.00000    ); 
     INSERT INTO [dbo].[T_Hops]    ([UID]    ,[From]    ,[To]    ,[Distance])  VALUES    (newid()    ,'A'    ,'B'    ,5.00000    ); 
     INSERT INTO [dbo].[T_Hops]    ([UID]    ,[From]    ,[To]    ,[Distance])  VALUES    (newid()    ,'B'    ,'C'    ,10.00000    ); 
     INSERT INTO [dbo].[T_Hops]    ([UID]    ,[From]    ,[To]    ,[Distance])  VALUES    (newid()    ,'C'    ,'D'    ,5.00000    ); 
     INSERT INTO [dbo].[T_Hops]    ([UID]    ,[From]    ,[To]    ,[Distance])  VALUES    (newid()    ,'A'    ,'F'    ,2.00000    ); 
     INSERT INTO [dbo].[T_Hops]    ([UID]    ,[From]    ,[To]    ,[Distance])  VALUES    (newid()    ,'F'    ,'G'    ,6.00000    ); 
     INSERT INTO [dbo].[T_Hops]    ([UID]    ,[From]    ,[To]    ,[Distance])  VALUES    (newid()    ,'G'    ,'H'    ,3.00000    ); 
     INSERT INTO [dbo].[T_Hops]    ([UID]    ,[From]    ,[To]    ,[Distance])  VALUES    (newid()    ,'H'    ,'D'    ,1.00000    ); 

अब मैं क्वेरी कर सकता है पॉइंट एक्स से पॉइंट वाई से सबसे अच्छा कनेक्शन इस तरह:

WITH AllRoutes 
(
    [UID] 
    ,[FROM] 
    ,[To] 
    ,[Distance] 
    ,[Path] 
    ,[Hops] 
) 
AS 
(
    SELECT 
     [UID] 
     ,[FROM] 
     ,[To] 
     ,[Distance] 
     ,CAST(([dbo].[T_Hops].[FROM] + [dbo].[T_Hops].[To]) AS varchar(MAX)) AS [Path] 
     ,1 AS [Hops] 
     FROM [dbo].[T_Hops] 
     WHERE [FROM] = 'A' 

    UNION ALL 


    SELECT 
     [dbo].[T_Hops].[UID] 
     --,[dbo].[T_Hops].[FROM] 
     ,Parent.[FROM] 
     ,[dbo].[T_Hops].[To] 
     ,CAST((Parent.[Distance] + [dbo].[T_Hops].[Distance]) AS [decimal](18, 5)) AS distance 
     ,CAST((Parent.[Path] + '/' + [dbo].[T_Hops].[FROM] + [dbo].[T_Hops].[To]) AS varchar(MAX)) AS [Path] 
     ,(Parent.[Hops] + 1) AS [Hops] 
    FROM [dbo].[T_Hops] 

    INNER JOIN AllRoutes AS Parent 
      ON Parent.[To] = [dbo].[T_Hops].[FROM] 

) 

SELECT TOP 100 PERCENT * FROM AllRoutes 


/* 
WHERE [FROM] = 'A' 
AND [To] = 'D' 
AND CHARINDEX('F', [Path]) != 0 -- via F 
ORDER BY Hops, Distance ASC 
*/ 

GO 

अब मैं उस के लिए मैं, उदाहरण के लिए, यह भी एक

के लिए डी से पथ मैं एक सबसे सरल परिवर्तन के साथ शुरू, और सिर्फ विज्ञापन विपरीत दिशा प्राप्त कर सकते हैं एक अनिर्दिष्ट ग्राफ बनाना चाहते हैं, एचडी के लिए

INSERT INTO [dbo].[T_Hops] 
      ([UID] 
      ,[From] 
      ,[To] 
      ,[Distance]) 
    VALUES 
      (newid() --<UID, uniqueidentifier,> 
      ,'D' --<From, nvarchar(1000),> 
      ,'H' --<To, nvarchar(1000),> 
      ,1 --<Distance, decimal(18,5),> 
      ) 
GO 

अब, के रूप में उम्मीद, मेरी क्वेरी एक अपवाद फेंकता है:

अनंत प्रत्यावर्तन/अधिकतम प्रत्यावर्तन स्तर (100) को पार कर

क्योंकि संभव कनेक्शन की संख्या अब अनंत है।

अब ओरेकल में आप एक पेड़ के बजाय "पहले से कनेक्ट" के साथ एक ही काम करते हैं। और अगर एक चक्र समस्या (अनंत प्रत्यावर्तन) संभव है, तो आप सिर्फ NOCYCLE पहले से कनेक्ट करने के लिए जोड़कर जोड़ने, यह "बंधन द्वारा NOCYCLE पहले"

अब MS-एसक्यूएल में, मुझे लगता है कि व्यवहार तय:

AND Parent.[Path] NOT LIKE '%' + [dbo].[T_Hops].[FROM] + '/%' 

आंतरिक शामिल खंड में, अनिवार्य रूप से NOCYCLE अनुकरण।

हालांकि

, के रूप में की तरह मूल रूप से strstr (या बुरा strcasestr) है, और इस तरह अधिकतम माता पिता तत्वों की एक सरणी, मैं प्रदर्शन के बारे में अत्यंत चिंतित हूँ जाँच की तुलना में धीमी।

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

किसी और के पास एमएस एसक्यूएल में NOCYCLE को प्रतिस्थापित करने का तरीका बेहतर (= तेज) तरीका है?

या यह वह बिंदु है जहां मेरे पास बस कोई अन्य विकल्प नहीं है लेकिन ओरेकल पर स्विच करना (स्वीकार्य गति में ऐसा करने के लिए)?

नोट: किसी भी अस्थायी तालिकाओं (डेटा की बड़ी राशि) समाधान धीमी, होगा, क्योंकि अस्थायी तालिकाओं HardDisk को लगा दिया हो जाएगा, जब पर्याप्त रैम (निरपेक्ष निश्चितता) नहीं है।

फ़ंक्शन और तालिका-मूल्यवान कार्यों का उपयोग करके किसी भी समाधान के लिए चला जाता है।

Answer 1

एक स्थायी तालिका में नोड्स के बीच चयन प्रदर्शन की दुकान संभव पथ में सुधार करने के

TABLE T_Hops_Path 
(
    FromNode, 
    ToNode, 
    HopCount, 
    TotalDistance 
) 

अपने वृक्ष संरचना अक्सर परिवर्तन नहीं करता है, तो आप एक संग्रहीत प्रक्रिया है कि इस तालिका हर एन घंटे उत्पन्न करता है लिख सकते हैं।