（计算机软件与理论专业论文）对结构化和半结构化数据的关键字搜索研究.pdf

论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名 论文使用授权声明 日期 2 口口7 彳。 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名：避导师签名：逝 日期：塑! z ：笸：乡 摘要 关键字搜索是现今最为流行的信息发现方法，因为用户不需要学习任何复杂 的查询语言，也不需要了解底层数据的结构，他只需要使用若干关键字来表达自 己的信息需求即可。在过去的十几年中，对非结构化数据的关键字搜索已经有过 较多的研究，随着结构化数据( 以关系数据为典型代表) 和半结构化数据( 以 x m l 数据为典型代表) 数量的日益增多，人们转而把目光投向对这两类数据的关 键字搜索研究。本文在充分吸取| i 人研究成果的基础上，以关键字搜索的效率和 有效性为侧重点，针对现有工作存在的问题进行了较为深入的研究，提出了创新 性的解决方法，主要取得了以下研究成果： 1 对关系数据的关键字搜索，目前最流行的方法是基于搜索时连接的搜索 方法，本文研究了其核心问题模式图上连接表达式的搜索算法，提 出了一种时间复杂度为多项式级延迟的搜索算法，并给出了它的正确性 证明和时间复杂度分析。 2 本文提出了一种基于预连接的对关系数据的关键字搜索方法。本文分析 了在关系数据库中引入关键字搜索之后可能引发的若干问题，提出将搜 索结果定义为包含所有查询关键字的完全元组图( c t g ) ，在此基础上设 计了基于归并排序的高效的搜索算法，并给出了对搜索结果集的相关性 排序方法。最后，对索引更新问题也给出了具体的解决方法。 3 本文提出了一种基于m i u 的对) ( m l 数据的关键字搜索方法。本文分析了 在x m l 关键字搜索中结果粒度精细化可能引发的若干问题，定义了最小 信息单元( m i u ) 的概念，给出了对任意x m l 文档划分最小信息单元的 方法，并提出以最小信息单元作为索引、搜索的最小粒度，设计了精简 的索引结构和相应的搜索算法。 对于上述这些研究成果，本文给出了相应的实验数据，实验结果表明这些方 法在关键字搜索的效率和有效性方面均有不同程度的提升，在科研领域和商业应 用中都有着很好的应用前景。 关键词：关键字搜索，结构化数据，半结构化数据，x m l 中图分类号：t p 3 1 1 1 3 4 a b s t r a c t k e y w o r ds e a r c hi sn o wt h em o s tp o p u l a ri n f o r m a t i o nd i s c o v e r ym e t h o d b e c a u s et h eu s e rd o e sn o tn e e dt oi e a ma n yq u e r yl a n g u a g e 。o rk n o wt h e u n d e r l y i n gs t r u c t u r eo ft h ed a t a h eo n l yn e e d st oi n p u ts e v e r a lk e y w o r d st o e x p r e s sh i si n f o r m a t i o nn e e d i nt h ep a s td e c a d e s k e y w o r ds e a r c hi nt h e u n s t r u c t u r e dd a t ah a sb e e nw e l is t u d i e d w i t ht h ei n c r e a s eo ft h ea m o u n to f s t r u c t u r e dd a t a ( t y p i c a l l yr e l a t i o n a ld a t a ) a n ds e m i s t r u c t u r e dd a t a ( t y p i c a l l y x m ld a t a ) ，r e c e n t l yk e y w o r ds e a r c hi nt h et w ok i n d so fd a t ah a sa t t r a c t e d m u c ha t t e n t i o n b a s e do nt h ee x s i t i n gw o r k s ，t h i sd i s s e r t a t i o nl a y se m p h a s i s o ne f f e c t i v e n e s sa n de f f i c i e n c yo fk e y w o r ds e a r c hi ns t r u c t u r e da n d s e m i s t r u c t u r e dd a t a t h em a i nc o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r e s u m m a r i z e da sf o l l o w s ： 1 t h ep o p u l a rm e t h o do fk e y w o r ds e a r c hi nr e l a t i o n a ld a t ai sb a s e do n s e a r c h - t i m e - j o i n t h i sd i s s e r t a t i o ns t u d i e si t sc o r ep r o b l e m - - s e a r c h a l g o r i t h mf o rt h ej o i ne x p r e s s i o n so nt h es c h e m ag r a p h i tp r o p o s e sa n e ws e a r c ha l g o r i t h mw i t ht h et i m ec o m p l e x i t yo fp o l y n o m i a ld e l a y , a n dg i v e si t sp r o o fo fc o r r e c t n e s sa n da n a l y s i so ft i m ec o m p l e x i t y 2 t h i sd i s s e r t a t i o np r o p o s e san e wm e t h o do fk e y w o r ds e a r c hi n r e l a t i o n a ld a t ab a s e do np r e - j o i n b a s e do nt h ea n a l y s i so ft h e p r o b l e m sc a u s e db yp h y s i c a ls c a t t e r i n go fd i f f e r e n ti n f o r m a t i o np a r b ， i tg i v e st h ed e f i n i t i o no fc o m p l e t et u p l eg r a p h ( c t g ) a n dr e g a r dc t g a st h eg r a n u l a r i t yo fi n d e ) ( i n ga n ds e a r c h i n g b a s e do nc t gi t d e s i g n st h ee f f i c i e n ts e a r c ha l g o r i t h m i ta l s op u tf o r w a r d st h em e t h o d o fi n d e xm a i n t e n a n c e 3 t h i sd i s s e r t a t i o np r o p o s e san e wm e t h o do fk e y w o r ds e a r c hi nx m l d a t ab a s e do nm i u b a s e do nt h ea n a l y s i so ft h ep r o b l e m sc a u s e db y r e f i n e m e n to fr e s u i tg r a n u l a d t y , i tg i v e st h ed e f i n i t i o n o fm i n i m a l i n f o n t l a t i o nu n i t ( m i u ) a n dp r e s e n t st h ea l g o r i t h mo fp a r t i t i o n i n gt h e x m ld o c u m e n ti n t o m i u s r e g a r d i n gm i ua st h eg r a n u l a r i t y o f i n d e ) ( i n ga n ds e a r c h i n g 。i td e s i g n se f f i c i e n ti n d e xs t r u c t u r e sa n dt h e c o r r e s p o n d i n gs e a r c ha l g o r i t h m s 5 a sf o rt h ea b o v ec o n t r i b u t i o n s ，t h i sd i s s e r t a t i o ng i v e st h ec o r m s p o n d i n g e x p e r i m e n t a ld a t a t h ee x p e n m e n t a lr e s u l t sd e m o n s t r a t et h eb e n e f i t so fo u r m e t h o do v e rp r e v i o u s l yp m p o s e dm e t h o d si nt e r m so fe f f e c t i v e n e s sa n d e f f i c i e n c y t h e s en e wm e t h o d sn o to n l yh a v et h ep r o m i s i n gf u t u r ei ns c i e n t i f i c r e s e a r c hf i e l d s ，b u ta l s oc a l lb ea p p l i e dt ot h ep r a c t i c a lb u s i n e s sa p p l i c a t i o n s k e y w o r d s ：k e y w o r ds e a r c h ，s t r u c t u r e dd a t a ，s e m i s t r u c t u r e dd a t a ，x m l c l c ：t p 3 1 1 1 3 6 第一章绪论 本章对整篇论文的研究背景进行了简要的介绍，首先讨论了数据与查询的分类及相互组 合，在此基础上引出了本文着重研究的两方面问题：关系数据库上的关键字搜索和x m l 文 档上的关键字搜索。此外，还介绍了本文的具体研究内容及组织结构。 1 1 研究背景 1 1 1 数据与查询 随着计算机技术和网络技术的飞速发展以及在社会各个领域中的广泛应用， 过去的几十年中基于计算机的数据信息呈现爆炸性的增长。现今众多商业数据库 的容量己经达到了海量的水平，很多数据库中已经存储了上万亿字节的数据。万 维网( w o r l dw i d ew e b ) 的出现更是加剧了数据生产的速度。在短短的十几年时 间里人类产生了近百亿个网页( g o o g l e2 0 0 6 ) ，而人类有文字以来的上万年里也 只产生了大约1 亿本书。到2 0 0 4 年初中国国内网上就已经有了约3 亿个网页( 天 网2 0 0 4 ) ，而中华民族有史以来出版的书籍大约不过2 7 5 万种。尽管书籍的容量 和质量是一般网页不可比的，但是在对应的时间背景上这种数据的总体数量和产 生速度是相当惊人的。最近几年随着x m l 逐渐成为数据表示和数据交换的标准， x m l 文档的数量也在与日俱增。 虽然这些产生出来的数据的内容林林总总各不相同，但是从数据是否具有结 构这个角度来考察，我们大致可以将这些数据划分为三类：非结构化数据( 以 h t m l 文档为典型代表) 、结构化数据( 以关系数据为典型代表) 和半结构化数据 ( 以) ( i l l 文档为典型代表) 。简单来说，非结构化数据不具有内在结构，结构化 数据具有确定的结构，而半结构化数据居于前面二者之间，它具有一定的结构， 但是这种结构具有不确定性。 数据产生出来如果事后无法加以利用，那么就没有任何保存的价值。针对产 生出来的这些数据，人们设计了各种查询语言来对数据进行查询，从中找出自己 想要的信息。虽然提出的查询语言的种类也是非常繁多，但是从查询条件的精确 性这个角度来考察，我们可以将查询划分为两类：结构化查询和关键字搜索。结 构化查询的查询条件是精确的，而关键字搜索的查询条件是模糊的。这也就导致 了结构化查询的查询结果都是精确的，而关键字搜索的搜索结果可能是不精确 7 的，可能并没有准确反映用户的真实信息需求。 图卜l 给出了上述三种类型的数据和两种类型的查询的所有组合。这里我们 可以看出现今广泛应用的数据库系统提供的是对结构化数据的结构化查询，而信 息检索系统提供的是对非结构化数据的关键字搜索。虽然它们都是用于数据的搜 寻，但是二者对于数据以及其上的查询有着不同的要求。近几年随着x m l 的普及 而发展起来的x q u e r y 查询系统则是对半结构化数据的结构化查询。因为非结构 化数据没有内在结构，所以不存在对它的结构化查询问题。这样，在图卜1 这张 数据与查询的组合图上就只剩下两块用阴影标记的区域，分别是对结构化数据和 半结构化数据的关键字搜索问题。随着以w e b 搜索引擎为代表的关键字搜索模式 开益广泛的为人们所接受并使用，对这两类数据的关键字搜索研究已经成为数据 库与信息检索领域一个新兴的研究方向。 k 0 y w o r ds c 椭 s t r u c m r c dd a t a s c m i - s t m c l u r e dd a t au n s t m c m r c dd a m 图卜1 数据与查询 1 1 2 关键字搜索搜索引擎 圆 早在w e b 出现之前，互联网上就已经有了很多共享的信息资源，这些资源主 要存在于各种允许匿名访问的f t p 站点上，内容以学术报告、研究性软件居多， 它们以文件的形式存在，文字材料的编码通常是p o s t s c r i p t 或者纯文本( 当时 还没有h t m l ) 。为了便于人们在分散的f t p 资源中找到自己所需要的东西，加拿 大麦吉尔大学( u n i v e r s i t yo fm c g i l l ) 计算机学院于1 9 9 0 年开发了a r c h i e 软件。该软件通过定期搜集并分析f t p 系统中存在的文件名信息，提供查找分布 在各个f t p 主机中文件的服务。a r c h i e 能在只知道文件名的前提下，为用户找 到这个文件所在的f t p 服务器的地址。a r c h i e 实际上是一个大型的数据库，再 加上与这个大型数据库相关联的一套检索方法。该数据库中包含大量可通过f t p 下载的文件资源的有关信息，包括这些资源的文件名、文件长度、存放该文件的 计算机名及目录名等。尽管a r c h i e 所提供服务的信息资源对象( 非h t m l 文件) 与现今搜索引擎的信息资源对象( h t m l 网页、x m l 文档、关系数据库) 存在一定 的差别，但是人们还是将a r c h i e 公认为现代搜索引擎的鼻祖。 在过去的十几年中随着互联网的飞速发展，以w e b 网页为搜索对象的搜索引 擎已经逐渐成为普通用户查找信息的重要手段，这也使得关键字搜索成为面向普 通用户最为实用的查询方式。w e b 搜索的基本原理是利用h t m l 文档之间的链接 关系，在w e b 上一个网页一个网页的“爬取”( c r a w l ) ，将这些网页“抓”( f e t c h ) 到本地后进行分析、索引。在提供关键字搜索服务时，当接收到用户提交的关键 字搜索引擎就把包含关键字的网页排序后返回给用户。1 9 9 3 年m a t t h e wg r a y 开 发了w o r l dw i d ew e bw a n d e r e r ，它是世界上第一个利用i t t m l 网页之间的链接 关系来监测w e b 发展规模的机器人程序。刚开始它只用来统计互联网上的服务器 数量，后来则发展为能够通过它来检索网站域名。现代搜索引擎的思路源于 w a n d e r e r ，不少人在m a t t h e w6 r a y 工作的基础上对它的程序做了改进。1 9 9 4 年 7 月，m i c h a e lm a u l d i n 创建了著名的l y c o s ，成为第一个现代意义的搜索引擎。 在那之后，随着w e b 上信息的爆炸性增长，搜索引擎的应用价值也越来越高，不 断有更新、更强的搜索引擎系统推出。在这其中，最引入注目的是g o o g l e ( h t t p ：w 啊g o o g l e c o m ) ，它由于采用了独特的p a g e r a n k 技术，使得它很快 后来居上，成为当前全球最受欢迎的搜索引擎。 搜索引擎实际上是一个信息获取系统，它的底层是待搜索的数据源，它能在 可接受的时间内返回一个和用户查询q 匹配的信息列表三。 图1 - 2 搜索引擎示意图 “可接受的时间”是指响应时间。对于面向广大用户提供服务的系统来说， 这个时间不能太长，通常也就在“秒”这个量级，它是衡量搜索引擎可用性的一 个基本指标。“匹配”指的是返回的信息中以某种形式包含有q 的内容，其中最 简单、最常见的形式就是q 在其中直接出现。“列表”蕴含着一种“序”( r a n k ) 。 9 在大多数情况下，是相当长的，如超过1 力个条目，这不仅是由底层数据源的 海量规模所导致的，搜索引擎查询方式的简单也是一个重要原因。简单，意味着 抽象；抽象，意味着有更多的具体事物可能是它的体现。因此，对搜索出来的结 果集进行相关性排序将有助于提高用户查阅的方便性，信息检索领域在这一方面 已经有了丰富的研究成果，可以直接加以应用。 1 2 研究内容与组织结构 1 2 1 研究内容 本文的研究内容主要包括以下两大部分： ( 1 ) 关系数据库上的关键字搜索研究 研究了基于搜索时连接的搜索方法的核心问题模式图上连接表达 式的搜索算法； 研究了基于预连接的搜索方法的系统结构、索引设计和搜索算法： 研究了基于预连接的搜索方法的索引更新问题。 ( 2 ) x m i - 文档上的关键字搜索研究 研究了基于m i u 的搜索方法的系统结构、索引设计和搜索算法； 研究了搜索结果集的聚类问题。 1 2 2 组织结构 本文的内容是围绕关系数据库上的关键字搜索和x i i l 文档上的关键字搜索 而展开的，共分为六章，组织结构如下： 第一章绪论 本章对整篇论文的研究背景进行了简要的介绍，首先讨论了数据与 查询的分类及相互组合，在此基础上引出了本文着重研究的两方面问 题：关系数据库上的关键字搜索和x m l 文档上的关键字搜索。此外，还 介绍了本文的具体研究内容及组织结构。 第二章关键字搜索相关研究概述 本章主要介绍了两部分内容，首先是关系数据库上的关键字搜索的 研究概述，然后是】( m l 文档上的关键字搜索的研究概述。 第三章基于搜索时连接的关系数据库中的关键字搜索 本章主要研究了基于搜索时连接的搜索系统的核心问题模式 图上连接表达式的搜索算法，提出了一种时问复杂度为多项式级延迟的 搜索算法，并给出了它的】下确性证明和时间复杂度分析。 第四章基于预连接的关系数据库中的关键字搜索 本章主要研究了基于预连接的关系数据库中的关键字搜索问题，它 分析了在关系数据库中引入关键字搜索之后可能引发的若干问题，提出 将搜索结果定义为包含所有查询关键字的完全元组图( c t g ) ，设计了基 于归并排序的高效的搜索算法，并给出了相应的对搜索结果集的相关性 排序方法。最后，对索引更新问题给出了具体的方法，并进行了优化。 第五章基于m i u 的x m l 文档检索 本章主要研究了对于x m l 文档的关键字搜索问题，在详细分析结果 粒度精细化可能引发的若干问题的基础上，定义了最小信息单元( m i u ) 的概念，给出了对任意x m l 文档划分最小信息单元的方法，并以最小信 息单元作为索引、搜索的最小粒度，设计了精简的索引结构和相应的搜 索算法。 第六章结论与展望 本章对全文进行了总结，并对将来的工作进行了展望。 图i - 3 是本文研究内容的组织结构图。 第一章绪论 j 第二章关键字搜索相关研究概述 i ， i ，第兰章基予搜索时连接的芙系数据库中的关键字搜索j 莨第四章基予预连接的关系数据库中的关键字搜索“j i f ” 第五章基于m i u 的x a 纯文档检索“一j 本文工作 上 第六章结论与展望 图1 - 3 论文的组织结构 1 1 第二章关键字搜索相关研究概述 本章主要介绍了两部分内容，首先是关系数据库上的关键字搜索的研究概述，然后是 x i v l l 文档上的关键字搜索的研究概述。 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 文档。这种关键字搜索服务大大方便了 普通用户在浩瀚如海的万维网上查找感兴趣的信息。 事实上，现有的搜索引擎在万维网上可以搜索到的数据只占总数据量的很小 一部分，更多的数据对于现有的搜索引擎来说是不可搜索的，这些数据大多存储 于关系数据库中。万维网上关系数据库中的数据构成了所谓的“隐形网” ( h i d d e nw e b ，d e e pw e b ) 。l a w r e n c e 和g i l e s 8 9 在1 9 9 8 年估计了万维网上的 数据大约有8 0 存储在隐形网中，b e r g m a n 9 0 在2 0 0 1 年发现存储在隐形网中 的数据总量要比可见网大4 0 0 到5 5 0 倍。因此，如何扩展现有的搜索引擎技术使 其能够搜索到“隐形网”中的数据就成为一个重要的研究课题。 现代信息系统需要管理复杂的数据，这一复杂性主要体现在数据种类的多样 化，现代信息系统中可能包含结构化的关系数据、半结构化的x m l 数据和非结构 化的w e b 文本数据。然而，当需要对这些复杂数据进行查询时目前使用的却是各 不相同的查询语言。例如，对于关系数据只能通过s q l 语言来进行查询，对于 x m l 数据只能通过x q u e r y 语言来进行查询，而对于网页数据则通常是通过关键 字搜索来进行查询。对于现代信息系统来说，如何为用户提供一种一致的查询语 言以方便管理这些复杂数据成为一个重要的挑战。就目前的研究现状而言，关键 字搜索有望能够成为这样一种一致的查询语言。在过去的十几年中人们已经对非 结构化的文本数据上的关键字搜索进行了深入的研究，因而如何针对结构化的关 系数据和半结构化的x m l 数据进行关键字搜索已经成为数据库和信息检索领域 一个重要的研究方向。 在过去的几年中关系数据库上的关键字搜索问题已经引起了数据库领域的 广泛关注，主要的研究工作有 1 2 5 ，本节将简要介绍其中几个最具代表性的 研究工作，它们分别是d b x p l o r e r 1 、d i s c 0 v e r 2 ，7 、b a n k s 3 ，1 8 和 o b j e c t r a n k 4 。 2 1 1d 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 ) 搜索符号表( s y m b o lt a b l e ) 来找出数据库中包含查询关键字的关系、 字段、元组。符号表实际上是一个倒排索引，它是在搜索之前对数据库进行预处 理的过程中创建的。 ( 2 ) 根据数据库模式图搜索出所有连接树。连接树是数据库模式图的一个 子树，它满足下面两个条件：对应于叶子节点的关系至少包含一个查询关键字， 每个查询关键字都包含于某个对应于叶子节点的关系中。如果把连接树中所有 的关系都连接起来，那么连接的结果中就可能存在包含全部关键字的元组。 ( 3 ) 对于步骤( 2 ) 中搜索出来的每个连接树，生成相应的s o l 语句来连接 其中的各个关系，并从结果中挑选出那些包含全部关键字的元组。最后，对这些 选出的元组进行相关性排序并返回给用户。 搜索连接树的过程包含下面三个步骤： ，( 1 ) 从数据库模式图口中移去那些不包含任何关键字的叶子节点，生成一 个新的模式图口7 。 ( 2 ) 通过启发式的方法在口中选取出一个叶子节点。 ( 3 ) 从选定的叶子节点开始对口进行宽度优先遍历，这将生成出所有的 连接树。 例如，在图2 1 ( a ) 中，模式图f 包含5 个关系。假定查询关键字是彤、尼 和局，关系7 ；包含了所有这三个关键字，关系乃包含如关系乃包含尼，黑色 节点表示至少包含一个关键字的关系。在这个例子中搜索算法从叶子节点乃开 始搜索出四个连接树，如图2 - 1 ( b ) 所示。 o 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 使用简单的用户界面来表示结 果，它用文本来描述连接树，并在一个关系中呈现连接结果。 当! z 乃ll - k 3 s c h e n m 挚 p h g ( a ) 2 1 2d i s c o v e r l l t 5 f 瓢， j ， ( b ) 图2 - 1 连接树( 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 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 会及时将其剪除。图2 - 2 是一个元组集合图的实例，图中的a u t h o r “ 表示关系a u t h o r 中包含关键字u l l m a n 的所有元组构成的集合，p a p e r “表示 关系p a p e r 中包含关键字d a t a b a s e 的所有元组构成的集合。注意在元组集合图 中边的方向是由主键指向外键。假定用户提交的查询关键字是“u i i m a n d a t a b a s e ”，那么由图2 - 2 将生成候选网络a u t h o r “酗w r i t e s ”i x p a p e r “。 图2 - 2 元组集合图( d i s c o v e r ) d i s c o v e r 使用的相关性评判函数是： 仍纠：学 这里口是查询关键字，是返回的结果，爿是，的所有文本属性值构成的集 合，s c o r e 丘k 纠是属性岛的相关性分值，这是由数据库系统决定的，s i z e r 秒 是生成结果7 时连接的数目。 1 4 2 1 3b a n k s b a n k s 使用有向的数据库数据图来进行关键字搜索。在b a n k s 的数据图中， 数据库的每个元组被表示为一个节点，两个元组问外键到主键的联系被表示为一 条有向边。 在b a n k s 中，关键字查询就是n ( n 1 ) 个搜索关键字“如，如。对 于每个关键字玉，生成一个相关的节点集合s 。如果节点在属性值或元数据( 如 关系名称、字段名称等) 中包含某关键字，那么就称该节点与这个关键字相关。 假定与“如厶对应的相关节点集合是品s ，b a n k s 将结果定 义为连接树( c o n n e c t i o nt r e e ) 。连接树是一棵有向树，并且对于每个s ，至少 包含其中一个节点，连接树的根节点被称为信息节点。b a n k s 使用启发式的算法 来搜索所有的信息节点，该算法使用d i j k s t r a 最短路径算法从每个叶子节点出 发来遍历整个数据图。在结果输出方面，b a n k s 使用一个嵌套表来表示结果树。 2 1 40 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 不仅需要计算节点的全局重要性，还需要计算它与查询关键字 的相关性。节点y 相对于关键字矿的分值是 尹( v ) = p l v ) ( ( v ) y 这里， 是关键字矿的相关性分值，r 砂是v 的全局重要性分值，g 是由 用户定义的常数。在o b j e c t r a n k 中，节点相对于关键字的分值是由预处理模块 计算的并存储于分值索引文件中。分值的计算是计算密集型的操作，o b j e c t r a n k 中给出了几种高效的计算方法。 2 1 5 相关研究分类及总结 关系数据库上的关键字搜索的相关研究可以按照搜索对象和搜索结果的不 同来对其进行分类，如图2 - 3 所示。首先，从搜索算法的搜索对象来考虑，可以 分为搜索数据库模式图的系统和搜索数据库数据图的系统两种。搜索数据图的系 统直接搜索最终结果，而搜索模式图的系统的搜索结果是连接表达式，之后需要 将其转化为相应的s q l 语句，经查询后得到最终结果。其次，从搜索结果来考虑， 可以分为包含数据图中的单个节点和包含多个节点两种。如果搜索结果包含数据 图中的多个节点，那么需要连接这些节点以使用户了解其内在联系。例如， d a t a s p o t 和b a n k s 使用信息节点来表明搜索结果的含义，d b x p l o r e r 和d i s c o v e r 则是把结果定义为若干节点的连接。 在模式图上搜索 在数据图上搜索 d b x p l o t c f 【1 1 d a t a b a 齄f u l l * t e x t 啪北h d i s c o v e r 【2 1 s i s o h l 3 l l v l t a g y a t i 2 5 l b a n k s l 3 o 坷噬艰蛆珥4 l m , s e t f t t l 5 】 m 哪【2 3 1 包含多个节点包含单个节点 圆 圈2 - 3 相关研究分类 下面将对关系数据库上的关键字搜索的已有研究从体系结构、数据模型、查 询语言、结果的定义和排序、搜索算法的效率等多个方面进行总结。 体系结构 已有的数据库检索系统一般都具有两个模块：预处理模块和查询模块。 预处理模块负责在执行第一次检索之前对数据库进行预处理。预处理模 块会创建查询模块所需的各种数据结构( 如倒排索引等) ，以便加快查 询的执行。这些数据结构在有些系统中是存储在主存中的( 如b a n k s 中 的数据图) ，在有些系统中是存储在外存中的( 如d b x p l o r e r 中的符号 表) 。 查询模块负责对用户查询的处理。首先，查询模块需要对用户的输入进 行解析，以确定查询关键字和查询语义。然后，查询模块执行搜索算法 以产生结果，这部分的具体工作取决于各个检索系统。例如，在 o b j e c t r a n k 中这里的任务就是计算与查询有关的每个节点的分值，然后 生成最终结果，而在d i s c o v e r 中则是先生成元组集合图，然后搜索出 候选网络再执行相应的s o l 查询。最后，查询模块还要将查询结果按相 关性排序后返回给用户。 数据模型 大多数数据库检索系统都是将数据库建模为数据库图，数据库图分为模 式图和数据图两种，它们可以是无向图，也可以是有向图。例如，b a n k s 通过搜索有向数据图来找出所有信息节点，d b x p l o r e r 通过搜索无向模 式图来找出所有连接树。通常在模式图中节点表示关系，边表示两个关 系之间的外键一主键联系，在数据图中节点表示元组，边表示两个元组 之间的外键一主键联系。把数据库表示为图是很有好处的，因为w e b 文 档集也是被表示为图，而w e b 图和数据库图之间的这种相似性使得我们 在研究数据库检索系统时可以借鉴现有w e b 搜索引擎中的某些成熟技 术。o b j e c t r a n k 就是一个成功的例子。 至于是直接在数据图上进行搜索还是先通过模式图进行搜索，二者各有 其优缺点，直接在数据图上进行搜索一般在性能上具有较好的表现，但 是它对数据图规模的限制是一个严重的制约问题，毕竟内存的容量在任 何系统中都是有限的。 查询语言 查询实际上是用户信息需求的一种抽象，数据库检索系统需要定义它所 支持的查询语言的语法和语义。最基本的基于关键字的查询形式是关键 字搜索，其它的查询形式还包括短语查询、邻近查询和模式匹配等，但 是现有的数据库检索系统并没有对所有这些查询形式都提供支持。 d i s c o v e r 、d b x p l o r e r 和b a n k s 对a n d 语义的查询提供了支持，而 o b j e c t r a n k 则对a n d 语义和o r 语义的查询都提供了支持。 最基本的查询对象包括所有关系的所有文本属性。尽管大多数系统都声 称它们的查询对象可以很容易的扩展到元数据( 如关系名称、字段名称 等) ，但是实际上还是存在着一些问题有待解决。例如，在b a n k s 中如 果某个关键字可以匹配某个关系名称，那么这个关系的所有元组都将与 这个关键字相关。因为b a n k s 会为每个匹配关键字的节点都创建一个线 程，所以如果这个关系包含了大量的元组，那么就要创建大量的线程。 结果的定义和排序 查询结果在有些系统中被定义为来自某个关系的单个元组( 如 o b j e c t r a n k ) ，在有些系统中则被定义为来自若干关系的若干元组( 如 d b x p l o r e r 、d i s c o v e r 、b a n k s 等) 。因为查询结果最后要返回给用户查 阅，所以如何使得查询结果语义完整丰富也是一个重要的问题。现有的 大多数系统返回的不仅仅是包含关键字的元组，而是数据图中包含所有 关键字的最小子树，但是如本文后面章节所述这样做仍然是不够的。 结果的相关性排序对于数据库检索系统来说也是非常重要的。每个查询 结果会按照一定的评判标准得到一个相关性分值，然后对所有结果按照 这个分值的降序来进行排列并返回给用户。现有的数据库检索系统主要 考虑了下面三个相关性评判因素： 第一个评判因素是文本属性值的i r 分值，这个分值是根据其包含的关 键字的数目来计算的。计算的方法可以借鉴传统信息检索领域中的某些 成熟的评判方法，如 ，- j 出方法等。 第二个评判因素是结果树的结构和语义。这里的结果树在d b x p l o r e r 中 指的是连接树( j o i nt r e e ) ，在d i s c o v e r 中指的是候选网络( c a n d i d a t e n e t w o r k ) ，在b a n k s 中指的是连接树( c o n n e c t i o nt r e e ) 。结果树主要 是根据其大小( 即边的数目) 来评判分值的。此外，还可以根据结果树 的语义来评判其分值。例如，如果事先认为在d b l p 文献数据库中结构 a u t h o r w r i t e s p a p e r 优于结构p a p e r - c i t e s p a p e r ，那么尽管二者结 构的大小是一样的，但是可以给予前者较高的分值来体现其所表达的语 义的重要性。 第三个评判因素是链接的语义，即一个节点的分值还依赖于它和周围节 点之间的链接。例如，o b j e c t r a n k 就使用了这样的链接语义。 现有数据库检索系统中使用的相关性评判函数与它们各自的查询结果 的定义有关。例如，d i s c o v e r 的查询结果可能包含多个节点，所以它使 用的评判函数就会涉及到文本属性值的i r 分值和结果树的结构，而 o b j e c t r a n k 的查询结果只会包含单个节点，所以它使用的评判函数就只 需考虑链接的语义。 搜索算法的效率 不同的系统使用不同的算法来搜索查询结果，而且一般都做了相应的优 化，但是这些算法大多数是启发式的搜索算法，缺乏明确的时间复杂度 上界或者在最坏情况下具有指数级的时间复杂度。因此，在设计搜索算 法时如何保证其具有明确的时间复杂度上界也是一个重要的问题。 2 2x m l 文档上的关键宇搜索相关研究概述 非结构化数据可以看成是由标点或句法标签间隔的原始文本，例如h t m l 文 档就是一种典型的非结构化数据。h t m l 文档中的标签只是一种句法标签，并不 含有任何与内容有关的语义信息。h t m l 文档不具有严格的结构，其中的标签可 以随意嵌套，开始标签和结束标签可以不配对。虽然这种结构上的随意性给h t m l 1 8 文档的丌发者带来了方便，但是这也使它丧失了结构等元数据信息，从而导致对 它的搜索查询会返回相当数量的无关结果。结构化数据是具有严格预定义格式的 数据，它的元数据信息给出了与内容有关的精确描述，例如数据项的类型、长度 等属性信息。用户提出精确的信息需求就可以得到精确的结果，但是其查询模式 一般较为复杂，而且如果用户不了解底层数据的结构就无法进行查询。 以x m l 为代表的半结构化数据是一种介于非结构化数据和结构化数据之间 的数据，它的结构要求比非结构化数据要高，但是没有结构化数据那么严格。从 信息检索的角度来说，仅仅找出用户想要的信息是不够的，而应该返回给用户具 有最少无关信息的适当粒度的结果。这就需要把结构信息也考虑到搜索技术中 去，但是现今的搜索引擎无法做到这一点，因为它们搜索的表层网( s u r f a c e w e b ) 主要包含的是不具有结构的非结构化数据。正如2 1 节所述更多的数据是存储于 “隐形网”中的，对于这部分数据除了可以直接对其所在的关系数据库进行搜索 以外，还可以将关系数据发布为x m l 数据，进而对】( m l 数据进行搜索。这种方法 的优点在于随着x m l 逐渐成为数据表示和数据交换的标准，这种方法具有更好的 通用性和可移植性。 目前在针对x m l 数据的关键字搜索这一研究领域中主要有两个方向。 一个研究方向是对x m l q l 之类的x m l 精确查询语言进行信息检索方面的扩 展，使之具有全文检索和相关性排序等信息检索的典型特点，这一方向主要的研 究工作有 3 0 ，3 2 ，3 3 ，3 4 ，4 0 ，4 l 等 。文献 3 0 对x m l - q l 语言进行了关键字 搜索方面的扩展，并给出了性能实验。文献 3 2 3 中提出的x i r q l 是对x q l 进行的 扩展，使之具有模糊谓词、数据项加权和最小结构抽象等特征。文献 3 3 中提出 的x x l 搜索引擎具有类s q l 的语法和相关性排序等功能，还使用本体知识来进行 相似性比较。这些研究工作的优点是返回结果比较精确，毕竟它们是基于像 x 札一q l 、x q l 这样的精确查询语言，并且是对已知结构的x m l 文档进行检索。然 而，所有这些经过扩展后的语言都更不适合普通用户使用，因为用户需要学习复 杂的查询语言的语法，并且需要了解x m l 文档的结构。 另一个研究方向则是从针对w e b 文档的关键字搜索发展而来，它利用x m l 文档的独特特点来进行关键字搜索，这一方向主要的研究工作有 2 6 2 9 ，4 2 ，4 3 ， 4 4 ，6 2 等 ，其中具有代表性的有：x r a n k 2 6 、x k e y w o r d 2 7 、x s e a r c h 2 8