System and method for fast evaluation of standing queries in conjunctive normal form
View Patent ↗Methods and systems are provided for evaluating standing queries against updated contact entries configured as a stream of facts. The method includes resolving the standing queries into an array of rules, each rule having a first and a second condition; sorting t one of the facts into a first property and a second property; comparing the first property of the fact to the first condition of each rule in the array of rules to produce a first subset of matching rules; comparing the second property of the fact to the second condition of each rule in the first subset of rules to produce a second subset of matching rules; and reporting at least one of the second subset of rules to an author of the matching rule. The method further includes populating a first hash with indicia of the first subset, and populating a second hash with the second subset.
1. A computer implemented method of evaluating standing queries in conjunctive normal form, comprising:
resolving the standing queries in conjunctive normal form into a set of rules, each rule comprising a sequence of conditions;
sorting, for each rule, the conditions into a logical order; identifying a fact having a plurality of properties sorted in a logical order; evaluating the sorted fact against each sorted rule, wherein the evaluating comprises comparing the fact to each rule using hash tables, and further comprises using a second property associated with the fact as a key into a hash table to return a second set of rules; and
identifying a subset of the set of rules which match the fact.
2. The method of claim 1 , wherein the logical order is lexicographical.
3. The method of claim 1 , wherein resolving comprises reducing at least one clause in a query from a disjunction of literals to a single literal.
4. The method of claim 1 , wherein the fact comprises N properties and each rule comprises up to N conditions, where N is an integer.
5. The method of claim 1 , wherein the conditions and the properties include at least two of: city; last name; first name; country; company; zip code; and title.
6. The method of claim 1 , wherein identifying comprises selecting a fact from a database of contact entries.
7. The method of claim 6 , wherein selecting comprises selecting a contact entry that has been changed.
8. The method of claim 7 , wherein selecting comprises incorporating the fact into an event stream.
9. The method of claim 1 , wherein a first property is used as a key into a hash table to return a first set of rules.
10. The method of claim 1 , wherein evaluating comprises creating a high level hash table representing first evaluation results.
11. The method of claim 10 , wherein evaluating comprises creating at least one secondary hash table representing second evaluation results.
12. A computer implemented method of evaluating standing queries in conjunctive normal form, comprising:
resolving the standing queries in conjunctive normal form into a set of rules, each rule comprising a sequence of conditions;
sorting, for each rule, the conditions into a logical order; identifying a fact having a plurality of properties sorted in a logical order; evaluating the sorted fact against each sorted rule; identifying a subset of the set of rules which match the fact; and reporting the subset of rules which match the fact.
13. The method of claim 12 , wherein reporting comprises notifying an author of one of the rules in the subset of rules.
14. The method of claim 12 , wherein reporting comprises posting at least one of the rules of the subset of rules on a website accessible by an author of the posted rule.
15. A computer implemented method of evaluating standing queries in conjunctive normal form, comprising:
resolving the standing queries in conjunctive normal form into a set of rules, each rule comprising a sequence of conditions;
sorting, for each rule, the conditions into a logical order; identifying a fact having a plurality of properties sorted in a logical order; evaluating the sorted fact against each sorted rule; and
identifying a subset of the set of rules which match the fact, wherein evaluating is performed by a server in a multitenant computing environment.