（计算机应用技术专业论文）基于语义的数据库关键字检索优化技术研究.pdf

r e s e a r c ho no p t i m i z i n gs e m a n t i c - b a s e d k e y w o r d s e a r c ho v e rd a t a b a s e s at h e s i ss u b m i t t e dt o s o u t h e a s tu n i v e r s i t y f o rt h ea c a d e m i c d e g r e eo fm a s t e ro fs c i e n c e b y l i us e n s u p e r v i s e db y p r o f e s s o rj i n y u a n p i n g s c h o o lo fc o m p u t e rs c i e n c e e n g i n e e r i n g s o u t h e a s tu n i v e r s i t y , n a n j i n g ，p r c h i n a 2 0 1 0 0 6 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名： 堑! 1 2 惑 导师签名：研究生签名： 堡! _ | 壬 导师签名：e l 期：2d h 6 ， 摘要 摘要 数据库系统和信息检索系统在处理数据的方法上有很大的差别，数据库系统 通过复杂的查询语言搜索结构化数据，其结果集完整精确；信息检索系统通过关 键字搜索非结构化数据，其结果集通常是不精确和不完整的。传统的关系数据库 查询采用s q l 语言，而由于其结构复杂、难以学习，不能适应大众用户；而且， 人们很难从含有大量文本数据的数据库中得到准确的结果。于是，用关键字搜索 关系数据库逐渐成为研究热点。 在信息检索中，搜索引擎所检索到的信息仅局限于爬虫程序所能找到的浅层 网页( s u r f a c ew e b ) ，而对于大量存储在网络数据库中的深度网络( d e e pw e b ) ， 由于搜索引擎同数据库间接口的不一致而无能为力。如果数据库本身提供关键字 检索机制，允许使用简单的关键词自由的检索数据库，挖掘其中的信息和知识， 信息资源的利用效率将得到很大提高。 本文提出了一种基于无向图的数据库关键词检索方法s b k s 。首先，以元组 为节点，元组间的主外键联系作为边构造元组数据图，然后依据此图的结构计算 任意元组间的语义联系，以此为边构造数据库的语义关系图，作为系统的检索模 型。处理查询时，使用聚类的方法查找出相互语义联系紧密的关键节点集作为查 询结果，并参照d i s c o v e r 2 和s p a r k 的评分方法提出一种适合本文查询结果 的评分标准。最后经过实验证明s b k s 的正确性，并且在合理的选取阀值参数的 情况下，s b k s 将取得良好的性能效果。 关键词：关键字检索；关系数据库；语义；聚类；无向图 a b s t r a c t 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 so ns e a r c h i n gd a t a ， m e t h o d st os o l v et h ep r o b l e ma l 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 hs t r u c t u r e d d 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 r es o u n da n dc o m p l e t e ，a n da l lr e s u l t s a 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 ab 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 r em o r er e l e v a n t t h a no t h e r s t r a d i t i o n a l l y , s o ll a n g u a g ei su s e dt oq u e r yr e l a t i o n a ld a t a b a s e s h o w e v e r , i ti si n a p p r o p r i a t ef o re n d u s e r s ，s i n c ei ti sc o m p l e xa n dh a r dt ol e a r n w h a t sm o r e ，i t sd i f f i c u l tt og e te x a c t l yr e s u l t sf o r mt h ed a t a b a s et h a tc o n t a i n sal a r g e a m o u n to ft e x td a t a a sar e s u l t ，t h es t u d yo nk e y w o r ds e a r c ho fr e l a t i o n a ld a t a b a s e d r a w sm o r ea n dm o r ea t t e n t i o n o nt h ev i e wo fi n f o r m a t i o nr e t r i e v a l ，t h ei n f o r m a t i o nt h a ts e a r c he n g i n e sc a ng e t i sl i m i t e db ys p i d e rs o f t w a r e ，w h i c hc a no n l yr e a c ht oap a r to fs u r f a c ew e b b u tm o r e a n dm o r ei n f o r m a t i o np r e s e n t e di nd e e pw e ba r es t o r ei nn e t w o r kd a t a b a s e s ，w h i c ha r e b e y o n ds p i d e rs o f t w a r e sr e a c h t h eh i d d e nw e bp r o b l e mi sc a u s e db yt h em i s m a t c h o fs e a r c hi n t e r f a c e sb e t w e e ns e a r c he n g i n e sa n dd a t a b a s e s i fd a t a b a s es y s t e m s s u p p o r tk e y w o r ds e a r c h ，p u b l i s h i n ga n ds e a r c h i n gad a t a b a s ei se x p e c t e dt ob em o r e s i m p l ea n de a s y t h i sp a p e rp r o p o s e sa nu n d i r e c t e dg r a p hb a s e dk e y w o r ds e a r c hm e t h o do v e r r e l a t i o n a ld a t a b a s ec a l l e ds b k s i nt h i sm e t h o d ，t u p l e sa r et a k e na sn o d e st oc o n s t r u c t t h es e m a n t i cr e l a t i o n s h i p g r a p hf o rt h ew h o l ed a t a b a s ea n df o ra n yq u e r y , t h e c o r r e s p o n d i n gs e to fq u e r yr e s u l tt r e e si nw h i c hk e y w o r d sa r ea sn o d e si sc o n s t r u c t e d u s i n gc l u s t e ra p p r o a c h ar a n k i n gc r i t e r i o n t h a tc a nr e v e a ls e m a n t i cr e l a t i o n s h i p b e t w e e nk e y w o r d sa n dm a k et h ei m p l e m e n t a t i o no fk e y w o r d ss e a r c ho v e rd a t a b a s e s m o r ee f f e c t i v ei sg i v e na sw e l lb yi m p r o v i n gt h a to fd i s c o v e r 2a n ds p a r k a t l a s t ，e x p e r i m e n t a lr e s u l t ss h o wt h ec o r r e c t n e s so fs b k s ，a n dt h a tg i v e nr e a s o n a b l e t h r e s h o l d ，s b k sw i l la c h i e v eg o o dp e r f o r m a n c er e s u l t s k e y w o r d s ：k e y w o r ds e a r c h ；r e l a t i o n a ld a t a b a s e s ；s e m a n t i c s ；c l u s t e r ；u n d i r e c t e d g r a p h ； 日录 目录 第一章引言1 1 1研究背景1 1 1 1 数据库查询技术与文本数据库。1 1 1 2 信息检索技术与文本数据库2 1 2研究意义和研究目标。3 1 3本文工作。4 1 4本文的主要内容和组织结构5 - 第二章关系数据库关键字检索概述6 2 1 关键字检索：6 2 2 关系数据库上的关键字检索。6 2 3 数据库上的关键字检索研究现状。7 2 3 1 d b x p l o r e r 8 2 3 2d i s c o v e r 9 2 3 3b a n k s 1 0 2 3 4 o b j e c t r a n k 1 0 2 4 相关研究分类总结1 0 2 4 1 检索基本模型1 1 2 4 2 结果排序1 1 2 4 3执行效率1 2 2 4 4 结果返同1 2 2 5 数据库关键字检索小结1 2 第三章检索模型的改进和语义计分方法。1 4 3 1 基本概念1 4 3 2对语义的解释1 5 3 3 建立模型的假设和改进1 5 3 4 语义计分公式1 7 3 4 1 关系模式图边的语义计分1 7 3 4 2 元组数据图直接相邻节点间距离的语义计分1 9 3 4 3 元组数据图间接相邻节点间距离的语义计分1 9 3 4 4 元组数据图中不相邻节点间距离的语义计分2 0 3 4 5 元组数据图关键节点的语义计分2 1 3 5 生成查询结果树的聚类方法2 1 3 5 1聚类的目标2 1 3 5 2生成聚类的基本方法2 2 3 6 查询结果树的评分排序方法2 2 3 6 1 现有关键字检索排序方法简介2 2 3 6 2 s b k s 系统的查询结果评分方法2 4 3 7本章小结2 5 第四章s b k s 系统检索模型的设计与实现2 6 4 1设计目标2 6 4 2 总体模块设计2 6 4 3 构建检索模型：。2 7 i i i 日录 4 3 1模块功能2 7 4 3 2生成关系模式图2 7 4 3 3生成元组数据图2 8 4 3 4 计算关系模式图边的语义计分3 1 4 3 5 计算元组数据图节点间距离的语义计分3 1 4 3 6 关键词倒排索引表的构建。3 7 4 4 1关系模式图节点的删除3 7 4 4 2 语义关系图节点的删除3 8 4 4 3倒排索引表关键词的删减4 0 4 5 本章小结4 0 第五章s b k s 系统的检索过程与评分标准4 1 5 1 检索过程4 1 5 1 1查询预处理4 1 5 1 2关键节点聚类4 1 5 1 3 聚类的数据结构和合并簇算法4 2 5 2 评分排序4 3 5 2 1 s b k s 的评分排序方法4 4 5 3 本章小结4 5 第人章实验测试与性能分析4 6 6 1测试环境4 6 6 2关键字个数对性能的影响4 6 6 3 查询结果树规模限制对性能的影响4 7 6 4 查询结果树边长度阀值限制对性能的影响4 7 6 5 本章小结4 8 第七章总结4 9 参考文献51 致谓 5 4 i v 第章0 i 苦 第一章引言 本章对整篇论文的研究背景进行了简要的介绍。首先论述了传统的数据库查 询技术和信息检索技术在文本数据库中的不适应，在此基础上引出了本文着重研 究的问题：关系数据库上的关键字搜索。此外，还给出了本文的具体研究内容及 全文组织结构。 1 1 研究背景 1 1 1 数据库查询技术与文本数据库 传统的数据库查询，需要用户理解数据库的结构和模式，并使用精确的s o l 语言，这对于非专业人员过于复杂，限制了数据库技术的广泛应用。另一方面， 现代数据库存储更多的是含有语义信息的文本数据，精确的查询语言不能很好的 描述文本字段的特征，因此，传统的s q l 语言难以适应现代文本数据库。 表1 1 表示一个简单的文献信息数据库，由四张表组成。作者表存储作者信 息，撰写表是撰写关系，论文表存储文献信息，引用表存储引用关系。其中，作 者简介，文献题名，甚至文献内容及其他注释字段都是自然语言；数据库中表间 的语义联系很明显：作者撰写论文，论文引用其他论文。对于此表，用传统的 s q l 查询有以下困难： 首先，查询难以给出精确的查询条件。包含自然语言的数据库系统，非结构 化的数据字段很难实现全字匹配。以表1 1 为例，从理论上说，若要根据题名查 询一篇文献( 比如说，t 5 的厉膨物统兹锸盼斩的路径序刃搓街黝，在输入查询条 件时，如果误输一个同义词，一个字，甚至是一个空格，都将无法实现全文匹配， 无法得到正确的查询结果。 其次，查询不需要精确的查询结果，但是需要区分查询结果的重要程度。传 统的数据库查询，由于查询条件精确，查询结果集也必然是精确的，但是无法给 出区分排序。如果查询结果集很大，这会给用户查找信息带来困难。而以自然语 言为数据源的数据库系统，由于自然语言的模糊性，甚至用户自己可能也无法精 确描述所要检索的信息，但是他们也不会在乎查询结果是不是完全的符合查询条 件的限制。事实上，他们只会在乎是不是返回了他们感兴趣的结果。这样，像搜 索引擎一样返回给用户一些与查询条件相近的经过区分排序的查询结果就变得 可以接受。 再次，对于传统的数据库查询方法，需要查询者理解数据模式，s q l 语言等 比较专业的知识，而且如果d b m s 较复杂时，理解和处理那些数据表和它们间 的关系将变得较为繁琐，即使具有专业的知识也很难在短时间内掌握。这就提高 了数据库查询使用者的门槛，限制了数据库技术的广泛使用。 东南人学硕一l ：学位论义 1 1 2 信息检索技术与文本数据库 信息检索技术的成熟，使得互联网上的各种商业搜索引擎( j t i l g o o g l e 、y a h o o 、 百度) 取得了空前的成功。用户只需简单的提交关键词，搜索引擎根据相关度对 搜索结果进行排序返回，这种关键字检索技术使用方便，对用户友好，因而成为 人们在网上搜集信息的主要方式。 但是，搜索引擎所能搜索的网页仅仅是互联网上的浅层网页( s u r f a c ew e b ) ， 对于大量由后台网络数据库动态产生的深层网页( d e e pw e b ) ，由于技术上的原 因而无法索引。b r i g h tp l a n e t 的d e e pw e b 白皮书瞳1 指出，互联网上d e e pw e b 的 信息是传统s u r f a c ew e b 信息的4 0 0 至i j 5 0 0 倍d e e pw e b 的数据总量可以达到 7 5 0 0 t b ，而传统的s u r f a c ew e b 的信息仅仅只有1 9 t b 。这些d e e pw e b 的数据主要 存储在后台的关系数据库中。随着越来越多的数据被存储在数据库中，如何在数 据库中便利、有效的检索信息逐渐成为数据库领域的一个研究热点。 由于传统数据库查询语言( s q l ) 的局限性，在数据库上运用关键字检索就成 为这一领域的主流研究方向。使用关键字检索，用户不需理解数据库的数据模式 和组织结构，不需学习复杂的查询语言( s q l ) ，仅仅是使用关键词来描述需求， 用信息检索的方式来找到所有与查询关键字相关的信息项，并按照一定的标准将 相关信息项排序，将排序结果返回给用户，这就是关系数据库关键字检索 ( 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 s ，简称k s o r d ) 。 但是，这种类似信息检索形式的关键字检索却无法直接使用信息检索的方法 来完成。因为数据库是将客观世界的信息抽象为简要的结构化的数据类型来存储 的结构，是对客观存在实体信息简要而完整的描述，因此从逻辑上来讲数据库 中的数据是用来描述一个完整的实体信息的。数据库的结构化特征使得基于文本 的检索方式并不能直接应用于数据库检索。例如：数据库设计人员为了便于对数 据进行有效的管理或者出于减少数据冗余和存储空间的目的，很大程度上会将一 些有意义的数据分割存储在多个数据表中，而数据表之间则通过主外键约束联 系。数据库关键字检索需要发现多个数据表之间的关系，将分布在多个数据表中 有意义的数据拼接作为查询结果心。在表1 1 中，如果仅仅是使用信息检索的方 法，就无法发现并返回完整的“作者 “撰写 “论文 的查询结果。 2 第一章一j i 高 t 8 t 9 h o t l l 表1 1 文献信息表 工号姓名简介 文献号 题名摘要 a i d l 刘彻 关联规则数据挖掘方法的研究和应用 s i d l面向分类信息网站的数据挖掘算法 t 4s i d 2 a i d 2 王猛 t 5s i d 3 面向物流数据分析的路径序列挖掘算泫 s c h e m a jf 作者论文 ，i 工号文献 文献号 ll 撰写 引用 l x 7 工号文献 引用 引用文献号被引用文献号 a i d ls i d l t 6 d d ls i d ls i d 2 a i d ls i d 2 t 7 c i d 2 s i d 3s i d 2 a i d 2s i d 2 a i d 2s i d 3 1 2 研究意义和研究目标 通常，数据库技术处理结构化的数据，采用结构化的查询语言，使用精确的 查询条件，得到精确的查询结果。而信息检索技术则处理非结构化的数据，采用 关键词搜索的查询方式，输入几个笼统的关键字，获得不精确不完全而且要根据 相关性排序的查询结果，允许有准确率和查全率的存在。但是，有很多的应用既 要管理结构化数据又要管理非结构化数据( 如表1 1 ) 。为了满足这些应用的需 求，就要集成数据库和信息检索技术( 见表1 2 ) 。 表1 2 数据库和信息检索系统幢1 关键字检索 结构化查询 语言 数据库上 的关键词信息检索 检索 数据库检 索( s o l ) 结构化数据非结构化数据 3 东南人学坝i j 学位论义 数据库上的关键字检索( k s o r d ) 是信息检索技术同数据库查询技术结合的 产物，但是又与二者相互区别。 首先，研究对象不同。数据库查询技术的研究对象主要是可以用结构化的格 式统一描述的数据。如数字，枚举值，日期时间等。信息检索技术研究对象主要 是互联网上可被抓取到的网页。这些网页数据是形同自然语言的完全非结构化的 数据。而数据库上的关键字检索的研究对象是以结构化的形式存在数据库系统中 的非结构化数据。例如表1 1 ，数据库的主要字段是同自然语言贴近的文本数据， 如作者的简介，文献的题名，摘要等。 其次，研究模型不同。数据库查询的基本模型是将所有与查询相关的表做笛 卡尔乘积，再从中选择符合查询条件的元组集并投影到查询字段作为返回结果， 并在此模型基础上做查询的分解与优化，从而提高查询效率。信息检索技术的基 本模型主要是向量模型，将爬虫程序抓取到的网页按照与查询关键词的相关度大 小评分，并在此基础上加入其他因素( 如g o o g l e 的p a g e r a n k ) ，作为查询结果的 排序依据。而数据库上的关键词检索则是将关系表或元组作为节点，将关系表间 的主外键联系作为边，从而将数据库转化为一个图，进而在图上检索出一个或多 个与关键词相关度最高的子图，作为查询结果。 再次，返回结果不同。数据库查询返回的是符合查询条件的查询字段所构成 的一张新的关系表，信息检索返回的是根据关键词相关度排序的网页列表，而关 键字检索所返回的是按照与查询结果相关度排序的查询结果树集。 最后，也是其中最重要的一点不同，是关键字检索能表达出结构上的语义信 息。对于传统的数据库查询，虽然也能检索出结构上的语义联系，但是查询条件 太过严格。若使用传统的信息检索技术，则无法检索出结构化的联系所能带来的 语义信息。例如，在表1 1 中，若要检索工掰鬏诌蝴能得到所有包含这两 个关键词的元组，t 。，t 。，t 。，而无法得到- t 。一t 。这种经过连接后得到的含有明显 语义信息的结果。关键字检索必须做到这一点，否则与信息检索无异。 1 3 本文工作 本文通过与传统的数据库查询技术和信息检索技术比较，论述了数据库信息 检索技术及其研究现状，在分析已有主流关键字检索技术的基本原理、查询过程 和优缺点的基础上，提出一种基于语义的关键字检索方法( s e m a n t i c b a s e d k e y w o r ds e a r c h ，简称s b k s ) 。将关系数据库中关系表的元组作为节点，将元 组间的主外键联系作为边就构成了数据图。s b k s 系统基于数据图实现，首先根 据数据图的结构和各元组节点的连接关系确立数据图中各个边的权值，接着根据 语义的传递性和叠加性确立元组节点两两间的权值，并以此作为聚类分析的基 础。在检索过程中将包含关键词的元组节点聚类，聚类得到的簇即作为查询结果 树参与评分排序。最后按照评分公式将得分高的查询结果树返回给用户即为查询 4 第一章引吉 结果。 1 4 本文的主要内容和组织结构 本文共分七章，安排如下： 第一章，介绍了数据库上的关键字检索的研究背景和研究目标，区分其与 信息检索和数据库查询概念上的区别，指出了本文的主要工作，文章的内容和组 织结构。 第二章，详细论述了数据库上的关键字检索的概念和使用范围，重点论述 了现存的几种关键字检索系统实现的基本方法，并横向比较各种系统的优缺点。 第三章，定义了本文所使用的基本概念，提出了设计的思想假设，在此基础 上给出了s b k s 模型实现的基本原理和算法思想。 第四章，整体概括s b k s 模型的各功能模块和各模块的作用，重点实现了构 建检索模型模块，包括模型的构建，修改及维护。 第五章，实现了检索过程与评分标准模块，提出了检索过程聚类算法的实现 方式和对查询结果的评分公式。 第六章，给出了s b k s 模型原型系统测试的实验结果和各模块的性能分析， 重点分析不同参数的设置对性能的影响。 第七章，对研究成果进行总结，重点给出了模型设计中的几个创新点和现存 的待改进之处。 5 东南人学坝j ：学位论义 第二章关系数据库关键字检索概述 2 1 关键字检索 关键字搜索是现今最为流行的信息发现方法，因为用户不需要学习任何复杂 的查询语言，也不需要了解底层数据的结构，他只需要使用若干关键字来表达自 己的信息需求。著名的w e b 搜索引擎g o o g l e 提供的是针对万维网上h t m l 文档集 的关键字搜索功能，用户只需在简洁的界面上输入若干关键字，g o o g l e 就能够 返回所有包含全部关键字的h t m l 文档。这种关键字搜索服务大大方便了普通用 户在浩瀚如海的万维网上查找感兴趣的信息。 现代信息系统需要管理复杂的数据，包含结构化的关系数据、半结构化的x m l 数据和非结构化的w e b 文本数据等。然而，当需要对这些复杂数据进行查询时， 目前使用的却是各不相同的查询语言。例如，对于关系数据只能通过s q l 语言查 询，对于x m l 数据只能通过x q u e r y 语言查询，而对于网页数据则通常是通过关 键字检索查询。对于现代信息系统来说，如何为用户提供一种一致的查询语言以 方便管理这些复杂数据成为一个重要的挑战。就目前的研究现状而言，关键字搜 索有望能够成为这样一种一致的查询语言。在过去的十几年中人们已经对非结构 化的文本数据上的关键字搜索进行了深入的研究，因而如何针对结构化的关系数 据库中的数据进行关键字搜索已经成为数据库和信息检索领域一个重要的研究 方向。 2 2 关系数据库上的关键字检索 数据库搜索技术由于其巨大的应用潜力，近年来已经受到国内外众多学者和 研究团体的关注，从2 0 0 3 年开始，整合数据库与信息检索技术成为数据库研究 领域面临的主要挑战之一。当前的主流研究方向是关系数据库关键字检索 ( 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 s ，简称k s o r d ) ，其核心思想是使 普通用户能够使用关键词来检索关系数据库，而不需要了解数据库模式和s q l 语 l 口。 数据库关键词查询系统可以分为在线查询和离线查询两大类。在线系统将关 键词查询转换为s q l 语句查询，通过d b m s 执行传统的s q l 语句查询数据库来生 成查询结果。离线系统要预先对数据库内容建立索引和元组图，当用户提交关键 词查询时，根据索引检索元组图来生成查询结果。不同的查询系统采用不同的建 模方法。数据库可以表示为结构图或数据图进行建模。结构图的结点对应数据库 中的关系表，边表示模式定义的主外键约束；数据图中的结点对应关系中的元组， 边表示元组之间的主外键关系。结构图和数据图通常为有向图，采用有向图可以 明确表示节点问的关系( 引用与被引用，或者包含与被包含) ，进而赋予相应的权 6 第_ 二章关系数据库关键：检索概述 重。 在线系统将数据库表示为结构图，通过s o l 查询得到数据库“最近的一致性 状态”下的查询结果。由于转换而成的s o l 查询中有大量的连接操作，所以在线 系统提高查询速度的关键在于减少对数据库( 磁盘) 的访问次数。离线查询系统 由于对索引进行直接查询，减少了大量s o 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 等大多数系统中，每 个检索结果必须包含查询关键词，查询结果是来自多个关系的元组的连接( 查询 结果树) 。 2 3 数据库上的关键字检索研究现状 早期数据库关键字查询系统根据用户输入的关键字和查找属性，由系统为用 户生成复杂的查询语句。或者由系统设计者提供查找属性，用户只需输入查询关 键字。这种方式使用户不需要了解复杂的s q l 语法，但仍需要用户和系统设计者 了解系统的整体结构，并指明需要查询的具体位置。例如，当查询网上书店、数 字图书馆等专业网站上的信息时，需要通过该网站提供的查询表单分别输入作者 名、题名等信息，检索不同的网上书店或者数字图书馆时，需要使用不同的查询 界面。同时对数据库进行发布时，也需要设计和开发特定的查询表单，这些开发 和维护工作会非常的繁琐。 数据库全文检索将整个数据库视为文本，将数据库内容输出为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 采用了同一种策略：将数据库 看作是由数据库中的元组( 结点) 通过主键一外键关系( 边) 连接而成的图，当用户 7 东南人学坝一 ：学位论文 给出一个关键词查询时，首先找到包含至少其中任一关键词的所有元组，然后利 用关系数据库中表间的主外键连接关系作为边，把含有关键词的各个元组连接起 来，形成一棵含有所有关键词的元组组成的结果树。结果的排序主要根据子树结 点的多少、节点权重和节点之间联系的紧密程度。 2 3 1 d b x p l o r e r d b x p l o r e r 使用无向的数据库模式图来进行关键字检索。数据库模式图指的 是以关系表为节点，表间的主外键联系为边而建立的表示数据库整体结构的图， 可以为有向或无向图。d b x p l o r e r 将检索结果定义为包含全部关键字的若干元组 构成的连接树( 即查询结果树) 。 d b x p l o r e r 的检索过程如下所述： ( 1 ) 检索符号表以找出数据库中包含查询关键字的关系、字段和元组。符号 表实际上是一个倒排索引，在检索之前对数据库进行预处理的过程中创建。 ( 2 ) 根据数据库模式图检索出所有连接树。连接树是数据库模式图的一个子 树，它满足下面两个条件：对应于叶子节点的关系至少包含一个查询关键字， 每个查询关键字都包含于某个对应于叶子节点的关系中。如果把连接树中所有 的关系都连接起来，那么连接的结果中就可能存在包含全部关键字的元组。 ( 3 ) 对于步骤( 2 ) 中检索出来的每个连接树，生成相应的s q l 语句来连接其中 的各个关系表，并从结果中挑选出那些包含全部关键字的元组。最后，对这些选 出的元组进行相关性排序并返回给用户。 检索连接树的过程包含下面三个步骤： ( 1 ) 从数据库模式图g 中移去那些不包含任何关键字的叶子节点，生成一个 新的模式图g 。 ( 2 ) 通过启发式的方法在g 。中选取出一个叶子节点。 ( 3 ) 从选定的叶子节点开始对g ，进行宽度优先遍历，这将生成出所有的连接 树。 例如，在图2 - 1 ( a ) 中，模式图g 包含5 个关系。假定查询关键字是k 。，k 。 和k 。，关系t 。包含了所有这三个关键字，关系t 4 包含k 。，关系t 。包含k 。，黑色节 点表示至少包含一个关键字的关系。在这个例子中，检索算法从叶子节点t 2 开始 检索出四个连接树，如图2 1 ( b ) 所示。 d b x p l o r e r 用来排序结果的评判函数非常简单，结果的相关性分值就是结果 中连接的数目。因为涉及多个关系的连接一般较难理解，所以d b x p l o r e r 认为连 接树的相关性分值与它的大小成反比。d b x p l o r e r 使用简单的用户界面来表示结 果，它用文本来描述连接树，并在一个关系中呈现连接结果。 8 模式图g 乃 t 5 乃 t 5 t 5 ( a ) ( b ) 图2 - 1d b x p l o r e r 的连接树 2 3 2d i s c o v e r d i s c o v e r 与d b x p l o r e r 有许多相似之处，它也是使用数据库模式图来进行关 键字检索，实际上它是d b x p l o r e r 的一个改进版本。d i s c o v e r 根据元组集合图 来检索候选网络，候选网络就相当于d b x p l o r e r 中的连接树，元组集合图是建立 在模式图基础之上的，元组集合是关系中包含指定查询关键字的元组构成的集 合。d i s c o v e r 的检索算法也是基于宽度优先检索算法，它在检索过程中对每个 中间结果进行检查，如果发现此中间结果之后肯定构不成有效结果，d i s c o v e r 会及时将其剪除。d i s c o v e r 要求数据库系统提供全文索引功能。当用户提交一 个关键词查询时，d i s c o v e r 首先用数据库( o r a c l e ) 自带的全文索引功能为每一 个关系生成含不同关键词组合的元组集合，然后根据数据库结构图生成数据图， 再从中找出包括全部关键词的子图( 树) ，将子图转换为s o l 查询，最后查询数据 库得到查询结果。图2 2 是一个元组集合图的实例，图中的t 。k 。表示关系t 。中包 含关键字k 。的所有元组构成的集合，t 。k ：表示t 。中包含关键字k ：的所有元组构成 的集合。注意在元组集合图中边的方向是由主键指向外键。假定用户提交的查询 关键字是k 。，k 。，那么由图2 - 2 将生成候选网络正蜀o o 瓦硝z 图2 - 2d i s c o v e r 的元组集合图 9 一 一 弋 东南人学顾i ：学位论文 d i s c o v e r 所使用的相关性评判函数是 y $ c o r e ( a f ，a ) s c o r e ( t ，a ) = 生l j r ( 2 1 ) s i z e vj 这里q 是查询关键字，t 是返回的结果，a 是t 的所有文本属性值构成的集合， s c o r e ( a ；，q ) 是属性a ；的相关性分值，这是由数据库系统决定的，s iz e ( t ) 是生成 结果t 时连接的数目。 2 3 3b a n k s b a n k s 使用有向的数据图来进行关键字检索。在b a n k s 的数据图中，数据库 关系表中的每个元组( 每一行) 被表示为一个节点，两个元组间外键到主键的联 系被表示为一条有向边。 在b a n k s 中，在数据库中的信息检索过程变成从有向图中找出一棵子树的过 程，对于检索请求中的任一关键字均可在至少一个节点上找到。b a n k s 生成的子 树为有向加权图，节点和边分别进行赋值，检索结果按照节点之间的相关性和边 的权重进行计算。节点的权重根据节点的入度确定，边的权重根据正 向遍历和逆向遍历有所不同。包含关键字的最小子图利用d i j k s t r a 算法进 行查找。b a n k s 解决查询速度慢的方法是将整个数据图抽象信息存放在内存中， 详细信息存储在硬盘上，在查询时仅对需要的节点进行磁盘访问。b a n k s 不要求 系统提供全文索引功能。 2 3 4 0 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 算法( g o o g l e 用来为网页排序的算法) 的 方法来计算结果的相关性分值。在p a g e r a n k 算法中，某个节点可能在初始状态 是不重要的，但是在最终状态却可能演变为重要的。因为p a g e r a n k 算法具有这 一特性，所以o b j e c t r a n k 认为是相关的节点可能并不包含任何查询关键字。 o b j e c t r a n k 不仅需要计算节点的全局重要性，还需要计算它与查询关键字的相 关性。节点v 对于关键字w 的分值是 ，”g ( v ) = r t m o ) ( r g o ) ) g ( 2 2 ) 这里，”o ) 是关键字w 的相关性分值，r g o ) 是v 的全