Keyword Searching On Database Views

• US 20100299367A1
• Filed: 05/20/2009
• Published: 11/25/2010
• Est. Priority Date: 05/20/2009
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chaudhuri, Surajit, Ganti, Venkatesh, Chakrabarti, Kaushik
• Application Number:
  US12/469,399
• Publication Number:
  US 20100299367A1
• Time in Patent Office: Days
• US Class Current: 707/803
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/24535 of sub-queries or views
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/43 Querying

Abstract

A keyword search is executed on a view of a database based on a Boolean keyword query. The view includes multiple text columns, and the keyword search is executed on each of the multiple text columns in the view. The output results from the keyword search on each of the text columns include tuple identifiers of one or more relevant tuples and a relevancy score for ranking the results of the keyword query.

Claims

1. Computer readable storage media having computer readable program code embodied therein, the computer-readable program code adapted to be executed to implement a method comprising:

receiving a Boolean keyword search query for searching a view of a database, wherein the view is a virtual table that is not materialized that is generated by virtually joining one or more base relations stored in the database, wherein the view includes one or more text columns such that each text column is contained in a base relation of the view, wherein the keyword search query comprises a plurality of keywords connected by one or more Boolean operators;

executing a keyword search on each of the multiple text columns, wherein the executing the keyword search on each of the multiple text columns is based on the keyword query;

returning one or more highest scoring view tuples whose text column values together satisfy the Boolean expression on the keywords, wherein a relevancy score determined for each view tuple is based at least in part on a composition of keyword search scores of the text column values;

outputting results of the keyword search on each of the text columns, wherein the results include, for each base tuple, a tuple identifier, the relevancy score and a bit vector, wherein the bit vector is representative of which keywords from the query were located in the searched text column, wherein the bit vector for each result has a number of bit locations equal to a number and order of keywords contained in the keyword query;

storing the output results of the keyword search for each of the text columns in a plurality of buckets defined according to the bit vectors for each text column so that the output results are ordered according to the buckets;

identifying, for each bucket, a highest relevancy score from among the results stored in each bucket;

scheduling one or more buckets for processing by selecting buckets having a tuple with a highest relevancy score first in order to identify tuples most relevant to the keyword query as quickly as possible;

translating base tuples in the bucket being processed to determine corresponding view tuples in which the base tuples participate;

determining relevancy scores of those corresponding view tuples;

computing the bit vector of each view tuple from the bit vectors of the keyword search results for each text column;

filtering out view tuples that do not satisfy the Boolean expression on the keywords;

and

terminating processing of the buckets prior to processing all the buckets, and returning one or more view tuples in response to the keyword query when a total relevancy score of one or more view tuples in one or more processed buckets is determined to be greater than a possible maximum relevancy score of view tuples corresponding to buckets yet to be processed.

2. A method implemented by one or more processors executing instructions stored in computer-readable media, the method comprising:

receiving a keyword query for executing a keyword search on a view of a database, wherein the view includes multiple text columns of data;

executing the keyword search on each of the multiple text columns based on the keyword query, the keyword query comprising multiple keywords combined with one or more Boolean operators;

outputting results of the keyword search on each of the text columns, wherein the output results include a tuple identifier and a ranking for each base tuple in the results; and

identifying one or more highest-ranked view tuples that satisfies the Boolean expression on keywords in response to the keyword query.

3. The method according to claim 2,

wherein each text column is contained in a base relation of the view comprising a plurality of base tuples,

wherein the results output for each of the multiple text columns further include a bit vector for each base tuple in the results, and

wherein the bit vector indicates which keywords of the multiple keywords from the query are present in each corresponding base tuple.

4. The method according to claim 3, further comprising:

storing the results of the keyword search for each of the text columns in a plurality of buckets defined according to the bit vectors for each text column so that the results are ordered according to the buckets.

5. The method according to claim 4, further comprising:

identifying, for each bucket, a highest relevancy score from among the base tuples stored in each bucket;

scheduling one or more buckets for processing by selecting buckets having a tuple with a highest relevancy score first for identifying tuples most relevant to the keyword query as quickly as possible;

translating base tuples in the bucket being processed to determine the view tuples in which the base tuples participate;

terminating processing of the buckets prior to processing all the buckets, and returning one or more view tuples in response to the keyword query when a total relevancy score of one or more view tuples in one or more processed buckets is determined to be greater than an upper bound of view tuples corresponding to buckets yet to be processed.

6. The method according to claim 5,

wherein processing each bucket comprises finding the view tuples in which base tuples in the bucket participate, and determining the relevancy scores of those view tuples,

wherein the translating comprises issuing a query to a database management system that selects a base relation in the view corresponding to the bucket being processed, inserting tuple identifiers of the bucket into a temporary relation, and translating base tuples to view tuples based on the temporary relation and join conditions defining the view.

7. The method according to claim 6,

wherein the translating is optimized for primary key-foreign key joins when the selected base relation has a primary key column but does not have a foreign key column that references a primary key of another base relation,

wherein the optimization comprises avoiding joins with base relations that do not have a foreign key column and obtaining base tuple ids of such relations from the foreign key columns of other base relations that reference the primary key of such base relations,

wherein the join involves only the base relations having foreign key columns that reference the primary key of other base relations of the view.

8. The method according to claim 3,

wherein each text column is contained in a base relation of the view and comprises a plurality of base tuples,

wherein the results output for each text column further include a bit vector corresponding to one or more of the base tuples for each of the multiple text columns,

wherein the bit vector indicates which keywords of the multiple keywords from the query are present in each corresponding base tuple,

