Preference queries processing over imprecise data.

Abstract

With the increasing availability of various data sources, the preference queries are essential to find the relevant results to users. Several preference functions has been introduced in literature including: top-k [1], skylines [2], distributed skyline [3], spatial skyline [4], multi-objective [5], k-dominance [6], k-frequency [7], and ranked skylines [8], k-representative dominance [9], distance-based dominance [10], -skylines [11], top-k dominance [12], and stochastic skyline [13]. With the growing number of applications that generate imprecise data, e.g., sensor readings, human reading errors, and data imperfection, it has become essential to support preference queries of various types over imprecise data. Imprecise data can be classified into two categories: incomplete and uncertain data. Unfortunately, existing work for preference queries for the imprecise data are limited and isolated. This thesis addresses efficiently extending DBMS to be preference-aware over imprecise data. First, we address the problem of skyline queries over incomplete data where multi-dimensional data items are missing some values of their dimensions. We show that with incomplete data, the dominance relation among data points may not be transitive, thus, almost all existing techniques for skyline queries are not applicable. We propose an efficient algorithm to compute the skyline over incomplete data. Then, we define preference queries over uncertain data, represented as a continuous range. We propose a novel, efficient framework to answer these preference queries. Then, we present PrefJoin, an efficient preference-aware join query operator, designed specifically to deal with preference queries where the set of preferred attributes reside in more than one relation. The main idea of PrefJoin is to make the join operator aware of the required preference functionality. Finally, we extend PrefJoin framework to realize an efficient preference-aware operator which support imprecise data. The extended framework is denoted as PrefJoin*.