Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-03-24
2004-01-27
Rones, Charles (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C709S217000, C717S152000, C717S162000, C713S185000
Reexamination Certificate
active
06684226
ABSTRACT:
The present invention relates to the generation and alteration of a database and in particular to a database where different versions of the data therein should be accessible.
A number of computer/data storage theories and practises exist—one of which is the so-called shadow paging principle which is designed to especially take into account problems often encountered when a number of alterations are desired performed on e.g. a database—alterations which may be interconnected. If this operation fails in the process of altering the data, it may not be possible to actually regenerate the former data in order to attempt the alteration again. Thus, the database is in an unknown and thus undesired state.
Shadow paging solves this problem by not overwriting or deleting data but simply firstly copying and then altering all parts thereof which are required altered as a consequence of the desired alterations of the data. These new parts are stored separately from the former data. The actual data of the shadow paging principle are stored as a number of individually addressable data blocks and a tree structure having at the lowest level nodes—normally termed the leaves of the tree—pointing to these data blocks is generated. Altering a data block will require the copying thereof and performing the alteration on the copy. The address of this new data block is entered into a copy of the tree node pointing to the new data block. This new tree node is also stored at a new address and any node pointing to the former node will also be copied, altered—etc. This process is applied recursively until the root node of the tree has been processed.
This will provide a new set of data blocks of which some are new and some are not amended and thus old—and some old data blocks, which will not be relevant when the commit operation has been successfully completed. Also, a new tree structure is provided part of which is old and part of which is new. Each of these tree structures have a node—and these nodes are different.
The actual commit operation will finally be performed by having an overall pointer to the actual tree structure—and thereby to the actual data structure—point from the old root to the new root. The advantage of this function is that the commit operation is indivisible and is performed in a single operation. This operation can hardly be stopped in the process—whereby the fact that the overall pointer points to the new root will, as a fact, mean that the operation has been completed successfully. If this is not the case, the old root will still be actual—as will the old tree structure and the old data—whereby no alterations have been performed on the data.
This principle however has the disadvantage that upon a commit operation the old data will no longer be available. Thus, it will not be possible to actually retrieve an older version of the data.
The present invention relates to a solution to that problem.
In a first aspect, the invention relates to a method for storing information stored in one or more files on a permanent storage medium, the method comprising:
storing data transaction-wise according to the shadow paging principle,
but retaining, in a commit operation, the previous data and their physical storage on the storage medium together with a separate storage on the storage medium representing new data as changes to the previous data,
the previous data and the changes together constituting, upon commit, a new version of the data,
both the previous and the new versions of the data being separately accessible.
In the present context, “transaction-wise” will mean that a transaction is performed wherein all desired alterations to the data or database are assembled and performed in a single operation. This transaction is completed with the commit operation where e.g. the operator “commits” himself to the desired changes where after these are performed on the data.
Upon the commit operation, a new version of the data is generated and stored separately from the older data in a manner so that both the new and old version of the data are separately accessible.
In the standard shadow paging principle, the old data are not accessible upon a successful commit operation.
According to the invention, the old version of the data is separately accessible.
Preferably the data of a file is stored as a number of data blocks and wherein a change of the contents of the file, the previous data, results in a change of the contents of one or more of the data blocks.
Also, preferably, a single commit operation causes all changes, required by the transaction, to be applied to all of the one or more files.
During operation of a program accessing the database, it may be desired that at least a number of previous versions representing the maximum simultaneously outstanding transactions plus two are retained.
By a shadow paging principle it is normally meant that the data are stored as a number of individually addressable data blocks (normally the smallest individually addressable unit in the storage medium), addresses representing the physical storage of the individual data blocks being stored in a tree structure of one or more first data elements, and comprising:
a) identifying data blocks to be modified,
b) copying the identified data blocks,
c) performing the modification(s) on the copied data blocks,
d) storing the modified data blocks at addresses not coinciding with any of the addressable data blocks or any of the first data elements,
e) for each identified data block, identifying one or more of the first data elements of the tree structure from a root of the tree structure to the data block,
f) copying each identified first data element at an address not coinciding with any of the addressable data blocks or any of the first data elements,
g) replacing, in each copied first data element, the address of the identified data block or first data element with the address of the corresponding modified data block or first data element, and
h) providing a new root of the modified tree structure and having the new root represent the modified first data element corresponding to the first data element represented by the root of the tree structure.
If a first data element represents addresses of more than one data block having been altered by the procedure, preferably this first data element is only copied, altered and stored once.
A tree structure of the present type comprises a number of nodes (one of which is a root) each having at least two pointers pointing toward leaves or other nodes. Which pointer to choose will be determinable by the property of the desired leaf.
Normally, as mentioned, the commit operation comprises only step h) in shadow paging.
One of the advantages of the shadow paging principle may be seen from the depth of a tree describing a file is determined by the maximum size of the file, and the block size of the underlying physical storage media. The maximum depth of a tree can be expressed as
tmd=
(log 2(maxFileSize)−log 2(blockSize))/(log 2(blockSize/pointerSize)
If we assume a maxFileSize as 2**32 a block size of 512 and a pointerSize of 4 the maximum depth of a tree is less than or equal to 4. Thus, a memory of 4 GBytes may be described by a tree of depth 4 which means that the tree structure itself uses only {fraction (1/128)}′th of the space of the memory.
In order not to store an altered data block or first data element at an address representing an existing data block or first data element, it is desired to maintain an updated knowledge of free addresses or free space on the storage medium. One manner of obtaining that knowledge is one where:
i) prior to step d), information is provided relating to the free addresses of the data storage medium which are not occupied by the data blocks and the first data elements,
j) step d) comprises storing the modified data blocks at free addresses and removing the addresses from the free addresses,
k) step f) comprises storing the modified first data elements at free addresses and removing the addresses from the free addresses.
One
Birch & Stewart Kolasch & Birch, LLP
Frontline Software ApS
Pardo Thuy
Rones Charles
LandOfFree
Method for storing data in one or more files so that both... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for storing data in one or more files so that both..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for storing data in one or more files so that both... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3231810