wherein the bit vectors of base tuples are combined to produce bit vectors of view tuples by representing in the bit vector that a particular keyword from the keyword query is present in at least one of the text columns of the view,

wherein the bit vector of each particular view tuple is produced by taking a bitwise OR of the bit vectors of the base tuples that participate in the particular view tuple.

9. The method according to claim 3, further comprising:

supporting arbitrary Boolean expressions in the keyword query by determining from the bit vectors which keywords from the keyword query are included in a view tuple.

10. The method according to claim 3, further comprising:

storing the output results of the keyword search on each of the text columns in a plurality of buckets defined according to possible bit vectors for each text column, wherein the bit vectors are representative of presence or absence of each of the keywords included in the keyword query in the text column;

identifying possible combinations of buckets by including in the possible combinations one bucket from each text column searched;

retaining the combinations of buckets that satisfy the Boolean expression in the keyword query; and

identifying results for the keyword query by processing only the buckets retained and not processing buckets not retained.

11. The method according to claim 3,

wherein there are multiple views, each view being comprised of one or more base relations from the database,

wherein the keyword query is applied to the multiple views by:

storing the output results of the keyword search for each of the text columns in a plurality of buckets defined according to possible bit vectors for each text column, wherein the bit vectors are representative of presence or absence of each of the keywords included in the keyword query in the text column;

identifying, for each bucket, a highest relevancy score from among the results stored in each bucket;

selecting a view and a bucket for processing the results stored in each bucket by selecting the view having a bucket with a highest relevancy score first;

processing the bucket in the selected view having the highest relevancy score first, wherein the processing comprises, for each base tuple in the bucket, joining corresponding base relations in the selected view to compute a total relevancy score for the view tuples in which the base tuple participates;

storing the view tuple identifier and total relevancy score for each processed result; and

terminating processing and returning one or more tuples corresponding to the stored view tuple identifiers in response to the keyword query when the total relevancy score of the one or more view tuple identifiers is determined to be greater than a maximum possible score of an unseen tuple yet to be processed in the multiple views.

12. The method according to claim 2, wherein the ranking of the results is based at least in part on a relevancy score, wherein the score includes a weighting factor applied to the results of one or more particular columns of the multiple columns based on a perceived degree of importance.

13. The method according to claim 2, where the keyword search on a view is expressed using a search API (application program interface) that takes as arguments the view to search, a set of text columns to search on, the Boolean keyword query, a number of view tuples desired and a monotone function to combine relevancy scores of individual column values and returns, at most, K highest scoring tuples of the view that satisfy the Boolean keyword query, wherein K is an integer greater than 0.

14. A system comprising:

a database;

one or more processors coupled to the database and coupled to computer readable storage media storing instructions for configuring the one or more processors,

wherein the one or more processors are configured to receive a keyword search query comprising multiple keywords and one or more Boolean operators for searching a view, wherein the view is a virtual table comprised of multiple text columns from one or more identified base relations in the database,

wherein the one or more processors are configured to perform a keyword search on the view by conducting a keyword search on each of the multiple text columns by determining whether each of the keywords included in the query is included in each text column, and

wherein the one or more processors are configured to output results of the keyword search conducted on each of the text columns, wherein the results include, for each base tuple, a tuple identifier and a bit vector, wherein the bit vector is representative of which keywords from the query are located in the searched text column.

15. The system according to claim 14,

wherein the bit vector for each result has a number of bit locations corresponding to a number and order of the keywords contained in the keyword query, wherein each bit location receives a first digit to represent presence of a corresponding keyword in the text column or a second digit to represent absence of the corresponding keyword in the text column.

16. The system according to claim 14,

wherein the results for each text column further include a relevancy score that represents a relevancy of the results to the keyword query, wherein the relevancy score includes a co-occurrence consideration that increases the relevancy of the results when multiple keywords from the search query are located in a single text column.

17. The system according to claim 16,

wherein the one or more processors are configured to determine tuple identifiers of the matching base tuples from each view text column searched, and combine the relevancy scores and bit vectors for the matching base tuples to obtain merged results for corresponding view tuples, and

wherein the one or more processors are further configured to filter the merged results to achieve a desired Boolean function, sort the filtered results according to the relevancy score for each result, and return one or more tuples having highest relevancy scores in response to the keyword query.

18. The system according to claim 14, further comprising:

a computing device in communication with a server device via a network, the computing device including a display,

wherein one or more of the one or more processors and the computer readable media are contained in the computing device,

wherein the server device is in communication with the database for providing the computing device access to the database, and

wherein contents of one or more tuples identified as the results are displayed on the display.

19. The system according to claim 14, further comprising:

a server computing device,

wherein one or more of the one or more processors and the computer readable storage media are contained in the server computing device, and

wherein the database is stored in a mass storage device accessible by the server computing device.

20. The system according to claim 14,

wherein the one or more processors are configured to store the output results of the keyword search for each of the text columns in a plurality of buckets defined according to the bit vectors for each text column searched,

wherein the one or more processors are configured to identify, for each bucket, a highest relevancy score from among the results stored in each bucket, and process the buckets having a higher relevancy score first, wherein the processing comprises, for each result in the bucket, obtaining corresponding tuple identifiers for merging the corresponding tuples to create a temporary relation and joining the temporary relation and corresponding base relations to compute a total relevancy score for a corresponding view tuple, and

wherein the one or more processors are configured to return one or more of the view tuples in response to the keyword query when the total relevancy score of the one or more view tuples is determined to be greater than a maximum possible score of an unseen tuple yet to be processed.