Method for storing Boolean functions to enable evaluation, modification, reuse, and delivery over a network

• US 6,910,033 B2
• Filed: 07/19/2002
• Issued: 06/21/2005
• Est. Priority Date: 08/15/2001
• Status: Expired due to Fees

• Current Assignee: Precache Incorporated
• Original Assignee: Precache Incorporated
• Inventors: Rosenblum, David S.
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): Veillard, Jacques
• Application Number:
  US10/199,369
• Publication Number:
  US 20030154193A1
• Time in Patent Office: 1,068 Days
• Field of Search: 707/1, 707/3, 707/6, 707/103.R, 707/104.1, 707/200, 709/201, 709/203, 709/220, 709/223, 709/224, 709/227, 455/410, 455/411
• US Class Current: 709/223
• CPC Class Codes: H04L 67/55 Push-based network services
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: Y10S 707/954 Relational
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Data structures for storing subscription predicates for transmission in a publish-subscribe network. Subscriptions include Boolean-valued predicates defining content desired by a subscriber. An agent application converts the predicates into a suitable form for storing them in a common data structure. The predicates are used to generate filters to encapsulate the subscriptions, and the filters are specified in the data structure in addition to the Boolean relationships of the predicates. Routers in a network core use the data structure for content-based routing, which involves applying attributes in received packets to the filters.

Claims

1. A method for storing subscriptions for a publish-subscribe network, Comprising:

specifying a structure to store a subscription in the network;

dividing the structure into a plurality of sub-expressions, wherein the dividing step includes;

using the sub-expressions to store the subscription in a disjunctive normal form, and

simplifying AND expressions in the disjunctive normal form to contain range filters and membership tests in the sub-expressions;

using the sub-expressions to collectively specify a particular subscription; and

associating a Boolean-valued predicate with at least one of the sub-expressions for the particular subscription, wherein the Boolean valued predicate provides an indication of a notification element for the particular subscription in order to provide content-based routing for the subscription.

2. The method of claim 1 wherein the using step includes using one particular sub-expression in multiple subscriptions.

3. The method of claim 1 wherein the associating step includes associating a disjunction, conjunction, or negation predicate with the sub-expression for the particular subscription.

4. The method of claim 1, further including specifying a constant value for at least one of the sub-expressions for the particular subscription.

5. The method of claim 1, further including specifying a relationship among a plurality of notification elements for the particular subscription.

6. The method of claim 1 wherein the specifying step includes specifying an hierarchical structure having multiple levels for specifying the sub-expressions.

7. The method of claim 1 wherein the dividing step includes translating not-equal parameters in the subscription to positive form in the sub-expressions.

8. The method of claim 1, further including:

receiving the subscription; and

creating the sub-expressions from the subscription.

9. The method of claim 1, further including parsing the sub-expressions in order to detect errors in the subscription.

10. An apparatus for storing subscriptions for a publish-subscribe network, comprising:

a specify module for specifying a structure to store a subscription in the network;

a divide module for dividing the structure into a plurality of sub-expressions, wherein the divide module includes;

a module for using the sub-expressions to store the subscription in a disjunctive normal form; and

a module for simplying AND expressions in the disjunctive normal form to contain range filters and membership tests in the sub-expressions;

a use module for using the sub-expressions to collectively specify a particular subscription; and

an associate module for associating a Boolean-valued predicate with at least one of the sub-expressions for the particular subscription, wherein the Boolean valued predicate provides an indication of a notification element for the particular subscription in order to provide content-based routing for the subscription.

11. The apparatus of claim 10 wherein the use module includes a module for using one particular sub-expression in multiple subscriptions.

12. The apparatus of claim 10 wherein the associate module includes a module for associating a disjunction, conjunction, or negation predicate with the sub-expression for the particular subscription.

13. The apparatus of claim 10, further including a module for specifying a constant value for at least one of the sub-expressions for the particular subscription.

14. The apparatus of claim 10, further including a module for specifying a relationship among a plurality of notification elements for the particular subscription.

15. The apparatus of claim 10 wherein the specify module includes a module for specifying an hierarchical structure having multiple levels for specifying the sub-expressions.

16. The apparatus of claim 10 wherein the divide module includes a module for translating not-equal parameters in the subscription to positive form in the sub-expressions.

17. The apparatus of claim 10, further including:

a module for receiving the subscription; and

a module for creating the sub-expressions from the subscription.

18. The apparatus of claim 10, further including a module for parsing the sub-expressions in order to detect errors in the subscription.