Databases Reference
In-Depth Information
Like SPKI/SDSI [18], KeyNote [9] uses structured assertions. It defines
an assertion language that formally captures the decision semantics of a set
of credentials and a query (given by an action environment in KeyNote).
Monotonicity of KeyNote assertions is inherent in that decision semantics.
That said, it has been shown by Li and Mitchell [44] that KeyNote's semantics
are suciently expressive that it is undecidable to determine the set of all
requests that a collection of KeyNote assertions authorizes.
As we have discussed, trust management systems such as SD3 [32] and
RT
[46] use Datalog to represent policies and credentials. Although we do not
discuss them here, other trust management languages have also been based
on Datalog, including Binder [21] and Delegation Logic [43]. There are many
ways in which Datalog can be evaluated. In SD3, evaluation is performed in
a top-down manner, much as would be done by a Prolog interpreter, but dis-
tributed. In
RT
, evaluation is performed using a special-purpose goal-directed
algorithm that combines benefits of top-down and bottom-up evaluation. Dat-
alog can be extended to support constraints on variables ranging over specific
domains. If the constraint domains are selected with care, this can be done
while preserving the guarantee of polynomial-time query evaluation [44]. The
constraints are limited in the sense that they can be used only to define con-
stant bounds on variable values, either in numeric domains or in the domain
of finite sequences, such as can be used to represent directory paths or URLs.
Constraints over two variables are not permitted. Based on this work,
RT
has
been extended to support constraints [45].
Cassandra [5] is another system that uses Datalog with constraints to
express semantics of access control. Cassandra approaches the problem of
tractability quite differently than does
RT
. Policy authors have the ability to
select constraint domains that may not in general support ecient evaluation
or even to guarantee termination. In order to ensure that query evaluation
does in fact terminate for the clauses actually used as policy statements, the
Cassandra system uses a logic programming implementation technique called
static groundness analysis. During the course of evaluation, when summarizing
the effect of a single clause, the variable environment is projected on to the
variables appearing in the head of the clause by existentially quantifying the
variables that appear only in the body. The system of constraints that contains
existential quantifiers then needs to be simplified so as to eliminate these
quantifiers, and it is at this point that the presence of constraints threatens
to compromise ecient evaluation. Groundness analysis can be used to ensure
that at the time existential quantifier elimination must be performed, certain
potentially expensive functions and relational symbols in the constraint will
be applied only to constant values, not to unbound variables. This means that
these operations can be evaluated before quantifier elimination is performed. It
effectively removes these function and relational symbols from the constraint
domain on which quantifier elimination must be supported. In this way the
designers have made an interesting agreement with the policy writer that says,
roughly, you can use all these extra functions and relations when you express
