Page 1 of 2 12 LastLast
Results 1 to 15 of 18
  1. #1
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Provided Answers: 54

    Unanswered: Example code for user tree

    One of the users on another web site posted a question about how to associate users in a tree-like organization. That web site isn't well suited to posting code or ongoing discussions about code, so I'm going to post the example here. Feel free to discuss as you see fit.
    Code:
    DROP TABLE LI_UserLinks
    GO
    DROP TABLE LI_Users
    GO
    DECLARE @d1	DATETIME
    ,  @d2		DATETIME
    ,  @d3		DATETIME
    ,  @d4		DATETIME
    ,  @d5		DATETIME
    ,  @d6		DATETIME
    ,  @d7		DATETIME
    ,  @d8		DATETIME
    
    SELECT @d1 = GetDate()
    
    CREATE TABLE LI_Users (
       uid		INT
       PRIMARY KEY (uid)
       )
    
    SELECT @d2 = GetDate()
    
    CREATE TABLE LI_UserLinks (
       uid_from	INT
       CONSTRAINT XFK01LI_UserLinks FOREIGN KEY (uid_from)
          REFERENCES LI_Users (uid)
    ,  uid_to	INT
       CONSTRAINT SFK01LI_UserLinks FOREIGN KEY (uid_to)
          REFERENCES LI_Users (uid)
       CONSTRAINT XPKLI_UserLinks PRIMARY KEY (uid_from, uid_to)
       )
    
    ALTER TABLE LI_Userlinks
       ADD    CONSTRAINT XCK01LI_UserLinks CHECK (uid_from != uid_to)
    
    SELECT @d3 = GetDate()
    
    INSERT INTO LI_Users (
       uid) SELECT n0 + 10 * n1 + 100 * n2 + 1000 * n3 + 10000 * n4 + 100000 * n5
       FROM (SELECT 0 AS n0 UNION SELECT 1 UNION SELECT 2 UNION SELECT 3
          UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7
          UNION SELECT 8 UNION SELECT 9) AS z0
       CROSS JOIN (SELECT 0 AS n1 UNION SELECT 1 UNION SELECT 2 UNION SELECT 3
          UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7
          UNION SELECT 8 UNION SELECT 9) AS z1
       CROSS JOIN (SELECT 0 AS n2 UNION SELECT 1 UNION SELECT 2 UNION SELECT 3
          UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7
          UNION SELECT 8 UNION SELECT 9) AS z2
       CROSS JOIN (SELECT 0 AS n3 UNION SELECT 1 UNION SELECT 2 UNION SELECT 3
          UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7
          UNION SELECT 8 UNION SELECT 9) AS z3
       CROSS JOIN (SELECT 0 AS n4 UNION SELECT 1 UNION SELECT 2 UNION SELECT 3
          UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7
          UNION SELECT 8 UNION SELECT 9) AS z4
       CROSS JOIN (SELECT 0 AS n5 UNION SELECT 1 UNION SELECT 2 UNION SELECT 3
          UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7
          UNION SELECT 8 UNION SELECT 9) AS z5
    
    SELECT @d4 = GetDate()
    
    INSERT INTO LI_UserLinks (
       uid_from, uid_to) SELECT
       uid, 100 * uid + n0 + 10 * n1
       FROM LI_Users
       CROSS JOIN (SELECT 0 AS n0 UNION SELECT 1 UNION SELECT 2 UNION SELECT 3
          UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7
          UNION SELECT 8 UNION SELECT 9) AS z0
       CROSS JOIN (SELECT 0 AS n1 UNION SELECT 1 UNION SELECT 2 UNION SELECT 3
          UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7
          UNION SELECT 8 UNION SELECT 9) AS z1
       WHERE LI_Users.uid BETWEEN 0 AND 99
          AND uid != 100 * uid + n0 + 10 * n1
    
    SELECT @d5 = GetDate()
    
    INSERT INTO LI_UserLinks (
       uid_from, uid_to) SELECT
       uid, 100 * uid + n0 + 10 * n1
       FROM LI_Users
       CROSS JOIN (SELECT 0 AS n0 UNION SELECT 1 UNION SELECT 2 UNION SELECT 3
          UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7
          UNION SELECT 8 UNION SELECT 9) AS z0
       CROSS JOIN (SELECT 0 AS n1 UNION SELECT 1 UNION SELECT 2 UNION SELECT 3
          UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7
          UNION SELECT 8 UNION SELECT 9) AS z1
       WHERE LI_Users.uid BETWEEN 100 AND 9999
    
    SELECT @d6 = GetDate()
    
    SELECT u.uid, r1.uid_to, r2.uid_to
       FROM LI_Users AS u
       INNER JOIN LI_UserLinks AS r1
          ON (r1.uid_from = u.uid)
       INNER JOIN LI_UserLinks AS r2
          ON (r2.uid_from = r1.uid_to)
       WHERE  1 = u.uid
    
    SELECT @d7 = GetDate()
    
    SELECT Count(DISTINCT u.uid), Count(DISTINCT r1.uid_to), Count(distinct r2.uid_to)
       FROM LI_Users AS u
       INNER JOIN LI_UserLinks AS r1
          ON (r1.uid_from = u.uid)
       INNER JOIN LI_UserLinks AS r2
          ON (r2.uid_from = r1.uid_to)
    
    SELECT @d8 = GetDate()
    
    SELECT
       DateDiff(ms, @d1, @d2)
    ,  DateDiff(ms, @d2, @d3)
    ,  DateDiff(ms, @d3, @d4)
    ,  DateDiff(ms, @d4, @d5)
    ,  DateDiff(ms, @d5, @d6)
    ,  DateDiff(ms, @d6, @d7)
    ,  DateDiff(ms, @d7, @d8)
    ,  DateDiff(ms, @d1, @d8)
    -PatP

  2. #2
    Join Date
    Nov 2005
    Posts
    122
    What do you want us to discuss? Where is the description of the problem he/she wants to solve? Is it an organization hierarcy, a family tree?

    Really don't know what to discuss or comment on.

  3. #3
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Provided Answers: 54
    There is no need to discuss anything unless you have something to contribute. I haven't gotten an answer from the other site's management about whether they'll even tolerate cross-site references (some sites object to that as a form of advertising, DBForums is often abused by other sites using posts here to attract new users), so I'll hide the site name for the moment.

    The original question was:
    Quote Originally Posted by David
    I'm trying to come up with a solution on how <<removed by PatP>> stores relationships between users, specifically, how it recognizes, and retrieves the network tree.

    What I'm after is how this happens in the backend, and database. How it says "David is a 2nd tier connection to Joe". I can't seem to come up with any solution that would be scalable.
    I had originally considered using Joe Celko's "nested set" model, but this was simpler, efficient enough for this use, and uses much more common schema and code constructs.

    -PatP

  4. #4
    Join Date
    Nov 2002
    Location
    Jersey
    Posts
    10,322
    Well, that site was easy enough to find using Google
    Brett
    8-)

    It's a Great Day for America everybody!

    dbforums Yak CorralRadio 'Rita
    dbForums Member List
    I'm Good Once as I ever was

    The physical order of data in a database has no meaning.

  5. #5
    Join Date
    Jun 2003
    Location
    Ohio
    Posts
    12,592
    Provided Answers: 1
    My only comment would be that the logic is not recursive.
    If it's not practically useful, then it's practically useless.

    blindman
    www.chess.com: "sqlblindman"
    www.LobsterShot.blogspot.com

  6. #6
    Join Date
    May 2004
    Location
    Seattle
    Posts
    1,313
    the network on that site isn't really a tree, it's a graph where there can be more than one way to get from one node to another. There's no parent-child relationship, just a "we're connected" relationship.

    the trick is to find the *shortest* path to get from one to the other.

    a well known algorithm for this is Djikstra's. Peso has a slick impementation in sql here:

    http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=77262

    although my instinct is this algorithm would be better done in compiled code.

  7. #7
    Join Date
    Nov 2002
    Location
    Jersey
    Posts
    10,322
    Quote Originally Posted by jezemine
    http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=77262

    although my instinct is this algorithm would be better done in compiled code.
    I thought the goal was to get rid of all the developers
    Brett
    8-)

    It's a Great Day for America everybody!

    dbforums Yak CorralRadio 'Rita
    dbForums Member List
    I'm Good Once as I ever was

    The physical order of data in a database has no meaning.

  8. #8
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Provided Answers: 54
    Quote Originally Posted by Brett Kaiser
    Well, that site was easy enough to find using Google
    Yeah, I know that... Until I get the "mother may I" from their admins to link to another site (like here) I'm not going to just lay it out.

    They are relatively new to the question and answer format, and don't really have any good way that I can find to present code. I tend to follow the "ravioli" model for posting and keep things completely contained on one site when I can, but at least to me this problem just itched for a DBForums-like presentation for the solution.

    -PatP

  9. #9
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Provided Answers: 54
    Quote Originally Posted by jezemine
    the trick is to find the *shortest* path to get from one to the other.
    This isn't much of a trick because they only support three levels, and because this is a directed graph it is functionally identical to a tree. Someone of interest to you is either your own direct connection, or a connection of your direct connections... There is no need to search the entire graph because that site limits the search to two levels.

    -PatP

  10. #10
    Join Date
    May 2004
    Location
    Seattle
    Posts
    1,313
    Quote Originally Posted by Brett Kaiser
    I thought the goal was to get rid of all the developers
    without developers, your beloved SQL Server goes away.

    besides, I am a dev.

  11. #11
    Join Date
    May 2004
    Location
    Seattle
    Posts
    1,313
    Quote Originally Posted by Pat Phelan
    This isn't much of a trick because they only support three levels, and because this is a directed graph it is functionally identical to a tree. Someone of interest to you is either your own direct connection, or a connection of your direct connections... There is no need to search the entire graph because that site limits the search to two levels.

    -PatP
    a directed graph is not the same as a tree. trees don't have cycles (unless you are into incest?), but a graph can.

    also here's a current thread on sqlteam on this topic: http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=89323

  12. #12
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Provided Answers: 54
    An unconstrained graph can certainly have cycles, but a directed graph can never have cycles by its definition. Because a directed graph has "direction" and the start node of any link must be nearer the root than the end node of that link, cycles can't happen in a directed graph. That's part of why a directed graph can't have circular links (where a node connects to itself) because the end node must be further from the root than the start node for any given link.

    -PatP

  13. #13
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Provided Answers: 54
    One thought about the code sample that I posted that I do need to add is how to find the "degree of relation". You are in the U alias, your direct connections appear in the R1 alias, and their direct connections (your second level connections) appear in the R2 alias. When checking to see how "close" to you another node in the graph is, check R1 first then check R2 (because it is possible that someone could be both your direct connection as well as an indirect connection (through a common friend).

    -PatP

  14. #14
    Join Date
    May 2004
    Location
    Seattle
    Posts
    1,313
    Quote Originally Posted by Pat Phelan
    An unconstrained graph can certainly have cycles, but a directed graph can never have cycles by its definition. Because a directed graph has "direction" and the start node of any link must be nearer the root than the end node of that link, cycles can't happen in a directed graph. That's part of why a directed graph can't have circular links (where a node connects to itself) because the end node must be further from the root than the start node for any given link.

    -PatP
    a directed graph can certainly have cycles. a directed graph is just a normal graph where you replace the edges by "arcs" where arcs have a direction. edges have no direction.

    see the section here on directed graphs. there's a diagram there of a directed graph with a cycle.
    http://en.wikipedia.org/wiki/Graph_(mathematics)

    if a directed graph has no cycles, then it's called a directed acyclic graph.

    also I don't know what you mean by root. a graph has no root. trees have roots.

  15. #15
    Join Date
    Jun 2003
    Location
    Ohio
    Posts
    12,592
    Provided Answers: 1
    Christmas trees don't have roots.

    Shoe trees don't have roots.
    If it's not practically useful, then it's practically useless.

    blindman
    www.chess.com: "sqlblindman"
    www.LobsterShot.blogspot.com

Posting Permissions

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