METHOD AND SYSTEM FOR SEMANTIC PUBLISH-SUBSCRIBE SERVICES

• US 20080294644A1
• Filed: 05/25/2007
• Published: 11/27/2008
• Est. Priority Date: 05/25/2007
• Status: Active Grant

• Current Assignee: ServiceNow Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Ranganathan, Anand, Yang, Hao, Parthasarathy, Srinivasan, LIU, Zhen
• Granted Patent: US 8,112,416 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

A semantic publish-subscribe system, including: a plurality of subscribers; a plurality of publishers; and a server that receives and stores subscriptions that are described in web ontology language (OWL) graph patterns from the plurality of subscribers and that receives events that are described in semantic graphs formed by OWL assertions from the plurality of publishers, wherein when the server receives an event from a publisher, the server expands the OWL assertions of the event using a reasoner to produce an expanded event, the server matches the expanded event to a subscription, and then, the server notifies a subscriber whose interest matches the event.

Claims

1. A semantic publish-subscribe system, comprising:

a plurality of subscribers;

a plurality of publishers; and

a server that receives and stores subscriptions that are described in web ontology language (OWL) graph patterns from the plurality of subscribers and that receives events that are described in semantic graphs formed by OWL assertions from the plurality of publishers,

wherein when the server receives an event from a publisher, the server expands the OWL assertions of the event using a reasoner to produce an expanded event, the server matches the expanded event to a subscription, and then, the server notifies a subscriber whose interest matches the event.

2. The system of claim 1, wherein the reasoner is a description logic (DL) reasoner.

3. The system of claim 2, wherein the expanded event includes the original event and new OWL assertions.

4. The system of claim 3, wherein the new OWL assertions are a set of triples that describe additional information about the original event.

5. The system of claim 1, wherein a graph pattern of a first subscription of the subscriptions is a set of triple patterns, wherein each triple pattern includes three elements and each element is a resource description framework (RDF) term or variable,

wherein the first subscription includes a set of value constraints, wherein a value constraint in the first subscription is a boolean-valued expression of variables defined in the graph pattern of the first subscription.

6. The system of claim 5, wherein the expanded event is matched to the first subscription by,

determining if there is a pattern solution defined on the variables in the graph pattern of the first subscription such that:

after substituting variables in the graph pattern of the first subscription according to the pattern solution, the resulting graph is a sub-graph of the expanded event; and

for every value constraint in the first subscription, a logical expression obtained after substituting variables in the value constraints of the first subscription according to the pattern solution is true,

wherein if the pattern solution is satisfied, the original event matches the first subscription.

7. The system of claim 1, wherein the subscriptions are stored in a linked-chains structure by,

creating a chain of nodes for each subscription, wherein for each subscription each node in the chain of nodes represents a triple pattern in the subscription;

arranging the nodes in each chain of nodes in a decreasing order of selectivity, wherein nodes that are in different chains or the same chain are linked to each other if their triple patterns are equivalent; and

inserting the chain of nodes for each subscription into a queue by using a chain ordering algorithm.

8. The system of claim 7, wherein the expanded event is matched to the subscription by,

beginning with a first subscription in the queue and continuing until the queue becomes empty, for each subscription, evaluating the nodes in its chain of nodes from top to bottom, and for each node, checking the node against the event and finding solutions for the variables in the triple pattern of the node,

wherein if no solution is found, discarding the currently evaluated subscription and proceeding to the step of evaluating the node for a next subscription,

wherein if all nodes in the chain of nodes for the currently evaluated subscription have one or more solutions, computing a set of combined solutions for all variables in the currently evaluated subscription,

wherein for each combined solution, checking value constraints of the currently evaluated subscription to determine if the combined solution satisfies these constraints,

wherein if there is at least one combined solution that satisfies all value constraints in the currently evaluated subscription, returning the event as a match to the subscriber from whom the currently evaluated subscription was received.

9. The system of claim 7, wherein when a new subscription is received the new subscription is stored in the linked-chains structure by,

creating a new chain of nodes for the new subscription, wherein the nodes in the new chain of nodes are ordered from top to bottom in decreasing selectivity;

for each node in the new chains of nodes, an equivalent node having an equivalent triple pattern in the existing chains of nodes is searched for, and if an equivalent node is found, a link between the equivalent nodes is created; and

inserting the new chain of nodes into the queue by using the chain ordering algorithm.

10. The method of claim 7, wherein the chain ordering algorithm determines an order of subscriptions in the queue by,

constructing a complete graph and a weight function, wherein each node in the complete graph corresponds to one subscription, and a weight of an edge of the complete graph is a cost difference of evaluating a first subscription of a pair of subscriptions before a second subscription of the pair of subscriptions, as compared to evaluating the second subscription before the first subscription;

sorting the edges in an increasing order of weights;

starting from a least-weighted edge and continuing until a greatest-weighted edge, selecting the edge, if the edge alone or together with an already selected edge, does not cause a vertex to have a degree of three or more and does not form a cycle, unless the number of selected edges equals the number of vertices in the set of nodes in the complete graph; and

outputting a set of edges that covers the vertex and that has a least cost, wherein the set of edges defines the order of the subscriptions in the queue.

12. The server of claim 10, further comprising:

a linking module for creating a chain of nodes for each of the subscriptions and linking equivalent nodes in one or more of the chains of nodes so that a node which is equivalent to at least one other node is discarded so that it will not be evaluated again during the matching.

11. A server for a semantic publish-subscribe system, comprising:

a subscription maintenance module for receiving and storing subscriptions that are described in web ontology language (OWL) graph patterns from a plurality of subscribers;

