Sorting multiple-typed data

Details Sorting multiple-typed data Sorting multiple-typed data

2001-01-11

2004-05-18

Kindred, Alford (Department: 2172)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

06738769

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to sorting systems and methods, and more particularly to multiple data type sorting systems.
2. Description of Related Art
To enable a user to efficiently view of a group of records, the user may request that the records be ordered or sorted based on one or more fields in each record. In a record the fields to be sorted may be different data types. For example, an employee database is shown in FIG.
1
. The database includes a plurality of records where each record has six fields: name, date of birth, department number, annual salary, and sex (male/female). In this database each field is stored as a different data type. In particular, the name field is stored as a string data type, the date-of-birth field is a stored as a date data type, the department-number field is stored as an integer data type, the annual-salary field is stored as a double integer, and the sex field is stored as a Boolean data type.
In an object-oriented language, the data would be represented as instances of different classes; for example, in Java, the classes would be respectively, String, Date, Integer, BigDecimal, and Boolean. Even though all the data may be displayed as strings with readable characters, the data cannot be correctly ordered according to the numeric values of these characters. Otherwise, January would appear after February, and 2 would appear after 11. Therefore, data in a database or user-interface table is typically stored and sorted in appropriate data types instead of exclusively in the strings that represent their values to the user.
When a user requests the records of the employee database to be sorted, a sorting system invokes an algorithm to sort the records based on the selected fields . The sorting systems commonly invoke a different algorithm for each field data type to be sorted due to their different storage representations and sorting characteristics. Accordingly, when a user requests a group of records to be sorted based on fields of different data types, the sorting system may invoke different sorting algorithms to complete the ordering or sorting of the records. Depending on the number of records or fields, this technique can be processor intensive.
SUMMARY OF THE INVENTION
The present invention provides an efficient sorting system and method for sorting a plurality of records containing multiple-typed fields arranged in a plurality of columns. The records can be sorted based on the values in a selected subset of columns. The system generates a collation key for each field of the columns to be considered for sorting the records. Then the system sorts or orders the records based on the collation keys. The multiple columns may include at least two different data types. Further the collation keys generated by the system for the columns ideally have the same data type, such as an array of bytes. Then the system may use a common sorting algorithm to sort the records because the collation keys have the same data type.
The present invention may also sort records based on multiple fields by converting each of the multiple fields of the records to common data type fields. Then the invention orders the records based on the common data type fields. The multiple fields may include at least two different data types. Then the system may use a common sorting algorithm to sort the records because the common data type fields have the same data type. Further, the common data type fields are ideally arrays of bytes.


REFERENCES:
patent: 5274805 (1993-12-01), Ferguson et al.
patent: 5287494 (1994-02-01), Garcia et al.
patent: 5355478 (1994-10-01), Brady et al.
patent: 5414842 (1995-05-01), Archer et al.
patent: 5680607 (1997-10-01), Brueckheimer
patent: 5765167 (1998-06-01), Kiuchi et al.
patent: 5799309 (1998-08-01), Srinivasan
patent: 5924091 (1999-07-01), Burkhard
patent: 0111689 (1984-06-01), None
Jun Hyun Park et al., Storing and searching of keys and separators in B+-tree, Journal of KISS, Dec. 1997, 568-580, vol. 3, No. 6, Korea Inf. Sci. Soc., South Koera.
Jon L. Bentley et al., Fast Algorithms for Sorting and Searching Strings, Proceedings of the Eight Annual ACM-SIAM Symposium on Discrete Algorithms, 1997, 360-369, ACM, USA.
Arne Andersson, Faster deterministic sorting and searching in linear space, Proceedings 37thAnnual Symposium Foundations of Computer Science, 1996, 135-141, IEEE Comput. Soc. Process, Los Alamitos, CA, USA.
Arne Andersson, Sorting and Searching Revisited, Algorithm Theory—SWAT '96. 5thScandinavian Workshop on Alogorithm Theory. Proceedings, 1996, 185-197, Dept. of Comput. Sci., Berlin, Germany.
Gennady Antoshenkov, Order Preserving String Compression, Proceedings of the Twelfth International Conference on Data Engineering, 1996, 655-663, IEEE Comput. Soc. Press, USA.
D.R. Hicks, Compressing Sort Keys While Maintaining Sort Sequence, IBM Technical Disclosure Bulletin, Jun. 1983, 388-391, vol. 26, No. 1, IBM, USA.
Allen P. Croft, DECO, Program, Jul. 1982, 158-170, vol. 16, No. 3, Unilever Computer Services, London, UK.

Affiliated with

Also associated with

Rating

Sorting multiple-typed data does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Sorting multiple-typed data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sorting multiple-typed data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3267171