MySql or PHP query??? Looping through Tables to COUNT...

[itsallgood]

Hi guys,

Thanks to the help from everyone in my other thread (and Derokorians example), i've got 3 tables...

There is a user table - and a group table. The 3rd lets groups and users be put into other groups. Allowing groups-in-groups, and users in groups.

USER
#userID
userName

 userID  | userName 
---------------------
   1     |   Al
---------------------
   2     |   Babs
---------------------
   3     |   Chris
---------------------
   4     |   Don

GROUP
#groupID
groupName

 groupID | groupName 
---------------------
   1     |  Group-A
---------------------
   2     |  Group-B
---------------------
   3     |  Group-C
---------------------
   4     |  Group-D


GROUP-MEMBER
#groupMemberID
memberType - enum('group','user')
memberID

 groupMemberID |  memberType  |  memberID  

---------------------------------------------
  1 (Group-A)  |     user     |    1 (Al)
---------------------------------------------
  1 (Group-A)  |     user     |    2 (Babs)
---------------------------------------------
  1 (Group-A)  |     group    |    2 (Group-B)
---------------------------------------------
  2 (Group-B)  |     user     |    1 (Al)
---------------------------------------------
  2 (Group-B)  |     group    |    4 (Group-D)

I would like to query the tables -- to get the group name, the number of groups in-the-groups, and the number of users in the group

          |  Single Users   | Groups
--------------------------------------
Group-A   |       2         |    1
--------------------------------------
Group-B   |       1         |    1
--------------------------------------
Group-C   |       0         |    0
--------------------------------------
Group-D   |       0         |    0

I have no idea how to do this 🙁 -- But i am going to search the forum -- and see if i can work it out! I'm sure someone has asked something like that before 🙂

The real question i have is -- is there any way to count the number of users in the groups - "within" the groups.

So in the example - "GROUP-A" has 2 users - and also contains "GROUP B" - group-b holds 1 user, and "GROUP-D" -- group-4 has nothing in it -- so the total users in GROUP-A is 3 users (in all child groups, and in group-a itself). Would you do this in php with a loop? Or is there a way to do this in mysql?

I hope this makes sense. Sorry for the long thread! 🙂

