Efficient search result update mechanism

• US 7,979,453 B2
• Filed: 08/23/2007
• Issued: 07/12/2011
• Est. Priority Date: 08/23/2006
• Status: Expired due to Fees

• Current Assignee: Innovative Solutions, Inc. (Sakata INX Corporation)
• Original Assignee: Innovative Solutions, Inc. (Sakata INX Corporation)
• Inventors: Jagannathan, Govindarajan
• Primary Examiner(s): Stevens, Robert
• Application Number:
  US11/844,229
• Publication Number:
  US 20080071769A1
• Time in Patent Office: 1,419 Days
• Field of Search: 707/5, 707/E17.081, 707/E17.063, 707/999.5, 707/741, 707/758, 707/767
• US Class Current: 707/758
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A method/algorithm allows database queries to be saved and an efficient mechanism that matches records whenever they are added or modified to all of the saved queries and returns the list of those queries that match a given record as soon as the record is added or modified. If used in an online search portal example (e.g. a job search site), this invention would allow the searcher to submit and save his search criteria once and the application would return the listings that match the search criteria at that point in time and will also automatically match any new listings that get added after the query gets saved and if a match occurs would notify the user of the listing as soon as the listing is added. This matching on new listings to the saved search will happen continuously until the search is removed. According to an aspect of the invention, by matching a record that is added or changed to the database to all saved queries, it provides convenience to the users and it also reduces the computational cost to achieve the same result relative to other existing techniques to address the same scenario.

Claims

1. A computer-implemented method comprising:

receiving a query for identifying a set of data among a plurality of sets of data, wherein the query is an expression comprising one or more component conditions, wherein the data has a plurality of attributes;

parsing the query into its component conditions;

creating entries in a plurality of condition indices for each of the component conditions parsed from the query, wherein the plurality of condition indices correspond to a respective plurality of condition types, the entries being created based on the condition type of each of the component conditions;

creating a cross-reference between the query and the parsed component conditions that have to be true in order for the query to be true;

comparing a new or changed set of data to the stored condition indices and identifying conditions that are true based on values of the attributes in the new or changed set of data and

identifying the query using the cross-reference if the necessary conditions are true for the new or changed set of data,

wherein one or more of the receiving, parsing, creating and comparing steps are implemented by the computer.

2. The method of claim 1, further comprising:

returning updated search results for the identified associated query if there is a match.

3. The method of claim 1, wherein each set of the plurality of sets of data is part of a stream of data, each set having one or more fields, and the query is a Boolean rule to be applied to certain of the fields.

4. The method of claim 1, wherein the parsing step includes:

identifying the component conditions in the query;

generating an expression in disjunctive normal form with the identified component conditions; and

identifying the plurality of condition indices based on the generated expression.

5. The method of claim 4, wherein the identified set of data is a database record, and wherein the plurality of sets of data comprise a table, and wherein the query is an SQL query and the component conditions are identified from a where clause in the SQL query.

6. The method of claim 5, wherein the table comprises the plurality of attributes associated with each record, the step of creating the cross-reference including:

maintaining a master table that maps certain of the attributes to a plurality of types of the conditions; and

updating the master table based on the identified component conditions.

7. The method according to claim 6, wherein the comparing step includes:

determining whether the new or changed record contains any of the certain attributes in the updated master table; and

limiting a determination of whether there is a match based on the determination of the new or changed record contains any of the certain attributes.

8. The method of claim 4, wherein the step of creating a cross-reference includes:

maintaining an index conditions cross reference table that associates the query with each of the identified plurality of conditions; and

updating the index conditions cross reference table based on results of the parsing step.

9. The method according to claim 8, wherein the comparing step includes:

querying the updated index conditions cross reference table using the identified plurality of condition indices.

10. The method of claim 1, wherein the sets of data include text attributes, and wherein if the query includes a text string, the parsing step includes:

updating a node table based on the text string; and

updating a node branch table based on branch paths within the text string.

11. The method of claim 10, further comprising:

maintaining a plurality of the node table and the node branch table respectively associated with each of a plurality of text conditions,

wherein the text conditions include at least Begins With, Contains and Part of.

12. The method of claim 1, wherein the sets of data include numeric or date attributes, and wherein if the query includes a numeric or date value and uses a range operator, the parsing step includes:

updating a range condition table which identifies all true conditions for a given value of a numeric or date attribute in the sets of data.

13. The method of claim 1, wherein if the query includes a NOT or NOT IN operator, the parsing step includes:

updating a NOT condition index that returns all true NOT or NOT IN conditions for a given value of an attribute in the sets of data.

14. A method comprising:

providing one or more computers that are adapted with a query tool and a database of records accessible via an online portal, wherein the records have a plurality of attributes;

receiving a query from a user via the online portal, wherein the query is an expression comprising one or more conditions;

using the query tool to perform a search of the database, and returning search results to the user;

parsing the query to extract its conditions;

creating entries in a plurality of condition indices for each of the conditions parsed from the query, wherein the plurality of condition indices correspond to a respective plurality of condition types, the entries being created based on the condition type of each of the extracted conditions;

creating a cross-reference between the query and the parsed conditions that have to be true in order for the query to be true;

receiving a new or changed record for storing in the database;

comparing the received record against the stored condition indices to determine conditions that are true based on values of the attributes in the new or changed set of data;

identifying the query using the cross-reference if the necessary conditions are true for the received record; and

notifying the user if it is determined that the search results for the query are changed.

15. The method of claim 14, wherein the notifying step includes providing the user with the changed search results.

16. The method of claim 14, wherein the notifying step includes one or more of sending an email to the user, signaling the user via an online feed, and updating a search results screen.

17. An apparatus for searching for records in a table, wherein the records have a plurality of attributes, comprising:

a computer-implemented query processor that is adapted to parse a received query, wherein the query is an expression comprising one or more conditions and the parsing extracts the conditions, create entries in a plurality of condition indices for each of the extracted conditions parsed from the query, wherein the plurality of condition indices correspond to a respective plurality of condition types, the entries being created based on the condition type of each of the component conditions, and create a cross-reference between the query and the parsed component conditions that have to be true in order for the query to be true; and

a computer-implemented query matching processor that is adapted to compare a new or changed record to the stored condition indices and to identify conditions that are true based on values of the attributes in the new or changed set of data, and to further identify the query if the necessary conditions are true for the new or changed set of data.

18. The apparatus of claim 17, wherein the table comprises a relational database, and wherein query is an SQL query and the individual conditions are identified by the query processor from a where clause in the SQL query.

19. The apparatus of claim 17, further comprising:

an online portal adapted to receive the query from a user via a network and to return search results to the user via the network.

20. The apparatus of claim 19, wherein the online portal is further adapted to notify the user if the query match processor determines that there is a match for the new or changed record.