An empirical study on SAJQ (Sorting Algorithm for Join Queries)
Most queries that applied on database management systems (DBMS) depend heavily on the performance of the used sorting algorithm. In addition to have an efficient sorting algorithm, as a primary feature, stability of such algorithms is a major feature that is needed in performing DBMS queries. In thi...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2010-06-01
|
| Series: | Egyptian Informatics Journal |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S1110866510000046 |
| _version_ | 1818665947131543552 |
|---|---|
| author | Hassan I. Mathkour |
| author_facet | Hassan I. Mathkour |
| author_sort | Hassan I. Mathkour |
| collection | DOAJ |
| description | Most queries that applied on database management systems (DBMS) depend heavily on the performance of the used sorting algorithm. In addition to have an efficient sorting algorithm, as a primary feature, stability of such algorithms is a major feature that is needed in performing DBMS queries. In this paper, we study a new Sorting Algorithm for Join Queries (SAJQ) that has both advantages of being efficient and stable. The proposed algorithm takes the advantage of using the m-way-merge algorithm in enhancing its time complexity. SAJQ performs the sorting operation in a time complexity of O(nlogm), where n is the length of the input array and m is number of sub-arrays used in sorting. An unsorted input array of length n is arranged into m sorted sub-arrays. The m-way-merge algorithm merges the sorted m sub-arrays into the final output sorted array. The proposed algorithm keeps the stability of the keys intact. An analytical proof has been conducted to prove that, in the worst case, the proposed algorithm has a complexity of O(nlogm). Also, a set of experiments has been performed to investigate the performance of the proposed algorithm. The experimental results have shown that the proposed algorithm outperforms other Stable–Sorting algorithms that are designed for join-based queries. |
| first_indexed | 2024-12-17T05:56:43Z |
| format | Article |
| id | doaj.art-75ec459fbdda417aa2ffe661ba871ec8 |
| institution | Directory Open Access Journal |
| issn | 1110-8665 |
| language | English |
| last_indexed | 2024-12-17T05:56:43Z |
| publishDate | 2010-06-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Egyptian Informatics Journal |
| spelling | doaj.art-75ec459fbdda417aa2ffe661ba871ec82022-12-21T22:01:01ZengElsevierEgyptian Informatics Journal1110-86652010-06-01111192610.1016/j.eij.2010.06.003An empirical study on SAJQ (Sorting Algorithm for Join Queries)Hassan I. MathkourMost queries that applied on database management systems (DBMS) depend heavily on the performance of the used sorting algorithm. In addition to have an efficient sorting algorithm, as a primary feature, stability of such algorithms is a major feature that is needed in performing DBMS queries. In this paper, we study a new Sorting Algorithm for Join Queries (SAJQ) that has both advantages of being efficient and stable. The proposed algorithm takes the advantage of using the m-way-merge algorithm in enhancing its time complexity. SAJQ performs the sorting operation in a time complexity of O(nlogm), where n is the length of the input array and m is number of sub-arrays used in sorting. An unsorted input array of length n is arranged into m sorted sub-arrays. The m-way-merge algorithm merges the sorted m sub-arrays into the final output sorted array. The proposed algorithm keeps the stability of the keys intact. An analytical proof has been conducted to prove that, in the worst case, the proposed algorithm has a complexity of O(nlogm). Also, a set of experiments has been performed to investigate the performance of the proposed algorithm. The experimental results have shown that the proposed algorithm outperforms other Stable–Sorting algorithms that are designed for join-based queries.http://www.sciencedirect.com/science/article/pii/S1110866510000046SortingStable–SortingSort-merge algorithmsAuxiliary storage sortingMergingDatabase queries |
| spellingShingle | Hassan I. Mathkour An empirical study on SAJQ (Sorting Algorithm for Join Queries) Egyptian Informatics Journal Sorting Stable–Sorting Sort-merge algorithms Auxiliary storage sorting Merging Database queries |
| title | An empirical study on SAJQ (Sorting Algorithm for Join Queries) |
| title_full | An empirical study on SAJQ (Sorting Algorithm for Join Queries) |
| title_fullStr | An empirical study on SAJQ (Sorting Algorithm for Join Queries) |
| title_full_unstemmed | An empirical study on SAJQ (Sorting Algorithm for Join Queries) |
| title_short | An empirical study on SAJQ (Sorting Algorithm for Join Queries) |
| title_sort | empirical study on sajq sorting algorithm for join queries |
| topic | Sorting Stable–Sorting Sort-merge algorithms Auxiliary storage sorting Merging Database queries |
| url | http://www.sciencedirect.com/science/article/pii/S1110866510000046 |
| work_keys_str_mv | AT hassanimathkour anempiricalstudyonsajqsortingalgorithmforjoinqueries AT hassanimathkour empiricalstudyonsajqsortingalgorithmforjoinqueries |