（计算机系统结构专业论文）数字有机体数据库中信息检索研究与实现.pdf

摘要 摘要 传统上，数据库技术和信息检索技术两者独立发展。数据库技术处理结构化 数据，采用结构化查询语言，查询结果是精确的完全的并且被同等对待。信息检 索技术处理非结构化数据，采用非结构化查询语言，查询结果不精确不完全，根 据相关性进行返回。把信息搜索技术应用到数据库关键词的搜索中提高了数据库 系统的易用性，用户无需知道数据的存储结构和s q l 语法规则，可以使用简单的 关键词自由的检索数据库，挖掘其中的信息和知识，信息资源的利用效率得到很 大提高。因此，8 0 1 0 教研室在数字有机体数据库系统基础上，以数据库信息的灵 活检索为根本出发点，开发了数据库信息检索系统。 信息检索系统可分为预处理阶段和查询阶段。查询阶段首先对用户检索请求 进行语法分析，然后通过检索策略获得检索结果。在用户未指定检索关键字所在 属性的情况下，检索策略的设计是研究的一个重点，检索结果必须满足完整性和 非冗余性。 本课题充分分析现有数据库关键字检索系统和m y s q l 数据库。在数字有机体 数据库系统的基础上，设计和实现了基于数字有机体数据库信息检索系统的检索 策略。此部分主要分为四个阶段：索引查询、生成数据图、获得结果树和s q l 语 句的生成、执行。索引查询和生成数据图在同一模块中实现，数据图由关键字所 在位置和数据库结构生成，体现了数据库中包含检索关键字的关系以及关系之间 的联系。通过采用双层结构，充分利用数据库结构属性和查询类型特点对索引信 息进行精炼，减少数据图中无用数据的产生。遍历数据图，可获得所有满足用户 请求的子图( 结果树) 。在结果树生成算法中，在保证结果树完整性的同时，对遍历 起始节点的有效选择减少了在遍历时产生的冗余子树。结果树包含检索请求的所 有关键字，指明了关系中的选择操作和关系之间的连接条件，通过构造相应的s q l 查询语句，最终获得满足检索结果。 系统通过模块化和层次化设计使各模块算法具有良好的扩张性，并且采用 o d b c 接口与数据库服务器进行交互，确保了整个信息检索模块的独立性。最后 对系统进行功能和性能测试，指出不同参数对数据库关键字检索的影响。 关键词：数字有机体，关系数据库，关键字检索，检索策略 a b s t r a c t a l t h o u g hb o t hd a t a b a s ea n di n f o r m a t i o nr e t r i e v a ls y s t e m sf o c u s0 1 1s e a r c h i n gd a t a , t h e i rm e t h o d st os o l v et h ep r o b l e ma r ev e r yd i f f e r e n t d a t a b a s es y s t e m ss e a r c h s t r u c t u r e dd a t aw i t hc o m p l e xq u e r yl a n g u a g e s i t sr e s u l t sa l es o u n da n dc o m p l e t e ，a n d a l lt h er e s u l t sa r ee q u a l l yg o o d i n f o r m a t i o nr e t r i e v a ls y s t e m ss e a r c hu n s t r u c t u r e dd a t a b yk e y w o r d s i t sr e s u l t sa r eu s u a l l yi m p r e c i s ea n di n c o m p l e t e ，a n ds o m er e s u l t sa l e m o r er e l e v a n tt h a no t h e r s k e y w o r ds e a r c ho v e rr e l a t i o n a ld a t a b a s e ( k s o r d ) a l l o w si t s u s e rt oi s s u ek e y w o r dq u e r i e sw i t h o u ta n yk n o w l e d g eo ft h ed a t a b a s es c h e m ao ro fs q l t h e r e f o r e ，t h e8 0 10l a bd e v e l o p st h ek e y w o r dr e t r i e v a ls y s t e mo v e rd i g i t a lo r g a n i s m d a t a b a s es y s t e m ( d o s s q l ) a l ld a t a b a s er e t r i e v a ls y s t e m sh a v et w om o d u l e s ：p r e p r o c e s s i n gm o d u l ea n dq u e r y m o d u l e q u e r ym o d u l ei si nc h a r g eo fq u e r yp r o c e s s i n g a tf i r s ts t e p ，t h eq u e r ym o d u l e p a r s e su s e r si n p u t t of i n dq u e r yk e y w o r d sa n dq u e r ys e m a n t i c s t h e n ，t h eq u e r ym o d u l e e x e c u t e st h es e a r c ha l g o r i t h mt og e n e r a t er e s u l t s t h es e a r c ha l g o r i t h mi st h ek e yp o i n t o ft h er e t r i e v a ls y s t e m a tt h es a m et i m e ，t h es e a r c hr e s u l tm u s ts a t i s f yi n t e g r i t ya n d n o n r e d u n d a n c y a f t e rt h ef u l l ya n a l y s i so ft h ee x i s t e dk e y w o r dr e t r i e v a ls y s t e m ，m y s q la n d d o s s q l ，t h i st h e s i sh a sd e s i g n e da n di m p l e m e n t e dt h es e a r c ha l g o r i t h m i ti n c l u d e s s e a r c h i n gi n d e x ，g e n e r a t i n gt u p l es e tg r a p h ，e n u m e r a t i n gr e s u l tt r e e s ，a n de x e c u t i n gt h e s q lq u e r y ，n l et u p l eg r a p hi sg e n e r a t e da c c o r d i n gt od a t a b a s e ss c h e m aa n dt h e k e y w o r di n d e x ，r e f l e c t i n gt h ec o r r e l a t i o na n dt h ep o s i t i o no ft h ek e y w o r d si nt h e d a t a b a s e t h r o u g ha d o p t i n gt h ed o u b l e - l a y e rs t r u c t u r e ，t a k i n ga d v a n t a g eo ft h ea t t r i b u t e o fd a t a b a s es t r u c t u r ea n dr e f i n i n gt h ei n d e xi n f o r m a t i o n ，m o s to ft h en o n - u s e f u ld a t ah a s b e e nr e d u c e d t r a v e r s i n gt h e t u p l eg r a p hc a ng e n e r a t ea l lr e s u l tt r e e sw i t l ll e s s r e d u n d a n c y f i n a l l ya ns q ls t a t e m e n ti sp r o d u c e df o re a c hr e s u l t t r e ea n dt h e s e s t a t e m e n t sa r ep a s s e dt ot h ed b m s t h ed b m sr e t u r n st h ej o i n i n go f t u p l e s ，w h i c ha r e s o l u t i o n st ot h ep r o b l e m t h es o f t w a r ei m p l e m e n t a t i o n ，w i t ht h ea s s i s t a n c eo ft h e m o d u l a r i z a t i o na n dl a y e r i n gd e s i g n ，m a k e st h ea l g o r i t h mm o r ef l e x i b l ea n de x p a n s i b l e t h er e t r i e v a l s y s t e m u s e so d b ct oc o m m u n i c a t ew i n ld a t a b a s es e r v e r , w h i c h i t a b s t r a c t g u a r a n t e e st h ei n d e p e n d e n c eo f t h es y s t e m t e s t sp o i n to u tt h ei n f l u e n c eo ft h ed i f f e r e n tp a r a m e t e r s t h er e s u l ts h o w st h a tt h e s y s t e ma c h i e v e st h ef u n c t i o n a la n dt h ep e r f o r m a n c er e q u i r e m e n t s k e y w o r d s ：d o s s q l ，r e l a t i o n a ld a t a b a s e ，k e y w o r ds e a r c h , s e a r c ha l g o r i t h m i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：e t 期：矿够年岁月彩e t 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：导师签名： 日期：如裾 ：jb 仫 年卵6 日 第一章引言 1 1 研究背景 1 1 1 关系数据库关键字检索 第一章引言 信息检索技术是目前技术研究领域的一个热点。互联网搜索引擎使得关键字 搜索成为主流，用户通过提交关键字，搜索引擎根据相关度对搜索结果进行排序 返回。但是搜索引擎所能搜索到的网页数据只是w e b 上全部数据的小部分，8 0 的数据仍然在数据库中进行存储。用户通过合适的结构化查询语句( s q l ) 对数据 库进行查询。即使是最简单的查询语句，用户也需要了解数据库结构和查询语言 语法。为非专业人员设计的查询语言对普通用户来讲也过于复杂，为半结构化x m l 数据设计的查询语言则更加复杂。毫无疑问，结构化查询语言对用户使用数据库 提高了限制。近年来，使用非结构化查询语句对结构化和半结构化数据进行查询 开始引起研究人员的兴趣。同时，o r a c l e ，d b 2 ，s q ls e r v e r ，m y s q l 等关系数据 库都提供了文本搜索扩展，可以为数据库中的文本建立全文索引( 倒排表索引) ， 这些均为实现关系数据库的关键词查询提供了一个基础。 在用户不了解数据库结构的情况下，实现数据库关键词搜索是极具挑战性的 工作。数据库是将客观世界的信息抽象为简要结构化的数据类型来存储，是对客 7 观存在实体信息简要而完整的描述。因此从逻辑上来讲数据库种的数据是用来描 述了一个完整的实体信息，数据库的结构化特征使得基于文本的搜索方式并不能 直接应用于数据库搜索。例如：数据表设计人员为了方便于对数据表中的数据进 行管理或者出于减少数据冗余和存储空间，很大程度上会将一组有意义的数据分 割存储在多个数据表中，数据表之间通过主外键进行约束。数据库关键字需要发 现多个数据表之间的关系，将分布在多个数据表中的数据联合进行返回【2 1 1 。图1 1 显示了数据库系统与信息检索系统之间的关系。在本文中关系数据库的信息检索 与关键字搜索具有相同含义。 电子科技大学硕士学位论文 k e y w o r d s e a r c h s t r u c t u r e d q u e r y l a n g u a g e | | | jj 1 j 该嗲j j j 一f | i 臻 势 7 i n f o r m a t i o n 劳7 ：r e t r i e v a ls y s t e m s 熬i 锄貔壤娄缀潮 d a t a b a s es y s t e m s s t r u c t u r e dd a t au n s t r u c t u r e dd a t a 图1 1 数据库与信息检索关系图 1 1 2 数字有机体数据库 数字有机体系统是8 0 1 0 实验室开发的一个基础平台【3 2 1 。它的主要的目标是将 分布在较大范围内的大量计算机聚合成为一个整体，以便向应用提供强大的处理、 存储和通信等能力，从而满足大规模网络应用的需要。系统通过宽带网实现物理 上的互连，实现客户机智能动态的和若干服务器( 组) 建立连接，而不是静态的 和一个服务器建立连接，从而提高系统的可靠性( 可用性) 。系统保证客户机的服 务请求将自动智能的被转给其它服务器，直到获得服务为止。在一个足够大的范 围内，对一个客户机的请求服务尽可能实现局部化访问。 、 分布式数据库最初是为了实现分布式数据和复制数据的透明管理，通过使用分 布式事务而得到改进的系统可靠性。相对于集中式数据库，分布式数据库的出现 增加了用户共享数据的能力，降低了系统成本，对不同处理机间的负载进行平衡， 具有更高的灵活性，更易进行系统扩展。通过将工作负载分散到众多的系统节点 中能够达到很高的可靠性。 数字有机体数据库系统对数字有机系统和分布式数据库进行整合，针对分布式 数据环境，将p 2 p 分布式结构有效的利用到分布式数据库结构中。对于数据库， p 2 p 技术可以使数据更有效地分布到网络边缘，充分利用网络资源。数字有机体数 据库系统基于m y s q l 数据库进行开发，将数据存储在一个和多个网络节点的物理 数据库中，若干个数据库服务器通过高速网络连接起来，服务器与服务器之间实 现数据资源共享，用户可以通过连接本地数据库或者直接指定远端服务器p 连接 来实现访问整个数字有机体数据库系统中所有的数据资源。系统对外提供良好的 用户接口，包括应用程序函数库和系统管理界面等。能够满足不同用户的需求， 保证用户方便地使用本系统。 2 第一章引言 1 2 研究意义和目标 传统上，数据库技术和信息检索技术两者独立发展。数据库技术处理结构化 数据，采用结构化查询语言，查询结果是精确的完全的并且被同等对待。信息检 索技术处理非结构化数据，采用关键词搜索这样的非结构化查询语言，查询结果 不精确不完全而且要根据相关性排列。随着数据库日益成为信息存储和管理的载 体。将信息检索( i n f o r m a t i o nr e t r i e v a lr ) 与数据库( d a t a b a s e ) 技术相结合蕴含 着巨大的技术潜力和使用价值，与传统的s q l 查询语句相比具有以下优势：用户 无需知道数据的存储结构和了解s q l 语句的使用。并且，使用关键字搜索，用户 可以通过搜索结果的返回了解到关键字之间在数据库中的关联。 数据库在其发展过程中，日益成为多种媒体的载体。从整体结构来看，数据 库管理结构化数据。从局部来看，数据库同时也管理着非结构化数据。这就要求 将数据库与信息检索结合起来，即使应用只需要管理一种类型的数据，集成数据 库和信息检索技术也是有好处的，因为可以用一种技术的长处来弥补另一种技术 的不足。例如，数据库系统中的s q l 语言对于普通的最终用户来说难于学习和掌 握，并且在使用的时候必须知道数据库的模式，但信息检索系统中的关键词搜索 则没有这些问题。由于上面的原因，集成数据库和信息检索技术已经成为了近年 来的一个研究热点。随着经济和社会信息化的发展，越来越多的数据以数据库的 形式存储，使用数据库的人越来越多，其中的大多数人并没有专业的数据库知识， 只能依赖于定制好的应用软件或查询接口检索数据库。数据库关键词检索技术提 高了数据库系统的易用性，可以使用简单的关键词来自由的检索数据库，挖掘其 中的信息和知识，信息资源的利用效率将得到很大提高。 在数字有机体数据库上实现关键字搜索子系统具有相当高的应用价值。用户 直接使用关键词对数据库进行搜索，并不需要了解数据库结构和学习结构化查询 语言。在方便用户的同时，由于对数据库存储的信息进行了处理，也为以后系统 功能的进一步扩充提供了基础。当今数据库关键字搜索均基于单机且对m y s q l 数 据库不完全支持多表多属性连接查询。针对以上特点，设计了基于数字有机体数 据库系统基础上的信息检索子系统。 1 2 本文工作 论文对当前数据库搜索研究状况进行了分析研究，以现有的数据库搜索系统 电子科技大学硕士学位论文 结构、搜索方法为主要研究对象，并分析了数据库搜索系统与传统的网页文本搜 索之间的共性和差异。重点研究了关系数据库中关键字搜索的检索策略，系统基 于结构图实现，包括四个阶段：索引查询、生成数据图、获得结果树和s q l 语句 的生成、执行。检索策略在用户未指定关键字所在属性的情况下，根据系统结构 和索引信息，查找出系统中满足用户检索请求的结果，且保证其完整性和非冗余 性。 1 3 论文组织 论文的研究内容组织如下： 第一章介绍了论文的研究背景和研究目标，分析了数据库关键字搜索的必要 性和面临的问题，指出了本论文的研究意义。 第二章介绍了已经存在的数据库关键字搜索系统，以及各种搜索系统的设计 特点，并指出这些系统与传统的文本搜索之间的共性和差异。之后介绍了本系统 的设计平台数字有机体数据库( d o s s q l ) 。本章介绍的数据库关键搜索是本文 的研究对象。 第三章提出了基于d o s s q l 的数据库信息检索子系统。并详细介绍了信息检 索子系统的设计思想和模块功能。 第四、五、六章对信息检索子系统中的i r e n g i n e 模块、r t g e n e r a t o r 模块和 e x e c u t i o n e n 西n e 模块进行了详细的论述，提出其实现意义和存在的问题，并给出 模块详细设计方案。 一 第七章对系统性能进行功能和性能进行测试，分析不同参数对数据库关键字 检索的影响。 第八章对上一阶段的研究成果进行总结，分析出其中的不足之处，并提出一 些对未来的研究方向的看法。 4 第二章关系数据库关键字搜索概述 第二章关系数据库关键字搜索概述 2 1 文本搜索与数据库搜索 数据库技术和信息检索技术是各自独立发展的。数据库技术处理结构化数据， 采用结构化查询语言，查询结果是精确的完全的并且被同等对待，主要应用于精 确设计并实现的系统。而信息检索技术处理非结构化数据，采用关键词搜索这样 的非结构化查询语言，查询结果根据文本与关键字之间的相关性排列。 网页文本搜索引擎的成功，使得关键字搜索成为最为流行的非结构化查询方 式。采用关键字搜索，用户无需学习查询语言，也无需了解数据的底层结构。当 今的搜索引擎提供对于一组文本的关键字搜索。除去文本，大量的信息存储于数 据库中，用户采用结构化的查询语言进行查询( x q u e r y 或s q l ) ，并且需要知道 数据的存储位置。集成数据库和信息检索技术的好处在于可以用一种技术的长处 来弥补另一种技术的不足，采用非结构化查询语言对结构半结构化的数据进行查 询可以提高数据查询灵活性。例如，数据库系统中的s q l 语言对于普通的最终用 户来说难于学习和掌握，并且在使用的时候必须知道数据库的模式，但信息检索 系统中的关键词搜索则没有这些问题【6 】。 网页文本搜索引擎的发展促进了关系数据库关键字搜索发展。关系数据库关 键字搜索系统在架构、流程、索引算法和排序算法上大量借鉴了传统搜索引擎。 特别是与用户的交互界面上，现有系统均努力提供类似g o o g l e 的搜索界面。 2 2 关系数据库关键字检索 数据库关键词查询系统可以分为在线查询和离线查询两大类。在线系统将关 键词查询转换为s q l 语句查询，通过实时查询数据库来生成查询结果。离线系统 通过预先对数据库内容进行索引和建立元组图，当用户提交关键词查询时，根据 索引生成查询结果。不同的查询系统采用不同的数据库建模方法。 数据库主要通过将数据库表示为结构图或数据图进行建模。结构图的结点对 应数据库中的关系，边表示模式定义的主外键约束；数据图中的结点对应关系中 的元组，边表示元组之间的主外键关系。结构图和数据图通常为有向图，采用有 5 电子科技大学硕士学位论文 向图可以明确表示节点间的关系( 引用与被引用，或者包含与被包含) ，通过计 算搜索结果和搜索请求之间的相似性时对其赋予相应的权重。 在线系统通常将数据库表示为结构图，最终通过s q l 查询得到数据库“最近 的一致性状态 下的查询结果，由于转换而成的s q l 查询中有大量的连接操作， 所以在线系统提高查询速度的关键在于减少对数据库，尤其是对磁盘的访问次数。 离线查询系统由于对索引进行直接查询，减少了大量s q l 查询操作，所以响应时 间较短。离线系统在实现数据库关键字搜索之前，必须建立和保持元组图，算法 工作主要集中在巨大数据库的维护上。但是，由于离线系统需要一个预先计算过 程，并且要对索引内容进行维护，所以如何有效表达数据库内容和数据库结构化 特征成了主要的研究内容。其返回结果是从数据图中删除结点和边后得到的树， 称为元组结果树。将元组结果树中元组替换为元组所属的关系，就得到了一棵元 组集结果树。更通俗地说，数据库关键词搜索的结果可以是单个元组，也可以是 多个元组的连接。数据库全文检索就是以单个元组作为返回结果。 关系数据库关键字检索使得普通用户能够使用关键词来检索关系数据库，而 不需要了解数据库结构和s q l 语言。目前，基于数据图的系统包括b a n k s ， o b j e c t r a n k 等；基于结构图的系统包括d b x p l o r e ，d i s c o v e r ，i r - s t y l e 等。各 个系统对检索结果的定义有所差别：在o b j e c t r a n k 系统中，检索结果被定义为单 个元组，这个元组与查询相关但是不必包含查询关键词；而在d b x p l o r e r ，b a n k s ， i r s t y l e 等大多数系统中，每个检索结果必须包含查询关键词，通常，结果是来自 多个关系的元组的连接( 元组结果树) 。 黪! 赫赢茹鬻 荔移彩j 豁磁谬锄l爹黟酶锎貔髻灞 骖爹一荟黼j 鬻缓骖鬻黼菇灞 o ，。g p kd e n a r t m e n t l d 一卜一 p k s t u d e n t l dp k , f k 2b o o k i dp kb o n k l d p k p u b l i s h e r l d 一 p k , f k l s t u d e n t m f k ld e p a r t m e n t l df k lp u b l i s h e d d 图2 1 图书馆借阅记录模式 6 第二章关系数据库关键字搜索概述 b o i t o w i n f o s t u d e n t 5 1 ：u d e n t l d n a m e i d e p a r t m e n t i d，| l c o l l lm a r kc h a r l e s ：d 0 1 l c 0 2 1 3b i l lc h a r l e sd 0 2 l ；0 3 1 2 b i l lv i n c e n td 0 3 b 0 6 112 c o l l e a g ee n g l i s h “。 。一。一 l 璺璺嗍蔓! 曼鲤然掣堕塑 d e p a r t m e n t p u b l i s h e r 图2 2 图书馆借阅记录实例图 图2 1 显示了一个图书馆借阅记录逻辑图，图2 2 给出了该数据库的具体实例。 对于表b o r r o w l n f o 将每次的借阅信息作为一个元组进行记录，内部由借阅的学生 s t u d c n t i d 和该学生所借阅的图书b 0 0 k l d 对借阅进行唯一的标识。若需要查询与 关键字b i l lv i n c e n t 是否借阅p a t t e r n 相关书籍，采用全文索引的查询方式如下： s e l e c t b o o k s 幸， s t u d e n t f r o m b o o k , b o r r o w i n f o b ， s t u d e n tsw h i 淝 m a t c h ( b o o k s b o o k n a m e ) a g a i n s t ( p a t t e m ) a n dm a t c h ( s n a m e ) a g a i n s t ( b i l lv i n c e n t ) a n ds s m d e n t i d = b s t u d e n t i da n db b o o k i d = b o o k b o o k i d ； 若属性上并未建立全文索引，则需要使用l i k e 语句进行查询。 s e l e c tb o o k s ，s t u d e n t 事f r o mb o o k , b o 盯o w i n f ob ，s t u d e n tsw h e r eb o o k s b o o k n a m el i k e p a t t e r na n ds n a m el i k e o o b i l lv i n c e n t a n ds s t u d e n t i d = b s t u d e n t l da n db b o o k i d = b o o k b o o k i d ； 在s q l 语句中，需要指明b i l lv i n c e n tp a t t e r n 所在关系和属性。对于关系数据 7 电子科技大学硕士学位论文 库的关键字搜索，则仅需要用户输入检索关键字则返回与上述两条语句相同的结 果。在本文中，将采用此图2 1 所示结构图和图2 2 所示实例图进行讨论。 2 3 相关数据库关键字搜索系统分析 数据库开始广泛应用时，数据库的设计者便努力使用户从繁琐的s q l 查询语 言中解放出来。早期数据库关键字查询系统根据用户输入的关键字和查找属性， 由系统为用户生成复杂的查询语句。或者由系统设计者提供查找属性，用户只需 输入查找关键字。这种方式将用户不需要了解复杂的s q l 语法，但仍需要用户或 系统设计者了解系统的整体结构，并指明需要查询的具体位置。例如，当检索网 上书店、数字图书馆等专业网站上的信息时，需要通过该网站提供的查询表单分 别输入作者名、题名等信息，检索不同的网上书店或者数字图书馆时，需要使用 不同的查询界面。同时对数据库进行发布时，也需要设计和开发特定的查询表单， 这些开发和维护工作非常繁琐。 j d u l l m a n 在【l3 j 中提出u n i v e r s a lr e l a t i o n a l ( u r ) 概念，提出将一个数据库中多 个关系视为一个关系，若属性具有相同属性名则认为是同一对象( 主外键约束此 时还未提出) 。用户在进行查询时仅需要指明查询关键字所在数据库，而无需指明 其所在关系和属性。系统在执行时通过属性名对关系与关系之间形成约束，这一 思想对后来的数据库关键字搜索产生了极大影响。 随着数据库日益成为数据的存储方式，用户对数据库的使用灵活性提出了新 的要求。数据库关键字搜索将整个数据库视为文本，将数据库内容输出为w e b 页， 然后对其建立倒排索引，实现检索功能。这种方式虽然实现了内容索引，但增加 了数据的冗余度，失去了数据库结构化特点和数据之间的关联特征。在这种情况 下i b md b 2 ，m i c r o s o f ts q ls e r v e r ， o r a c l e ，p o s t g r e s q l ，和m y s q l 均提供 了与数据库引擎紧密关联的文本搜索引擎扩充功能。但是，在所有上述系统中文 本索引只针对单列进行建立。使用这一单独特性实现一个内部相关数据库数据的 关键词搜索要求对多个数据列文本索引结果进行整合。 d b x p l o r e r ，b a n k s ，d i s c o v e r 和o b j e c t r a n k 采用了同一种策略：将数据 库看作是由数据库中的元组( 定点) 通过主键- 夕f 键关系( 边) 连接而成的图，当 用户给出一个关键词查询时，首先找到包含至少其中任一关键词的所有元组，然 后利用关系数据库中表间的主外键链接作为边，把含有关键词的各个元组连接起 来，形成一棵含有所有关键词的元组组成的结果树。结果的排序主要根据子树结 8 第二章关系数据库关键字搜索概述 点的多少、节点权重和节点之间联系程度。 2 4 2d b x p l o r e r d b x p l o r 一2 1 ，由微软公司研发。为在线系统，基于结构图实现，结构图为无 向图，采用o d b c 接口与数据库进行交互。d b x p l o r e r 首先找到包含至少一个关 键字的表集合，根据结构图和关键字所在位置产生一组子图。每个子图均表示了 一组关系的连接，对于这组关系则包含了所有关键字。系统提供拓展到属性匹配 和提供更加复杂的搜索方法。系统采用p u b l i s h - s e a r c h 方式进行数据处理和实现关 键字搜索。p u b l i s h 包括：选择要发布的数据库，并将数据库中的表和列进行发布。 建立支持关键字搜索的表，其中最重要是索引表结构的设计，从而在查询期间能 够有效的决定查询关键字在数据库中的位置( 例如关键字出现的表，列，行) 。s e a r c h 对于给定的包含一组关键字的查询请求，系统的处理过程包括：对索引表进行查 询，以确定关键字的出现位置，位置信息为数据库名一表名一列名索引，根据系 统结构图得到所有可能符合搜索要求，包含所有查询关键字的连接树( j o i nt r e e ) 返回结果允许包含多个节点，对于多节点查询，通过s q l 语句将其连接成一个搜 索结果进行返回。d b x p l o r e r 不要求系统提供全文索引功能，并提供p r e - f i x 索引 结构以支持早期数据库。 d b x p l o r e r 仅根据子树中节点的多少对搜索结果进行排序，提供a p i 接口和网 页浏览两种方式显示搜索结果。 2 4 3b a n k s b a n k s t 3 1 ，由伯克力加利福尼亚大学和i b m 合作开发。为基于数据图实现的 系统，按照数据库中的关系模型进行数据的查询处理。将数据库中的元组作为有 向图中的节点，关系模型中元组之间的链接关系通过有向图的边进行表示。在数 据库中的信息检索过程变成从有向图中找出一棵子树的过程，对于搜索请求中的 任一关键字均可在至少一个节点上找到。b a n k s 生成的子树为有向加权图，节点 和边分别进行赋值，搜索结果按照节点之间的相关性和边的权重进行计算。节点 的权重根据节点的入度进行确定，边的权重根据正向遍历和逆向遍历有所不同。 包含关键字的最小子图利用d i j k s t r a 算法进行查找。b a n k s 解决查询速度慢的方 法是将整个数据图抽象信息存放在内存中，详细信息存储在硬盘上，在查询时仅 对需要的节点进行磁盘访问。b a n k s 不要求系统提供全文索引功能。 9 电子科技大学硕士学位论文 b a n k s 为用户提供网页接口和超链接。用户可直接对结构和数据进行浏览， 对每一个显示的结果，均自动添加链接可浏览详细信息，通过交叉表和聚合对数 据进行浏览，用户也可选择结果的显示形式。 2 4 4d i s c o v e r i r - s t y l e d i s c o v e r t 4 为在线、基于结构图实现的系统。利用o r a c l e 提供的全文索 引实现关键字搜索。返回元组连接网络，即由主- 夕f 键关系连接、包含所有关键字 的元组集。首先，候选网络生成器产生所有的候选网络，即可生成元组连接网络 的连接表达式最小关系网，然后计划生成器建立计划，有效评估候选网络集，发 现可重用的子表达式。生成无冗余的所有相关网络，其大小是数据绑定的( d a t a b o u n d ) ，或由数据库模式的结构确定。最优运行计划的选择为n p 完全问题。然后 生成s q l 语句对多个元组进行整合以包含所有的关键字。性能评估主要包括两个 方面：对关系网中不相关内容的删减和选择有效的算法产生中间结果，多个关系 网共享中间结果。在进行一个关键字查询时，搜索时间随着关键字个数和需要连 接的关系网个数而增加。 d i s c o v e r 要求数据库系统提供全文索引功能。当用户提交一个关键词查询 时，d i s c o v e r 首先用o r a c l e 的全文索引为每一个关系生成含不同关键词组合的 元组集合，然后根据数据库结构图生成数据图，再从中找出包括全部关键词的子 图( 树) ，将子图转换为s q l 查询，最后查询数据库得到查询结果。i r s t y l e i s 对 d i s c o v e r 进行了改进，提出了几种算法提高以提高查询效率。d i s c o v e r 根据 子树中节点的多少进行排序，m s t y l e 则利用信息检索的文本相关排序策略对查询 结果进行排序，将t o p k 查询结果返回给用户。 2 4 5o b j e c t r a n k o b e c t r a i l k 【7 】与上述三种系统不同，o b j e c t r a n k 的搜索结果必须包含在数据图 中的同一节点，o b j e c t r a n k 最显著特点为采用p a g e r a n k 算法为基础对搜索结果进 行排序。 p a g e r a n k 排序算法已经成功的被g o o g l e 应用于网页搜索中。对w e b 页面的排 序，是根据搜索的词组( 短语) 在页面中的出现次数，并用页面长度和h t m l 标签 的重要性提示等进行权重修订。链接名气( 1 i n kp o p u l a r i t y ) 技术通过其它文档链接到 当前页面( i n b o u n dl i n k s ) 的链接数量来决定当前页的重要性。p a g e r a n k 计算页面 1 0 第二章关系数据库关键字搜索概述 的重要性，对每个链, k ( i n b o u n d ) 赋以不同的权值，链接提供页面的越重要则此链 接入越高。当前页的重要性，是由其它页面的重要性决定的。p a g e r a n k 的算法为 b s ： p r ( a ) = ( 1 - d ) + d ( p r ( t 1 ) c ( t 1 ) + + p r ( t n ) c ( t n ) ) 其中：p r ( a ) 为页面a 的网页级别，p r ( t i ) 为页面t i 的网页级别，其中页面 t i 链向页面a ，c ( t i ) 为页面t i 链出的链接数量，d 为阻尼系数，取值在o 一1 之间。 在o b j e c t r a n k 中，节点权重由预处理模块提前进行计算并存储在索引文件中。 o b j e e t r a n k 支持o r 逻辑运算和t o p - k 查询。对于a n d 查询，o b j e c t r a n k 的排序 算法为 ，r 舳, w 2 ( y ) = 丌厂m ( v ) i = 1 ，m 其中，1 ，为数据图中的节点，w i 为查询关键字，叶( v ) 为节点v 与键字w i 的相 关性。 2 4 6 小结 根据搜索策略和返回策略的不同，可将数据库关键字搜索系统简要进行分类， 如表2 1 所示。 表2 1 数据库关键字搜索分类图 关键字搜索系统基于结构图数据图基于全文索引索引表多节点返回 d b x p l o r e r 结构图索引表y b a n k s数据图索引表y d i s c o v e r i r - s t y l e结构图 全文索引y o b j e c t r a n k 数据图索引表n 数据库关键词检索技术是在传统的数据库管理系统中实现信息检索技术的有 关功能，属于数据库和信息检索的交叉研究领域。这几个系统都致力于提出更优 化的方法来提高从数据库中查找到包含关键词的元组和形成结果树的效率，同时 提供更加广泛的连接条件对元组之间的关系进行约束。国内外研究热点主要集中 在检索语言、数据模型、性能优化、结果排序、结果展现、系统体系结构等方面。 电子科技大学硕士学位论文 2 4 功能概述 所有的数据库关键字检索系统均将模块分为两个部分：预处理模块和查询模 块。 在用户执行查询请求之前，预处理模块将数据库内容进行预处理。在查询模 块中所需要的所有数据均在预处理模块获得，从而加快查询速度。在预处理阶段 生成的数据存储在主存或磁盘中。例如：b a n k s 将数据图存储在主存中， d b x p l o r e r 将索引表存储在磁盘中。预处理模块需要根据查询模式进行设计，例如： 在d i s c o v e r 中，预处理模块采用o r a c l e 系统提供的全文索引，自身不再对 索引进行维护。o b j e c t r a n k 在预处理模块中完成了大部分计算。 查询模块负责查询请求的执行。与传统信息检索相似，查询模块首先需要对 用户的搜索请求进行语义分析。然后查询模块根据查询策略生成查询结果。各搜 索系统采用了不同的查询策略，例如，o b j e c t r a n k 在查询阶段仅计算数据图中各 节点与查询关键字之间的相似度，将节点按照相似度进行返回。d i s c o v e r 在查 询阶段需要生成数据图，枚举所有候选网络，最后进行t o p k 查询。系统实现是否 基于数据图或结构图决定了查询策略，o b j e c t r a n k 和d i s c o v e r 体现了两种不同 的查询策略。 2 4 1 结果排序 t o p - k 查询在数据库关键字查询之前就成为数据库领域的研究课题之一。t o p k 查询只返回最符合用户查询要求的前k 个查询结果，它可以表示为下面的s q l 语 句形式： s e l e c t 掌f r o mro r d e rb y f ( s l ，舵，跏) s t o pa f t e r k 其中尺是一个有万个属性的关系，研是由r 上一个或多个属性计算出的分 数，f 是一个单调函数，用于计算元组的得分。处理t o p k 查询最著名的算法是阀 值算法，它的主要过程是：1 对r n 个分数列j i ，6 2 ，s 埘排序；2 从各分数列取第 一个元素，计算出一个阀值和最多m 个新元组的分数；3 若此时已有k 个元组的 分数高于该阀值则算法结束，否则返回第2 步继续。b a s t 等人进一步研究了阀值 算法的调度问题，以确定在第2 步中应该以什么次序从各分数列读取元素。c a r e y 和k o s s m a l l n 【1 6 】最早研究了关系数据库上的t o p k 查询，他们提出了s t o pa f t e r k 子句。 查询结果的排序取决于节点和边的计分方法。o r a c l e ，m y s q l 在提供全文搜索 1 2 第二章关系数据库关键字搜索概述 功能时，同时也采用了，关键字查询系统的排序主要分为两类，一是根据返回结 果集中的节点个数进行判定，节点越少，认为相似度越高。