Method and system for processing grammar-based legality expressions

• US 7,299,171 B2
• Filed: 08/17/2004
• Issued: 11/20/2007
• Est. Priority Date: 08/17/2004
• Status: Active Grant

• Current Assignee: ContentGuard Holdings, Inc. (Pendrell Corporation)
• Original Assignee: ContentGuard Holdings, Inc. (Pendrell Corporation)
• Inventors: Chen, Eddie, Ta, Thanh, Valenzuela, Edgardo, Lao, Guillermo
• Primary Examiner(s): {hacek over (S)}mits; Talivaldis Ivars
• Assistant Examiner(s): Shortledge; Thomas E.
• Application Number:
  US10/919,438
• Publication Number:
  US 20060041421A1
• Time in Patent Office: 1,190 Days
• Field of Search: 704/10, 704/4, 704/1, 704/9
• US Class Current: 704/9
• CPC Class Codes: G06F 21/10 Protecting distributed programs or content, e.g. vending or licensing of copyrighted material protection in video systems or pay television H04N7/16 ; Digital rights management [DRM]

Abstract

Legality expressions are systematically pre-processed, organized, and stored to achieve faster real-time response, improved predictability, and increased reliability for queries against a large volume of legality expressions. Exponential improvements in both the time to locate the set of legality expressions matching specified search criteria and the processing costs of evaluating the request against the matching legality expressions are achieved using the disclosed systems, devices, and methods. The systems, devices, and methods are unique to the optimization of legality expression processing, but they can also enable the use of other optimization techniques for processing large amounts of data.

Claims

1. A method of processing grammar-based legality expressions that are adapted to be used within a system for enforcing licenses, the method comprising:

partitioning at least one legality expression into one or more units of evaluation to assess the semantic meaning of the legality expression; and

indexing at least one of the units of evaluation and the atomic expressions for subsequent retrieval based on the semantic meaning of each unit of evaluation and each atomic expression , the atomic expressions denoting the constituent components of the units of evaluation for storage, retrieval, and evaluation of the legality expressions,

wherein the indexing step further comprises assigning legality expressions to separate search spaces based upon predetermined criteria, and associating sets of key values with legality expressions where the sets of key values provide additional information related to the legality expressions.

2. The method of processing grammar-based legality expressions of claim 1, further comprising unifying a query context object and an atomic expression by evaluating the atomic expression against the context and resolving conflicts between the atomic expression and the result of the evaluation.

3. The method of processing grammar-based legality expressions of claim 2, further comprising:

creating profiles representing semantic meanings of the atomic expressions; and

classifying the atomic expressions into the corresponding profiles, the profiles comprising a set of identifications assigned to the atomic expressions.

4. The method of processing grammar-based legality expressions of claim 3, wherein the classifying step further comprises assigning a uniquely identifiable profile identification to each profile.

5. The method of processing grammar-based legality expressions of claim 4, wherein the profile is used to create all equivalent indices for atomic expressions and units of evaluation.

6. The method of processing grammar-based legality expressions of claim 5, wherein the profile is stored in a searchable profile table.

7. The method of processing grammar-based legality expressions of claim 2, further comprising:

selecting atomic expressions that match a context of a retrieval query based upon corresponding profiles of the atomic expressions; and

evaluating the selected atomic expressions by comparing the units of evaluation to the request context.

8. The method of processing grammar-based legality expressions of claim 7, wherein the indexing step further comprises storing the units of evaluation, the atomic expressions, and processing instructions in a repository with the corresponding profiles.

9. The method of processing grammar-based legality expressions of claim 7, wherein the selecting step further comprises:

planning queries from input context objects; and

constructing an initial search domain for the planned queries.

10. The method of processing grammar-based legality expressions of claim 9, wherein the selecting step further comprises executing each planned query to retrieve the set of atomic expressions that satisfy the query request.

11. The method of processing grammar-based legality expressions of claim 10, wherein the selecting step further comprises constructing the units of evaluation from the atomic expressions returned from the query request.

