Research And Implementation Of Reverse Skyline Query Processing Algorithms Over Joins

Information is stored in the database in the form of data. As the amount of information is enormous, the relevant data mostly built in several data tables. As a result, data query processing over two data tables becomes very common and popular in the data applications, and it is inevitable to involve the joins between two tables. However, the existing reverse query algorithms mostly deal with just one table, and the method of merging two tables into one then getting the reverse skyline is inefficient. For the reason that only a spot of join results will be the final results, a plenty of join operations are unwanted. In this thesis, the issue is studied, and reverse skyline query over joins is analysed in detail. Two Pruning strategies is proposed to reduce the amount of data to be accessed, and the number of joins and comparisons is reduced consequently. The algorithms designed in this thesis divide the query into each data table and process the query separately, instead of getting reverse skyline after joins. This can perfectly reduce the number of joins between tuples, and efficiently improve the performance of query processing. The contributions are summarized as follows:1.To deal with reverse skyline query processing over joins, efficient solutions are proposed. Each data table is indexed by grids. According to that, two early termination conditions are proposed to reduce the amount of data which need to be accessed and they can terminate the access to the whole data table early. Relevant definitions, properties and theorems are given and proved to be correct in this thesis. Based on that, basic reverse skyline query over joins (BRSJ) algorithm can be gotten.2. Make an improvement to BRSJ Algorithm to propose progressive reverse skyline query over joins (PRSJ) algorithm. Comparing to BRSJ, PRSJ process semi-dominance test before joins to judge which ones cannot be the results after joins, so the final reverse skyline result can be gotten only with the necessary joins. In this way, the number of joins can be reduced further.3. The two early termination conditions are proved to have high efficiency with experiments, they can reduce the data need to be accessed for each data table efficiently. Experiments also compare the two algorithms with each other. These two algorithms both have high performance, and PRSJ is better than BRSJ in processing time. Both two make a significant improvement to the performance of reverse skyline query processing over joins.