交互式多用戶Skyline查詢處理算法*

邵路伊，秦小麟，王瀟逸，郭成蓋，鄧丹萍

南京航空航天大學 計算機科學與技術學院，南京 210016

1 引言

隨著數據庫技術的發展，數據庫中存儲的數據量急劇增加，如何從海量數據中找到人們最感興趣的信息，為人們做出有效的決策，成為一個重要的研究課題。因此，Skyline查詢在2001年作為一種新的數據庫操作符被提出來[1]，從此得到了數據庫領域眾多研究者的大量關注。Skyline查詢在很多應用中都有著非常重要的作用，例如多目標決策、數據挖掘及可視化，以及用戶偏好查詢等[2]。數據庫領域最初的Skyline查詢是由單用戶發起的，例如，一個用戶發出查詢“查找一家價格便宜同時距離海邊近的酒店”。然而，在數據管理領域，隨著計算環境的不斷變化、信息技術的發展和應用新需求的出現，越來越多的數據庫應用會涉及到由多個用戶共同完成一個查詢，例如：

查詢1一群游客共同商定一個旅游城市，每位游客針對城市的氣候、地理位置、景點以及消費水平等提出不同要求的查詢。

查詢2一個家庭共同選擇一個寬帶方案，每位家庭成員針對方案的帶寬、價格、合約期限等提出不同要求的查詢。

查詢3一組同事共同預定一家聚餐餐廳，每位同事針對餐廳的口味、環境、服務以及人均價格等提出不同要求的查詢。

上述查詢事例可以抽象為：對于某數據集，多個用戶發起不同維度組合上的子空間Skyline查詢，系統對同時存在的子結果集進行整合，最終返回一個結果集。此類查詢可概括為MUSQ（multi-user Skyline query）問題，即多用戶Skyline查詢問題。……