12. The method of processing grammar-based legality expressions of claim 11, wherein the selecting step further comprises validating the results of each executed query against unification rules stipulating whether an atomic expression in a unit of evaluation may be unified with a corresponding atomic expression in the executed query.

13. The method of processing grammar-based legality expressions of claim 12, wherein the selecting step further comprises refining the search domain and executing a modified query if the results of the executed queries fail to meet an established relevancy criterion.

14. The method of processing grammar-based legality expressions of claim 10, wherein executing each planned query to retrieve the set of atomic expressions that satisfy the query request further comprises:

analyzing variations of the atomic expression from the request context by interchanging positions of components of the atomic expression to determine if permutations of the atomic expression exist that are consistent with semantics of a unit of evaluation; and

translating the identified permutation of the atomic expression into an atomic expression that matches the request context.

15. The method of processing grammar-based legality expressions of claim 9, wherein planning queries from input context objects further comprises retrieving the profile for each atomic expression in the input context object and using the profiles to construct queries to search for atomic expressions in a repository.

16. The method of processing grammar-based legality expressions of claim 9, wherein executing each query further comprises examining the query to determine if the query contains specific profile identifications for any atomic expressions and retrieving all possible profile identifications for the atomic expression.

17. The method of processing grammar-based legality expressions of claim 1, wherein partitioning the legality expression into units of evaluation further comprises validating the legality expression against a grammar and specification to ensure the legality expression conforms to grammar rules and specifications.

18. The method of processing grammar-based legality expressions of claim 17, wherein the partitioning step further comprises extracting the legality expression from a resource.

19. The method of processing grammar-based legality expression of claim 17, wherein the partitioning step further comprises decrypting the legality expression.

20. The method of processing grammar-based legality expressions of claim 17, wherein the units of evaluation comprise an agreement in a contract.

21. The method of processing grammar-based legality expressions of claim 17, wherein the units of evaluation comprise an evocable business activity.

22. The method of processing grammar-based legality expressions of claim 17, wherein the units of evaluation comprise an evocable operation.

23. The method of processing grammar-based legality expressions of claim 17, wherein the units of evaluation comprise a rule in a policy.

24. The method of processing grammar-based legality expressions of claim 17, wherein the units of evaluation comprise a privilege.

25. The method of processing grammar-based legality expressions of claim 17, wherein the indexing step further comprises identifying the semantic type of each atomic expression within the context of its unit of evaluation.

26. The method of processing grammar-based legality expressions of claim 1, wherein partitioning the legality expressions into units of evaluation further comprises verifying the integrity of the legality expression to ensure the legality expression has not been altered.

27. The method of processing grammar-based legality expressions of claim 1, wherein partitioning the legality expressions into units of evaluation further comprises normalizing the legality expression by converting the legality expression to a form suited for processing.

28. The method of processing grammar-based legality expression of claim 1, wherein the indexing step further comprises identifying semantic types of each atomic expression within the context of its language.

29. The method of processing grammar-based legality expressions of claim 1, wherein the indexing step further comprises associating synonymous names for each atomic expression conforming to a particular profile.

30. The method of processing grammar-based legality expressions of claim 1, wherein the sets of key values further comprise context regarding an intended use for the legality expression.

31. The method of processing grammar-based legality expressions of claim 1, wherein the sets of key values further comprise metadata associated with the legality expression.

32. The method of processing grammar-based legality expressions of claim 31, wherein the metadata associated with the legality expression comprises validity periods for the legality expression.

33. The method of processing grammar-based legality expressions of claim 31, wherein the metadata associated with the legality expression comprises information to categorize the legality expression to limit legality expression search space when processing an evaluation request.

34. The method of processing grammar-based legality expressions of claim 1, wherein the separate search spaces comprise separate database tables.

35. The method of processing grammar-based legality expressions of claim 1, wherein the separate search spaces comprise separate processors.

36. The method of processing grammar-based legality expressions of claim 1, wherein the separate search spaces comprise separate partition structures.

37. The method of processing grammar-based legality expressions of claim 1, wherein the separate search spaces comprise search spaces of different priorities.

38. The method of processing grammar-based legality expressions of claim 37, wherein the different priorities are assigned based upon the number of times that the legality expression is used.

