Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-04-22
2002-01-08
Corrielus, Jean M. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06338056
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates in general to database management systems performed by computers, and in particular, to the optimization of queries in a database management system that supports extended search capabilities such as relational extenders.
DESCRIPTION OF RELATED ART
Relational database systems using a Structured Query Language (SQL) interface are well known in the art. The SQL interface has evolved into a standard language for relational database systems and has been adopted as such by both the American Nationals Standard Organization (ANSI) and the International Standards Organization (ISO).
In relational database systems, all data is externally structured into tables. The SQL interface allows users to formulate relational operations on the tables either interactively, in batch files, or embedded in host languages such as C, COBOL, etc. Operators are provided in SQL that allow the user to manipulate the data, wherein each operator operates on either one or two tables and produces a new table as a result. The power of SQL lies on its ability to link information from multiple tables or views together to perform complex sets of procedures with a single statement.
Relational database systems have typically been used with databases comprised of traditional data types that are easily structured into tables. However, some vendors have proposed and offered relational database systems that can be used with text, images, video, audio, and other non-traditional data types. This has led to a new generation of databases, known as “object-relational databases”. These databases are extensible in terms of their type system and their query language, thereby allowing the user to create new data types and functions (or methods) to accommodate the new types of contents in the database as well as to manipulate and search such content.
Most of the existing object-relational database systems provide an architecture and application programming interface (API) for integrating content management and search functions for new data types in form of “plug-ins”. This gives vendors of content-specific search engines the opportunity to plug their existing systems into the database engine with minimal effort and provides database users with new data types and their advanced content search capabilities inside of SQL. However, to support the new data types efficiently, the database engine and optimizer have to be extended too, meaning they must be able to recognize and execute user-defined types and functions in the same way as built-types and functions. Furthermore, the internal index system needs to be extended in a way that it also covers user-defined data types. The internal index system of a database is not made for complex indexes over semi-structured data. Most databases just support a B-tree index, which is suitable for most of the conventional data types, such as integer and character data types. However, for semi-structured data, this index type is almost useless or at least not comparable in terms of efficiency with other index mechanisms.
One solution to support indexes for the data types would be to implement new index mechanism directly into the database engine. This would provide high performance and integration into the system. However, it also raises some problems. Which index mechanisms should a database provide? And how many different index types can a database system provide? Moreover, it is not an easy task to implement and integrate a new index mechanism into an existing database engine, because of its interaction with central database components such as locking and recovery management. And if someone finds a better mechanism to index the new data types, the database vendor would have to implement this new mechanism, too.
On the other hand, there are many third party vendors who already sell search engines for different semi-structured data types (e.g., all the different text search engines for the WWW). These vendors are more experienced in searching and indexing data such as text than the vendors of a database system, and they sometimes provide more than one index mechanism. Consequently, the solution for an extended index has to be much more flexible and should support the exploitation of content specific search engines that use external indexes.
For this reason, various approaches that address the extensibility of the index support have been developed over the last years. Some of them integrate user-defined access methods into the database. While this is probably the most effective way to enhance the index capability, this is also the most expensive one because it is actually just a generalized version of the approach from the paragraph above with the difference that the effort is shifted to the vendor of the search engine.
Thus, a new approach to the support of indexing of semi-structured data in a relational database system is required. Preferably, the database should use an External Search Engine through a standardized interface. The user could choose a preferred search machine to search and index the data stored in the database.
SUMMARY OF THE INVENTION
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses a method, apparatus, and article of manufacture for indexing semi-structured, non-traditional data, which is stored either in a table in a relational database or in a separate file system. The present invention uses an external search engine accessible to a database engine through a standardized interface. An index stored in the relational database managed by the database engine maps object identifiers associated with the non-traditional traditional data to row identifiers for a table stored in the relational database. In response to a query, one or more of the object identifiers are retrieved from the index in the external database by the external search engine. The object identifiers returned by the external search engine are then used by the database engine to retrieve one or more row identifiers from the index in the relational database. The row identifiers are then used to retrieve one or more rows from the table in the relational database.
REFERENCES:
patent: 4507752 (1985-03-01), McKenna et al.
patent: 5627764 (1997-05-01), Schutzman et al.
patent: 5689698 (1997-11-01), Jones et al.
patent: 5696973 (1997-12-01), Agrawal et al.
patent: 5706496 (1998-01-01), Noguchi et al.
patent: 5754841 (1998-05-01), Carino, Jr.
patent: 5765147 (1998-06-01), Mattos et al.
patent: 5778361 (1998-07-01), Nanjo et al.
patent: 5778378 (1998-07-01), Rubin
patent: 5784608 (1998-07-01), Meske, Jr. et al.
patent: 5799310 (1998-08-01), Anderson et al.
patent: 5802524 (1998-09-01), Flowers et al.
patent: 5809496 (1998-09-01), Byrd, Jr. et al.
patent: 5845278 (1998-12-01), Kirsch et al.
patent: 5893104 (1999-04-01), Srinivasan et al.
patent: 5930786 (1999-07-01), Carino, Jr. et al.
patent: 6069627 (2000-05-01), Conrad et al.
patent: 6085223 (2000-07-01), Carino, Jr. et al.
patent: WO 97/12334 (1997-03-01), None
Kim, Jeong-Ki et al., “Design and Performance Evaluation of a Dynamic Signature File Method for Parallel Database Environments,” Chongbo Kwahakhoe Nonmunji B (Journal of the Korea Information Science Society, Section B, Software and Applications), vol. 22, Issue 12, Dec. 1995, pp. 1634-1646.
Kim, Jeong-Ki et al., “Two-Dimensional Dynamic Signature File Method Using Extendible Hashing and Frame-Slicing Techniques,” Information Sciences, vol. 98, Issue 1-4, May 1997, pp. 1-26.
IBM Corporation, “DB2 Universal Database Text Extender.”, Administration and Programming, Version 5, Release 2, Sep. 1998. (Diskette only).
IBM Corporation, “Reflexive Index for Relational Databases,” Technical Disclosure Bulletin, vol. 36, No. 08, Aug. 1993, pp. 497-502.
IBM Corporation, “Method for Extending Index and Segmentation,” Technical Disclosure Bulletin, vol. 40, No. 12, Dec. 1997, pp. 139-142.
Kaushik, S.D. et
Dessloch Stefan
Fuh Gene Y. C.
Jou Michelle Mei-Chiou
Mattos Nelson Mendonca
Nitzsche Raiko
Corrielus Jean M.
Gates & Cooper LLP
LandOfFree
Relational database extender that supports user-defined... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Relational database extender that supports user-defined..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Relational database extender that supports user-defined... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2859086