a reasoning module for receiving events that are described in semantic graphs formed by OWL assertions from a plurality of publishers and for expanding the OWL assertions of the events to produce expanded events; and

a matching module for matching the expanded events to the subscriptions and notifying subscribers whose interests match the events.

13. A computer program product comprising a computer useable medium having computer program logic recorded thereon for matching an event to a subscription in a semantic publish-subscribe system, the computer program logic comprising:

program code for receiving and storing subscriptions that are described in web ontology language (OWL) graph patterns from a plurality of subscribers;

program code for receiving events that are described in semantic graphs formed by OWL assertions from a plurality of publishers and for expanding the OWL assertions of the events to produce expanded events; and

program code for matching the expanded events to the subscriptions and notifying subscribers whose interests match the events.

14. The computer program logic of claim 13, further comprising:

program code for creating a chain of nodes for each of the subscriptions and linking equivalent nodes in one or more of the chains of nodes so that a node which is equivalent to at least one other node is discarded so that it will not be evaluated again during the matching.

15. A method for matching an event to a subscription in a semantic publish-subscribe system, comprising:

receiving and storing subscriptions that are described in web ontology language (OWL) graph patterns from a plurality of subscribers;

receiving an event from a publisher that is described in a semantic graph formed by OWL assertions;

expanding the OWL assertions of the event by using reasoning to produce an expanded event;

matching the expanded event to a subscription; and

notifying the subscriber whose interest matches the event.

16. The method of claim 15, wherein the reasoning is description logic (DL) reasoning.

17. The method of claim 16, wherein the expanded event includes the original event and new OWL assertions.

18. The method of claim 17, wherein the new OWL assertions are sets of triples that describe additional information about the original event.

19. The method of claim 15, wherein a graph pattern of a first subscription of the subscriptions is a set of triple patterns, wherein each triple pattern includes three elements and each element is a resource description framework (RDF) term or variable,

wherein the first subscription includes a set of value constraints, wherein a value constraint in the first subscription is a boolean-valued expression of variables defined in the graph pattern of the first subscription.

20. The method of claim 19, wherein the expanded event is matched to the first subscription by,

determining if there is a pattern solution defined on the variables in the graph pattern of the first subscription such that:

after substituting variables in the graph pattern of the first subscription according to the pattern solution, the resulting graph is a sub-graph of the expanded event; and

for every value constraint in the first subscription, a logical expression obtained after substituting variables in the value constraints of the first subscription according to the pattern solution is true,

wherein if the pattern solution is satisfied, the original event matches the first subscription.

21. A method for matching an event to a subscription in a semantic publish-subscribe system, comprising:

receiving and storing subscriptions that are described in web ontology language (OWL) graph patterns from a plurality of subscribers, wherein the subscriptions are stored in a linked-chains structure by,

creating a chain of nodes for each subscription, wherein for each subscription each node in the chain of nodes represents a triple pattern in the subscription;

arranging the nodes in each chain of nodes in a decreasing order of selectivity, wherein nodes that are in different chains or the same chain are linked to each other if their triple patterns are equivalent; and

inserting the chain of nodes for each subscription into a queue by using a chain ordering algorithm;

receiving an event from a publisher that is described in a semantic graph formed by OWL assertions;

expanding the OWL assertions of the event by using reasoning to produce an expanded event; and

matching the expanded event to a subscription by,

beginning with a first subscription in the queue and continuing until the queue becomes empty, for each subscription, evaluating the nodes in its chain of nodes from top to bottom, and for each node, checking the node against the event and finding solutions for the variables in the triple pattern of the node,

wherein if no solution is found, discarding the currently evaluated subscription and proceeding to the step of evaluating the node for a next subscription,

wherein if all nodes in the chain of nodes for the currently evaluated subscription have one or more solutions, computing a set of combined solutions for all variables in the currently evaluated subscription,

wherein for each combined solution, checking value constraints of the currently evaluated subscription to determine if the combined solution satisfies these constraints,

wherein if there is at least one combined solution that satisfies all value constraints in the currently evaluated subscription, returning the event as a match to the subscriber from whom the currently evaluated subscription was received.

22. The method of claim 21, wherein two triple patterns are equivalent if they have equivalent subject fields, equivalent predicate fields and equivalent object fields, or if they are the same non-variable terra, or if they are variable terms that can be unified.

23. The method of claim 21, wherein when a new subscription is received the new subscription is stored in the linked-chains structure by,

creating a new chain of nodes for the new subscription, wherein the nodes in the new chain of nodes are ordered from top to bottom in decreasing selectivity;

for each node in the new chains of nodes, an equivalent node having an equivalent triple pattern in the existing chains of nodes is searched for, and if an equivalent node is found, a link between the equivalent nodes is created; and

inserting the new chain of nodes into the queue by using the chain ordering algorithm.

24. The method of claim 21, wherein the chain ordering algorithm determines an order of subscriptions in the queue by,

constructing a complete graph and a weight function, wherein each node in the complete graph corresponds to one subscription, and a weight of an edge of the complete graph is a cost difference of evaluating a first subscription of a pair of subscriptions before a second subscription of the pair of subscriptions, as compared to evaluating the second subscription before the first subscription;

sorting the edges in an increasing order of weights;

starting from a least-weighted edge and continuing until a greatest-weighted edge, selecting the edge, if the edge alone or together with an already selected edge, does not cause a vertex to have a degree of three or more and does not form a cycle, unless the number of selected edges equals the number of vertices in the set of nodes in the complete graph; and

outputting a set of edges that covers the vertex and that has a least cost, wherein the set of edges defines the order of the subscriptions in the queue.