针对隐藏Web数据库的Skyline查询方法研究

doi:10.3778/j.issn.1673-9418.1908036

摘要/Abstract

摘要：

通过Web接口查询服务端“隐藏”数据库的Skyline可以支持Web集成领域许多新应用。尽管受到客户端基于IP地址访问次数、top-k查询结果返回元组个数k，以及Web接口类型等诸多限制，但利用基本查询方法仍可获得隐藏Web数据库的Skyline，遗留的主要问题是查询代价过大。对此提出了混合属性的隐藏Web数据库Skyline的启发式求解方法。首先，利用平行坐标系分析Skyline元组相交性质，随后构造了启发式相交元组查询分解树，并证明了该树的查全性，最后针对典型的Web接口类型给出了启发式求解方法。理论分析和实验结果证实了启发式算法的有效性和相对基本查询方法的优越性。

关键词: 数据库Skyline, 隐藏Web数据库, 相交元组, 平行坐标系, 查询分解树

Abstract:

Skyline discovery from a hidden Web database can enable a wide variety of innovative applications in Web information integration area. Although there are many limitations such as the finite number of Web accesses one can issue through per-IP-address, no more than k tuples of all matching tuples one top-k query can return, and the restricted Web interface types, Skyline of hidden Web database can still be obtained by using the basic query method. However, the serious problem left is that the query cost is too high. To solve it, this paper puts forward a heuristic algorithm for getting Skyline tuples of a hidden Web database based on the mixture attributes. Specifically, this paper first analyzes intersecting characters of Skyline tuples by parallel coordinate system, and next defines a search decomposition tree for searching heuristically Skyline tuples of a hidden Web database, and then proves that the tree is guaranteed to discover all Skyline tuples. At last, a heuristic method is given for typical Web interface types. Theoretical analysis and experiments demonstrate the effectiveness of the proposed method and the superiority over baseline solutions.

Key words: database Skyline, hidden Web database, intersecting tuples, parallel coordinate system, search decomposition tree

李征宇，李贵，曹科研. 针对隐藏Web数据库的Skyline查询方法研究[J]. 计算机科学与探索, 2020, 14(8): 1307-1314.

