DB Theory Help for Category Editors Database

Need a little direction please

[Nick_W]

Hi all,

Let's say we have a website like ODP or indeed like WebmasterWorld. Some editors have higer permissions than others right?

Mods have perms in their forum
Admins in their section
BT on everything.
_________________________________________

Here's a simplified DB structure for the site categorie:

categories
id ¦ title ¦ desc

relationships
catid ¦ parent

and let's assume I have a very simple editor tables like:

editors
id ¦ status ¦ name

perms
editorid ¦ catid
______________________________________

So, here's my question (hope your with me so far!):

If I want to make myself have permissions for all categories and there are 100 of them. Do I have to put 100 entries in perms? - Course not, but I don't want to make dozens of calls to the DB just to find out if someone has permissions on a cat.

If you're not quite with me, then neither am I. But weather the above makes sense or not I hope you have an idea of what I'm trying to do.

I'd really appreciate it if someone could give me a shove in the right direction here.

The way I see the above is that I'd have to call up parent of each cat in some kind of recursive loop with many db calls to find out who the 'boss' of a section was (like BT or an Admin here). That seems silly.

Is there a better way, am I over complicating this?

Many thanks!

Nick

[lorax]

>> You guys are great for my mental stimulation,

The feeling is mutual. Like I noted earlier - this sort of thread/problem solving session, is what I love. Heck, I even crave it. There's nothing like a good discussion - or even a friendly debate - about the merits/approach/theory of a problem. Especially in this topic area of being a webmaster. Where I live, there are no other folks that I have that understand MySQL and PHP as well as you guys. So it is of great comfort to know that I have this Board - including all of those who read this thread but didn't post - to exchange ideas and problem solve with. You guys/gals are the cat's meow.

Now about that article - I'm in weekend mode so it'll take me a day or so to read and absorb it.
;)

[grahamstewart]

Brief Analysis of Different Storage Methods
As I promised I would in the other big Nick thread [webmasterworld.com] I have done a bit of benchmarking on the three main suggestions for storing a tree of data.

The Methods
The parent key - (aka the adjacency model) This is the first one everyone thinks of. Each node simply has a 'parent' key.

 id(int) ¦ name(varchar) ¦ parent(int) 

The parent list - suggested by various people. This is where each node stores a list of its parent ids in an ordered string. (Obviously this is denormalised - but sometimes that can help speed problems).

 id(int) ¦ name(varchar) ¦ depth(int) ¦ parent_list(varchar) 

Pre-order - method suggested by Joe Celko that I mentioned in the other thread. Basically its like storing the tree as a hash tree.

 id(int) ¦ name(varchar) ¦ lft(int) ¦ rgt(int) 

The Test
I created a php script that populates three tables (one for each method) with a full tree with the depth and branching factor that you specify.

It then times how long each method takes to generate a list of parents for a given node at the bottom of the tree (eg the path-to-node). (It does this 100 times per method to magnify the differences).

The Results

A normal tree Depth: 4 Branching: 10 
Parent List method:_0.5333 secs 
Pre-order method:___0.3112 secs 
Parent key method:__1.0181 secs 
  
Shallow wide tree Depth: 2 Branching: 10 
Parent List method:_0.4343 secs 
Pre-order method:___0.2491 secs 
Parent key method:__0.5778 secs 
  
Deep thin tree Depth: 10 Branching: 2 
Parent List method:_0.5936 secs 
Pre-order method:___0.3503 secs 
Parent key method: _2.3389 secs 

Conclusions
For this test, pre-order easily rules the roost, it only involves a single select and seems very scalable.

Parent list is also fairly promising. It only requires two selects and benefits from MySQLs good handling of the IN clause. However, it is denormalised and therefore not as flexible as the others. Plus additional keys would have to be added before it is useful (for example how do you show children of a given node?)

The parent key method operates recursively and requires a select for each level of the table. Its performance ranges from bad on shallow tables to awful on deeper ones. Don't use it. :)

Notes

MySQL didn't seem to want to use indexes with the BETWEEN clause - which put the skids under the pre-order method. I solved this by changing the select to

select c2.name from category_preorder as c1, category_preorder as c2 
   where c2.lft <= c1.lft and c1.lft <= c2.rgt 
     and c1.id =? 

Which should do exactly the same thing as the other one, but MySQL seemed happier to use indexes with it.

All tests were conducted on my laptop using MySQL 4.0.9 and PHP 4.3.1 Obviously if you were using a super-charged dedicated MySQL server you would expect better results, but these test should be indicative of the performance differences between the methods.

If you want the full code for these tests (190 lines of PHP + some SQL) then drop me a Sticky - its probably a bit too big to just post here.

[Nick_W]

SELECT editors.*, edit_permissions.*
FROM editors,edit_permissions,permission
LEFT JOIN editors ON editors.
edID=edit_permissions.edID
LEFT JOIN permissions ON permissions.permID=edit_permissions.permID
WHERE edID = 2

Hmmm...

>>Not unique table editors

Can anyone help with this please?

Nick

[aspdaddy]

>>Not unique table editors

I dont really understand the problem you have, do you want to select unique editors and the query is selecting repeating groups?

If the LEFT-JOIN is selecting rows with null values, maybe an INNER-JOIN will resolve it.

[ShawnR]

>>Not unique table editors

Are you saying that you are getting this back as an error message?
One problem might be: FROM editors,edit_permissions,permissions

Also, did you mean to do:
SELECT editors.*, permissions.*