Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1997-09-17
2001-04-10
Hong, Stephen S. (Department: 2176)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C717S152000
Reexamination Certificate
active
06216140
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to managing hierarchically organized information, and more particularly to an improved method for the efficient sharing and copying of hierarchically organized information.
BACKGROUND OF THE INVENTION
In the development of software, a single hierarchy composed of both files and directories is commonly developed to serve multiple distinct purposes or applications that often stem from a common baseline of code. Each of the distinct applications that use the hierarchy may require changes or modifications be made to some portion of the files or directories of the hierarchy and the required changes may be expected to vary from one application to the next.
It is of course desirable that changes made to the hierarchy of files and directories for a given application be kept distinct from the original hierarchy as well as from changes that may be made for other applications. Copying the hierarchy of files and directories for each application in order to keep track of any changes made for that application, however, may entail the duplication of thousands, perhaps millions, of files and directories. In a system employing a large number of applications (or releases) or employing a hierarchy having a large number of files and directories, such duplication is wasteful of storage space because each copy of the hierarchy that is changed must be stored. Additionally, the system will incur a time penalty in proportion to the number of times the hierarchy of files must be copied in order to accommodate changes required by various applications that share the hierarchy.
Several prior art approaches have been developed in an attempt to reduce the storage space and the time required for copies required of a system that utilizes a hierarchy of files and directories developed for multiple and distinct applications. A first approach has been to make an exact duplication of the data of the entire hierarchy each time a modification by any application is indicated. This approach results in the use of a large storage space and a large instantiation time during which the user of the system waits for the duplication of the hierarchy to be completed.
A second approach has been to maintain revision information concerning every modification made to every file or directory of the hierarchy. Each file and directory has its own revision history and a particular revision of the revision history of a file or directory is selected for an application according to criteria appropriate to that application. When an application requires new or additional changes be made to the hierarchy, a selected version of the hierarchy is accordingly modified to create a new revision of the file or directory that then becomes part of the revision history of the file or directory. This approach offers the advantage of making a particular revision only once that can thereafter by used by any application having need of that revision by simply selecting the correct revision. Whenever a new application or version is created, it is necessary to record the baseline from where it starts in each file or directory. The time associated with initializing a new application or version is significant, then, because the starting point from which it began must be marked resulting in quite a large overhead burden. Consequently, the user of the system encounters significant instantiation time or delay at copy time that is only exacerbated by a large hierarchy of files and directories.
A third prior art approach has been to perform a linear copy-on-write operation only when a file or directory of the hierarchy is to be modified. This approach is commonly used in the kernels of operating systems to share large arrays of memory that are expected to remain unchanged by multiple processes or applications of the system. The control structures required to manage the data of the arrays of memory are not shared and thus must be duplicated for each process, thereby increasing the instantiation time apparent to the user of a system that uses the linear copy-on-write approach. This approach is nonetheless suitable in instances in which the amount of control information of a control structure is very small compared to the amount of data being managed. A reference counter integer for each page of memory of the memory array, for instance, is an illustration of a control structure being very small in comparison to a large amount of data to be managed.
The linear copy-on-write approach of the prior art sacrifices effectiveness for a large hierarchy having a great number of files and directories. The large number of copies expected to be made of a large hierarchy used by multiple, distinct applications would eventually require that the control structures themselves be shared between applications in order to render efficient copy instantiation time. At the present time, control structures are not shared and thus the linear-copy-on-write approach does not offer an efficient instantiation time if used in a system having a hierarchy with a great number of files and directories.
In light of the above discussion, it is clear that there exists in the art an unmet need to be able to efficiently copy and share large amounts of hierarchically organized information.
In addition to the need for efficient copying and sharing of large amounts of hierarchically organized information, there is the need to be able to efficiently compare virtually copied, hierarchically organized information. One obvious way to perform such a comparison is to compare each and every file or directory item of the hierarchies being compared. A problem with this approach is because sub-hierarchies that may be equivalent between the compared hierarchies is not recognized, much duplicate work is performed in comparing items between the hierarchies that are in fact the same. A further difficulty with a simplistic compare operation is that only information concerning the differences between items of the hierarchies, and not the direction or source of the differences, may be obtained. There is no change history available to distinguish between a create in a first hierarchy and a delete in a second hierarchy, for instance. It would likewise not be possible to determine in which hierarchy of the two or more hierarchies being compared a rename of an item occurred.
There is thus an unmet need in the art to be able to perform an efficient compare operation between two or more hierarchies of files and directories to be compared. There is further an unmet need in the art to not only be able to perform such an efficient compare operation but to also be able to ascertain the source of any differences between the hierarchies.
Yet another aspect of software development is that it is often desirable to develop a new feature independently of other features for a period of time and then to merge the new feature with other features of the software should the change prove worth keeping. In a large hierarchy of files and directories, the number of differences and hence merges that are associated with such improvements may become quite large and thus the task of merging differences is tedious and prone to human error. It is characteristic of even a large hierarchy, however, that most merges have predictable defaults.
While merging is a common task performed in regard to software, the extent of a merge typically only includes merging the content of files that have divergent changes. Attributes of a file are not merged and no systematic method for handling the copying of changes from one logical branch of a program to another is provided. Attributes of a hierarchy item may include the content of the item, the name of the item, the parent directory of the item, the mode of the item, the type of input/output associated with an item, the keyword expansion type for the item, a user-designed attribute string of the item, the state of create or delete for the item, and whether the item is a file or directory. Additionally, merges typically occur one item at a time, thereby being an e
Bashore William L.
Hewlett--Packard Company
Hong Stephen S.
LandOfFree
Methodology for the efficient management of hierarchically... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methodology for the efficient management of hierarchically..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methodology for the efficient management of hierarchically... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2530879