?
Solved

Tree Database

Posted on 2003-03-10
12
Medium Priority
?
462 Views
Last Modified: 2007-12-19
Witch database can I use with PHP to make a tree structure (Like folders tree)?
0
Comment
Question by:n_pelov
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 2
  • 2
  • +3
12 Comments
 
LVL 6

Expert Comment

by:carchitect
ID: 8108283
any database preferablt mysql....
0
 
LVL 15

Expert Comment

by:VGR
ID: 8109376
yes, but I've to admit that postgresql is more powerful and faster
0
 

Author Comment

by:n_pelov
ID: 8141994
I whant to know how with tabe can I make Tree stucture
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:n_pelov
ID: 8141995
I whant to know how with table can I make Tree stucture
0
 
LVL 15

Expert Comment

by:VGR
ID: 8142255
that's an other question, isn't it ? :D

let's try to be gentle to you :

basically a tree (folder tree or other) is a structure in which elements have parents (links to other elements) and children (ditto).

Do you know how many leaves/children you may have per node/element ? 2 is for a binary tree, 3 for a ternary one, etc

Let's suppose you provide up to 5 leaves per node.

Then the DB structure would ressemble this :

CREATE DATABASE mytree;
USE mytree;
CREATE TABLE firstree(id integer unique auto_increment,name char(10),parent integer,child1 integer default 0,child2 integer default 0,child3 integer default 0,child4 integer default 0,child5 integer default 0);
# now create some sample and simple tree
INSERT INTO firstree VALUES (0,'root',0,1,2,0,0,0);
INSERT INTO firstree VALUES (0,'first child',1,0,0,0,0,0);
INSERT INTO firstree VALUES (0,'second child',1,0,0,0,0,0);
# you now have a tree of three nodes all linked together
# to add a child to an element ID1, search for a 0 in its children (child1,2,3,4,5), insert the new element with parent=ID1 and no children (set to 0 as above), get its id ID2, then modify the parent ID1 so that childrenX=ID2
# to display the tree, start with the (unique) element having parent=0 : it's the root of the tree
# then memorize its children in sequence
# then display their names horizontally while memorizing their children
# repeat until no children memorized to display. (this is naturally recursive and should be done that way, in PHP for example)
0
 
LVL 15

Expert Comment

by:VGR
ID: 8142261
I think my answer is worth the points 8-)
0
 
LVL 2

Expert Comment

by:bobsledbob
ID: 8170643

Yuck.  Not very foward thinking of you VGR, IMHO.  What if more children are needed later on?

Look, you don't need to specify who the children are in you table.  You table structure simply needs to look like this:

  create table tree(
        id int primary key not null,
    parent int references(id) null
  );

Put whatever else you need in the table per your needs.  Any nodes in the tree that are on the root level will have parent set to NULL.  Otherwise, the parent will be set to the node's parent id.

insert into tree(parent) values (NULL);
insert into tree(parent) values (NULL);
insert into tree(parent) values (1);
insert into tree(parent) values (2);
insert into tree(parent) values (3);

This would result in a tree that looks like:

1 -
  3 -
    5
2 -
  4

Sorry if the above spacing doesn't come out.  Basically, you'll have node 3 a child of node 1 and node 5 a child of node 3, node 4 a child of node 2.

In order to traverse the tree, you would use a recursive function.  Or, if you're blessed with PostgreSQL, you can just write a recursive stored procedure or whatever.


If you really want to specify who the children are, then you'll need a seperate table that map children nodes to parent:

  create table childMapping (
          id int primary key not null,
     tree_id int,
    child_id int
  );

But this is really not necessary because you can always find out who the children of a certain node are by simply:

  select * from tree where parent = $id;

0
 
LVL 15

Expert Comment

by:VGR
ID: 8172156
not very pragmatic thinking of you bobsledbob , IMHO

you've to check the DB to have the children of an element...

Leave the academic "minimal" definition (I know it), and accept that IN PRACTICE, 5 children is more than enough for a lot of applications.

A sexary balanced tree I'm still waiting to see.

Doing the "joint table" childMapping is also what I would have suiggested if the maximum number of leaves par node was unknown and potentially big. BUT it's INEFFICIENT to stay polite.

My suggestion to the Asker is : do whatever suits your needs the more closely, and think "database space" and "efficiency, time to compute" too :D
0
 
LVL 2

Expert Comment

by:bobsledbob
ID: 8174816

agree with you VGR, my method is potentially not as efficient, but that would depend on the database and the requirements of the application.

my technique for a large tree in MySQL for instance would require an enormous amount of select statements to say traverse the tree from top to bottom.

however, with a real database like PostgreSQL, it would be trivial to write a very fast recursive select statement that would perform just as fast as the required statements to traverse your tree.

for a fairly flat tree or small tree (like a small file system or a website sitemap), my definition works pretty good.  For a fairly deep or large tree, contraining the definition like you've got is probably better.

I think your advice is very correct, 'do whatever suits your needs...'  Ultimately, this type of decision is contingent on what your specific needs are and what you've got to work with resource wise (db, etc.).

0
 
LVL 15

Expert Comment

by:VGR
ID: 8175692
yes, and in this case the Asker has said "like a folders tree", so I suppose there will be a lot of leaves per node and no known maximum, so my solution is worse than yours (more general).
0
 
LVL 33

Expert Comment

by:snoyes_jw
ID: 11934491
No comment has been added to this question in more than 21 days, so it is now classified as abandoned.

I will leave the following recommendation for this question in the Cleanup topic area:
    PAQ - no points refunded

Any objections should be posted here in the next 4 days. After that time, the question will be closed.

snoyes_jw
EE Cleanup Volunteer
0
 
LVL 1

Accepted Solution

by:
DarthMod earned 0 total points
ID: 11975691
Submitted to PAQ with no points refunded (of 50)

DarthMod
Community Support Moderator
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction This article is intended for those who are new to PHP error handling (https://www.experts-exchange.com/articles/11769/And-by-the-way-I-am-New-to-PHP.html).  It addresses one of the most common problems that plague beginning PHP develop…
Originally, this post was published on Monitis Blog, you can check it here . In business circles, we sometimes hear that today is the “age of the customer.” And so it is. Thanks to the enormous advances over the past few years in consumer techno…
The viewer will learn how to count occurrences of each item in an array.
The viewer will learn how to create and use a small PHP class to apply a watermark to an image. This video shows the viewer the setup for the PHP watermark as well as important coding language. Continue to Part 2 to learn the core code used in creat…
Suggested Courses

752 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question