SitePoint Sponsor

User Tag List

Page 2 of 6 FirstFirst 123456 LastLast
Results 26 to 50 of 141
  1. #26
    SitePoint Member
    Join Date
    Jan 2005
    Location
    Moorhead
    Posts
    0
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    I was just browsing around and found this article. Great theories but why would you ever want to store hierarchical data in a flat database? Unless of course it was the only choice you had it seems like a bad idea to me. The first way takes too much system resources and the second has to have the tree rebuilt everytime you add a row to the table. Icky. I'd say this is the perfect situation for an XML database. An article that explores the XML database options for heirarchical data and php would be a great companion for this article. Anyone know of a good one?

  2. #27
    Non-Member
    Join Date
    Jan 2003
    Posts
    5,748
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    XML does have it's uses, though in your point you could query the XML with XPATH though you'd be limited to that given data within the XML file, whereas you couldn't (easily) query the data in one XML file against another one, suchas product catelog and products.

    Two seperate though interwinded entities that is where the database has the upperhand... relational data in other words.

    On your last question, XML is a great technology... For distribution but not for performing queries. There are a number of XML databases out there, but I cannot see any benifit of using one over a relational database if all your going to do is to perform lookups/queries

  3. #28
    Courtney Miles
    SitePoint Community Guest
    The Modified Preorder Tree Traversal method solves a lot of the problems of the Adjacency list model but it also has a few of it's own.

    When using a tree as the navigation of a website (or folders in Windows Explorer) you rarely see all branches of the tree at once. Rather, just the current node, child nodes, parent node, parent-siblings and so on back to root. So using food as an example, if the current node is Red you would see Food > Meat|Fruit > Yellow|Red > Cheery.

    This isn't easy to do using the Adjacency list model either. But with the Adjacency list model you can easily query the children of a node (without getting grand children) and the siblings of a node. I can't see how to query the same with the traversal method so I will probably use a combination of the two methods unless someone can enlighten me.

  4. #29
    Sebastian Picklum
    SitePoint Community Guest
    @Courtney Miles: Explorer-Style? That can be done quite simply using the same technique.

    First of all, you have to create Node-Groups. In our example case there would be the Groups (Food) (Fruit, Meat) (Red, Yellow) (Cherry) (Banana) (Beef, Pork).
    Now add two more variables (e.g. "GroupLft" and "GroupRgt") to the database and use the Tree Traversal on the groups.
    In our example, this would result in
    1(Food)12 2(Fruit, Meat)11 3(Red, Yellow)8 4(Cherry)5 6(Banana)7 9(Beef, Pork)10
    Your DB should now look like this
    Name,Lft,Rgt,GroupLft,GroupRgt
    ================================
    Food,1,18,1,12
    Fruit,2,11,2,11
    Meat,12,17,2,11
    Red,3,6,3,8
    Yellow,7,10,3,8
    Cherry,4,5,4,5
    Banana,8,9,6,7
    and so on...

    When you now Query "Cherry" by its Lft+Rgt-Values, you'll get the path. Querying by GroupLft+GroupRgt will get you a nice basement to build an "Explorer-Style"-menu.

    About only getting children and _not_ grandchildren: Simply introduce a "depth" field. E.g.
    Food=depth 0
    Fruit,Meat=1
    Red,Yellow,Beef,Pork=2

    In combination with Lft and Rgt you are now able to choose how many "generations" of children you want to fetch.
    (e.g. finding Children of Fruit, but not Grandchildren: SELECT * WHERE Lft>2 AND Rgt<11 AND Depth=(Depth_of_Fruit+1))


  5. #30
    Hendrix
    SitePoint Community Guest
    In response to Courtney's comment above. If you add an extra field called level, then you can find children by searching within the left/right values that a level of level + 1.

    To find siblings you can just find all nodes with the same parent ID

    There is an article about this here:

    http://www.phpriot.com/d/articles/php/application-design/nested-trees-1/index.html


  6. #31
    SitePoint Member
    Join Date
    Mar 2005
    Posts
    1
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    immediate children

    Using postgresql for a hierarchy, and I came up with this to find the immediate children of a node. Assuming that the parent node has:
    nodeleft = $L
    noderght = $R
    HTML Code:
    <pre>
    SELECT * FROM node AS a 
        INNER JOIN node AS b ON a.nodeid=b.nodeid 
        WHERE a.nodeleft>$L AND a.noderght<$R 
            AND (SELECT COUNT(nodeid) FROM node WHERE nodeleft<=b.nodeleft AND noderght>=b.noderght)=(SELECT COUNT(nodeid) FROM node WHERE nodeleft<=$L AND noderght>=$R)+1
        ORDER BY a.nodeleft ASC;
    </pre>
    First we have a table of all the children. In a separate table, we finds all nodes that are one level deeper than the parent node. We do this by first retrieving the path to the root, then counting the records in that path. Then it returns the common nodes of the two tables.

    I don't know enough about PostgreSQL's internals to know how optimal this operation is. For a small number of nodes, it's trivial, but it would take a significant amount of time on a large set if PostgreSQL isn't smart enough to satisfy the first table first, which would significantly reduce the result set that it has to look at.

    I haven't tried Weirdan's method (mentioned above) yet, because I don't understand it. If anyone has better, please post it.

  7. #32
    S
    SitePoint Community Guest
    This code simply doesn't work for me ...

  8. #33
    SitePoint Enthusiast
    Join Date
    Jan 2005
    Location
    Rome
    Posts
    77
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Very nice article. Thanks fo even just making me think again today. :)

  9. #34
    Peter
    SitePoint Community Guest
    Unfortunately, the method described in this article is incredibly inefficient.

  10. #35
    SitePoint Member
    Join Date
    Apr 2005
    Location
    Sydney, Australia
    Posts
    8
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    can someone list a practival use for this?
    and explain why its inneficient

  11. #36
    SitePoint Member
    Join Date
    Apr 2005
    Posts
    3
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Hi ! .. I would like to know how could I make a node that would have many parents ...

    Let's say I have this:

    fruits
    Apples
    Oranges
    Strawberry
    Colored food
    Red
    Apples ( I want this to link to the other Apples )
    Orange
    Oranges (Same thing)
    Black

    How can I do that ? I'm really having a hard time trying to figure this out ! ... It must be me !

  12. #37
    w31rd0
    SitePoint Community Guest
    annweb,
    By your description I understand you need to have two trees?
    Or... you may need to add an extra property for every node (color property).

    You can contact me on Y!M by sebastianvasile, I'll try to give you a hand.

    Regards

  13. #38
    SitePoint Member
    Join Date
    Apr 2005
    Posts
    3
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Thanks w31rd0 !

    But I found a way, about a week ago on how to do it with one table ... I just create a "ghost" category that will link to "apple" (for example) and that ghost category will be empty ... Then with a good MySQL headscratching command I call the actual apple category instead of the ghost !

    Neet huh ! ?

    Well I think it's neet !

  14. #39
    SitePoint Member
    Join Date
    May 2005
    Posts
    16
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Hi!

    I would like to know how can I display my tree in a horizontal way just like the sample image used in the topic Modified Preorder Tree Traversal.

    just like this image without the numbers:
    Last edited by hubster; May 5, 2005 at 01:29.

  15. #40
    SitePoint Member
    Join Date
    Apr 2005
    Posts
    3
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Hello hubster !

    I've decided to post the reply in the forum so that maybe it can help somebody else too !

    Okay:

    #1 You need to create a column in the table that you can call "link" and that column will be NULL for entries that have no link or will contain the ID of the entry that it's linked to.

    Example:
    ID|name|left|right|LINK
    1|fruit|1|12|NULL
    2|red|2|7|NULL
    3|apple|3|4|NULL
    4|strawberry|5|6|NULL
    5|Delicious|8|11|NULL
    6|GHOST LINKED TO STRAWBERRY|9|10|4


    so this way you have
    fruit
    red
    apple
    strawberry
    delicious
    LINK TO STRAWBERRY


    Then you need that magic MySQL command that gave me a 2 weeks headache:

    SELECT table1.*, table2.link as link
    FROM food as table1
    LEFT JOIN food as table2
    ON table1.id=table2.link
    WHERE table1.link IS NULL
    GROUP BY table1.id
    ORDER BY table1.name

    Will give you :

    id name left right link link
    0000003 apple 3 4 NULL NULL
    0000005 delicious 8 11 NULL NULL
    0000001 fruit 1 12 NULL NULL
    0000002 red 2 7 NULL NULL
    0000004 strawberry 5 6 NULL 4

    Notice that you the category "Strawberry" but not the "Ghost category"

    So that was my big pain for the last 2 weeks o if you use this code, don't be shy to give me credit for it !

    I hope it was a good explanation !
    Last edited by annweb; May 5, 2005 at 09:43.

  16. #41
    SitePoint Member
    Join Date
    May 2005
    Posts
    0
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    I have been experimenting using the Modified Preorder Tree Traversal example on sitepoint.

    http://www.sitepoint.com/article/hie...-data-database

    Food
    Fruit
    Red
    Cherry
    Strawberry
    Yellow
    Banana
    Meat
    Beef
    Pork

    I was wondering if i could use this example to create a list <ul><li> etc for the output, but then I realised it was a bit more complex than I first thought.

    Any thoughts

  17. #42
    SitePoint Member
    Join Date
    May 2005
    Posts
    10
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Multiple trees

    Nice article. How might you store multiple independent trees? I'd like to avoid introducing a grouping field as it would make moving items between trees messy, plus surely much of the point is that which tree an item belongs to is implicit in knowing who its parent is. What's more, my trees don't have any semantic value - they are merely unnamed hierarchical collections with equal status. At present I have the obvious adjacency setup where independent trees are easily identified as they all start with items whose parent id is 0/NULL. Moving items between trees is trivial - just change the parent id pointer in the appropriate child. As far as I can see, the only way to handle this with preordering is to rebuild the two trees involved in their entirety, which can't be efficient. How can I parallel these operations using the preorder approach?

  18. #43
    SitePoint Addict
    Join Date
    Mar 2005
    Posts
    231
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by owarnes
    I have been experimenting using the Modified Preorder Tree Traversal example on sitepoint.

    http://www.sitepoint.com/article/hie...-data-database

    Food
    Fruit
    Red
    Cherry
    Strawberry
    Yellow
    Banana
    Meat
    Beef
    Pork

    I was wondering if i could use this example to create a list <ul><li> etc for the output, but then I realised it was a bit more complex than I first thought.

    Any thoughts
    I had the same question and it was answered here on Sitepoint.

    http://www.sitepoint.com/forums/show...6&postcount=68

  19. #44
    Jiro
    SitePoint Community Guest
    Question:
    Multi-User issues?

    the whole
    [quote]
    UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
    UPDATE tree SET lft=lft+2 WHERE lft>5;
    INSERT INTO tree SET lft=6, rgt=7, title='Strawberry';
    [\quote]

    should be locked. which would be very slow. hmm...

  20. #45
    voila
    SitePoint Community Guest
    how do i get the immediate children of 'Food' which are only 'Fruit' and 'Meat' by SQL?

  21. #46
    reads the ********* Crier silver trophybronze trophy longneck's Avatar
    Join Date
    Feb 2004
    Location
    Tampa, FL (US)
    Posts
    9,854
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by voila
    how do i get the immediate children of 'Food' which are only 'Fruit' and 'Meat' by SQL?
    Code:
    select title from items where parent = 'Food';

  22. #47
    Sam
    SitePoint Community Guest
    Pretty not-well done.
    Page 3 is just sth "i got rid of this article"
    The explanation of how adding new nodes is very bad.
    Sure explaining the easiest posibility is good, but try to add "Green" to the Fruit Stack. It could be a lot better explained how to get the values for the new node.

  23. #48
    chef
    SitePoint Community Guest
    uhm, add green to fruit would be : set lft for green value of rgt of fruit, increase all where rgt>=fruit.rgt + 2,set green.rgt to green.lft+1

    not that complex, I agree setting parent id of green to fruit is easier, but as mentionned I can be worth the effort to test the performance of both systems...

  24. #49
    Data
    SitePoint Community Guest
    Does anyone have the code to insert a node, I can't believe the author of this article left that out. Please Help, I'm so confused.

  25. #50
    SitePoint Member
    Join Date
    Jul 2005
    Posts
    13
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    In playing around, here's the quick insert_node code I came up with. His description was pretty accurate, and I probably took the long way around a few hurdles, but it works.

    function add_node($parent, $title) {
    // first, we need to look at the right node of the parent. This will become the left node
    // of the new child node (the right node of the new child will be left+1). Thus, the parent
    // node's right value will be right+2. And each node, left or right, of a higher value than
    // the parent's right needs to be incremented by two as well.

    // First, get the parent node's right value.
    $result = mysql_query('SELECT rgt FROM tree WHERE title="'.$parent.'";');
    $row = mysql_fetch_array($result);
    $adjVal = $row['rgt']-1;
    $newLeft = $row['rgt'];
    $newRight = $row['rgt']+1;

    // Now, we'll update each node with this right value or greater.
    $result2 = mysql_query('UPDATE tree SET rgt=rgt+2 WHERE rgt>'.$adjVal.';');
    $result3 = mysql_query('UPDATE tree SET lft=lft+2 WHERE lft>'.$adjVal.';');

    // OK, now we just insert the node. Set values as appropriate - $lft to the parent's old $rgt
    // and $rgt to the parent's old $rgt+1
    $result = mysql_query('INSERT INTO tree (parent,title,lft,rgt) VALUES ("'.$parent.'","'.$title.'",'.$newLeft.','.$newRight.');');
    }



Bookmarks

Posting Permissions

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