Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-10-19
2004-09-14
Choules, Jack (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06792414
ABSTRACT:
TECHNICAL FIELD
The invention relates to the field of databases. More particularly, the invention relates to a method of enabling keyword based searches featuring generalized keyword matching on relational databases.
BACKGROUND OF THE INVENTION
SQL databases are used extensively to store information on intranets. For example, a corporation typically has multiple databases on the intranet to store a variety of information, such as an “address book” or directory of the employees, mailing list information, product, and sales details. The ability to seamlessly access and browse the information stored in these databases is important. Customized applications with front-ends that are closely tied to the schema of the database are used to enable database searching over the intranet. These applications often direct the search in a structured manner.
Structured searches are most effective when the user knows how to get to the information. However, few users are familiar with or willing to learn about the details of the schema of the various databases stored on their intranet. Furthermore, building customized web applications over each database is time consuming. These issues have limited the exploitation of the richness of intranet database information. In the field of document searches, internet search engines have popularized keyword match searches. A user submits keywords to the search engine and a ranked list of documents including a summary is returned. Internet search engines exploit an index over the document collection to enable such a search. The results of a search may retrieve documents that belong to completely different parts of the hierarchy.
While keyword searches are popular in the field of document searches, there is little support for keyword searching over a database or a collection of databases. One approach to enable keyword searching over a database is to duplicate the contents of the database as documents in a middle tier. Traditional text search techniques are then used to perform keyword searches. However, these methods typically have large space and time overheads as well as manageability concerns. In addition, the methods fail to exploit the native query processing functionality of the databases.
Keyword searches are more difficult in databases than in document collections. This is because the database has an inherent structure that may cause the required information to reside in one or more of many tables/columns. Because relational databases can search non-text data and have stored procedures that can support the notion of semantic nearness, in some ways keyword searching can be enhanced through the use of a relational database.
Some common approaches to keyword based searching of text documents are inverted lists, signature files, and prefix trees. One approach to keyword searching of XML documents parses the documents to generate inverted file information that in turn is loaded into a relational database. This approach effectively builds an inverted list that maps values to individual data objects (rows). Because this approach maps at an instance level, it suffers from scalability issues caused by duplication of data that leads to manageability problems.
The work on universal relations treats a database as a universal relation for querying purposes, thus hiding the inherent complexity of schema normalization for the purposes of querying. The challenge in this approach is to map a selection query over the universal relation to a SQL over the normalized schema. However, keyword queries are analogous to specifying universal relation queries without naming the columns involved in the selection conditions. Thus universal relation concepts are not directly applicable to keyword searches over relational databases. “DataSpot” is a commercial system that supports keyword-based searches by extracting the content of the database into a “hyperbase”. Subsequently, all keyword searches are made over the hyperbase. Thus, this approach duplicates the content of the database and suffers from the scalability issues already discussed. Most major commercial database vendors allow a full text search engine to be invoked while processing SQL. The full text search capability is invoked by virtue of specialized predicates in SQL that are processed by the full text engine. Since a “hit” using keyword may span multiple tables, full text searching is not sufficient to support keyword search over databases. Furthermore, as already discussed, such engines may encounter serious scalability problems.
Generalized matching capabilities have been used in the document retrieval field to enhance the functionality of keyword searches. Most traditional indexes used in relational databases such as a B+tree are incapable of returning cells (a cell refers to a particular column in a given row) that contain partial matches to a keyword. However, some commercial database systems have recently been enhanced to support full-text indexes that enable generalized search in text columns.
SUMMARY OF THE INVENTION
Searching over relational databases can be made more efficient by preprocessing the database to form an inverted list or lookup table of the data record components at an interim level of granularity. The list can be searched to generate a focused query on the database tables that searches only the sets of data records identified in the initial search of the index.
Special inverted lists can be constructed to support generalized keyword matching, such as sub-string or stemmed matches. These lists contain components of data records mapped to a region of the database in which they can be found. Regions of the database having components found in the search keyword are identified and a query is constructed that corresponds to the given search criteria. The query is executed on the identified regions to efficiently retrieve records matching the search criteria.
The inverted list includes a plurality of columns in which a keyword is placed in one column and a prefix component of the data record having a predetermined number of characters is placed in another column. Traditional B+ indexes are constructed for the columns. The inverted list is accessed to determine what tables/columns and prefixes have been associated with a given keyword and then a search query is constructed that searches for each prefix/keyword combination in the returned tables/columns.
REFERENCES:
patent: 5551027 (1996-08-01), Choy et al.
patent: 5701467 (1997-12-01), Freeston
patent: 5926820 (1999-07-01), Agrawal et al.
patent: 6122626 (2000-09-01), Brandsma
patent: 6505191 (2003-01-01), Baclawski
Sanjiv Kapoor and H.Ramesh, “Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs”, SIAM J Comput., vol. 24, No. 2, pp. 247-265, Apr. 1995.
Shaul Dar, Gadi Entin, Shai Geva, Eran Palmon, Data Technologies, Ltd. “DTL's DataSpot: Database Exploration Using Plain Language”, Proceedings of the 24thVLDB Conference, New York, USA, 1998, pp. 645-649.
Roy Goldman, Narayanan Shivakumar, Suresh Venkatasubramanian, Hector Garcia-Molina, Stanford University, “Proximity Search in Databases”, Proceedings of the 24thVLDB Conference, New York, USA, 1998, pp. 26-37.
Tomas Feder, Rajeev Motwani, “Clique Partitions, Graph Compression and Speeding-Up Algorithms”, STOC, 1991, pp. 123-133.
G.J. Minty, “A Simple Algorithm for Listing all Trees of a Graph”, IEEE Trans. On Circuit Theory, 1965.
J.D. Ullman, “Principles of Databases and Knowledge-Base Systems”, vol. II, Computer Science Press, 1989, pp. 1026-1062.
Agrawal Sanjay
Chaudhuri Surajit
Choules Jack
Microsoft Corp.
Microsoft Corporation
LandOfFree
Generalized keyword matching for keyword based searching... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Generalized keyword matching for keyword based searching..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generalized keyword matching for keyword based searching... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3211013