Optimized query tree
First Claim
1. A method for filtering information structures so as to select any of the information structures that satisfy a logical expression of at least one query, the method comprising the steps of:
- providing a first query having a logical expression that defines a subset of the information structures that is to be selected;
constructing a filtering tree representing the logical expression, comprising the steps of;
creating a first non-leaf node of the filtering tree, the first non-leaf node representing a first operation associated with the logical expression;
creating a first leaf node and a second leaf node, each having a logical value to be assigned to the first query when the particular leaf node is encountered during a process of traversing the filtering tree, each of the first leaf node and the second leaf node depending directly or indirectly from in the first non-leaf node; and
storing, in a computer-readable medium accessible by a computer system, computer-executable code for traversing the filtering tree.
2 Assignments
0 Petitions
Accused Products
Abstract
Systems and methods for constructing and using filtering trees to compare events, data, or other instances of objects defined in an object-oriented schema against one or more query-based definitions. The filtering trees correspond to the logical expressions of one or more query-based definitions, and represent the structure of the computer-executable instructions for comparing events with the definitions. The filtering trees can be traversed so as to simultaneously compare the parameters of an event against multiple logical expressions. The filtering tree is traversed in a top to bottom cascading fashion until a leaf node is encountered in a process that is conceptually equivalent to processing the logical operations associated with the nodes. When a leaf node is encountered, an ordered set of logical values associated with the leaf node indicates which, if any, of the definitions are satisfied by the event. The filtering definitions can be conveniently used to filter events detected by event providers in a computer system so as to identify the event that are to be reported to event subscribers.
147 Citations
31 Claims
-
1. A method for filtering information structures so as to select any of the information structures that satisfy a logical expression of at least one query, the method comprising the steps of:
-
providing a first query having a logical expression that defines a subset of the information structures that is to be selected;
constructing a filtering tree representing the logical expression, comprising the steps of;
creating a first non-leaf node of the filtering tree, the first non-leaf node representing a first operation associated with the logical expression;
creating a first leaf node and a second leaf node, each having a logical value to be assigned to the first query when the particular leaf node is encountered during a process of traversing the filtering tree, each of the first leaf node and the second leaf node depending directly or indirectly from in the first non-leaf node; and
storing, in a computer-readable medium accessible by a computer system, computer-executable code for traversing the filtering tree. - View Dependent Claims (2, 3, 4, 5, 6)
providing a second query having a second logical expression that defines another subset of the information structures that is to be selected; and
creating a second node of the filtering tree, the second non-leaf node depending from the first non-leaf node and representing a second operation, the second operation being associated with the second logical expression.
-
-
3. A method as defined in claim 1, further comprising the step of providing a second query having a second logical expression that defines another subset of the information structures that is to be selected, wherein the first non-leaf node further represents a second operation, the second operation being associated with a logical operation of the second query.
-
4. A method as defined in claim 1, further comprising the steps of:
-
comparing the first operation represented by the first-level node with a value of a parameter of the information structure so as to determine which of two or more child nodes depending from the first-level node is to be considered next;
continuing to compare operations represented by any successive non-leaf nodes with the value of corresponding parameters of the information structure until one of the first leaf node and the second leaf node is encountered; and
assigning the value of the encountered leaf node to the first query.
-
-
5. A method as defined in claim 1, wherein the information structure is included in a relational database.
-
6. A method as defined in claim 1, wherein the information structure is an event detected by the computer system.
-
7. In a computer system, a method for assembling a filtering tree representing operations whereby a detected event can be simultaneously compared to logical expressions of at least a first query and a second query, the method comprising the steps of:
-
communicating the first query and the second query to an event-filtering component of the computer system, the first query and the second query being satisfied when the value of one or more parameters of a detected event satisfy the conditions of a logical expression of the particular query;
creating a first non-leaf node of the filtering tree, the first non-leaf node representing a first operation associated with the logical expression of the first query;
creating a first leaf node and a second leaf node, each having an ordered set of logical values to be assigned to the first query and the second query when the particular leaf node is encountered during a process of traversing the filtering tree, each of the first leaf node and the second leaf node depending directly or indirectly from the first non-leaf node; and
storing, in a computer-readable medium accessible by the computer system, computer-executable code for traversing the filtering tree. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. In a computer system, a method for traversing a filtering tree so as to execute operations for comparing a detected event with at least one filtering query associated with one or more event subscribers, the method comprising the steps of:
-
providing the filtering tree, wherein the filtering tree includes at least;
a first-level non-leaf node representing a first operation associated with a logical expression of a first query selected from the at least one filtering query, the first-level node having child nodes depending therefrom;
a first leaf node depending directly or indirectly from the first-level node, the first leaf node being associated with a false value; and
a second leaf node depending directly or indirectly from the first-level node, the second leaf being associated with a true value;
comparing the first operation represented by the first-level node with a value of a parameter of the detected event so as to determine which of the child nodes is to be considered next;
continuing to compare operations represented by any successive non-leaf nodes with the value of corresponding parameters of the detected event until one of the first leaf node and the second leaf node is encountered; and
assigning the value of the encountered leaf node to the first query. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
traversing said one of the plurality of filtering trees until one of the leaf nodes of said one of the plurality of filtering trees is encountered; and
assigning, to each of one or more event-filtering queries associated with said one or more of the plurality of filtering trees, a logical value contained in an ordered set of one or more logical values associated with the encountered leaf node.
-
-
22. A method as defined in claim 13, further comprising the step of determining that an event provider is associated with an empty filtering tree that indicates that the event provider does not report any event for which notification is to be made to any of the one or more event subscribers.
-
23. A method as defined in claim 22, further comprising the step of deactivating the event provider.
-
24. In a computer system including one or more event providers for detecting the occurrence of events and one or more events subscribers for receiving notification of the occurrence of a subset of the events, a method of determining whether a selected event provider can detect events for which notification is to be made to any of the one or more event subscribers, comprising the steps of
communicating one or more event-filtering queries to an event-filtering component of the computer system, wherein each event subscriber is associated with one event-filtering query and wherein each event-filtering query specifies a subset of events for which notification is to be made to the associated event subscriber; -
communicating an event-reporting query associated with one event provider to the event-filtering component, wherein the event-reporting query indicates that the associated event provider can report only events satisfying a logical expression of the event-filtering query;
determining that there is no possible event that both satisfies the logical expression of the event-filtering query and is included in any of said subsets of events; and
deactivating said one provider such that it does not report the occurrence of any event to the event-filtering component. - View Dependent Claims (25, 26)
determining that there is a possible event that both satisfies a logical expression of another event-filtering query associated with another one of the event providers and is included in at least one of said subsets of events; and
activating said other one of the event providers.
-
-
26. A method as defined in claim 24, wherein the step of determining that there is no possible event comprises the steps of:
-
constructing a filtering tree representing all operations of the logical expressions of all the event-filtering queries and all operations of the logical expression of the event-reporting query, the filtering tree including;
a first non-leaf node representing at least one operation selected from at least one of the logical expressions of the event-filtering queries and the logical expression of the event-reporting query; and
a plurality of leaf nodes depending directly or indirectly from the first non-leaf node, each of the leaf nodes having an ordered set of logical values to be assigned to the event-filtering queries and the event-reporting query when the particular leaf node is encountered while traversing the filtering tree; and
determining that none of the leaf nodes has an ordered set of logical values that includes a true value to be assigned to the event-reporting query and a true value to be assigned to any one of the event-filtering queries.
-
-
27. A computer program product for implementing a computer-executed method of assembling a filtering tree that represents operations whereby an event detected by a computer system can be simultaneously compared to logical expressions of at least a first query and a second query, the computer program product comprising:
-
a computer-readable medium carrying computer-executable instructions for implementing the method, the computer-executable instructions comprising;
program code means for receiving a first query and a second query, wherein the first query and the second query are satisfied when the value of one or more parameters of a detected event satisfy the conditions of a logical expression of the particular query;
program code means for constructing a computer-executable routine for traversing a filtering tree so as to compare parameters of the detected event with the conditions of the logical expressions, the filtering tree including;
a first non-leaf node representing a first operation associated with the logical expression of the first query;
a first leaf node and a second leaf node, each having an ordered set of logical values to be assigned to the first query and the second query when the particular leaf node is encountered while traversing the filtering tree, each of the first leaf node and the second leaf node depending directly or indirectly from the first non-leaf node. - View Dependent Claims (28, 29, 30, 31)
-
Specification