基于智能技术top-n关系查询处理和优化

《基于智能技术top-n关系查询处理和优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、北京工业大学博士学位论文基于智能技术的Top-N关系查询处理和优化姓名：朱亮申请学位级别：博士专业：计算机应用技术指导教师：刘椿年20081201摘要数据库系统正在经历巨大的变化，智能技术已经引入到数据库系统的研究中。2004年在SIGMOD国际会议上，Jim研ay说：“我们正沿着一条有价值的链条从数据到信息到知识到智慧在慢慢地攀爬”。数据库研究的核心问题之一为查询处理和优化。近年来top-N查询倍受关注，成为国际上非常活跃的研究课题。top．N查询比传统查询的应用更广泛、更灵活、功能更强大，能够

2、解决传统数据库管理系统(DBMS)无法处理的查询问题；其主要应用包括：数据挖掘、搜索引擎、决策支持系统、多媒体数据库、信息检索、Web智能和Web数据库等。在查询的研究中，关键是对查询准确和快速地处理，因此需要研究查询处理的理论、方法、技术及优化策略。本文主要对top-N查询进行研究。top．N查询就是，对于用户指定的正整数Ⅳ，如N=10，20或100，检索出Ⅳ个元组使其最好地匹配查询条件，但不一定完全匹配查询条件；输出的结果集合按所用的距离函数排序。具体内容如下：1．基于学习的top-N查询处理

3、：本文运用基于学习的策略，给出top-N查询处理的一种新方法。其主旨为，在初始阶段，对于少数随机的top-N查询，找出其最佳搜索区域并将相关信息存储在一个知识库中；然后用知识库中的知识处理新提交的top-N查询；随着被处理的top-N查询的增加，原始知识库将被不断更新，因而能够更好地处理频繁提交的查询。另外，给出知识库的维护方法并且用时间序列的理论和方法讨论知识库的稳定性。最后，用大量的实验来验证基于学习策略的性能，且与其它方法进行比较。实验结果表明基于学习的方法不仅可以很好地处理低维数据，而且能

4、够很好地处理高维数据，不惧怕“维数灾难”；与现有其它方法比较，其效率更有优势。2．基于区域聚类的多top-N查询优化：在很多数据库应用中，存在同时处理多个提交的top．N查询的情形。通常，同时处理多个查询的开销比单个地逐一处理更有效。对于关系数据库，本文提出了同时处理多个top-N查询的一种新方法，其基本思想是区域聚类。区域聚类把各个top-N查询的搜索区域聚集成一些较大的区域并且从这些较大的区域检索元组。这种方法避免了多次访问同一区域并且减少了对底层数据库随机I／O访问次数。通过大量实验测北京工

5、业大学T学博上学位论文试这种新策略的性能；实验结果表明对于低维(2，3和4维)和高维(25，50和104维)数据，这种方法明显优于逐一处理的朴素方法。另外，虽然区域聚类方法是为多top-N查询优化提出的，但可以直接运用于多区域查询优化；对此，本文也进行了研究，其性能也显著优于朴素方法。3．Top-N查询流处理：在数据库系统及其应用中，另一个重要问题是处理在不同时间提交的top-N查询所形成的查询流。为此，改进了上述基于学习的策略并且结合区域聚类方法，同时运用缓存机制，对top-N查询流进行综合优化

6、处理。这种方法使用知识库来存储一些过去查询的相关信息，聚类以往查询的搜索区域为较大的区域，进而从这些较大区域检索元组。为了回答一个新提交的查询，尽量从内存中已经检索的结果获取元组。这样，通过尽量减小搜索区域和避免访问底层数据库来寻求缩短响应时间。同时，这种方法保持查询高维数据的高效性。另外，给出知识库的维护策略。大量的实验用来验证此策略的性能，实验结果表明，无论是对低维数据还是高维数据，此方法的性能比朴素方法的性能明显提高。本文也探究了用类似方法处理区域查询流，实验表明其性能显著优于朴素方法。4．

7、基于语义距离的top—N查询处理：传统数据库搜索在查询和元组的比较过程中使用模式匹配。对于一个查询，只有当元组和查询完全匹配时，元组才被检索。本文研究具有语义的文本属性的top-N查询处理，通过定义新的语义距离函数，实现数据库搜索过程中词与词之间的语义匹配。目的是不仅返回与查询完全匹配的元组，而且与查询的语义距离靠近的元组也能被取出。实现方法的主旨是：基于WordNet创建索引将元组的词进行语义扩展；通过此索引来匹配查询词和元组的扩展词，运用一个简单的SQL选择语句于关系的自然连接检索出候选元组；

8、然后，用语义距离对候选元组排序，最后输出top．N结果。大量的实验用于测量这种新策略的性能。基于以上内容的研究结果，本文的主要贡献在于：1．对于top-N查询处理，提出了基于学习的新方法，通过估计查询的局部分布密度，确定top．N查询的搜索区域；用时间序列的理论和方法，定义和分析知识库的稳定性。2．提出了多top—N查询优化新问题，并且为了解决此问题，提出了区域聚类的新方法。区域聚类的对象为“刀一维超矩形”，而通常聚类的对象是“点”。上lI摘要述基于学习的和区域聚类的两种方法，不仅