Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-07-13
2001-01-09
Amsbury, Wayne (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06173278
ABSTRACT:
FIELD OF THE INVENTION
My present invention relates to a method of and to an algorithm for effectively and optimally utilizing an index of a relational data base table and, more particularly, deriving information from a table by accessing locations therein in an improved manner. The invention also relates to a special-purpose computer programmed to carry out the method and in accordance with the algorithm.
BACKGROUND OF THE INVENTION
In relational data bases, it is a common practice to provide an index of a relational data base table in which the index is structured in levels and wherein each row of the table is identified by a respective row identifier (RID). The index can be defined by an ordered list of columns of the table and a concatenation of the list of columns, in a binary number, can serve as a key for the index. The index points to the respective rows of the table by the row identifiers. The index can be used to respond to a query defining a request to access a subset of the rows of the table. Values of some of the columns can be restricted, depending upon the query, to certain ranges and each of the ranges can consist of an ordered list of subranges which have upper and lower bounds.
Such indexes are used in many file systems and data base management systems in order to expedite access to the data contained therein.
Having indexes involves a trade-off, on the one hand, between the effort, disk space and time invested in the maintenance of indexes during update operations and, on the other hand, the effort and time spared when these indexes facilitate in finding relevant data and ignoring irrelevant data.
OBJECTS OF THE INVENTION
It is the principal object of the present invention to provide an improved method for more effectively using existing indexes and which will increase the contribution of the index to the time-sparing accessing of data while reducing the need for additional indexes where increased accessibility to data is desired.
Another object of the invention is to provide a method of utilizing an index of a relational data base which includes an improved method of calculating I/O operations performed.
Yet another object of the invention is to provide a method of utilizing indexes which involves improved selection of the index used.
It is also an object of the invention to provide a special purpose computer programmed to carry out the improved method.
SUMMARY OF THE INVENTION
These objects and others which will become apparent hereinafter are achieved with a method of utilizing such an index in which for as long as all relevant ranges of the key have not been exhausted and without relying upon an implicit or explicit definition of ranges of the key, finding a beginning of a next range, and extracting respective row identifiers from successive entries of the index where the key belongs to the next range until the next range is exhausted.
According to the invention the requested rows of the table are accessed by the steps of:
(a) defining a highest level as a highest relative sequence number in a definition of the index of a column for which the index is to be used and defining oldkey to be a last key created for direct access of the index;
(b) defining a procedure Generate_key as a function of a value parameter and of a level of operation by the steps of:
(b1) in oldkey, replacing a value of the column that appears in the definition of the index in a position designated by the level of operation, by the value parameter, and
(b2) in oldkey, replacing the value of all columns appearing in the list defining the index in positions that are greater than the level of operation, by lowest values allowed by their respective ranges;
(c) defining a procedure Generate_next_key as a function of the operation level passed as a parameter by the steps of:
(c1) setting X to be one more than the binary value of the column appearing in the position designated by the operation level in the ordered list of columns;
(c2) if the X is in the range corresponding to the column, returning the result of the activation of Generate_key with X and the operation level as parameters to a caller or requester,
(c3) otherwise, if there are any more subranges in the range, setting X to be a beginning of the next subrange of the range and returning the result of Generate_key with X and the operation level as parameters,
(c4) otherwise, if the activation level is a lowest level returning to the caller and signaling an end of the index,
(c5) otherwise, returning the result of the activation of Generate_next_key with the activation level minus 1 as a parameter,
(d) defining a procedure Next_entry as a function of the level in which it is expected to operate, by the steps of:
(d1) if the end of the index has been reached, returning this information to the caller; otherwise until the end of the index is reached or until any subsequent step returns to the caller, repeating the following steps:
(d11) if the level is the highest level, getting the next physical index entry, otherwise carry out Generate_next_key with the level as a parameter in order to generate an access key for direct access of the index and then getting the first index entry with a key greater than or equal to the access key,
(d12) checking the key of the index entry just accessed and, if the values of all the columns composing it are in their respective ranges, returning the index entry rust accessed,
(d13) otherwise defining a level L to be the lowest level for which the value of the index column disagrees with the range for that column,
(d14) if L is not equal to the highest level, activate Next_entry recursively with L as a parameter and return the result; otherwise set K to be the result of the activation of the function Generate_next_key with L as a parameter and access to the first physical index entry with a key that is greater than or equal to K;
(e) until the end of the index is reached, repeatedly using the procedure Next_entry in order to focus on the next relevant index entry; and
(f) obtaining the (RIDS) of the relevant rows from the relevant index entries.
The method of the invention is capable of using index prefixes even in cases where some of the columns constituting the prefix have not been referred to by the query. This is accomplished by artificially defining ranges for columns in the column list for which no range can be inferred from the request, as ranges starting with a lowest possible value of the column and ending with a highest possible value.
The methods of the invention as described above can be embedded in a system which also can calculate an estimated number of input/output I/O operations. That system can calculate the I/O operations by the steps of:
(I) defining DB to be a number of blocks in the table,
(II) defining DC to be a number of rows in the table,
(III) defining K to be a blocking factor of the table (K=DC/DB),
(IV) defining M to be a number of RIDs collected and sorted before the data records are accessed,
(V) defining Ci to be the cardinality of index column i,
(VI) defining Pi to be the selectivity of index column i,
(VII) defining R(i) to be the number of ranges for index column i,
(VIII) defining IL as the level of the least significant index column for which a nontrivial range is used,
(IX) defining DEPTH as the total number of levels in the index,
(X) defining Ik as the number of index blocks in index_level k,
(XI) defining IB as the number of blocks in the lowest index_level,
(XII) defining
EF
(
m
,
k
,
n
)
≡
1
-
Γ
(
n
-
k
+
1
)
×
Γ
(
n
-
m
+
1
)
Γ
(
n
+
1
)
×
Γ
(
n
-
k
-
m
+
1
)
,
(XIII) defining the recursive function CARD as:
m
1
)CARD(0)≡1,
m2
)
CARD
(
i
)
≡
CARD
(
i
-
1
)
×
Ci
×
EF
(
D
C
CARD
(
i
-
1
)
,
D
C
Ci
,
D
C
)
,
(XIV) defining the recursive function PROD as:
n
1
)PROD(0)≡1,
n2
)
PROD
(
i
)
≡
PROD
(
i
-
1
)
×
Ci
×
Pi
×
Amsbury Wayne
Dubno Herbert
Le Uyen
Newframe Corporation Otd.
LandOfFree
Method of and special purpose computer for utilizing an... 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 of and special purpose computer for utilizing an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of and special purpose computer for utilizing an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2557191