Writing an inheritance query written in SQL using an inner join?

Question

I confess that my knowledge of SQL (using mySQL) extends little beyond the standard queries required for database management, and that the majority of my data manipulation has been done through php.

I have been keen to change that, and have enjoyed success until now, and would appreciate it if someone could advise me on how I create a stored procedure for an inheritance query on a standard table containing 'parent', 'child' fields, inner joined on a permissions table.

As sample data (for demonstration purposes):

table_group_inherit

parent        child
------------------------
admin         moderator
member        guest
super_admin   admin
moderator     member

table_group_permissions

moderator    move_post
----------------------
super_admin  create_forum
admin        move_forum
guest        view_post
member       create_post
member       edit_post

Then I would call the procedure on a group name (e.g. 'admin')to return an array of its permissions ('move_forum', 'view_post', 'create_post', edit_post'). I do not know whether I require iteration or recursion here (I read something about mySQL not supporting this?), but any advice is welcome.

(N.B. I have elected against using permissions as fields with a TRUE/FALSE check as I intend to attach further fields to each permission e.g. description).

Answer 1

You'll need to create nested left and right keys as documented here, and use those for your inheritance queries.

Answer 2

had a quick stab at it so suggest you double check the results !

full script here : http://pastie.org/1213230

-- TABLES

drop table if exists roles;
create table roles
(
role_id tinyint unsigned not null primary key,
name varchar(255) unique not null,
parent_role_id tinyint unsigned,
key (parent_role_id)
)
engine=innodb;


drop table if exists actions;
create table actions
(
action_id smallint unsigned not null auto_increment primary key,
name varchar(255) unique not null
)
engine=innodb;


drop table if exists role_actions;
create table role_actions
(
role_id tinyint unsigned not null,
action_id smallint unsigned not null,
primary key (role_id, action_id)
)
engine=innodb;

-- STORED PROCEDURES

drop procedure if exists list_role_actions;

delimiter #

create procedure list_role_actions
(
in p_role_id tinyint unsigned
)
proc_main:begin

declare done tinyint unsigned default 0;
declare dpth smallint unsigned default 0;

drop temporary table if exists hier;
drop temporary table if exists tmp;

create temporary table hier(
 parent_role_id tinyint unsigned, 
 role_id tinyint unsigned, 
 depth smallint unsigned default 0
)engine = memory;

insert into hier select parent_role_id, role_id, dpth from roles where role_id = p_role_id;

/* http://dev.mysql.com/doc/refman/5.0/en/temporary-table-problems.html */

create temporary table tmp engine=memory select * from hier;

while done <> 1 do

    if exists( select 1 from roles r inner join hier on r.parent_role_id = hier.role_id and hier.depth = dpth) then

        insert into hier 
            select r.parent_role_id, r.role_id, dpth + 1 from roles r
            inner join tmp on r.parent_role_id = tmp.role_id and tmp.depth = dpth;

        set dpth = dpth + 1;            

        truncate table tmp;
        insert into tmp select * from hier where depth = dpth;

    else
        set done = 1;
    end if;

end while;

/*
select 
 r.*,
 p.name as parent_role_name,
 hier.depth
from 
 hier
inner join roles r on hier.role_id = r.role_id
inner join roles p on hier.parent_role_id = p.role_id
order by
 hier.depth, hier.role_id; 
*/

select
 ra.*,
 r.name as role_name,
 a.name as action_name
from
 role_actions ra
inner join hier h on h.role_id = ra.role_id
inner join actions a on ra.action_id = a.action_id
inner join roles r on ra.role_id = r.role_id
order by
 ra.role_id desc;

drop temporary table if exists hier;
drop temporary table if exists tmp;

end proc_main #


delimiter ;


-- TEST DATA

insert into roles values 
(0,'guest',1),(1,'member',2),(2,'moderator',3),(3,'admin',99),(99,'super admin',null);

insert into actions (name) values 
('view post'), ('create post'), ('edit post'), ('move forum'), ('create forum');

insert into role_actions values 
-- guest
(0,1),
-- member
(1,2),
-- moderator
(2,3),
-- admin
(3,4),
-- super admin
(99,5);

-- TESTING

call list_role_actions(0);
call list_role_actions(1);
call list_role_actions(2);
call list_role_actions(3);
call list_role_actions(99);

Answer 3

If you're looking at a tree hierarchy, then the nested set model works fairly well, but involves a major change in the structure of your inheritance table.

If you're implementing an arbitrary directed graph (for instance, you have an "author" profile who can publish articles but not moderate comments, and a "moderator" profile who can moderate comments but not publish articles), you might want to look for some other solution.

One possibility is to give up on inheritance and manually set the permissions for every group.

Another possibility is to use the inheritance table to store both direct and indirect inheritance (that is, a node would be related to all its children using a "direct" relationship, as well as all its descendants using an "indirect" relationship). This strategy requires you to re-create all the indirect relationships in the table whenever you change one of the direct relationships (this can be done by using a simple INSERT SELECT), but has the advantage of only requiring a single join to access all descendants.

The basic idea is:

CREATE TABLE group_inherit (
  parent INT NOT NULL, 
  child INT NOT NULL, 
  distance INT NOT NULL, 
  PRIMARY KEY (parent,child)
);

/* Clean up indirect relations */
DELETE FROM group_inherit WHERE distance <> 0;

/* Repeat this for each D > 0 until the maximum distance is reached */
INSERT IGNORE INTO (parent, child, distance) 
SELECT fst.parent, snd.child, D
FROM group_inherit fst
INNER JOIN group_inherit snd ON snd.parent = fst.child
WHERE fst.distance = 0 AND snd.distance = D - 1;

/* Select all permissions for a user type */
SELECT perm.*
FROM group_permissions perm
INNER JOIN group_inherit ON perm.moderator = child
WHERE parent = ?

The loop on distance should be done until there are no more elements of distance D-1 available, which can be done using a select query or, if you have it, meta-information about how many lines were inserted.

Answer 4

If the hierarchy simply means higher up = more allowed, it would be far easier to just give roles a rating, the higher, the more powerful. And then give the actions a rating. Any user in a group with a rating equal or higher than the action can perform the action.