Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-08-27
2002-10-22
Robinson, Greta (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06470344
ABSTRACT:
BACKGROUND
This invention relates to the field of database management systems. More particularly, a system and methods are provided for indexing multi-dimensional data, storing such data in a relational database management system and efficiently retrieving the data upon demand.
Various methods of managing collections of data (e.g., databases) have been developed since data was first stored in electronic form. From initial systems and applications that simply collected data in one or more flat database files to present sophisticated database management systems (DBMS), different solutions have been developed to meet different requirements. Early solutions may have had the advantage of simplicity but became obsolete for a variety of factors, such as the need to store large—even vast—quantities of data, a desire for more sophisticated search and/or retrieval techniques (e.g., based on relationships between data), the need to store different types of data (e.g., audio, visual), etc.
A database may be considered distinct from a DBMS, in that a DBMS, as the name implies, includes utilities for accessing, updating and otherwise managing or operating a database. As the amount and complexity of data stored in databases has increased, DBMS design and development efforts have increasingly focused upon the ability to organize, store and access data quickly and efficiently. As a result, today's database management systems can be very effective in managing collections of linear information such as inventory, customer lists, etc.
With such linear (or uni-dimensional) data—data that varies in value in a single dimension—determining and maintaining relationships between data elements is relatively easy. For example, one value or data point (e.g., a price, a quantity) can easily be compared to another to determine which is “greater” or which ones match a particular query. The ordinal nature of linear data therefore readily lends itself to basic indexing and subsequent storage, search, retrieval and other data management operations. In particular, the appropriate point for insertion, retrieval or deletion of a data element in a database of linear data may be found with great facility by referring to a table or other data index.
In short, today's database management systems have been designed to manage linear data very effectively. Present database management schemes are still poorly suited, however, for managing data that are multi-dimensional in nature. Geographic data, for example, may be meaningful only when expressed in at least two dimensions (e.g., latitude and longitude) and can thus be considered “inherently” multi-dimensional Because such data can vary in value in more than one dimension, the relationship between selected geographic points is more complex and, unless a particular reference dimension or other criteria is chosen, one point cannot automatically be considered “greater” or “less” than another. The difficulty in expressing relations among inherently multi-dimensional data makes indexing such data (e.g., for storage and retrieval) more complicated and can also complicate schemes for buffering the data as queries are processed.
Closely related to inherently multi-dimensional data are multi-dimensional data that may also be termed “multi-attribute” in nature. Multi-attribute data may be defined as information that possesses multiple defining characteristics that are not inherently related. For example, sales data may be considered multi-attribute in nature if characteristics such as time of sale, region of sale, salesperson, product sold, type/model of product, and so on are recorded for each sale. These data become multi-dimensional or multi-attribute in nature when queries are made or reports are desired that specify range predicates in two or more of the data attributes (e.g., the sales made by Salesperson A during the previous month, the best time of year for selling a particular product). Today's database management systems are, unfortunately, not designed to organize this data in a manner that enhances the ability to retrieve those data items satisfying a particular multi-dimensional query pattern.
Present techniques for dealing with (e.g., indexing, storing, retrieving) multi-dimensional data often involve attempts to translate the data into a single dimension so that existing systems may be used. These techniques may fail to maintain important spatial relationships, however, thus adversely affecting the ability to respond rapidly to multi-dimensional queries. For example, linear quadtrees and Hilbert R-trees transform multi-dimensional data into a single dimension and then construct B-trees on the linearized data. Although these schemes may be adequate for two-dimensional data, linearizing data having three or more dimensions may result in an unacceptable loss of a spatial or other data relationship.
Meanwhile, the number and types of applications that use multi-dimensional and multi-attribute data—such as geographic information systems (GIS) and computer-aided design and manufacturing (CAD/CAM) systems—continue to grow. A GIS application may work with maps or charts in which spatial data are expressed in two or three dimensions (e.g., latitude, longitude and, possibly, altitude). Similarly, in CAD/CAM applications, products such as printed circuit boards for computer systems may be designed using rectangular areas or cubical volumes. A person using one of these applications may select an area of interest that contains or intersects one or more elements. The application must be able to accurately identify those elements and facilitate modification of the data.
Multi-media applications, in which audio and visual elements are combined in one database, are another area that can benefit from efficient storage of multi-dimensional data. For example, an element of a graphical image may require multi-dimensional data for accurate representation. In particular, graphic images may be described in terms of numerous spectral characteristics (all or some of which may be inherently inter-related). Thus, in a graphical element that embodies a combination of colors (e.g., some mixture of red, green and blue pixels on a computer display) the different colors of the element may be represented in different dimensions. Each dimension's value could, for example, represent the relative proportion of the corresponding color within the element or the number of pixels within the element that have that color. Accurate representation of this data would allow an application to easily identify elements that have similar coloring.
Because effective methods of organizing multi-dimensional data in a DBMS have been generally unknown, applications that use such data have been unable to reap the advantages offered by today's database management systems, especially relational database management systems (RDMBS). Among those advantages are backup and recovery utilities, robust security, and controls allowing concurrent data access. Developers of these applications have, instead, had to rely upon other methods of indexing and storing such data.
What is needed then is a method of organizing multi-dimensional/multi-attribute data in a DBMS, particularly a relational DBMS, in order to reap the advantages of sophisticated management controls (e.g., concurrent access to the data) without sacrificing spatial relationships. Advantageously, such a DBMS would provide for efficient organization of the data to facilitate rapid retrieval.
Further, an efficient method or system for facilitating retrieval of multi-dimensional/multi-attribute data is also needed. In particular, a suitable technique is required for buffering data as database queries are processed.
SUMMARY
In addition to providing for effective management of data that are inherently multi-dimensional (e.g., geographic, multi-media), an embodiment of the invention also provides for the storage and management of linear data having multiple attributes. For example, a database of sales figures may be indexed according to attributes such
Banerjee Jayanta
Kothuri Ravi
Ravada Siva
Sharma Jayant
Singh Ambuj
Oracle Corporation
Park, Vaughn & Fleming LLP
Robinson Greta
LandOfFree
Buffering a hierarchical index of multi-dimensional data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Buffering a hierarchical index of multi-dimensional data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Buffering a hierarchical index of multi-dimensional data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2948587