近年来Web数据大量增长,如何为用户提供有效的搜索技术成为研究的热点。在分布式环境下,通过数据收集,得到的Web数据主要存储在关系数据库中,大量来自不同数据源的Web数据,具有异构模式。在目前的发展阶段,搜索引擎是支持用户查询请求的重要手段。用户根据兴趣,通过搜索引擎接口输入相关的关键字,系统提供快速响应回答用户的请求。很多情况下,用户提交的请求不能与数据库中的数据进行精确匹配,例如：用户对数据了解的程度有限、录入的数据包含错误信息、来自多个数据源的数据存在不一致性等。因此,在关系数据库上有效地支持近似关键字搜索带来了一系列新的挑战,诸如,面向关系数据库的近似查询处理,字符串近似匹配的执行效率和查询结果的排序等问题。本文针对上述问题进行研究,主要工作包括以下几点：(1)为改善对关系元组中字符串数据的近似查询效率,提出一种新颖的索引结构,简称VGRAM (变长GRAM)。与传统的解决近似字符串查询的索引方法相比,VGRAM索引不但节省了近似查询算法的时间,并且将索引的空间缩小了1倍以上。同时,该技术具有很好的可移植性,任何一个基于gram思想的近似字符串查询算法都可以采用该索引技术并提高原有算法的执行效率。其主要思想是：在字符串集合中,选择高质量的变长gram来支持该集合上的查询。重点研究的问题包括：如何从特定集合中选择高质量的gram、如何基于预选的gram将字符串分解成一组变长的gram集合,以及分析两个gram集合间的相似度同它们编辑距离间的关系。基于真实数据集上大量的实验测试结果表明,VGRAM索引技术可以显著地改善最新的三种经典算法的查询性能。(2)提出了基于代价的高质量gram选择技术。当采用基于gram的倒排列表作为索引结构时,索引项gram的选取直接决定索引结构,进而决定近似查询的执行效率。针对gram索引项集和查询性能间的关系,提出一种计算两个字符串公共gram数目的下限的动态规划算法,以提高下限值,从而获得更快的近似匹配时间。系统地分析gram索引结构对近似匹配性能的影响,并提出一个自动构造高质量gram索引项集的算法。在真实数据集上的实验展示了这些技术对查询性能的改善。就目前所知,这是第一个基于代价分析的gram选择方法。(3)针对有限的form查询接口进行查询扩展,提出基于form查询接口的改善近似搜索能力的查询重写技术。很多近似搜索引擎为用户提供form接口,用户通过form接口提交关键字并获得搜索结果。返回给用户的结果大多数是根据填写在查询接口中不同值域内的关键字计算得到的,导致查询结果的查全率(recall)很低。本文提出一种数据挖掘方法,通过对历史查询及其结果进行挖掘分析,得到一组查询重写知识,包括数据项树和推理规则。利用这些重写知识,可以对用户查询进行扩展,以提高基于form的近似搜索能力,特别是查全率。从不同Web网站上随机选取的3,800篇文档组成的测试集上的实验结果表明：所提出的数据挖掘和查询重写方法获得的平均查准率和查全率均高于80%,而假通过率低于2.0%。(4)针对关系数据表之间以及元组间的数据依赖关系,提出一种支持关系数据库的关键字近似搜索的语义评价模型,包括语义相关度计算和语义评分函数。基于提出的语义评分函数,提出两种以数据块为处理单位的Top-k搜索算法,分别为BA(Blocking Algorithm)算法和EBA(Early-stopping Blocking Algorithm)算法。EBA在BA基础上引入了过滤阈值以便尽早终止算法的迭代过程。实验结果显示所提出的语义评分函数保证了搜索结果的高查准率和查全率,BA算法和EBA算法改善了现有方法的查询性能。总之,本文研究了面向关系数据库的关键字近似搜索技术的几个核心问题,并提出了新的解决方案。理论分析和大量基于实际数据集的测试表明所提出的方法的有效性和高效性。