TOP-K AND SKYLINE QUERY PROCESSING OVER RELATIONAL DATABASE
Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Top-k and Skyline queries are a long study topic in database and information retrieval communities and they are two popular operations for preference retrieval. Top-k query returns a subset of the most relevant answers instead of all answers. Efficient top-k processing retrieves the k objects that have the highest overall score. In this paper, some algorithms that are used as a technique for efficient top-k processing for different scenarios have been represented. A framework based on existing algorithms with considering based cost optimization that works for these scenarios has been presented. This framework will be used when the user can determine the user ranking function. A real life scenario has been applied on this framework step by step.
Skyline query returns a set of points that are not dominated (a record x dominates another record y if x is as good as y in all attributes and strictly better in at least one attribute) by other points in the given datasets. In this paper, some algorithms that are used for evaluating the skyline query have been introduced. One of the problems in the skyline query which is called curse of dimensionality has been presented. A new strategy that based on the skyline existing algorithms, skyline frequency and the binary tree strategy which gives a good solution for this problem has been presented. This new strategy will be used when the user cannot determine the user ranking function. A real life scenario is presented which apply this strategy step by step.
Finally, the advantages of the top-k query have been applied on the skyline query in order to have a quickly and efficient retrieving results.
Place, publisher, year, edition, pages
2012. , 67 p.
Top-k query, Skyline query, Fagin’s algorithm, Threshold Algorithm, No random access algorithm, Minimal Probing algorithm, Block-Nested-Loop algorithm, Nearest Neighbor algorithm, Branch and Bound Skyline Algorithm, Divide and Conquer algorithm
Engineering and Technology
IdentifiersURN: urn:nbn:se:hj:diva-20108OAI: oai:DiVA.org:hj-20108DiVA: diva2:577360