Results 1 to 6 of 6
  1. #1
    Join Date
    May 2009
    Posts
    3

    Question Unanswered: Multiple parents tree (or digraph) implementation

    Hi guys,
    I need to implement a multi-parented tree (or digraph) onto SQL Server 2005.
    I've read several articles, but most of them uses single-parented trees with a unique root like the following one.
    Code:
    -My PC
       -Drive C
          -Documents and Settings
          -Program Files
             -Adobe
             -Microsoft
          -Folder X
       -Drive D
          -Folder Y
          -Folder Z
    In this one, everything derives from a root element (My PC).

    In my case, a child could have more than 1 parent, like the following:
    Code:
    G  A
     \ /
      B
     / \
    X  C
      / \ 
    D   E
      \ /
       F
    So I have the following code:
    Code:
    create table #ObjectRelations
    (
    	Id varchar(20),
    	NextId varchar(20)
    )
    
    insert into #ObjectRelations values ('G', 'B')
    insert into #ObjectRelations values ('A', 'B') 
    insert into #ObjectRelations values ('B', 'C')
    insert into #ObjectRelations values ('B', 'X')
    insert into #ObjectRelations values ('C', 'E') 
    insert into #ObjectRelations values ('C', 'D') 
    insert into #ObjectRelations values ('E', 'F') 
    insert into #ObjectRelations values ('D', 'F') 
    
    declare @id varchar(20)
    set @id = 'A';
    
    WITH Objects (Id, NextId) AS
    ( -- This is the 'Anchor' or starting point of the recursive query
      SELECT rel.Id,
             rel.NextId
        FROM #ObjectRelations rel
       WHERE rel.Id = @id
       UNION ALL -- This is the recursive portion of the query
      SELECT rel.Id,
             rel.NextId
        FROM #ObjectRelations rel
       INNER JOIN Objects -- Note the reference to CTE table name (Recursive Join)
          ON rel.Id = Objects.NextId
    )
    SELECT 	o.*
    FROM	Objects o
    
    drop table #ObjectRelations
    ----------------------------------------
    Which returns the following SET:
    Code:
    Id                   NextId
    -------------------- --------------------
    A                    B
    B                    C
    B                    X
    C                    E
    C                    D
    D                    F
    E                    F
    Expected result SET:
    Code:
    Id                   NextId
    -------------------- --------------------
    G                    B
    A                    B
    B                    C
    B                    X
    C                    E
    C                    D
    D                    F
    E                    F
    Note that the relation G->B is missing, because it asks for an starting object (which doesn't work for me also, because I don't know the root object from the start) and using A as the start point will ignore the G->B relationship.

    So, this code doesn't work in my case because it asks for a starting object, which is obvious in a SINGLE-parent tree (will always be the root object). But in multi-parent tree, you could have more than 1 "root" object (like in the example, G and A are the "root" objects, where root is an object which doesn't have a parent (ancestor)).

    So I'm kind of stucked in here... I need to modify the query to NOT ask for a starting object and recursively traverse the entire tree.
    I don't know if that's possible with the (Id, NextId) implementation... may be I need to store it like a graph using some kind of Incidence matrix, adjacency matrix or whatever (see http://willets.org/sqlgraphs.html).

    Any help? What do you think guys?
    Thank you very much for your time =)

    Cheers!

    Sources:
    http://www.sqlservercentral.com/arti...rver2005/1846/
    http://www.rcs-solutions.com/blog/20...erver2005.aspx
    http://www.experts-exchange.com/Data..._23102605.html
    Last edited by emzero; 05-13-09 at 00:31.

  2. #2
    Join Date
    Nov 2004
    Posts
    1,427
    Provided Answers: 4
    Code:
    WITH Objects (Id, NextId) AS
    ( -- This is the 'Anchor' or starting point of the recursive query
      SELECT rel.Id,
             rel.NextId
        FROM #ObjectRelations rel
    --   WHERE rel.Id = @id
       UNION ALL -- This is the recursive portion of the query
      SELECT rel.Id,
             rel.NextId
        FROM #ObjectRelations rel
       INNER JOIN Objects -- Note the reference to CTE table name (Recursive Join)
          ON rel.Id = Objects.NextId
    )
    SELECT 	distinct o.*
    FROM	Objects o
    With kind regards . . . . . SQL Server 2000/2005/2012
    Wim

    Grabel's Law: 2 is not equal to 3 -- not even for very large values of 2.
    Pat Phelan's Law: 2 very definitely CAN equal 3 -- in at least two programming languages

  3. #3
    Join Date
    Nov 2004
    Posts
    1,427
    Provided Answers: 4
    Even shorter and faster, as you have no root to start from, and just want all relations :
    Code:
    SELECT * 
    FROM #ObjectRelations
    With kind regards . . . . . SQL Server 2000/2005/2012
    Wim

    Grabel's Law: 2 is not equal to 3 -- not even for very large values of 2.
    Pat Phelan's Law: 2 very definitely CAN equal 3 -- in at least two programming languages

  4. #4
    Join Date
    May 2009
    Posts
    3
    Of course is not that simple. In the real case table I'm going to store several graphs, not just 1. A group of objects that are conected and are also child of a common entity in another table (irrelevante for the example) is needed to be treated as 1 graph.

    I was able to get around the problem of multi-parents.
    But now I need to support cycles, let's say A->B->C->A. So I'm going to pick any of those (the way I pick it is irrelevant for the problem) and start traversing from it. The problem is it's getting into a infinite cycle and I just need to get the rows:
    Id NextId
    A B
    B C
    C A

    So I need a way to remember the "way" I'm traversing an check that we're not passsing through an object we've already passed.

    The code I have is the following. It doesn't work because it's stucked in the infinite loop. Any way to get around this?

    Code:
    create table #ObjectRelations
    (
    	Id varchar(20),
    	NextId varchar(20)
    )
    
    insert into #ObjectRelations values ('A', 'B')
    insert into #ObjectRelations values ('B', 'C') 
    insert into #ObjectRelations values ('C', 'A')
    
    /*
    insert into #ObjectRelations values ('G', 'B')
    insert into #ObjectRelations values ('A', 'B') 
    insert into #ObjectRelations values ('B', 'C')
    insert into #ObjectRelations values ('B', 'X')
    insert into #ObjectRelations values ('C', 'E') 
    insert into #ObjectRelations values ('C', 'D') 
    insert into #ObjectRelations values ('E', 'F') 
    insert into #ObjectRelations values ('D', 'F') 
    */
    
    declare @startIds table
    (
    	Id varchar(20) primary key
    )
    
    ;WITH 
    	Ids (Id) AS
    	(
    		SELECT	Id
    		FROM	#ObjectRelations
    	),
    	NextIds (Id) AS
    	(
    		SELECT	NextId
    		FROM	#ObjectRelations
    	)
    INSERT INTO @startIds
    /* This select will not return anything since there are not objects without predecessor, because it's a cyclic of course */
    SELECT DISTINCT
    	Ids.Id
    FROM
    	Ids
    LEFT JOIN
    	NextIds on Ids.Id = NextIds.Id
    WHERE
    	NextIds.Id IS NULL
    UNION
    /* So let's just pick anyone. (the way I will be getting the starting object for a cyclic doesn't matter for the regarding problem)*/
    SELECT TOP 1 Id FROM Ids
    
    ;WITH Objects (Id, NextId, [Level]) AS
    ( -- This is the 'Anchor' or starting point of the recursive query
      SELECT rel.Id,
             rel.NextId,
    		 1
        FROM #ObjectRelations rel
       WHERE rel.Id IN (SELECT Id FROM @startIds)
       UNION ALL -- This is the recursive portion of the query
      SELECT rel.Id,
             rel.NextId,
    		 [Level] + 1
        FROM #ObjectRelations rel
       INNER JOIN Objects -- Note the reference to CTE table name (Recursive Join)
          ON rel.Id = Objects.NextId
    )
    SELECT 	DISTINCT *
    FROM	Objects
    ORDER BY [Level]
    
    drop table #ObjectRelations

  5. #5
    Join Date
    Nov 2004
    Posts
    1,427
    Provided Answers: 4
    Quote Originally Posted by emzero
    Of course is not that simple. In the real case table I'm going to store several graphs, not just 1. A group of objects that are conected and are also child of a common entity in another table (irrelevante for the example) is needed to be treated as 1 graph.
    OK, so your DDL script will look like this:
    Code:
    create table #ObjectRelations
    (
    	Id varchar(20),
    	NextId varchar(20),
    	GraphId INTEGER
    )
    And you will get all nodes for a certain graph with
    Code:
    SELECT * 
    FROM #ObjectRelationscreate table #ObjectRelations AND
    	GraphId  = 1
    Look at the INSERT scripts and the expected result list: they are identical. You don't need any recursion to get that result out of that table.

    I wrote my first SELECT * statement as a joke, but if your real question is exactly as you stated in your first post, you don't need any complex SQL-script. You only need recursion if your question would be: give me a list of all the nodes that are reachable from all the other nodes in a given graph, either directly or indirectly. It would contain, in addition to the list you already created with the INSERT scripts
    Code:
    id     NextId
    ----  -------
    G	F
    A	F
    B	F
    C	F
    X	F
    E	F
    D	F
    G	E
    A	E
    B	E
    C	E
    X	E
    ...
    It doesn't work because it's stucked in the infinite loop. Any way to get around this?
    Try writing it in a stored procedure.
    With kind regards . . . . . SQL Server 2000/2005/2012
    Wim

    Grabel's Law: 2 is not equal to 3 -- not even for very large values of 2.
    Pat Phelan's Law: 2 very definitely CAN equal 3 -- in at least two programming languages

  6. #6
    Join Date
    May 2009
    Posts
    3
    No, I don't have a 'Graph' table with GraphId. A group of objects are in the same Graph is they share some business properties which is not relevant here.

    I came up with this "solution" that seems to work fine so far.
    Based on a Id, NextId (or Id, ParentId, it's the same) table it returns a set of incidences (like an incidence list in graph theory) that tells you which objects points to which objects.
    It needs an start point (one or more than one). It support cyclics (without falling in infinite recursions loops) but is up to you to decide which is the "starting object" in a cycle (in the example is just any of them).

    So here's the query:
    Code:
    create table #ObjectRelations
    (
    	Id varchar(20),
    	NextId varchar(20)
    )
    
    /* Cycle */
    /*
    insert into #ObjectRelations values ('A', 'B')
    insert into #ObjectRelations values ('B', 'C') 
    insert into #ObjectRelations values ('C', 'A')
    */
    
    /* Multi root */
    
    insert into #ObjectRelations values ('G', 'B')
    insert into #ObjectRelations values ('A', 'B') 
    insert into #ObjectRelations values ('B', 'C')
    insert into #ObjectRelations values ('B', 'X')
    insert into #ObjectRelations values ('C', 'E') 
    insert into #ObjectRelations values ('C', 'D') 
    insert into #ObjectRelations values ('E', 'F') 
    insert into #ObjectRelations values ('D', 'F') 
    
    
    declare @startIds table
    (
    	Id varchar(20) primary key
    )
    
    ;WITH 
    	Ids (Id) AS
    	(
    		SELECT	Id
    		FROM	#ObjectRelations
    	),
    	NextIds (Id) AS
    	(
    		SELECT	NextId
    		FROM	#ObjectRelations
    	)
    INSERT INTO @startIds
    /* This select will not return anything since there are not objects without predecessor, because it's a cyclic of course */
    SELECT DISTINCT
    	Ids.Id
    FROM
    	Ids
    LEFT JOIN
    	NextIds on Ids.Id = NextIds.Id
    WHERE
    	NextIds.Id IS NULL
    UNION
    /* So let's just pick anyone. (the way I will be getting the starting object for a cyclic doesn't matter for the regarding problem)*/
    SELECT TOP 1 Id FROM Ids
    
    ;WITH Objects (Id, NextId, [Level], Way) AS
    ( -- This is the 'Anchor' or starting point of the recursive query
      SELECT rel.Id,
             rel.NextId,
    		 1,
    		 CAST(rel.Id as VARCHAR(MAX))
        FROM #ObjectRelations rel
       WHERE rel.Id IN (SELECT Id FROM @startIds)
       UNION ALL -- This is the recursive portion of the query
      SELECT rel.Id,
             rel.NextId,
    		 [Level] + 1,
    		 RecObjects.Way + ', ' + rel.Id
        FROM #ObjectRelations rel
       INNER JOIN Objects RecObjects -- Note the reference to CTE table name (Recursive Join)
          ON rel.Id = RecObjects.NextId
       WHERE RecObjects.Way NOT LIKE '%' + rel.Id + '%'
    		
    )
    SELECT 	DISTINCT 
    		Id,
    		NextId,
    		[Level]
    FROM	Objects
    ORDER BY [Level]
    
    drop table #ObjectRelations

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •