Capability Safety as Datalog: A Foundational Equivalence
Organizations: Minerva CQ, 114 Lester Ln, Los Gatos, CA 95032.
Abstract
We prove that capability safety admits an exact representation as propositional Datalog evaluation (Datalogprop: the monadic, ground, function-free fragment of first-order logic), enabling the transfer of algorithmic and structural results unavailable in the native formulation. This addresses two structural limitations of the capability hypergraph framework of Spera [2026]: the absence of efficient incremental maintenance, and the absence of a decision procedure for audit surface containment. The equivalence is tight: capability hypergraphs correspond to exactly this fragment, no more.
Capability-Based Security
Capability-based security controls access through explicit, narrowly scoped authority that can be delegated, constrained, and revoked.
See all 27 papers