Database schema for ACL

Question

I want to create a schema for a ACL; however, I'm torn between a couple of ways of implementing it.

I am pretty sure I don't want to deal with cascading permissions as that leads to a lot of confusion on the backend and for site administrators.

I think I can also live with users only being in one role at a time. A setup like this will allow roles and permissions to be added as needed as the site grows without affecting existing roles/rules.

At first I was going to normalize the data and have three tables to represent the relations.

ROLES { id, name }
RESOURCES { id, name }
PERMISSIONS { id, role_id, resource_id }

A query to figure out whether a user was allowed somewhere would look like this:

SELECT id FROM resources WHERE name = ?
SELECT * FROM permissions WHERE role_id = ? AND resource_id = ? ($user_role_id, $resource->id)

Then I realized that I will only have about 20 resources, each with up to 5 actions (create, update, view, etc..) and perhaps another 8 roles. This means that I can exercise blatant disregard for data normalization as I will never have more than a couple of hundred possible records.

So perhaps a schema like this would make more sense.

ROLES { id, name }
PERMISSIONS { id, role_id, resource_name }

which would allow me to lookup records in a single query

SELECT * FROM permissions WHERE role_id = ? AND permission  = ? ($user_role_id, 'post.update')

So which of these is more correct? Are there other schema layouts for ACL?

Rest

You can look up permissions in a single query with the proper, correct, normalised schema too. Use a JOIN. – Subminiature

My direct experience with cascading permissions is that it was difficult for me (the software developer/maintainer) to get right, but made life much nicer for administrators. Partly because I included in the permission UI the ability to see what you had permission to do and why you had permission to do it. So they could easily see where the permission came from. This was quite intuitive for them. – Lewse

Answer 1

In my experience, the real question mostly breaks down to whether or not any amount of user-specific access-restriction is going to occur.

Suppose, for instance, that you're designing the schema of a community and that you allow users to toggle the visibility of their profile.

One option is to stick to a public/private profile flag and stick to broad, pre-emptive permission checks: 'users.view' (views public users) vs, say, 'users.view_all' (views all users, for moderators).

Another involves more refined permissions, you might want them to be able to configure things so they can make themselves (a) viewable by all, (b) viewable by their hand-picked buddies, (c) kept private entirely, and perhaps (d) viewable by all except their hand-picked bozos. In this case you need to store owner/access-related data for individual rows, and you'll need to heavily abstract some of these things in order to avoid materializing the transitive closure of a dense, oriented graph.

With either approach, I've found that added complexity in role editing/assignment is offset by the resulting ease/flexibility in assigning permissions to individual pieces of data, and that the following to worked best:

1. Users can have multiple roles
2. Roles and permissions merged in the same table with a flag to distinguish the two (useful when editing roles/perms)
3. Roles can assign other roles, and roles and perms can assign permissions (but permissions cannot assign roles), from within the same table.

The resulting oriented graph can then be pulled in two queries, built once and for all in a reasonable amount of time using whichever language you're using, and cached into Memcache or similar for subsequent use.

From there, pulling a user's permissions is a matter of checking which roles he has, and processing them using the permission graph to get the final permissions. Check permissions by verifying that a user has the specified role/permission or not. And then run your query/issue an error based on that permission check.

You can extend the check for individual nodes (i.e. check_perms($user, 'users.edit', $node) for "can edit this node" vs check_perms($user, 'users.edit') for "may edit a node") if you need to, and you'll have something very flexible/easy to use for end users.

As the opening example should illustrate, be wary of steering too much towards row-level permissions. The performance bottleneck is less in checking an individual node's permissions than it is in pulling a list of valid nodes (i.e. only those that the user can view or edit). I'd advise against anything beyond flags and user_id fields within the rows themselves if you're not (very) well versed in query optimization.

Exceed

