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

Patent metadata

Field	Value
Publication number	US-9614854-B2
Application number	US-201514668666-A
Country	US
Kind code	B2
Filing date	Mar 25, 2015
Priority date	Mar 25, 2014
Publication date	Apr 4, 2017
Grant date	Apr 4, 2017

Abstract

Disclosed can improve rights list management as well as performance of systems utilizing an access control list. A database server having a transitive closure management module may receive an identification of an entity defined in a database storing a cached transitive closure. The transitive closure management module may incrementally update the cached transitive closure stored in the database by generating a new transitive closure for the entity and determining a delete transitive closure record. The delete transitive closure record may be determined by analyzing the cached transitive closure and the new transitive closure, determining a first transitive closure path for the entity that is not specified in the new transitive closure and that is specified in the cached transitive closure, and selecting as the delete transitive closure record a record specifying the first transitive closure path. The delete transitive closure record can then be deleted from the cached transitive disclosure.

First claim

What is claimed is:

1. A transitive closure system comprising:
a database embodied on a non-transitory data storage medium, the database comprising a cached transitive closure of a directed graph, the cached transitive closure containing transitive closure records for some or all entities in the directed graph, each transitive closure record specifying a transitive closure path from one entity to another entity, the transitive closure path containing at least one edge, each entity representing a user or group of users;
at least one processor; and
a transitive closure management module embodied on non-transitory computer readable medium including instructions translatable by the at least one processor to perform:
receiving an identification of an entity defined in the database;
interacting with a relational database management system receiving queries according to a relational query language, the relational database management system embodied on a non-transitory data storage medium, said interacting incrementally updating the cached transitive closure comprising:
generating a new transitive closure for the entity from the directed graph;
determining a delete transitive closure record, said determining the delete transitive closure record comprising:
comparing the new transitive closure generated for the entity and the cached transitive closure in the database to determine a first transitive closure path for the entity that is not specified in the new transitive closure generated for the entity and that is specified in the cached transitive closure in the database; and
selecting a cached transitive closure record identifying the first transitive closure path as the delete transitive closure record; and

deleting the delete transitive closure record from the cached transitive disclosure in the database.

2. The transitive closure system of claim 1 , wherein determining the delete transitive closure record for the entity comprises:
determining a set of common records for the entity from the cached transitive closure that specify common transitive closure paths for the entity also specified by new transitive closure records for the entity in the new transitive closure; and
selecting as the delete transitive closure record, a cached transitive closure record for the entity that is not in the set of common records for the entity.

3. The transitive closure system of claim 1 , wherein determining the delete transitive closure record comprises determining a set of delete transitive closure records (D) according to D=(R\R′), where:
R=a current set of cached transitive closure records for the entity;
R′=a set of new transitive closure records for the entity.

4. The transitive closure system of claim 1 , wherein the method further comprises:
determining an insert record, said insert record specifying a second transitive closure path for the entity, the second transitive closure path specified in the new transitive closure but not the cached transitive closure; and
inserting the insert record in the cached transitive closure.

5. The transitive closure system of claim 4 , 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 entity;
R′=a set of new transitive closure records for the entity.

6. The transitive closure system of claim 1 , wherein the method further comprises:
receiving an object identifier from a server;
filtering an access control list for the object using the cached transitive closure to create a filtered access control list; and
returning the filtered access control list to the server.

7. The transitive closure system of claim 6 , wherein filtering the access control list further comprises:
identifying end point entities in cached transitive closure records for the entity;
selecting permissions specified for the end point entities from the access control list, wherein the filtered access control list comprises the permissions specified for the end point entities for the object.

8. A transitive closure method comprising:
receiving, by a transitive closure management module embodied on non-transitory computer readable medium, an identification of an entity defined in a database embodied on a non-transitory data storage medium, the database storing a cached transitive closure of a directed graph, the cached transitive closure containing transitive closure records for some or all entities in the directed graph, each transitive closure record specifying a transitive closure path from one entity to another entity, the transitive closure path containing at least one edge, each entity representing a user or group of users;
the transitive closure management module interacting with a relational database management system according to a relational query language to incrementally update the cached transitive closure stored in the database, the relational database management system embodied on a non-transitory data storage medium, said incrementally updating the cached transitive closure by the transitive closure management module further comprising:
generating a new transitive closure for the entity from the directed graph;
determining a delete transitive closure record, said determining the delete transitive closure record comprising:
analyzing the cached transitive closure in the database and the new transitive closure generated for the entity to determine a first transitive closure path for the entity that is not specified in the new transitive closure generated for the entity and that is specified in the cached transitive closure in the database; and
selecting as the delete transitive closure record a record specifying the first transitive closure path; and

deleting the delete transitive closure record from the cached transitive disclosure in the database.

9. The transitive closure method according to claim 8 , wherein determining the delete transitive closure record for the entity comprises:
determining a set of common records for the entity from the cached transitive closure that specify common transitive closure paths for the entity also specified by new transitive closure records for the entity in the new transitive closure; and
selecting as the delete transitive closure record, a cached transitive closure record for the entity that is not in the set of common records for the entity.

10. The transitive closure method according to claim 8 , wherein determining the delete transitive closure record comprises determining a set of delete transitive closure records (D) according to D=R\R′), where:
R=a current set of cached transitive closure records for the entity;
R′=a set of new transitive closure records for the entity.

11. The transitive closure method according to claim 8 , further comprising:
the transitive closure management module determining an insert record, said insert record specifying a second transitive closure path for the entity, the second transitive closure path specified in the new transitive closure but not the cached transitive closure; and
the transitive closure management module inserting the insert record in the cached transitive closure stored in the database.

12. The transitive closure method according to claim 11 , 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 entity;
R′=a set of new transitive closure records for the entity.

13. The transitive closure method according to cl

Assignees

• Open Text Sa Ulc

Inventors

• Obbard Geoffrey Michael

Classifications

• H04L63/101 Primary

  Access control lists [ACL] · CPC title

• H04L63/104

  Grouping of entities · CPC title

• H04L67/28

  Electricity · mapped topic

• G06F17/30011

  Physics · mapped topic

• G06F17/30345

  Physics · mapped topic