【作者】 刘欣；

【导师】 刘国华；

【作者基本信息】 燕山大学 ， 计算机应用技术， 2006， 硕士

【摘要】 空间查询及优化是空间数据库相关技术研究的难点和突破点,轮廓查询技术已经成为空间查询及优化领域的热点课题。目前轮廓查询技术还处于起步阶段,各方面的技术还不成熟,存在一定的缺陷。本文对轮廓和轮廓体的查询及更新技术进行了综合分析,在此基础上提出了新的查询和更新处理方法,具体内容如下。首先,对轮廓查询技术进行了研究,提出并证明了修剪空间定理,给出有效区的形式化定义,在此基础上提出了基于动态窗口查询的轮廓查询算法,对算法的正确性进行了证明,并通过实例对算法进行了分析说明。其次,对轮廓更新技术进行了研究,给出了查询区和空白区的定义,提出并证明了添加数据点轮廓更新判定定理和删除数据点轮廓更新判定定理,在此基础上提出了Addpoint_Skyline算法和Deletepoint_Skyline算法,并对算法的正确性进行了证明,对时间复杂度进行了计算。再次,对轮廓体更新技术进行了研究,提出并证明了不同值定理,根据该定理设置了不同值条件,在此基础上提出了Addpoint_Skycube算法和Deletepoint_Skycube算法,并对算法的正确性进行了证明,对时间复杂度进行了计算。然后,对数据流中轮廓体查询技术进行研究,提出并证明了单点定理,给出了数据流中轮廓体查询框架,对其各模块的功能及算法进行了分析说明,并对算法的正确性和时间复杂度分别进行了证明和计算。最后,对上述算法进行了实验验证,通过分析实验结果发现,轮廓查询算法无需访问整个数据集就能渐进地返回完整的轮廓结果,更新算法能够准确地完成轮廓和轮廓体的更新操作,数据流中轮廓体的查询框架能够快速追踪轮廓体的变化,并实时更新轮廓体,且保证查询结果准确有效。更多还原

【Abstract】 Spatial query and optimization are difficult points and breakthrough of the related technologies in spatial database, the technology of skyline query has become a hot subject of spatial query and optimization. Now, the technology of skyline query is still at the initial stage, and the technical aspects are not mature, which still has some shortcomings. In this paper, the query and updating technologies of skyline and skycube are analyzed synthetically, and some new methods are proposed based on these, the material contents are as follows.Firstly, the technology of skyline query is studied. The pruning space theorem is presented and demonstrated, and the formal definition is given. Based on these, the algorithm for skyline query based on dynamic window query is proposed. In addition, the correctness of the algorithm is proved and analyzed through examples.Secondly, the technology of skyline updating is studied. The definitions of query region and blank region are presented, and then the skyline updating determinant theorems of inserting and deleting point are presented and demonstrated. Based on these, the Addpoint_Skyline algorithm and Deletepoint_Skyline algorithm are proposed. In addition, the correctness is proved, and the time complexity is computed.Thirdly, the technology of skycube updating is studied. The distinct value theorem is presented and demonstrated, according to this theorem, the distinct value condition is configed. Based on these, the Addpoint_Skycube algorithm and Deletepoint_Skycube algorithm are proposed, then the correctness is proved, and the time complexity is computed.Fourthly, the technology of skycube query in data stream environment is studied. The single point theorem is presented and demonstrated, based on this,the architecture of skycube in the stream environment is proposed, and then every module and its algorithm are analyzed in detail. In addition, the correctness of every algorithm is proved, and the time complexity is computed.Finally, the algorithms in this paper are validated. The algorithm for skyline query based on dynamic window query can return the whole skyline result progressively and it is not nessary to access the whole query space, the updating algorithms can quickly and exactly complete the updating operators of skyline and skycube, and the architecture of skycube in the stream environment can quickly track skycube changes, guarantee the updating of skycube real-time and the results are exact and effective.更多还原