Thank you for that good overview of more complex relations. I would imagine this is the type of permissions graph that something like facebook would be using. I remember taking with a guy about roles a while ago and he mentioned lots of edge cases that would require having multiple roles. The only thing that concerns me is that the size of the object/array which would be required to store this graph in memory would be at least a megabyte. It seems like only querying for the parts you need and leaving the graph in the database would save a lot of RAM. – Rest

For the permission graphs I've run into, the results were actually quite small. But then, I've never needed to manage hundreds of roles either. :-) – Exceed

Actually, I was trying to think of some examples where individual objects would need permissions also - but I can't think of a time where they should belong in the graph. If it was a user profile permission like you said, I agree that the profile row should contain a bit column. If it was a private forum for a certain role, I think that too should go in the forum object. Do you have any other examples of situations that wouldn't work with just roles? – Rest

Roles are not enough if you want to allow users to assign read/write permissions to data that they own, e.g. customer has accounting staff and wants to let the latter view his invoices. – Exceed

Dear @Denis I need to implement this structure as mentioned by you. Can you please tell me what is the table structure and what query should I use? – Improper

@DenisdeBernardy would also love to see a (example, simple) database structure to explain your concept. I think I follow, but I'm not totally sure, and seeing a simple database table structure would make it really clear. Thanks! – Angelikaangelina

I'm trying to create a role/permission system, and this didn't help much. Too much theory :) I came accross this page. At least, it provides some SQL/PHP examples. Trying to make it work, atm. – Collude

Answer 2

This means that I can exercise blatant disregard for data normalization as I will never have more than a couple hundred possible records.

The number of rows you expect isn't a criterion for choosing which normal form to aim for. Normalization is concerned with data integrity. It generally increases data integrity by reducing redundancy.

The real question to ask isn't "How many rows will I have?", but "How important is it for the database to always give me the right answers?" For a database that will be used to implement an ACL, I'd say "Pretty danged important."

If anything, a low number of rows suggests you don't need to be concerned with performance, so 5NF should be an easy choice to make. You'll want to hit 5NF before you add any id numbers.

A query to figure out if a user was allowed somewhere would look like this:

SELECT id FROM resources WHERE name = ?
SELECT * FROM permissions 
WHERE role_id = ? AND resource_id = ? ($user_role_id, $resource->id)

That you wrote that as two queries instead of using an inner join suggests that you might be in over your head. (That's an observation, not a criticism.)

SELECT p.* 
FROM permissions p
INNER JOIN resources r ON (r.id = p.resource_id AND 
                           r.name = ?)

Cryolite

What would an ACL schema in 5NF look like? – Rest

Completly agree, the most important thing is that the tables should stay clear. If you want optimizations in term of speed, then you should look at bitfileds in databases, some applications with fixed ACL elements use bitfields and bit operations to perform ACL checks, but this is far less readable than a few tables with clear relations and future extensions available. In term of speed the application can cache the ACL object after a complete initial load of all ACL tables in an application-level object and perform the check with application language and not SQL. – Audet

Answer 3

You can use a SET to assign the roles.

CREATE TABLE permission (
  id integer primary key autoincrement
  ,name varchar
  ,perm SET('create', 'edit', 'delete', 'view')
  ,resource_id integer );

Svensen

The rules are not known before hand. While it's true basic CRUD rules are needed on most resources, there might be other custom rules so a SET will not work since they cannot be defined at the start of the project. – Rest

You can expand the set afterwards using ALTER TABLE. – Svensen

Well, the problem is the rules are unique to some modules. Perhaps "Revise" is a permission of articles and "refund" is a permission of the payment system. Plus, ALTER TABLE isn't very fast on large datasets and is bothersome each time you need to add a new permission. – Rest

@Xeoncross, IIRC, ALTER TABLE where you add items at the end of a set only causes the tableheader to be updated (the .frm file), not the table itself. As long as the alteration in the set does not cause the datasize to grow (max 8 setitems in a byte, 16 setitems in a word, 32 in a dword etc). – Svensen