Recursive SQL Query

By | 2013-07-08

Imagine these tables (I’m using PostgreSQL):

    CREATE Capabilities (
        ID     serial PRIMARY KEY,
        Code   text   NOT NULL
    );

    CREATE CapabilityPermissions (
        ID              serial  PRIMARY KEY,
        CapabilitityID  integer NOT NULL REFERENCES Capabilities(ID),
        PermissionID    integer NOT NULL REFERENCES Capabilities(ID)
    );

What I’m aiming for here is the ability to make a permissions hierarchy. This will let us define, say, an ADMIN capability, and have that imply USER capabilities, EDITOR capabilities, etc. In other words, the CapabilityPermissions table is recursive. I’ve done this sort of thing in quite a few projects – a flexible permissions system is surprisingly useful. Usually in your app, as soon as the user is identified, you look up their permissions from the database and assemble them into an easily-searched structure. With a recursive table like this you might do (in pseudo-python):

    def fetchPermissions( startPermissionID, permissionDict = None ):
        if permissionDict is None:
            permissionDict = {}
        cursor = db.execute("SELECT CP.PermissionID, C.Code
            FROM CapabilityPermissions AS CP
                INNER JOIN Capabilities AS C ON (C.ID=CP.PermissionID)
            WHERE CP.CapabilityID = %s", (startPermissionID,))
        for row in cursor:
            if row[1] not in permissionDict:
                permissionDict[row[1]] = row[0]
                fetchPermissions( row[0], permissionDict )

        return permissionDict

This function recursively queries as it finds each new permission. Nothing in particular wrong with it other than it’s making lots of queries.

If you’ve got a compliant database (PostgreSQL for example), then you can get the database to do the work with a recursive query.

    CREATE VIEW AllPermissions AS
    WITH RECURSIVE RecursedCP(CapabilityID,PermissionID) AS (
            -- This is the non-recursive query, and forms the basis of the
            -- whole sequence, each record in this result is stored into a
            -- temporary working table, which is then available in the
            -- recursive query (named after the recursive output name,
            -- RecursedCP)
            SELECT CapabilityID,CapabilityID FROM CapabilityPermissions
        UNION
            -- The recursive query has the temporary table available
            -- and will add its output to the result, and make that output
            -- the new temporary table.  For each capability then, we want to
            -- use its permission as the new capability for the next
            -- iteration
            SELECT AP.CapabilityID,CP.PermissionID
                FROM RecursedCP AS AP
                    INNER JOIN CapabilityPermissions AS CP ON (CP.CapabilityID=AP.PermissionID)
    ) SELECT CapabilityID, PermissionID FROM RecursedCP;

The two parts are a query to “seed” the recursion, then the query that takes that seed and expands it, which becomes the next seed. The use of UNION tells the database that the expansions should all be aggregated into the single query result.

With this VIEW in place, you can then easily convert the whole lot into a filtered query: so if you’re user is assigned capability ID#1, you can get the full list of permissions that that capability implies like this:

    SELECT * FROM AllPermissions WHERE CapabilityID = 1;

I like to treat these top-level capabilities as “roles”, and the leaf permissions at the codes that are checked throughout the application. That way you get a role-based access system with fine-grained access.

Leave a Reply