Redundant information in an authorization mechanism

摘要

Decentralized authorization mechanisms are a popular technique for controlling the users' privileges for manipulating a database. In such a mechanism, a user may grant a privilege to another user and he may optionally permit the grantee to also grant the privilege. The potential for useless grant information in a timestamp based mechanism (such as SQL's) is characterized and an algorithm for removing such grants is given. Even though the algorithm is sufficient for many situations, the problem is shown to be NP -complete. These results are then extended for mechanisms that limit privileges to specified intervals of time.