40. The method of processing grammar-based legality expressions of claim 7, wherein the evaluating step further comprises:

validating the context of a retrieval query against requirements of an application;

profiling each atomic expression in the context of a retrieval query;

retrieving the matching atomic expressions, units of evaluation, and processing instructions from the repository;

validating the atomic expressions against unification rules;

validating the units of evaluation against unification rules; and

resolving conflicts between units of evaluation.

41. The method of processing grammar-based legality expressions of claim 40, wherein the resolving step further comprises applying the application'"'"'s policies to select preferred units of evaluation from among the units of evaluation that conflict.

42. The method of processing grammar-based legality expressions of claim 40, wherein the resolving step further comprises applying the application'"'"'s policies to combine conflicting units of evaluation.

43. The method of processing grammar-based legality expressions of claim 40, wherein the evaluating step further comprises caching requests and their corresponding results and pre-computing a set of expected common requests.

44. The method of processing grammar-based legality expressions of claim 43, wherein the caching step further comprises re-running the cached request and pre-computing a set of expected common requests at a pre-determined periodic time.

39. A method of processing grammar-based legality expressions that are adapted to be used within a system for enforcing licenses, the method comprising:

partitioning at least one legality expression into one or more units of evaluation to assess the semantic meaning of the legality expression; and

indexing at least one of the units of evaluation and the atomic expressions for subsequent retrieval based on the semantic meaning of each unit of evaluation and each atomic expression, the atomic expressions denoting the constituent components of the units of evaluation for storage, retrieval, and evaluation of the legality expressions,

wherein the indexing step further comprises creating a database table encompassing the atomic expressions associated with frequently queried entities to expedite all queries related to that entity, and associating sets of key values with legality expressions where the sets of key values provide additional information related to the legality expressions.

45. A method of translating grammar-based legality expressions into searchable independent expressions for efficiently processing communication requests for digital content, the method comprising:

validating a syntax of the legality expression against a grammar and specification to ensure the legality expression conforms to grammar rules and a specification;

verifying the integrity of the validated legality expression based on an application trust model to preserve privacy and secure usage;

normalizing the verified legality expression into a form suited for machine processing;

partitioning the normalized legality expression into units of evaluation to assess the semantic meaning of the normalized legality expression;

atomizing the units of evaluation into atomic expressions;

indexing at least one of the units of evaluation and the atomic expressions based on the semantic meanings of each unit of evaluation and each atomic expression; and

storing the indexed units of evaluation, the atomic expressions, and corresponding processing instructions in a repository,

wherein after the storing step, the method further comprises constructing a query to locate and access atomic expressions and processing instructions from the repository to match a profile of a desired input context object,

after the constructing a query step, the method further comprises retrieving atomic expressions matching a profile of the desired input context object,

after the retrieving step, the method further comprises validating atomic expressions matching a profile of the desired input context object against a predetermined unification rule, and

the predetermined unification rule evaluates whether an input context object may be used to substitute for a unit of evaluation.

46. The method of claim 45, further comprising:

profiling the atomic expressions to identify, organize, and manage storage and retrieval of legality expressions, units of evaluation, and atomic expressions that represent an identical object,

wherein the profile of a legality expression is updated each time a new profile is created in the repository.

47. The method of translating grammar-based legality expressions of claim 46, wherein the organization of the atomic expressions is based on a context in which the legality expression was received.

48. The method of translating grammar-based legality expressions of claim 47, wherein the context in which the legality expression was received comprises at least one of the following:

metadata associated with the legality expression, validity periods for the legality expression, and information used to categorize the legality expression to partition search space.

49. The method of translating grammar-based legality expressions of claim 47, wherein the context in which the legality expression was received comprises priority criteria indicating that each legality expression must be stored in a separate search space in the repository based upon the priority criteria.

50. The method of translating grammar-based legality expressions of claim 45, wherein the constructing a query step further comprises constructing an initial search domain based upon the desired input context object.

51. The method of translating grammar-based legality expressions of claim 45, wherein the separate search spaces comprise separate database tables.

