Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-05-28
2001-07-03
Homere, Jean R. (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C711S136000, C711S160000, C711S209000
Reexamination Certificate
active
06256644
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a system for controlling the storing of data in a storage of an electronic computer system, and more particularly to a data storing control system in which data are stored and read in by a program.
In a system for storing files blocks and databases in a storage for example in a nonvolatile storage such as a magnetic disk, each of the files blocks and the databases is composed as a set of records, and the record is composed as a set of data items. The program requires inputs and outputs in units of record. Input and output processes between the magnetic disk and a main memory device are performed in units of page or block (hereinafter called page) as a set of records.
FIG. 19
shows a conventional network database (NDBA). The database is composed as a set of a record A
1
, record A
2
, record B
1
, record B
2
, and record C
1
. The record A
1
is a set of data items of A
11
, A
12
, A
13
and A
14
, the record B
1
is a set of data items of B
11
, B
12
, B
13
and B
14
, and record C
1
is a set of data items of C
11
, C
12
, C
13
and C
14
. Each of the records A
1
, B
1
and C
1
is an owner record of indexed sequential organization. Each of the records A
2
and B
2
is designated as a via set of each of the records A
1
and B
1
. Therefore, the records A
1
, A
2
, B
1
, B
2
and C
1
are stored in a storage area
21
b
of the magnetic disk of the
FIG. 20
in the arrangement shown in the figure. The program requests input and output in units of record (A
1
, A
2
, B
1
, B
2
, C
1
). However, between the storage area
21
b
and the main memory device, the input and output are carried out in units of page (page 1, page 2, page 3).
In order that the program obtains a desired record in a file or database, it is necessary to decide a head address information of the record wherein the record is stored. It is necessary that the program can exactly read all records even if the number of records changes. Therefore, the storing position of the record is decided by using a positioning logic which is commonly applied to respective records in files or databases. For example, in a sequential organization file, such a positioning logic that a leading position of a record is decided by an address which is obtained by adding the length of the last record to the leading address of the last record.
As another positioning logic, there is provided a logic for a direct organization. The logic is composed in such that a desired record is stored in a page which is decided by hashing a key information for identifying the desired record. In the case that a plurality of records are stored in a page decided by the hashing, the records are detected by using the key information so as to identify the desired record. The key information for deciding a desired record from a plurality of records stored in the same page which is decided by the positioning logic is hereinafter called record identifying information.
In the case that a program uses a data item in a record, the record is read in a predetermined position of a main memory, such as an input buffer or a user working area. The record has a fixed structure in which respective data items are arranged in a predetermined order based on a physical continuity, and the relative address from the head of the record is decided for the data item. Therefore, the head position of the data item is decided by using the relative address from the head of the read in record.
Meanwhile, in the electronic computer system, the shortening of the access time to data stored in an above described storage causes the process time to shorten. The fact that the process time is shortened has important value for the industry in aspects such as the improvement of process efficiency, improvement of productivity, and others.
A first example of a conventional method for shortening the access time will be described hereinafter. Assuming that data necessary for a program are records A
1
, B
1
and C
1
at the database (NDBA) having a structure shown in
FIG. 19
, and that the database (NDBA) has a storing structure of
FIG. 20
, it is necessary to read three pages of “page
1
”, “page
2
” and “page
3
” in storage area
21
b.
On the assumption that, as shown in
FIG. 21
, there are two storage areas
21
b
and
21
c
, and the records A
1
and B
1
are stored in the page
1
of the storage area
21
b
, and the record C
1
is stored in the page
2
of the storage area
21
b
, and that the remaining records are stored in a storage area
21
c
, and that the page storing a desired record is already read and stored in the main memory, it is not necessary to read again, the page from the storage area. (This operation is, for example, described in the Japanese Patent Application Publication
7-89334
). Therefore, two pages of page
1
and page
2
are read from the storage area
21
b
. As a result, the average access time for the records A
1
, B
1
and C
1
is shortened to {fraction (2/3+L )}.
There is a case that, in the database NDBA of
FIG. 19
, a program requires three data comprising A
11
in the record A
1
, B
11
in the record B
1
and C
11
in the record C
1
. In the case that the database NDBA has the storing structure of
FIG. 20
, it is necessary to input three pages comprising the page
1
including the data item A
11
, page
2
including data item B
11
and page
3
including data item C
11
. If there are two storage areas
21
b
and
21
c
as shown in
FIG. 22
, and data items A
11
, B
11
and C
11
are stored in the page
1
of the storage area
21
b
, remaining data items are stored in the storage area
21
c
, the average access time for the data items A
11
, B
11
and C
11
is to read only page
1
of the storage area
21
b
, thereby being shortened to {fraction (1/3+L )}.
The effect on the shortening of the average access time dependent on the adjacent location of records or data items is hereinafter called adjacent location effect. The combination of the records A
1
and B
1
has a higher adjacent location effect than the combination of records A
1
and A
2
. The combination of data items A
11
and B
11
has a higher adjacent location effect than the combination of data items B
11
and B
12
. The aggregating of data of high adjacent location effect is hereinafter called adjacent concentration. As an example of the using the adjacent concentration in the record units, there is the via set specification for a member record of the network database. It is possible to obtain the adjacent concentration effect by specification to a database schema. There is no technique capable of adjacently aggregating data in the units of data item.
As a second method of shortening the access time, the disk cache is used. This method, in the case of using a record on a magnetic disk, is to locate a copy of a page including the record on the disk cache which is an upper storage hierarchy. After the location, the record can be used at the speed of the access time of the disk cache.
A third method for shortening the access time is to move a file or database to a memory of a faster storage hierarchy when the file or database is used in units of the file or database. For example, when a file which is ordinarily located on the magnetic disk is used, the file is moved to an electronic disk. Japanese Patent Laid Open 6-44108 discloses an example of the third method.
Above described second and third access time shortening methods use the storage hierarchy. In the use of the storage hierarchy, the access time can be shortened by locating data having a high probability of use on a higher storage hierarchy. Since the memory capacity decreases as the storage hierarchy becomes higher, it is important to locate the data on the storage hierarchy in accordance with the probability of use of the data for the shortening of the access time.
It is possible to grasp the adjacent location effect in units of the records or data items and the probability of use, by analyzing the internal structure of the program used for the data or by statistically analyzing
Dennison, Scheiner Schultz & Wakeman
Homere Jean R.
LandOfFree
Control system for storing data in accordance 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 Control system for storing data in accordance with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Control system for storing data in accordance with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2533895