System and method for maintenance of transitive closure of a graph and user authentication

1. A user authorization system comprising:

a database server including a database management system that manages a database, the database server maintaining, in the database, a cached user rights list as a cached transitive closure and an access control list for a set of objects, the database embodied on non-transitory computer memory, the user rights list comprising user rights records of associations between users and related entities from which the users inherit rights and the access control list specifying permissions of entities to access the set of objects; and

an authorization server coupled to the database server via a network, the authorization server comprising a processor and a memory and configured to:

receive a request from a user for an object; and

interact with the database server to cause the database server to perform:

determining a new transitive closure for the user based on a directed graph of associations between entities in the database;

determining a delete user rights record by:

comparing the cached user rights list and the new transitive closure;

determining a first transitive closure path for an entity that is not specified in the new transitive closure and that is specified in the cached user rights list; and

selecting as the delete user rights record a record specifying the first transitive closure path; and

deleting the delete user rights record from the cached user rights list.

2. The user authorization system of claim 1 , wherein the authorization server is further configured to pass an object identifier for the object requested by the user to the database server.

3. The user authorization system of claim 2 , wherein the database server is further configured to perform:

filtering the access control list for the user according to the cached user rights list; and

sending a filtered access control list to the authorization server.

4. The user authorization system of claim 1 , wherein in determining the delete user rights record, the database server is further configured to perform:

determining, from the cached user rights list, a set of common records for the user that specify common associations between the user and related entities also specified by new transitive closure records for the user in the new transitive closure; and

selecting as the delete user rights record, a cached user rights record for the user that is not in the set of common records for the user.

5. The user authorization system of claim 1 , wherein in determining the delete user rights record, the database server is further configured to perform:

determining a set of delete user rights records (D) according to D=(R\R′), where:

R=a current set of cached user rights records for the user;

R′=a set of new transitive closure records for the user.

6. The user authorization system of claim 1 , wherein the database server is further configured to perform:

determining an insert record, said insert record specifying a second association between the user and a second related entity, the second association specified in the new transitive closure but not the cached user rights list; and

inserting the insert record in the cached user rights list.

7. The user authorization system of claim 6 , wherein determining the insert record further comprises determining a set of insert transitive closure records (I) according to I=(R′\R), where:

R=a current set of cached transitive closure records for the user;

R′=a set of new transitive closure records for the user.

8. The user authorization system of claim 1 , wherein the related entities from which the users inherit rights comprise groups or roles.

9. The user authorization system of claim 1 , wherein the entities in the database comprise users, groups, roles, files, and directories.

10. The user authorization system of claim 1 , wherein determining the new transitive closure for the user comprises transforming a membership graph containing one or more cycles to the directed graph.

11. A user authorization system comprising:

a first server coupled to a database server via a network and comprising a processor and a memory, the database server including a database management system that manages a database embodied on a non-transitory computer readable medium and manages and maintains user rights and access control permissions for the database, the first server configured to:

receive a request from a user for an object;

pass access information to the database server, the access information comprising a user identifier and an object identifier; and

enforce a filtered access control list returned by the database server to grant or deny access to the object by the user;

the database server configured to:

determine a transitive closure of a hierarchy of entities that define inheritance of rights to generate a user rights list that comprises transitive closure paths between users and related entities from which users inherit rights;

maintain the user rights list in a cache in the database as a cached user rights list;

maintain an access control list in the database, the access control list comprising a first set of access control entries specifying permissions of entities to access the object;

receive the user identifier and object identifier passed from the first server;

responsive to the access information:

filter the access control list based on the cached user rights list to generate the filtered access control list specifying permissions to the object for the user, wherein to generate the filtered access control list further comprises to determine a filtered set of access control entries from the first set of access control entries for inclusion in the filtered access control list, the filtered set of access control entries comprising access control entries from the first set of access control entries that map the user or an entity from which the user inherits rights to the object; and

return the filtered access control list to the first server.

12. The user authorization system of claim 11 , wherein the database server is further configured to:

determine a first set of entities related to the user, the first set of entities related to the user comprising entities related to the user in the cached user rights list; and

wherein the permissions to the object for the user in the filtered access control list comprise permissions to the object for the first set of entities related to the user.

13. The user authorization system of claim 11 , wherein the related entities from which the users inherit rights comprise groups or roles.

14. The user authorization system of claim 11 , wherein the first server utilizes the filtered access control list returned from the database server to determine whether the user has permission to access the object.

15. The user authorization system of claim 11 , wherein the first server comprises an application server or a content server.

16. The user authorization system of claim 11 , wherein the object is managed by the first server and wherein each object managed by the first server has a specific access control list.

17. The user authorization system of claim 16 , wherein permissions to objects managed by the first server are set based on policies and the objects are associated with the policies.

18. The user authorization system of claim 11 , wherein the object comprises a content resource.

19. The user authorization system of claim 18 , wherein the content resource comprises a file, a directory, a document, a folder, a topic, a reply, a task, a task list, a task group, a blog, or a blog entry.

20. The user authorization system of claim 11 , wherein the filtered access control list contains only access control list entries that apply to the user and the object.