52. The method of translating grammar-based legality expressions of claim 45, wherein the separate search spaces comprise separate processors.

53. The method of translating grammar-based legality expressions of claim 45, wherein the separate search spaces comprise separate partition structures.

54. The method of translating grammar-based legality expressions of claim 45, wherein the separate search spaces comprise search spaces of different priorities.

55. A legality expression processing system to process grammar-based legality expressions, the system comprising:

means for partitioning at least one legality expression into one or more units of evaluation to assess the semantic meaning of the legality expression; and

means for indexing at least one of the units of evaluation and the atomic expressions for subsequent retrieval based on the semantic meaning of each unit of evaluation and each atomic expression, the atomic expressions denoting the constituent components of the units of evaluation for storage, retrieval, and evaluation of the legality expressions,

wherein the indexing means further comprises means for assigning legality expressions to separate search spaces based upon predetermined criteria, and means for associating sets of key values with legality expressions where the sets of key values provide additional information related to the legality expressions.

56. The legality expression processing system of claim 55, wherein the separate search spaces comprise separate database tables.

57. The legality expression processing system of claim 55, wherein the separate search spaces comprise separate processors.

58. The legality expression processing system of claim 55, wherein the separate search spaces comprise separate partition structures.

59. The legality expression processing system of claim 55, wherein the separate search spaces comprise search spaces of different priorities.

60. A data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses comprising:

instructions for partitioning at least one legality expression into one or more units of evaluation to assess the semantic meaning of the legality expression; and

instructions indexing at least one of the units of evaluation and the atomic expressions for subsequent retrieval based on the semantic meaning of each unit of evaluation and each atomic expression, the atomic expressions denoting the constituent components of the units of evaluation for storage, retrieval, and evaluation of the legality expressions,

wherein the instructions for indexing further comprise instructions for creating a database table encompassing the atomic expressions associated with frequently queried entities to expedite all queries related to that entity, and instructions for associating sets of key values with legality expressions where the sets of key values provide additional information related to the legality expressions.

61. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 60, further comprising instructions for unifying a query context object and an atomic expression by evaluating the atomic expression against the context and resolving conflicts between the atomic expression and the result of the evaluation.

62. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 61, further comprising:

instructions for creating profiles representing semantic meanings of the atomic expressions; and

instructions for classifying the atomic expressions into the corresponding profiles, the profiles comprising a set of identifications assigned to the atomic expressions.

63. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 62, wherein the instructions for classifying further comprise instructions for assigning a uniquely identifiable profile identification to each profile.

64. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 63, wherein the profile identification is used to create all equivalent indices for atomic expressions and units of evaluation.

65. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 64, wherein the profile is stored in a searchable profile table.

66. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 61, further comprising:

instructions for selecting atomic expressions that match a context of a retrieval query based upon corresponding profiles of the atomic expressions; and

instructions for evaluating the selected atomic expressions by comparing the units of evaluation to a request context.

67. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 66, wherein the instructions for indexing further comprise instructions for storing the units of evaluation, the atomic expressions, and processing instructions in a repository with corresponding profiles.

68. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 66, wherein the instructions for selecting further comprise:

instructions for planning queries from input context objects; and

instructions for constructing an initial search domain for the planned queries.

69. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 68, wherein the instructions for selecting further comprise instructions for executing each planned query to retrieve the set of atomic expressions that satisfy the query request.

70. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 69, wherein the instructions for selecting further comprise instructions for constructing the units of evaluation from the atomic expressions returned from the query request.

71. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 70, wherein the instructions for selecting further comprise instructions for validating the results of each executed query against unification rules stipulating whether an atomic expression in a unit of evaluation may be unified with a corresponding atomic expression in the executed query.

72. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 71, wherein the instructions for selecting further comprise instructions for refining the search domain and for executing a modified query if the results of the executed queries fail to meet an established relevancy criterion.

73. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 69, wherein the instructions for executing each planned query to retrieve the set of atomic expressions that satisfy the query request further comprises:

instructions for analyzing variations of the atomic expression from the request context by interchanging positions of components of the atomic expression to determine if permutations of the atomic expression exist that are consistent with semantics of a unit of evaluation; and

