Paper Info
Title
Algorithms for Sorting and Sort-Based Database Operations Using a Special-Function Unit
Abstract
This paper presents the design of a Special Function Unit for DataBase operations (SFU-DB), which is used as a backend database machine for performing sort and sort-based database operations. This machine implements a most-significant-digit-first radix sort algorithm by using a special hardware device called Automatic Retrieval Memory (ARM). The ARM performs an efficient content-to-address mapping to sort the data. Without performing any comparisons in the sorting process, the SFU-DB avoids the lower bound constraint on comparison-based sorting algorithms and achieves a complexity of O(n) for both execution time and main memory size. Based on the sorting algorithm, the SFU-DB also performs other primitive database operations such as relational join, elimination of duplicates, set union, set intersection, and set difference with a complexity of O(n). The capacity of the SFU-DB is limited by the size of its main memory rather than by the number of special processing elements as in most sorting machines. Hence, the SFU-DB has a better cost/performance and is more suitable for processing very large databases. Currently, a prototype SFU-DB system is under construction.
Year
DOI
Venue
1987
10.1007/978-1-4613-1679-4_8
IWDM
Keywords
Field
DocType
special functions
Intersection (set theory),Computer for operations with functions,Computer science,Radix sort,sort,Parallel computing,Algorithm,Sorting,Complement (set theory),Database machine,Sorting algorithm,Database
Conference
Citations 
PageRank 
References 
4
0.59
2
Authors
3
Name
Order
Citations
PageRank
Chiang Lee140.59
Stanley Y. W. Su216221403.92
Herman Lam330591.31