Methods and systems for updating an inheritance tree with...

Details Methods and systems for updating an inheritance tree with... Methods and systems for updating an inheritance tree with...

2000-07-12

2003-04-01

Metjahic, Safet (Department: 2171)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

06542884

ABSTRACT:

BACKGROUND OF THE INVENTION
1. The Field of the Invention
The present invention relates to database and file management. Specifically, the present invention relates to methods and systems for updating an inheritance tree of a hierarchical directory tree structure with minimal increase in memory usage, the hierarchical directory tree structure including properties that describe certain nodes within the hierarchical directory structure.
2. The Prior State of the Art
Computer systems typically use a hierarchical directory tree structure for organizing data objects such as files. The following illustrates a conventional hierarchical directory tree structure (hereinafter, “tree”) used to store files including “file1.log” through “file5.log”.
/root/
dir1/
file1.log
file2.log
file3.log
file4.log
dir2/
file5.log
In the tree, directories are represented by the entries that end with a forward slash “/” while files have no such forward slash. For example, root, dir1 and dir2 are directories and file1.log, file2.log, file3.log, file4.log and file5.log are files. Each directory is followed by an indented list of resources (i.e., files or directories) directly contained by that directory. For example, the root directory “root” directly contains directories “dir1” and “dir2”. The directory “dir1” directly contains files “file1.log”, “file2.log”, “file3.log” and “file4.log”. The directory “dir2” directly contains file “file5.log”.
Each file and directory represents a “node” in the hierarchical directory tree structure. With the exception of the root directory “root”, each node has a “parent” node in which the node is directly contained. For example, the parent node of “dir1” and “dir2” is “root”; the parent node of “file1.log”, “file2.log”, “file3.log” and “file4.log” is “dir1”; and the parent node of “file5.log” is “dir2”. Each directory node may also directly contain “child” nodes. For example, the child nodes of “root” are “dir1” and “dir2”; the child nodes of “dir1” are “file1.log”, “file2.log”, “file3.log” and “file4.log”; and the child node of “dir2” is “file5.log”.
Each file has an “ancestral line” proceeding from right to left through the progenitors of the file starting at the file and terminating at the root directory. For example, the ancestral line of “file1.log” proceeds from “file1.log” through “dir1” and to “root”. The ancestral lines of “file2.log”, file3.log” and “file4.log” also proceed from the respective file though “dir1” and to “root”. The ancestral line of “file5.log” proceeds from “file5.log” through “dir2” and to “root”. This proceeding from child to parent through the ancestral line will be referred to as proceeding “up” the ancestral line.
A typical file system might represent a file with its ancestral line. For example, in a file system that uses backslashes, “file5.log” might be represented as “root\dir2\file5.log”.
Conventional hierarchical directory tree structures may also store property information (sometimes termed “metadata”) that describes the nodes in the tree. For files, this property information might include the content type, title, subject, author, creation date, last edited date and so forth. For directories, this property information might include the content type to be inherited by descendent files, the title, the creation date, the available free space size and so forth.
In the following discussion, the focus will be on a property called a file extension/content type mapping (sometimes termed “MIMEMAP”) in which certain file extensions are mapped to certain content types. For example, “mimemap ‘.log; text/plain’” is a mapping property that would indicate that, for the corresponding node, files that have the “.log” extension are in plain text format.
For example, the following tree illustrates a conventional hierarchical directory tree structure similar to the above-described tree, but which includes the file extension/content type map “mimemap: ‘.log; text/plain’” for the root directory “root/”.
/root/ | mimemap:“.log;text/plain”
dir1/
file1.log
file2.log
file3.log
file4.log
dir2/
file5.log
Sometimes a hierarchical directory tree structure follows “first one wins” inheritance semantics in which property information for a certain directory applies by inheritance to all descendent files and directories contained within the parent directory. However, following “first one wins” inheritance semantics, the inherited property value can be overwritten for any of the descendent files or directories. In “first one wins” inheritance semantics, if the property value for a file property is found at the file itself, then that is the property value that applies to the file. If the property value for a file property is not found at the file itself, then one examines the ancestral line of the file to determine the first node that has a property value for the corresponding property proceeding up the ancestral line. The file inherits that first property value found. If there is no property value for the corresponding property at the file or in the ancestral line, then a derived property value is applied to the file from a “global” location which may be in another branch of the inheritance tree or may be completely outside of the inheritance tree.
In the example tree immediately above, assume that “first one wins” inheritance semantics are followed. This would means that the mapping of file extensions “.log” to the plain text format content type in the root directory “root” would apply to all of the descendent files and directories of the root directory. Since none of the descendent files and directories has a mapping property that expresses overwrites the mapping in the root directory, the file extension/content type mapping applies to all of the descendent files and directories within the directory “root”. Since all of the files contain the “.log” extension, all of the files “file1.log”, “file2.log”, “file3.log”, “file4.log” and “file5.log” are considered plain text files since they inherit the mapping under the “first one wins” inheritance semantics.
Now suppose that the tree is to be updated. Specifically, a new plain text file called “file6.log” is to be written into “dir1” of the tree. Conventional methods would write the file extension/content type mapping directly at the new file “file6.log” as follows.
/root/ | mimemap:“.log;text/plain”
dir1/
file1.log
file2.log
file3.log
file4.log
file6.log | mimemap:“.log;text/plain”
dir2/
file5.log
Suppose that now a HyperText Markup Language (HTML) text file called “file7.log” is written into “dir1” of the tree. Conventional methods would write the file extension/content type mapping for that specific file directly at the file as follows.
/root/ | mimemap:“.log;text/plain”
dir1/
file1.log
file2.log
file3.log
file4.log
file6.log | mimemap:“.log;text/plain”
file7.log | mimemap:“.log;text/html”
dir2/
file5.log
Note that for every new file written into the tree, the conventional method of updating the tree has written a corresponding file extension/content type mapping property for the file. In trees in which numerous new files are written into the tree, the number of file/extension mapping properties for the tree can become enormous consuming massive quantities of memory space.
Therefore, what is desired are methods and system for updating a hierarchical directory tree structure that follows inheritance semantics while minimizing memory usage.
SUMMARY OF THE INVENTION
Methods and systems are described for minimizing increases in memory usage when updating an inheritance tree. An inheritance tree is a parent-child hierarchical directory tree structure that contains files and directory and that also contains property information for some of the files and directories in the tree. In the inheritance tree, property information for a parent directory is inherited by its descendent files and directories. The exception is that the inherited property information is not inherited by a descendent file or directory (or by the descendent's descendents) that has property informatio

Affiliated with

Also associated with

Rating

Methods and systems for updating an inheritance tree with... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Methods and systems for updating an inheritance tree with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and systems for updating an inheritance tree with... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3010841