Computer-implemented method for compressing representation of binary relation

• US 7,904,476 B1
• Filed: 07/30/2007
• Issued: 03/08/2011
• Est. Priority Date: 07/30/2007
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Schreiber, Robert Samuel
• Primary Examiner(s): Vy; Hung T
• Application Number:
  US11/888,001
• Time in Patent Office: 1,317 Days
• Field of Search: 707/9, 707/781, 707/785, 726/4, 726/6
• US Class Current: 707/785
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: G06F 2221/2141 Access rights, e.g. capability lists, access control lists, access tables, access matrices

Abstract

One embodiment relates to an automated method for compressing an n-partite representation of an access control list or other binary relation. A first joining procedure is applied to join first and second relations in the n-partite representation and so eliminate a first intermediate set of elements, resulting in a first (n−1)-partite representation. A first re-factoring procedure generates updated first and second relations and an updated first intermediate set of elements, resulting in an updated n-partite representation. Other features, aspects and embodiments are also disclosed.

Claims

1. A computer-implemented method for compressing an n-partite representation of a binary relation where n is at least four, the method comprising:

applying a first joining procedure to join first and second relations in the n-partite representation and so eliminate a first intermediate set of elements, resulting in a first (n−

1)-partite representation; and

applying a first re-factoring procedure to generate updated first and second relations and generate an updated first intermediate set of elements, resulting in an updated n-partite representation.

2. The computer-implemented method of claim 1, further comprising:

applying a second joining procedure to join second and third relations in the updated n-partite representation and so eliminate a second intermediate set of elements, resulting in a second (n−

1)-partite representation; and

applying a second re-factoring procedure to generate updated second and third relations and generate an updated second intermediate set of elements, resulting in a further updated n-partite representation.

3. The computer-implemented method of claim 2, further comprising:

determining whether a complexity of the further updated n-partite representation is lower than a complexity of the updated n-partite representation.

4. The computer-implemented method of claim 3, further comprising:

repeating the joining and re-factoring procedures if the complexity of the further updated n-partite representation is lower than a complexity of the n-partite representation.

5. The computer-implemented method of claim 1, wherein n=4 such that the n-partite representation is a quadrapartite representation and the (n−

1)-partite representations are tri-partite representations.

6. The computer-implemented method of claim 1, wherein the binary relation comprises a binary relation between user accounts and resources in an access control system.

7. The computer-implemented method of claim 1, wherein the binary relation comprises a binary relation between user accounts and resources in an access control system, and wherein n=4 such that the n-partite representation is a quadrapartite representation and the (n−

1)-partite representations are tri-partite representations.

8. A computer-readable medium configured with computer-readable program code to compress a n-partite representation of an access control list, the computer-readable medium comprising:

computer-readable program code configured to apply a first joining procedure to join first and second relations in the n-partite representation and so eliminate a first intermediate set of elements, resulting in a first (n−

1)-partite representation; and

computer-readable program code configured to apply a first re-factoring procedure to generate updated first and second relations and generate an updated first intermediate set of elements, resulting in an updated n-partite representation.

9. The computer-readable medium of claim 8, further comprising:

computer-readable program code configured to apply a second joining procedure to join second and third relations in the updated n-partite representation and so eliminate a second intermediate set of elements, resulting in a second (n−

1)-partite representation; and

computer-readable program code configured to apply a second re-factoring procedure to generate updated second and third relations and generate an updated second intermediate set of elements, resulting in a further updated n-partite representation.

10. The computer-readable medium of claim 9, further comprising:

computer-readable program code configured to determine whether a complexity of the further updated n-partite representation is lower than a complexity of the initial n-partite representation.

11. The computer-readable medium of claim 10, further comprising:

computer-readable program code configured to repeat the joining and re-factoring procedures if the complexity of the further updated n-partite representation is lower than a complexity of the updated n-partite representation.

12. The computer-readable medium of claim 8, wherein n=4 such that the n-partite representation is a quadrapartite representation and the (n−

1)-partite representations are tri-partite representations.

13. The computer-readable medium of claim 8, wherein the binary relation comprises a binary relation between user accounts and resources in an access control system.

14. The computer-readable medium of claim 8, wherein the binary relation comprises a binary relation between user accounts and resources in an access control system, and wherein n=4 such that the n-partite representation is a quadrapartite representation and the (n−

1)-partite representations are tri-partite representations.

15. An automated method for compressing a 4-partite representation of an access control list, the method comprising:

applying a first joining procedure to join first and second relations in the 4-partite representation and so eliminate a first intermediate set of elements, resulting in a first 3-partite representation;

applying a first re-factoring procedure to generate updated first and second relations and an updated first intermediate set of elements, resulting in an updated 4-partite representation;

applying a second joining procedure to join second and third relations in the 4-partite representation and so eliminate a second intermediate set of elements, resulting in a second 3-partite representation; and

applying a second re-factoring procedure to generate updated second and third relations and an updated second intermediate set of elements, resulting in a further updated 4-partite representation; and

determining whether a complexity of the further updated 4-partite representation is lower than a complexity of 4-partite representation and/or the updated 4-partite representation.

16. The method of claim 15, further comprising repeating steps of said method until a determination is made that the complexity of the further updated 4-partite representation is not lower than the complexity of the 4-partite representation and/or the updated 4-partite representation.

17. The method of claim 15, wherein the first relation is a relation between users and groups, the second relation is between groups and roles, and the third relation is between roles and resources.