System and method for fast evaluation of standing queries in conjunctive normal form

• US 9,135,556 B2
• Filed: 01/18/2013
• Issued: 09/15/2015
• Est. Priority Date: 03/08/2012
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Fuchs, Matthew
• Primary Examiner(s): Starks, Wilbert L
• Application Number:
  US13/744,680
• Publication Number:
  US 20130238545A1
• Time in Patent Office: 970 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06N 5/046 Forward inferencing; Production systems
• CPC Class Codes: G06Q 10/00 Administration; Management

Abstract

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.

Claims

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.