Data processing: measuring – calibrating – or testing – Measurement system in a specific environment – Earth science
Reexamination Certificate
1999-02-18
2002-07-30
Breene, John (Department: 2177)
Data processing: measuring, calibrating, or testing
Measurement system in a specific environment
Earth science
Reexamination Certificate
active
06427123
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to database systems, and in particular to using a hierarchical index to access hierarchically organized information in a relational database system.
BACKGROUND OF THE INVENTION
Humans tend to organize information in categories. The categories in which information is organized are themselves typically organized relative to each other in some form of hierarchy. For example, an individual animal belongs to a species, the species belongs to a genus, the genus belongs to a family, the family belongs to an order, and the order belongs to a class.
With the advent of computer systems, techniques for storing electronic information have been developed that largely reflected this human desire for hierarchical organization. Conventional computer file systems, for example, are typically implemented using hierarchy-based organization principles. Specifically, a typical file system has directories arranged in a hierarchy, and documents stored in the directories. Ideally, the hierarchical relationships between the directories reflect some intuitive relationship between the meanings that have been assigned to the directories. Similarly, it is ideal for each document to be stored in a directory based on some intuitive relationship between the contents of the document and the meaning assigned to the directory in which the document is stored.
FIG. 1
shows an example of a typical file system. The illustrated file system includes numerous directories arranged in a hierarchy. Two documents
118
and
122
are stored in the directories. Specifically, documents
118
and
122
, both of which are entitled “Example.doc”, respectively stored in directories
116
and
124
, which are respectively entitled “Word” and “App
4
”.
In the directory hierarchy, directory
116
is a child of directory
114
entitled “Windows”, and directory
114
is a child of directory
110
. Similarly, directory
124
is a child of directory
126
entitled “VMS”, and directory
126
is a child of directory
110
. Directory
110
is referred to as the “root” directory because it is the directory from which all other directories descend. In many systems, the symbol “/” is used to refer to the root directory.
When electronic information is organized in a hierarchy, each item of information may be located by following a “path” through the hierarchy to the entity that contains the item. Within a hierarchical file system, the path to an item begins at the root directory and proceeds down the hierarchy of directories to eventually arrive at the directory that contains the item of interest. For example, the path to file
118
consists of directories
110
,
114
and
116
, in that order.
Hierarchical storage systems often allow different items to have the same name. For example, in the file system shown in
FIG. 1
, both of the documents
118
and
122
are entitled “Example.doc”. Consequently, to unambiguously identify a given document, more than just the name of the document is required.
A convenient way to identify and locate a specific item of information stored in a hierarchical storage system is through the use of a “pathname”. A pathname is a concise way of uniquely identifying an item based on the path through the hierarchy to the item. A pathname is composed of a sequence of names. In the context of a file system, each name in the sequence of names is a “filename”. The term “filename” refers to both the names of directories and the names of documents, since both directories and documents are considered to be “files”.
Within a file system, the sequence of filenames in a given pathname begins with the name of the root directory, includes the names of all directories along the path from the root to the item of interest, and terminates in the name of the item of interest. Typically, the list of directories to traverse is concatenated together, with some kind of separator punctuation (e.g., ‘/’, ‘\’, or ‘;’) to make a pathname. Thus, the pathname for document
118
is /Windows/Word/Example.doc, while the pathname for document
122
is /NVMS/App
4
/Example.doc.
The relationship between directories (files) and their contained content varies significantly between different types of hierarchically organized systems. One model, employed by various implementations, such as Windows and DOS file systems, requires each file to have exactly one parent, forming a tree. In a more complicated model, the hierarchy takes the form of a directed graph, where files can have multiple parents, as in the UNIX file system in which hard links are used.
In contrast to hierarchical approaches to organizing electronic information, a relational database stores information in tables comprised of rows and columns. Each row is identified by a unique RowID. Each column represents an attribute of a record, and each row represents a particular record. Data is retrieved from the database by submitting queries to a database management system (DBMS) that manages the database.
Each type of storage system has advantages and limitations. A hierarchically organized storage system is simple, intuitive, and easy to implement, and is a standard model used by most application programs. Unfortunately, the simplicity of the hierarchical organization does not provide the support required for complex data retrieval operations. For example, the contents of every directory may have to be inspected to retrieve all documents created on a particular day that have a particular filename. Since all directories must be searched, the hierarchical organization does nothing to facilitate the retrieval process.
A relational database system is well suited for storing large amounts of information and for accessing data in a very flexible manner. Relative to hierarchically organized systems, data that matches even complex search criteria may be easily and efficiently from a relational database system. However, the process of formulating and submitting queries to a database server is less intuitive than merely traversing a hierarchy of directories, and is beyond the technical comfort level of many computer users.
In the past, hierarchically organized systems and relationally organized systems have been implemented in different ways that were not compatible. With some additional processing, however, a relationally organized system can emulate a hierarchically organized system. This type of emulation is especially desirable when the storage capability and flexibility of a relational system is needed, but the intuitiveness and ubiquity of the hierarchical system is desired.
Such emulation may be implemented through the use of two relational tables: a “File” table and a “Directory
13
links” table. The File table stores information relating to each file in the emulated hierarchical system. For files that are documents, the File table further stores either the body of the file (in the form of a large binary object (BLOB)), or a pointer to the body of the document. The Directory
13
links table stores all of the link information that indicates the parent-child relationships between files.
To illustrate how these two tables may be used to emulate a hierarchical storage system, suppose that a file system having the hierarchical structure of
FIG. 1
is implemented in a database. The file system of
FIG. 1
can be illustrated as follows (a unique ID, shown in parentheses, is assigned by the system to uniquely identify each file):
/(X
1
)
Windows (X
2
)
Word (X
3
)
Example.doc (X
4
)
Access (X
5
)
Unix (X
6
)
App
1
(X
7
)
App
2
(X
8
)
VMS (X
9
)
App
3
(X
10
)
App
4
(X
11
)
Example.doc (X
12
)
FIG. 2
shows a files table
210
, and
FIG. 3
shows a directory links table
310
, which may be used by a computer system to emulate the file system of
FIG. 1
in a relational database system. Files table
210
contains an entry for each file in the system. Each entry includes a RowID, a file ID, a name, a body column, and a modification date column (plus other system-maintained information such as creation date, access permission information
Breene John
Henkhaus John D.
Hickman Brian D.
Hickman Palermo & Truong & Becker LLP
Oracle Corporation
LandOfFree
Hierarchical indexing for accessing hierarchically organized... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hierarchical indexing for accessing hierarchically organized..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hierarchical indexing for accessing hierarchically organized... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2917445