Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-10-19
2004-10-05
Choules, Jack (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06801904
ABSTRACT:
TECHNICAL FIELD
The invention relates to the field of databases. More particularly, the invention relates to a method of enabling keyword based searches 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.
SUMMARY OF THE INVENTION
Searching over relational databases can be made more efficient by preprocessing the database to form an index of the data records at an interim level of granularity. The index 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.
A search of a relational database for data records relating to given search criteria is enabled by creating an index of the data records that maps a record to a region of the database in which it is found. The index is accessed to identify regions of the database that contain data records relating to the given search criteria. A query is constructed that corresponds to the given search criteria and the query is executed on the identified regions of the database to retrieve records matching the search criteria.
To prepare a database to enable searches based on keywords a symbol table is constructed that stores location information for each keyword. The location information may be at a table/column level or at a cell level where a cell corresponds to a particular column in a given row. The symbol table may be constructed by hashing the keywords into a hash table and then compressing the table.
Upon receiving search keywords, the symbol table is searched to identify tables and columns that contain the search keywords. Database subgraphs of the overall schema graph of the relational database that span the set of search keywords are enumerated having nodes that represent tables. The enumerated subgraphs are evaluated to generate queries on the database that select records containing the search keywords. The enumeration of database subgraphs may be based on a schema graph describing a structure of the database tables. The enumerated database subgraphs may be pruned by eliminating leaves that do not contain and of the search keywords. A database query may be generated that joins the tables represented in the database.
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 Tress 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”, Proceeding 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
Das Guatam
Choules Jack
Microsoft Corp.
LandOfFree
System for keyword based searching over relational databases does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for keyword based searching over relational databases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for keyword based searching over relational databases will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3293565