LI Zhengyu, LI Gui2, CAO Keyan. Research of Skyline Query Method for Hidden Web Database[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(8): 1307-1314.

参考文献

[1] Han X X, Song C, Ge Y R, et al. Efficient top-k Skyline query algorithm on massive data[J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(5): 775-787.韩希先, 宋翠, 戈韵如, 等. 海量数据上有效的top-k Skyline查询算法[J]. 计算机科学与探索, 2019, 13(5): 775-787.
[2] Shao L Y, Qin X L, Wang X Y, et al. Algorithm for interactive multi-user Skyline query[J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(8): 1202-1213.邵路伊, 秦小麟, 王潇逸, 等. 交互式多用户Skyline查询处理算法[J]. 计算机科学与探索, 2018, 12(8): 1202-1213.
[3] Li S, Dou Y N, Zhang L P, et al. Method of spatial Skyline query in obstacle environment[J]. Journal of Frontiers of Com-puter Science and Technology, 2018, 12(12): 1882-1890.李松, 窦雅男, 张丽平, 等. 障碍环境中空间Skyline查询方法[J]. 计算机科学与探索, 2018, 12(12): 1882-1890.
[4] Wang Z Q, Ba J M, Huang D, et al. ρ-dominant Skyline com-putation on data streams[J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(7): 1080-1091.王之琼, 霸建民, 黄达, 等. 数据流中ρ-支配轮廓查询算法[J]. 计算机科学与探索, 2017, 11(7): 1080-1091.
[5] Gong Z Q, Sun G Z, Yuan J, et al. Efficient top-k query alg-orithms using K-skyband partition[C]//Proceedings of the 4th International ICST Conference on Scalable Information, Hong Kong, China, Jun 10-11, 2009. Berlin, Heidelberg: Springer, 2009: 288-305.
[6] Lin X M, Yuan Y D, Zhang Q, et al. Selecting stars: the k most representative Skyline operator[C]//Proceedings of the 23rd International Conference on Data Engineering, Istanbul, Apr 15-20, 2007. Washington: IEEE Computer Society, 2007: 86-95.
[7] Borzsony S, Kossmann D, Stocker K. The Skyline operator[C]//Proceedings of the 17th International Conference on Data Engineering, Heidelberg, Apr 2-6, 2001. Washington: IEEE Computer Society, 2001: 421-430.
[8] Dells E, Seeger B. Efficient computation of reverse Skyline queries[C]//Proceedings of the 33rd International Conference on Very Large Data Bases, Vienna, Sep 23-27, 2007. New York: ACM, 2007: 291-302.
[9] Papadias D, Tao Y F, Fu G, et al. An optimal and progressive algorithm for Skyline queries[C]//Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, Jun 9-12, 2003. New York: ACM, 2003: 467-478.
[10] Ilyas I F, Beskales G, Soliman M A. A survey of top-k query processing techniques in relational database systems[J]. ACM Computing Surveys, 2008, 40(4): 1-58.
[11] Sun Y J, Yuan Y, Wang G R. Answering probabilistic top-k queries over P2P networks[J]. Chinese Journal of Computers, 2011, 34(11): 2155-2164.孙永佼, 袁野, 王国仁. P2P环境下面向不确定数据的Top-k查询[J]. 计算机学报, 2011, 34(11): 2155-2164.
[12] Bai M, Xin J C, Wang G R. Research on dynamic Skyline query processing over data streams[J]. Chinese Journal of Com-puters, 2016, 39(10): 2007-2030.白梅, 信俊昌, 王国仁. 数据流上动态轮廓查询处理技术的研究[J]. 计算机学报, 2016, 39(10): 2007-2030.
[13] Liu T T, Wang F, Agrawal G. Stratified sampling for data mining on the deep Web[J]. Frontiers of Computer Science, 2012, 6(2): 179-196.
[14] Wang F, Agrawal G. Effective and efficient sampling methods for deep Web aggregation queries[C]//Proceedings of the 14th International Conference on Extending Database Technology, Uppsala, Mar 21-24, 2011. New York: ACM, 2011: 425-436.
[15] Shen D R, Ma Y, Nie T Z. A query relaxation strategy applied in a deep Web data integration system[J]. Journal of Computer Research and Development, 2010, 47(1): 88-95.申德荣, 马也, 聂铁铮.一种应用于Deep Web数据集成系统中的查询松弛策略[J]. 计算机研究与发展, 2010, 47(1): 88-95.
[16] Lo E, Yip K Y, Lin K I, et al. Progressive Skylining over Web-accessible databases[J]. Data & Knowledge Engineering, 2006, 57(2): 122-147.
[17] Han S S, Zheng J P, Dong Q. Efficient processing of k-regret queries via Skyline frequency[C]//LNCS 11242: Proceedings of the 15th International Conference on Web Information Sys-tems and Applications, Taiyuan, Sep 14-15, 2018. Berlin, Heidelberg: Springer, 2018: 434-441.
[18] Han S D, Zheng J P, Dong Q. Efficient processing of k-regret queries via Skyline priority[C]//LNCS 11242: Procee-dings of the 15th International Conference on Web Information Systems and Applications, Taiyuan, Sep 14-15, 2018. Berlin, Heidelberg: Springer, 2018: 413-420.
[19] Madhavan J, Ko D, Kot L, et al. Google??s deep Web crawl[J]. Proceedings of the VLDB Endowment, 2008, 1(2): 1241-1252.
[20] Sheng C, Zhang N, Tao Y F, et al. Optimal algorithms for crawling a hidden database in the Web[J]. Proceedings of the VLDB Endowment, 2012, 5(11): 1112-1123.