instructions for translating the identified permutation of the atomic expression into an atomic expression that matches the request context.

74. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 68, wherein the instructions for planning queries from input context objects further comprise instructions for retrieving the profile for each atomic expression in the input context object and for using the profiles to construct queries to search for atomic expressions in a repository.

75. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 68, wherein the instructions for executing each query further comprise instructions for examining the query to determine if the query contains specific profile identifications for any atomic expressions and retrieving all possible profile identifications for the atomic expression.

76. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 66, wherein the instructions for evaluating further comprise:

instructions for validating the context of a retrieval query against requirements of an application;

instructions for profiling each atomic expression in the context of a retrieval query;

instructions for retrieving the matching atomic expressions, units of evaluation, and processing instructions from the repository;

instructions for validating the atomic expressions against unification rules;

instructions for validating the units of evaluation against unification rules; and

instructions for resolving conflicts between units of evaluation.

77. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 76, wherein the instructions for resolving further comprise instructions for applying the application'"'"'s policies to select preferred units of evaluation from among the units of evaluation that conflict.

78. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 76, wherein the instructions for resolving further comprise instructions for applying the application'"'"'s policies to combine conflicting units of evaluation.

79. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 76, wherein the instructions for evaluating further comprise instructions for caching requests and their corresponding results and for pre-computing a set of expected common requests.

80. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 79, wherein the instructions for caching further comprise instructions for re-running the cached request and for pre-computing a set of expected common requests at a pre-determined periodic time.

81. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 60, wherein the instructions for partitioning the legality expression into units of evaluation further comprise instructions for validating the legality expression against a grammar and specification to ensure the legality expression conforms to grammar rules and specifications.

82. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 81, wherein the instructions for partitioning further comprise instructions for extracting the legality expression from a resource.

83. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 81, wherein the instructions for partitioning further comprise instructions for decrypting the legality expression.

84. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 81, wherein the units of evaluation comprise an agreement in a contract.

85. The method of processing grammar-based legality expressions of claim 81, wherein the units of evaluation comprise an evocable business activity.

86. The method of processing grammar-based legality expressions of claim 81, wherein the units of evaluation comprise an evocable operation.

87. The method of processing grammar-based legality expressions of claim 81, wherein the units of evaluation comprise a rule in a policy.

88. The method of processing grammar-based legality expressions of claim 81, wherein the units of evaluation comprise a privilege.

89. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 81, wherein the instructions for indexing further comprise instructions for identifying the semantic type of each atomic expression within the context of its unit of evaluation.

90. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 60, wherein the instructions for partitioning the legality expressions into units of evaluation further comprise instructions for verifying the integrity of the legality expression to ensure the legality expression has not been altered.

91. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 60, wherein the instructions for partitioning the legality expressions into units of evaluation further comprise instructions for normalizing the legality expression by converting the verified legality expression to a form suited for processing.

92. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 60, wherein the instructions for indexing further comprise instructions for identifying all semantic types of each atomic expression within the context of its language.

93. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 60, wherein the instructions for indexing further comprise instructions for associating synonymous names for each atomic expression conforming to a particular profile.

94. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 60, wherein the sets of key values further comprise context regarding an intended use for the legality expression.

95. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 60, wherein the sets of key values further comprise metadata associated with the legality expression.

96. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 95, wherein the metadata associated with the legality expression comprises validity periods for the legality expression.

97. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 95, wherein the metadata associated with the legality expression comprises information to categorize the legality expression to limit legality expression search space when processing an evaluation request.

98. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 60, wherein the instructions for indexing further comprise instructions for assigning legality expressions to separate search spaces based upon predetermined criteria.

99. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 98, wherein the separate search spaces comprise separate database tables.

100. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 98, wherein the separate search spaces comprise separate processors.

101. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 98, wherein the separate search spaces comprise separate partition structures.

102. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 98, wherein the separate search spaces comprise search spaces of different priorities.

103. The data storage medium with computer-executable instructions for processing grammar-based legality expressions for enforcing licenses of claim 102, wherein the different priorities are assigned based upon the number of times that the legality expression is used.