Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-07-09
2002-05-14
Mizrahi, Diane D. (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06389425
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to computer-implemented database systems, and, in particular, to an embedded storage mechanism for structured data types.
2. Description of Related Art
Databases are computerized information storage and retrieval systems. A Relational Database Management System (RDBMS) is a database management system (DBMS) which uses relational techniques for storing and retrieving data. Relational databases are organized into tables which consist of rows and columns of data. The rows are formally called tuples or records. A database will typically have many tables and each table will typically have multiple tuples and multiple columns. The tables are typically stored on direct access storage devices (DASD), such as magnetic or optical disk drives for semi-permanent storage.
Traditionally, a RDBMS stores simple data, such as numeric and text data. In a traditional RDBMS, the underlying storage management has been optimized for simple data. More specifically, the size of a record is limited by the size of a data page, which is a fixed number (e.g., 4 K) defined by a computer developer. This restriction in turn poses a limitation on the length of data in columns of a table. To alleviate such a restriction, most computer developers today support a new built-in data type for storing large objects (LOBs). Large object types include audio, video, image, text, spatial data (e.g., shape, point, line, polygon, etc.), time series data, OLE documents, Java objects, C++ objects, etc. Large objects typically take up a great deal of storage space. However, the access time for LOB object data is significantly slower than that of simple data types. This occurs because the LOB object data is accessed through a LOB descriptor stored in a record buffer and requires an extra input/output (I/O) access of a database. In many applications, where the average size of an object is typically much smaller than the largest size of the object, using a LOB descriptor is the only way to store object data, but storage comes at the cost of performance. This problem also applies to structured object types, such as abstract data types, arrays, lists, sets, etc.
In some conventional systems, when a column is defined for data of a structured data type, the conventional system stores a token in the column that refers to another table, which contains a column for each attribute of the structured data type. However, if a user wants to store data in that column having more attributes, the conventional system does not have a simple and efficient technique for storing that data in the column.
Moreover, conventional systems are not adequate for handling storage for structured data types for user-defined data. Therefore, there is a need in the art for an improved embedded storage mechanism for structured data types.
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 a computer-implemented embedded storage mechanism for structured data types.
In accordance with the present invention, A statement is stored in a database stored on a data storage device connected to a computer. At compile-time, specific methods for a structured data type are mapped to generic methods using parse trees. At run-time, an in-memory representation of the structured data type is generated using the information conveyed in the parse trees. Then, linearization of the generated in-memory representation is performed.
An object of the invention is to provide substitutability for columns defined with structured data types. Another object of the invention is to provide extensibility of a type hierarchy.
REFERENCES:
patent: 4531186 (1985-07-01), Knapman
patent: 4841433 (1989-06-01), Hakim et al.
patent: 5043872 (1991-08-01), Cheng et al.
patent: 5299123 (1994-03-01), Wang et al.
patent: 5327543 (1994-07-01), Miura et al.
patent: 5404510 (1995-04-01), Smith et al.
patent: 5454039 (1995-09-01), Coppersmith et al.
patent: 5544357 (1996-08-01), Huei
patent: 5546576 (1996-08-01), Cochrane et al.
patent: 5553281 (1996-09-01), Brown et al.
patent: 5590325 (1996-12-01), Kolton et al.
patent: 5604892 (1997-02-01), Nuttall et al.
patent: 5608904 (1997-03-01), Chaudhuri et al.
patent: 5619692 (1997-04-01), Malkemus et al.
patent: 5630125 (1997-05-01), Zellweger
patent: 5630127 (1997-05-01), Moore et al.
patent: 5857182 (1999-01-01), DeMichiel et al.
patent: 6061678 (2000-05-01), Klein et al.
patent: 6065013 (2000-05-01), Fuh et al.
patent: 0 650 131 (1995-04-01), None
IEEE publication, “A Practical and Space Efficient Scheme For Keeping Source Code Location in Parse Trees”, by Jianhua Zhu, U.S. West Advanced Technologies, Boulder Colorado, pp. 374-379, Nov. 1993.*
IEEE publication, “Modeling and Querying Structure and Contents of the Web” by Wolfgang May, Institute fuer Informatik, Universitaet Frieburg, Germany, pp. 721-725, Nov. 1993.*
“Heirarchical Data Model for a Relational Database based Geographic Information System”,IBM® Technical Disclosure Bulletin, 40(03):107-116 (Mar. 1997).
Lynch, C. et al., “Extended User—Defined Indexing with Application to Textual Databases”, Proceedings of the 14th VLDB Conference, pp. 306-317 (1988).
Rudolf Bayer, “The Universal B—Tree for Multidimensional Indexing: General Concepts”, Worldwide Computing and Its Applications, International Conference, WWCA '97, Tsukuba, Japan, (Mar. 1997). pp. 198-209.
Faloutsos, C. et al., “Fast Map: A Fast Algorithm for Indexing, Data—Mining and Visualization of Traditional and Multimedia Datasets”, Proc. of ACM SIGMOD, pp. 163-174 (May 1995).
Ouksel, M. et al., “Multidimensional B—trees: Analysis of Dynamic Behavior”, Dept. of Elec. Eng. and Computer Science, Northwestern Univ., Evanston, Ill., BIT 21, pp. 401-418 (1981).
Klaus, F. et al., “Flexible, Runtime Efficient Fector—Radix Algorithms For Multidimensional Fast Fourier Transform”, SPIE, vol. 2247, Sensors and Control for Automation, pp. 216-226 (1994).
Sang, K.S. et al., “Applicability of genetic algorithms to optimal evaluation of path predicates in object—oriented queries”, Information Processing Letters, vol. 58, No. 3, 123-128 (abstract), (May 1996).
Byungwook, K. et al., “A new indexing scheme supporting multi-attribute database applications: MAX”, Journal of Systems Architecture, vol. 42, No. 2, (abstract), (Sep. 1996). p. 1.
Silberschatz, A. et al., “Managing Class Types”, SPI Database of Software Technologies, 6 pages, (May 1977).
Scheuermann, P. et al., “Multidimensional B—Trees For Associative Searching In Database Systems”, Inform. Systems, vol. 7, No. 2, pp. 123-137 (1982).
DeMichiel Linda Gail
Fuh Gene Y. C.
Lindsay Bruce Gilbert
Mattos Nelson Mendonca
Tran Brian Thinh-Vinh
Mizrahi Diane D.
Sughrue & Mion, PLLC
LandOfFree
Embedded storage mechanism for structured data types does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Embedded storage mechanism for structured data types, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Embedded storage mechanism for structured data types will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2820252