Role-Based Access Control in PHP: Database Schema, Algorithms, and Implementation

Role-Based Access Control (RBAC) is the standard approach to managing user permissions at scale. Instead of assigning permissions directly to users, you assign permissions to roles, and roles to users. Adding a new user means assigning roles - not reconfiguring every permission.

This post covers RBAC from theory to implementation: the database schema, the algorithms behind efficient permission checks, and how to implement it in PHP using the simple-rbac library.

Why RBAC?

There are three common access control models:

• Mandatory Access Control (MAC) - permissions defined by system-level rules and properties attached to actions. Rigid; common in security-critical environments.
• Discretionary Access Control (DAC) - permission decisions based on the identity of the requesting user. Flexible but hard to manage at scale.
• Role-Based Access Control (RBAC) - roles belong to users; permissions belong to roles. Permissions are never directly assigned to users.

RBAC is the right default for most web applications. When a user changes team, you reassign their role. When a new permission is needed for an action, you add it to the appropriate role - not to every user individually. The indirection through roles is what makes it manageable.

Database Schema

The minimal schema for RBAC:

• user - your users
• role - named roles (e.g. admin, editor, viewer)
• permission - named permissions (e.g. post.create, post.delete)
• user_role - many-to-many: a user can have multiple roles
• permission_role - many-to-many: a role can have multiple permissions

Permissions are never in a user_permission table - they only reach users through roles.

The Performance Question: Naive vs Optimal

The core operation is: given a user and a permission, is the user allowed to perform the action?

A naive implementation iterates all users, all roles, all permissions: O(u × r × p). For any non-trivial system this is unacceptable.

Hash tables look attractive - average lookup is O(1). But hash tables depend on a good hash function. A poorly distributed function degrades to O(n) due to collisions, and worst-case is still O(u × r × p).

Binary Search Trees (BST) are the better fit here. Users, roles, and permissions can each be indexed numerically (e.g. by primary key), giving a natural ordering for BST insertion and lookup. BST search is O(log n), which is reliably better than hash table worst-case.

The algorithm:

1. Load the user - O(1) (we check one user at a time)
2. Load the user's roles as a BST
3. Load the permission's roles as a BST
4. Pre-order traverse the user's roles tree; for each role, binary-search the permission's roles tree
5. If any role is found in both trees: access granted

Total complexity: O(1) + O(n log m) where n = number of user roles and m = number of permission roles - far better than the naive approach.

One caveat: if your database returns roles ordered by ID (ORDER BY id ASC), inserting them sequentially produces a maximally unbalanced BST (a linked list). The fix: find the median element of your list, make it the root, recurse on left and right halves. The PHPAlgorithms library implements this as createFromArrayWithMinimumLength().

Implementing simple-rbac

The simple-rbac library is available on Packagist:

composer require doganoo/simple-rbac

1. Database Queries

Fetch a user's roles:

SELECT r.id
FROM role r
LEFT JOIN user_role ur ON r.id = ur.role_id
LEFT JOIN user u ON u.id = ur.user_id
WHERE ur.user_id = ?;

Fetch a permission's roles:

SELECT r.id
FROM role r
LEFT JOIN permission_role pr ON r.id = pr.role_id
WHERE pr.permission_id = ?;

2. Implement IUser

IUser represents the user being checked. It must expose the user's roles as a Binary Search Tree:

<?php
use doganoo\SimpleRBAC\Entity\IUser;

class User implements IUser {
    private BinarySearchTree $roles;

    public function __construct(int $id) {
        $rows = $db->fetchRolesForUser($id);
        $this->roles = BinarySearchTree::createFromArrayWithMinimumLength(
            array_column($rows, 'id')
        );
    }

    public function getRoles(): BinarySearchTree {
        return $this->roles;
    }
}

3. Implement IDataProvider

IDataProvider gives the PermissionHandler all it needs: the user, all permissions with their associated roles, and default permissions:

<?php
use doganoo\SimpleRBAC\Handler\PermissionHandler;

$user       = new User($currentUserId);
$permission = new Permission('post.delete'); // loads its roles internally

$handler = new PermissionHandler(new MyDataProvider($user, $permission));
$allowed = $handler->hasPermission();

Complexity Summary

Conclusion

RBAC's power comes from the role indirection: permissions never attach to users directly. At the implementation level, Binary Search Trees give you reliable O(n log m) permission checks regardless of data distribution - which hash tables cannot guarantee.

The simple-rbac library is available on GitHub and Packagist under the MIT license. It is designed to be lightweight and focused - one user, one permission, one check - and is straightforward to extend for more complex RBAC scenarios.