Browse Prior Art Database

Optimum Data Migration and Code Switching Algorithm

IP.com Disclosure Number: IPCOM000078087D
Original Publication Date: 1972-Nov-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 6 page(s) / 42K

Publishing Venue

IBM

Related People

Gorenstein, S: AUTHOR [+2]

Abstract

The algorithm disclosed herein enables the determination as to when data should be migrated among systems in a distributed data base to minimize cost, and when a switch should be made among alternative codes in a data compression system to minimize the quantity of bits which are transmitted.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 24% of the total text.

Page 1 of 6

Optimum Data Migration and Code Switching Algorithm

The algorithm disclosed herein enables the determination as to when data should be migrated among systems in a distributed data base to minimize cost, and when a switch should be made among alternative codes in a data compression system to minimize the quantity of bits which are transmitted.

To understand the purport of the algorithm, there is considered a data base which is distributed among several computing systems A, B, C, D,... . Each record of data is permitted to reside at any one or more of these systems. If the record of data resides in only one system, then, such record is denoted as not being duplicated. Alternatively, if the record resides at more than one of the systems, it is stated that there are duplicate copies of the record. Application programs running on the various systems will make accesses to the various records in this distributed data base. Occasionally, it will be possible for these accesses to be satisfied locally on the system making the access. In other cases, it will be necessary for the accessing system to communicate with some remote system.

In this type of distributed data base, costs may be assigned to each of the required functions. With these costs having been assigned, there would be desired a minimizing of the total expense of operating the distributed data base. Accordingly, there is required an algorithm which can inform as to when data should be migrated between systems, when it should not, when it should be duplicated, and when a duplicate copy should be expunged. Such algorithm is referred to herein as a Data Migration Algorithm.

The optimal data migration algorithm is hypothecated on the premise that there is known ahead of time, the future history of all of the accesses which will be made. It is readily appreciated that the optimal data migration algorithm is not feasible since, in any real situation, the future cannot be precisely foretold. However, the algorithm is useful, because it provides a base against which the performance of any other migration algorithm can be compared. Also, the algorithm can determine when it has sufficient "look-ahead" so that its decision is optimal regardless of future requests.

If there is considered the situation wherein there is assumed a data base distributed between only two systems and wherein no data duplication is required, in such case the optimal data migration algorithm takes on a relatively simple form. There is first discussed hereinbelow this simple form, i.e., the case wherein the data base is distributed between only two systems and no duplication is assumed. A. Data Migration Cost.

There are two systems: A and B. Each record is at system A or at system B, but not at both systems A and B. Each access can have its origin at either system A or system B. If the access originates from the same system at which the record is located, then the access is satisfied locally. In this situation, a co...