Back to Search
Start Over
Algorithms for Sorting and Sort-Based Database Operations Using a Special-Function Unit
- Source :
- The Kluwer International Series in Engineering and Computer Science ISBN: 9781461289487, IWDM
- Publication Year :
- 1988
- Publisher :
- Springer US, 1988.
-
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.
Details
- ISBN :
- 978-1-4612-8948-7
- ISBNs :
- 9781461289487
- Database :
- OpenAIRE
- Journal :
- The Kluwer International Series in Engineering and Computer Science ISBN: 9781461289487, IWDM
- Accession number :
- edsair.doi...........c9981fe518e244e6cab9dd03aa7af7f6