(I'll make sure before people add groups-in-groups that parent groups cannot be put into child groups -- to stop any infinite loops)

Thanks again!

[Derokorian]

First I would say that my previous example was incomplete, the GroupMemberId column should be the primary key for the table, and there should be a forth column to specify the group.

+---------------+---------+------------+----------+
| GroupMemberId | GroupId | MemberType | MemberId |
+---------------+---------+------------+----------+
| 1             |  1      |  Group     |  2       |
| 2             |  1      |  User      |  1       |
| 3             |  1      |  User      |  2       |
| 4             |  2      |  User      |  3       |
+---------------+---------+------------+----------+

+---------+-----------+
| GroupId | GroupName |
+---------+-----------+
| 1       | My Group  |
| 2       | His Group |
+---------+-----------+

+--------+----------+
| UserId | UserName |
+--------+----------+
| 1      | Steve    |
| 2      | Bob      |
| 3      | Jill     |
+--------+----------+

I'm at a loss right now though as to how to get the descendants of a group in mysql, in sql server I would use a with clause and recursion but I am unsure how to convert that to mysql. If you can get the descendants with the group itself you could use that set in an in clause. some like select count(*) from groupmembers where groupid in (list of descendant ids) hopefully someone can help you with that, if not I'll try to convert a working query to mysql when I get home this evening.

[tomhath]

MySQL doesn't support recursion so you'll probably need to do this in PHP.

[sneakyimp]

My first thought is that group membership should probably not have both users and groups in it. If groups have a hierarchical structure (meaning groups contain other groups which may contain other groups, etc), then it seems like a bad idea to me to try and describe both a hierarchical data structure and user membership in groups in the same table. Hierarchical data structures are complicated enough without throwing in group membership too.

My second thought is that when you try to calculate the number of members in a particular group, you are trying to count how many users either belong directly to that group or that belong to some group which is a child (or "descendant") of the group in question. This is complex also because a member might be a member of some ParentGroup and also a member of it's ChildGroup and also a member of its GrandChildGroup. Would that count as 3 members or really just one?

My intuition tells me that you would need to use PHP to recursively fetch your first group and then all its members and children and maintain a list of users that you've seen so that you don't count them twice. These recursive-type operations become expensive as your hierarchy of groups grows so you would probably want to maintain a "member_count" value for each group and update it as users are added to/removed from groups.

I have a vague recollection of "adjacency list" and "nested set" models for hierarchical data.

[laserlight]

Ah, this is the next step from the thread Database Normalisation - Group within a Group???

When I mentioned that my suggestion "may not be the best design if you expect many (as in deep) levels of subgroups", I had the modified preorder tree traversal algorithm for databases in mind (search the Web for more information), except that it looks more complicated here as you might not be dealing with a tree, and inded you rejected barand's suggestion because that requires a tree structure only.

I agree with sneakyimp: I do not like Derokorian's suggestion because you don't really save anything by having one join table instead of two. In fact, look at Derokorian's example: the rows with GroupMemberId 1 and 3 are duplicated except that the MemberType is different. That is duplication of data, and indeed if the MemberType is group, the MemberId is not relevant.

[itsallgood]

Derokorian's solution just seemed so simple -- it looked like it did what i wanted.

laserlight;11011999 wrote:

In fact, look at Derokorian's example: the rows with GroupMemberId 1 and 3 are duplicated except that the MemberType is different. That is duplication of data, and indeed if the MemberType is group, the MemberId is not relevant.

If you use the enum to describe which ID (group/user) is being held in "linkID" -- you don't need a "GroupId and MemberId" being shown in Derokorian's latest example. In his reply in the other post - i asumed it worked more like this:

GROUP-MEMBER:
+---------------+------------+----------------+
| GroupMemberId | MemberType | linkId         |
+---------------+------------+----------------+
| 1 (My Group)  |  Group     |  2 (His Group) |
| 1 (My Group)  |  User      |  3 (Jill)      |
| 2 (His Group) |  User      |  1 (Steve)     |
| 2 (His Group) |  User      |  2 (Bob)       |
+---------------+------------+----------------+

GROUP:
+---------+-----------+
| GroupId | GroupName |
+---------+-----------+
| 1       | My Group  |
| 2       | His Group |
+---------+-----------+

USER:
+--------+----------+
| UserId | UserName |
+--------+----------+
| 1      | Steve    |
| 2      | Bob      |
| 3      | Jill     |
+--------+----------+

To me -- this looked/worked great. But i don't know databases as good as you guys. I want to make sure it will be ok in the future - for 1000's of users.

Maybe i marked my other post as resolved too quick 🙁

laserlight;11011999 wrote:

and inded you rejected barand's suggestion because that requires a tree structure only.

barand's suggestion only allowed for 1 group to have 1 parent. I really need groups to be able to put in lots of groups.

What about going back to my original idea. Would this be the best choice?

+----------+       +-------------+ 
| USER     |       |GROUP_MEMBER |
+----------+       +-------------+ 
| userID   |>---+  | groupID     |>----+
| username |    +--| userID      |     |
+----------+       +-------------+     |   +-----------+ 
                                       |   |  GROUP    |
                                       |   +-----------+
                   +-------------+     +---| groupID   |
                   |GROUP_MEMBER |     |   | groupName |
                   +-------------+     |   +-----------+
                   | groupID     |>----+
                   | userID      |
                   +-------------+

sneakyimp -- your "member_count" idea is great. I will give that a try. Maybe also with a "group_count". I'll have to have a play.

Thanks so much for your help on this guys!! Its really appreciated 🙂

[laserlight]

itsallgood wrote:

If you use the enum to describe which ID (group/user) is being held in "linkID" -- you don't need a "GroupId and MemberId" being shown in Derokorian's latest example.

Then you would still be conflating two different tables into one. You won't be able to specify that the linkID is a foreign key to the group table, because it might also be a foreign key to the user table, and as far as I know you cannot specify that it is a foreign key to both tables.

itsallgood wrote:

barand's suggestion only allowed for 1 group to have 1 parent. I really need groups to be able to put in lots of groups.

Yes, that is what I mean by it requiring a tree of groups. You have a directed acyclic graph in mind instead.

[Derokorian]

On the other hand, my suggestion works great in the real world, in a multiple production environments however the difference is that we use SQL server and that supports recursion. I did not realize at the time that recursion wasn't possible in mysql and therefore if using mysql my suggestion may not be the best route as others have pointed out. I apologize for not thinking about this at the time. I have a series of nice, simple recursion queries for gathering data that stores keys to multiple tables with a key type identifier.

[itsallgood]

With mysql not supporting recursion -- I'm lost now to what the best method is. I've never heard of directed acyclic graph (dag) before -- so i'm just reading about it.

What i want to make sure is the database tables works, and wont start causing problems when there are say 3000 users, and multiple groups within groups.

Thinking about it now - i don't know how this is going to work.

If "GROUP-A" has 5 users, and 10 groups (each with 5 users in them) -- and this group has the permission to write to a forum.

Then a user logins in - who is in one of the sub-groups -- the site would need to look through each group in "GROUP-A" for that user to see if they have permission.

It's complicated stuff 🙁

[tomhath]

Depending on how deep the subgroups get you could just use a stored procedure and temporary table to keep track of members and groups that haven't been reduced to individual members; you would need to iterate through the subgroups instead of recursing but it shouldn't be difficult. MySQL does support recursive stored procedures, might be fun to try it that way. At least yo wouldn't have multiple database hits from PHP.