Skyline 查詢是一個典型的多目標最佳化的問題.對它的研究最早可以追溯到1975 年.
資料庫領域的研究人員對Skyline 查詢的研究始於2001 年,最早由Borzsonyi 等人提出[1].主要關注在數據量很大、無法放入記憶體的情況下,如何處理Skyline 查詢.
1) 單Skyline 查詢處理算法.該類算法假定所有的Skyline 對象都處在某一個特定的D-維空間中,返回的結果集合只有1 個.根據查詢過程中是否藉助索引,單Skyline 查詢處理算法又分為兩類:不帶索引算法和帶索引算法.前者假定沒有任何索引存在,通過掃描整個數據集(至少1 次)來返回Skyline 查詢的結果;後者通過引入適當的索引結構,如R-樹,來提高查詢處理的效率.
2) 多Skyline 查詢處理算法.針對現實生活中不同的用戶可能有不同的興趣和偏好,需要在不同的子空間中處理Skyline 查詢的需求,數據倉庫和OLAP 領域的研究者對在不同子空間上進行Skyline 查詢的研究產生了濃厚的興趣,提出了SKYCUBE的概念.SKYCUBE 借用傳統的Data Cube 的多維層次結構,提出了有效的同時計算多個Skyline 查詢的思想.該類算法主要包含針對SKYCUBE 的計算、維護和壓縮等.
3) 不同套用環境下的Skyline 查詢處理.主要包括Web 信息系統中的Skyline 查詢處理、P2P 網路環境下的Skyline 查詢處理、數據流環境下的Skyline 查詢處理、移動的公路網路環境下的Skyline 查詢處理等.
4) Skyline 查詢處理問題的擴展.例如,文獻中首次擴展了空間資料庫中不同數據點之間的控制關係的概念,將其用於經濟學框架下的商業分析,提出了控制關係分析的概念;文獻針對高維空間下出現在Skyline 查詢結果中的點非常多,從而導致該結果在很多時候對用戶失去意義的問題,提出了k-Dominant 的概念,等等.