IDSA: an efficient algorithm for skyline queries computation on dynamic and incomplete data with changing states
Skyline queries have been widely used as an effective query tool in many contemporary database applications. The main concept of skyline queries relies on retrieving the non-dominated tuples in the database which are known skylines. In most database applications, the contents of the databases are dy...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers
2021
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/97610/1/ABSTRACT.pdf |
| _version_ | 1825937899106861056 |
|---|---|
| author | Gulzar, Yonis Alwan, Ali Amer Ibrahim, Hamidah Turaev, Sherzod Wani, Sharyar Soomo, Arjumand Bano Hamid, Yasir |
| author_facet | Gulzar, Yonis Alwan, Ali Amer Ibrahim, Hamidah Turaev, Sherzod Wani, Sharyar Soomo, Arjumand Bano Hamid, Yasir |
| author_sort | Gulzar, Yonis |
| collection | UPM |
| description | Skyline queries have been widely used as an effective query tool in many contemporary database applications. The main concept of skyline queries relies on retrieving the non-dominated tuples in the database which are known skylines. In most database applications, the contents of the databases are dynamic due to the continuous changes made towards the database. Typically, the changes in the contents of the database occur through data manipulation operations (INSERT and/or UPDATE). Performing these operations on the database results in invalidating the most recent skylines before changes are made on the database. Furthermore, the presence of incomplete data in databases becomes frequent phenomena in recent database applications. Data incompleteness causes several challenges on skyline queries such as losing the transitivity property of the skyline technique and the test dominance process between tuples being cyclic. Reapplying skyline technique on the entire updated incomplete database to determine the new skylines is unwise due to the exhaustive pairwise comparisons. Thus, this paper proposes an approach, named Incomplete Dynamic Skyline Algorithm (IDSA) which attempts to determine the skylines on dynamic and incomplete databases. Two optimization techniques have been incorporated in IDSA, namely: pruning and selecting superior local skylines. The pruning process attempts to exploit the derived skylines before the INSERT/UPDATE operation made on the database to identify the new skylines. Moreover, selecting superior local skylines process assists in further eliminating the remaining non-skylines from further processing. These two optimization techniques lead to a large reduction in the number of domination tests due to avoiding re-computing of skylines over the entire updated database to derive the new skylines. Extensive experiments have been accomplished on both real and synthetic datasets, and the results demonstrate that IDSA outperforms the existing solutions in terms of the number of domination tests and the processing time of the skyline operation. |
| first_indexed | 2024-03-06T11:06:21Z |
| format | Article |
| id | upm.eprints-97610 |
| institution | Universiti Putra Malaysia |
| language | English |
| last_indexed | 2024-03-06T11:06:21Z |
| publishDate | 2021 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | upm.eprints-976102022-07-25T03:56:55Z http://psasir.upm.edu.my/id/eprint/97610/ IDSA: an efficient algorithm for skyline queries computation on dynamic and incomplete data with changing states Gulzar, Yonis Alwan, Ali Amer Ibrahim, Hamidah Turaev, Sherzod Wani, Sharyar Soomo, Arjumand Bano Hamid, Yasir Skyline queries have been widely used as an effective query tool in many contemporary database applications. The main concept of skyline queries relies on retrieving the non-dominated tuples in the database which are known skylines. In most database applications, the contents of the databases are dynamic due to the continuous changes made towards the database. Typically, the changes in the contents of the database occur through data manipulation operations (INSERT and/or UPDATE). Performing these operations on the database results in invalidating the most recent skylines before changes are made on the database. Furthermore, the presence of incomplete data in databases becomes frequent phenomena in recent database applications. Data incompleteness causes several challenges on skyline queries such as losing the transitivity property of the skyline technique and the test dominance process between tuples being cyclic. Reapplying skyline technique on the entire updated incomplete database to determine the new skylines is unwise due to the exhaustive pairwise comparisons. Thus, this paper proposes an approach, named Incomplete Dynamic Skyline Algorithm (IDSA) which attempts to determine the skylines on dynamic and incomplete databases. Two optimization techniques have been incorporated in IDSA, namely: pruning and selecting superior local skylines. The pruning process attempts to exploit the derived skylines before the INSERT/UPDATE operation made on the database to identify the new skylines. Moreover, selecting superior local skylines process assists in further eliminating the remaining non-skylines from further processing. These two optimization techniques lead to a large reduction in the number of domination tests due to avoiding re-computing of skylines over the entire updated database to derive the new skylines. Extensive experiments have been accomplished on both real and synthetic datasets, and the results demonstrate that IDSA outperforms the existing solutions in terms of the number of domination tests and the processing time of the skyline operation. Institute of Electrical and Electronics Engineers 2021 Article PeerReviewed text en http://psasir.upm.edu.my/id/eprint/97610/1/ABSTRACT.pdf Gulzar, Yonis and Alwan, Ali Amer and Ibrahim, Hamidah and Turaev, Sherzod and Wani, Sharyar and Soomo, Arjumand Bano and Hamid, Yasir (2021) IDSA: an efficient algorithm for skyline queries computation on dynamic and incomplete data with changing states. IEEE Access, 9. 57291 - 57310. ISSN 2169-3536 https://ieeexplore.ieee.org/abstract/document/9400828 10.1109/ACCESS.2021.3072775 |
| spellingShingle | Gulzar, Yonis Alwan, Ali Amer Ibrahim, Hamidah Turaev, Sherzod Wani, Sharyar Soomo, Arjumand Bano Hamid, Yasir IDSA: an efficient algorithm for skyline queries computation on dynamic and incomplete data with changing states |
| title | IDSA: an efficient algorithm for skyline queries computation on dynamic and incomplete data with changing states |
| title_full | IDSA: an efficient algorithm for skyline queries computation on dynamic and incomplete data with changing states |
| title_fullStr | IDSA: an efficient algorithm for skyline queries computation on dynamic and incomplete data with changing states |
| title_full_unstemmed | IDSA: an efficient algorithm for skyline queries computation on dynamic and incomplete data with changing states |
| title_short | IDSA: an efficient algorithm for skyline queries computation on dynamic and incomplete data with changing states |
| title_sort | idsa an efficient algorithm for skyline queries computation on dynamic and incomplete data with changing states |
| url | http://psasir.upm.edu.my/id/eprint/97610/1/ABSTRACT.pdf |
| work_keys_str_mv | AT gulzaryonis idsaanefficientalgorithmforskylinequeriescomputationondynamicandincompletedatawithchangingstates AT alwanaliamer idsaanefficientalgorithmforskylinequeriescomputationondynamicandincompletedatawithchangingstates AT ibrahimhamidah idsaanefficientalgorithmforskylinequeriescomputationondynamicandincompletedatawithchangingstates AT turaevsherzod idsaanefficientalgorithmforskylinequeriescomputationondynamicandincompletedatawithchangingstates AT wanisharyar idsaanefficientalgorithmforskylinequeriescomputationondynamicandincompletedatawithchangingstates AT soomoarjumandbano idsaanefficientalgorithmforskylinequeriescomputationondynamicandincompletedatawithchangingstates AT hamidyasir idsaanefficientalgorithmforskylinequeriescomputationondynamicandincompletedatawithchangingstates |