（计算机应用技术专业论文）基于p2p搜索引擎的数据库检索方案研究.pdf

摘要 在如今的信息时代，基于关键字的信息搜索引擎，例如著名的三大搜索引擎： 谷歌g o o g l e 、百度b a id u 和雅虎y a h o o ，已经逐渐成为人们在同常生活中获取信 息的重要手段之一。无论用户想要查询哪一方面的信息资料，只需要提供有关该 信息的搜索关键字，搜索引擎便能根据用户提出的搜索请求，向客户端返回与该 关键字相关的所有页面链接，并按相关度顺序显示在页面上。 然而，现有的绝大多数互联网搜索引擎检索的对象主要是针对静态页面，但在 实际网络应用中，大量的有用数据恰恰被保存在后台数据库中，不能够被现有的 搜索引擎直接索引。因此如何根据用户提交的关键字，从各类数据库中搜索出有 关的信息记录，是本文研究的主要内容。 本文围绕基于p 2 p 的数据库搜索引擎，介绍了p 2 p 的相关概念与技术，包括开 发p 2 p 网络的平台之一：j x t a 。重点研究了数据库信息搜索的基本方法，并且在 已有的按列扫描的检索方案的基础上进行了改进，提出了基于副表的按行扫描以 及基于s q l 语句优化的按行扫描的数据库检索方案。这两种方案与按列扫描方案 相比，减少了数据扫描的次数，从而能在一定程度上提高数据库的查询效率。最 后，针对基于s q l 语句优化的按行扫描的数据库检索方案作了详细的分析与实现。 关键字：搜索引擎，p 2 p ，数据库检索，按行扫描，全文检索 a b s t r a c t i nc u r r e n ti n f o r m a t i o nt i m e ，t h ek e y - w o r d sb a s e ds e a r c he n g i n e e r i n g ，s u c ha s g o o g l e ，b a i d u ，y a h o oa n de t c h a v eb e c o m eac o m m o nw a yo fp e o p l ew h e nl o o k i n gf o r i n f o r m a t i o ni nd a i l yl i f e n om a t t e rw h a tp e o p l ew a n tt os e a r c h ，a sl o n ga sh ec a n p r o v i d es e a r c hk e yw o r d s ，t h es e a r c he n g i n e e r i n gc a na s kt h ec l i e n tf o ra l lt h er e l e v a n t l i n k sa n ds h o wi to nt h ep a g ea c c o r d i n gt ot h er e l e v a n c e h o w e v e lm o s ti n t e r n e ts e a r c he n g i n e e r i n gt a r g e t sa r es t a t i cp a g e ，b u td u r i n gt h e n e t w o r kp r a c t i c e ，m o s tu s e f u ld a t aa r eu s u a l l ys a v e di nb a c k g r o u n dd a t a b a s ea n dc a n t b ef o u n db ys e a r c he n g i n e e r i n gd i r e c t l y t h ek e yc o n t e n to ft h ee s s a yi st od i s c u s sh o w t os e a r c hf o rr e l e v a n ti n f o r m a t i o nf r o md a t a b a s ea c c o r d i n gt ot h ek e yw o r d st h a tu s e r p r o v i d e t h ee s s a y , b a s e do np 2 pd a t a b a s es e a r c he n g i n e e r , i n t r o d u c e sp 2 pr e l e v a n tc o n c e p t a n dt e c h n o l o g y , i n c l u d i n go n eo ft h ep 2 pn e t w o r kp l a t f o r m sj x t a t h ee s s a yf o c u s e s o nt h eb a s i cm e t h o do fd a t a b a s es e a r c ha n dm a k e ss o m ei m p r o v e m e n tb a s e do nc u r r e n t p r o g r e s s i v es c a ns e a r c hm e t h o d t h ei m p r o v e m e n ti n c l u d es i d e - t a b l eb a s e dp r o g r e s s i v e s c a na n ds q ll a n g u a g eb a s e dp r o g r e s s i v es c a n t h et w om e t h o d sr e d u c et h et i m eo f d a t as c a na n di n c r e a s et h ee f f i c i e n c yo fd a t a b a s es e a r c h f i n a l l y , t h ee s s a ym a k ead e t a i l a n a l y s i so fs q ll a n g u a g eb a s e dp r o g r e s s i v es c a nd a t a b a s es e a r c hm e t h o da n dm a k ei t b e c o m ep r a c t i c a l k e yw o r d s ：s e a r c he n g i n e e r i n g ，p 2 p , d a t a b a s es e a r c h ，p r o g r e s s i v es c a n ，f u l l t e x t s e a r c h 学位论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除了 特别加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写过的研究成 果。其他同志对本研究的启发和所做的贡献均已在论文中做了明确的声明并表示 了谓 意。 论文作者签名g 岛铀期：f d 年r 月叫同 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权保 留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分 内容，可以采用影印、缩印或其它手段保存论文。保密的论文在解密后遵守此规 定。 论文作者签名凼匆期1 0 年厂月1 日 导师签名：日期：年月日 丽骂备夕hy l 1 4 5 上海师范人学硕士学位论文 h u 罱 第一章前言弟一早日u 百 1 1研究目的和意义 当今世界正是信息大爆炸的时代，传统的搜索引擎( 例如；谷歌g o o g l e 、百 度b a i d u 和雅虎y a h o o ) 的检索范围存在局限，它们所针对的搜索对象主要是静态 页面；此外，搜索引擎提供的信息的更新速度不够及时。事实上大量的有用信息 不仅仅局限于静态页面，而往往保存于后台的数据库中，而这些恰恰是我们所忽 略并且没有能够有效利用的。因此，如何高效且准确地获取数据库中的信息资源 正是需要我们深入关注的。 基于p 2 p 网络的搜索系统为我们提供了一个有效的、可扩展的平台去搜索各种 不同形式的文件，例如h t m l 、音乐、图像、视频以及本文所讨论的数据库。之所 以采用基于p 2 p 网络搜索的最主要原因在于基于p 2 p 网络的搜索系统相比传统搜 索引擎尤其特有的优势。 最近的一个统计报告显示：全球大约9 3 的信息以数字形式产生，每年增加的 数据量估计大于1 太兆字节，并预计以指数级增长。这一信息的增值趋势需要一 个可扩展的基础设施，它必须能够索引和搜索丰富的内容，例如h t m l 、音乐、图 像、视频以及数据库。 一个解决方案是建立一个集中式搜索引擎，类似谷歌g o o g l e 。然而，这一解 决方案需要维护一个巨大的、包含所有在线信息的集中式数据库；并且，为了使 这类搜索引擎成为可扩展引擎，需要一个非常庞大的、且价格昂贵的基础设施去 维持它们的运行( 例如，谷歌g o o g l e 为此需要配备成千上万台计算机) ，这些硬 件和软件的成本，以及维护和使用的成本都是非常昂贵的；此外，集中式的数据 库同样存在着单点失效的安全隐患，并且，几个星期以内最近创建或者修改过的 信息经常不能被索引进搜索数据库。类似的，搜索结果时也常包含失效的文件链 接，这些文件可能最近已经被删除。 另一个解决方案是建立一个基于p 2 p 网络的搜索引擎，这正成为一个极其具有 吸引力和前途的代替品。传统的集中式搜索引擎的整个搜索过程均依赖于中央服 务器，往往使服务器的负担过重，并且一旦服务器瘫痪，便会造成整个搜索服务 的停滞。然而，基于p 2 p 网络的搜索系统正好弥补了这些不足：基于p 2 p 网络的 搜索系统的结构是完全分布的，网络中的任何一个节点既能充当服务器又能充当 客户端，系统不依赖于某一个特定节点，任何节点的退出均不会影响该系统的运 作。相比传统式搜索引擎，基于p 2 p 网络的搜索系统具有较高的可用性、较低的 成本、良好的可扩展性，并且得到的数据是最新的。 玎i j 鬲上海师范大学硕士学位论文 1 2国内外研究现状 1 2 1 搜索引擎的现状 现有的互联网搜索引擎( 例如知名的谷歌g o o g l e 、百度b a i d u 和雅虎y a h o o ) 检索的对象主要是基于页面内容的，该类搜索引擎存在着以下两大不足： 1 ) 搜索的非实时性 该类集中式的互联网搜索引擎由于搜索模式的限制，存放于服务器端的页面 u r l 的更新需要一定的周期，因此常常导致用户搜索得到无效的页面链接。 2 ) 搜索对象不支持数据库 该类集中式的互联网搜索引擎的检索对象仅限于页面，而网络资源的存在形式 是多种多样的，特别是以存放数据为主要目的的数据库。 1 2 2 p 2 p 研究的现状 目前，国内的多所重点大学，例如清华大学、北京大学、以及华中科技大学等 都对p 2 p 网络进行了研究，并相继开发出了他们各自的p 2 p 系统。其中，g r a n a r y 是清华大学自主研发的对等计算存储服务系统；m a z e 是北京大学自主开发的对等 计算机共享系统；a n y s e e 是华中科技大学自主研发的视频直播系统。 在国外，几个较为著名的p 2 p 研究有：斯坦福大学对p 2 p 系统的搜索、资源分 配和聚集以及安全问题的研究；s u n 公司的j x t a 平台；以及麻省理工的i r i s ( i n f r a s t r u c t u r ef o rr e s i1l e n ti n t e r n e ts y s t e m s ) 计划。、 1 3 论文目标和创新点 从上- d , 节可以看出，传统的集中式搜索引擎不支持数据库检索，并且搜索不 具有实时性，而国内外的p 2 p 研究对于数据库检索方面的涉及较少。本文将p 2 p 技术运用于搜索引擎，以提高搜索引擎的实时性，并且以数据库为搜索对象，弥 补了传统集中式搜索引擎的不足。 本文的研究重点集中在基于p 2 p 网络的数据库检索部分，在传统的数据库检索 的基础上进行了归纳和总结，创新提出了2 种按行扫描的数据库检索方案，即： 基于副表的按行扫描和基于s q l 语句优化的按行扫描，在一定程度上提高了检索 效率。 文章最后，针对基于s q l 语句优化的按行扫描的数据库检索方案进行了实现， 并对该系统进行了测试。 1 4 论文结构 本文共分为六个章节，余下的五个章节将针对基于p 2 p 的数据库搜索引擎的体 系结构、基于p 2 p 的数据库检索方案及其实现进行详细的阐述。各章节的具体内 2 上海师范人学硕十学位论文日u 舌 容如下所示： 第二章整体地阐述了基于p 2 p 的数据库搜索引擎的体系结构；并对其中的p 2 p 部分进行了简单的介绍。 第三章主要对数据库检索方案进行了深入的探讨，归纳总结了现有的几种基本 方法，并分析了各方法的优缺点。并且，在此基础上创新提出了基于副表的按行 扫描和基于s q l 语句优化的按行扫描的数据库搜索方案。 第四章针对基于s q l 语句优化的按行扫描的数据库检索方案的实现过程中的 关键部分进行了详细的阐述，包括数据源的配置，以及列名词典的生成，并对搜 索流程进行了介绍。 第五章对系统进行了测试，给出了实验的环境数据以及实验结果的部分截图， 比较了按列扫描和基于s q l 语句优化的按行扫描这两种数据库检索方案的执行效 率。 第六章对本文作了概括与总结，就文章的不足进行了分析，并对未来的工作做 了展望。 基t - p 2 p 的数据库搜索引擎的体系结构上海师范人学硕+ 学位论文 第二章基于p 2 p 的数据库搜索引擎的体系结构 本章首先对p 2 p 数据库搜索引擎的总体框架作了阐述；并对其中的p 2 p 部分作 了简单的系统介绍。至于p 2 p 数据库搜索引擎中的数据库检索部分将作为本文研 究的重点，在后续第三章、第四章中进行详细阐述。 2 1基于p 2 p 的数据库搜索引擎的总体框架 基于p 2 p 的数据库搜索引擎的总体框架如图2 - 1 所示： 底层网络 p 2 p 通信网络 丁王 工i 工 用户接口用户接口用户接口 王 丁王 检索器 检索器检索器 工 王 e o d b co d b co d b c 图2 一l 基于p 2 p 的数据库搜索引擎的总体框架 基于p 2 p 的数据库搜索引擎的总体结构大致可以分为两大部分：p 2 p 网络通信 部分和数据库关键字检索部分。 p 2 p 网络通信部分与其它p 2 p 应用类似，主要负责搜索请求和搜索结果的发送 和传递。数据库关键字检索部分主要负责对搜索请求所包含的关键字进行数据库 检索，并生成结果文档。 其搜索过程主要步骤如下： 1 ) 用户节点a 通过用户接口发出关键字搜索请求。 2 ) 处于p 2 p 通信网络中的其他用户节点b 通过用户接口接收到该请求。 3 ) 用户节点b 根据搜索请求中的关键字k e y ，通过本地的检索器对共享的数据库 进行查询操作，并生成x m l 文档。 4 上海师范人学硕士学位论文基于p 2 p 的数据库搜索引擎的体系结构 4 ) 将搜索结果返回给提出搜索请求的用户节点a 。 2 2p 2 p 技术及其相关内容 2 2 1 p 2 p 定义 p 2 p ( p e e rt op e e r ) 可以理解为“端对端”的意思，或称为对等网络。p 2 p 较为简单的定义是通过端对端的直接交换来共享计算机的服务与资源。p 2 p 网络不 同于传统的客户机服务器( c s ) 模型，在p 2 p 网络中，节点之间的通信不依赖于 特定的服务器，取而代之的是节点之间的直接连接，数以万计台彼此相互连接的 节点均处于对等的地位，p 2 p 网络中的每一个节点既能充当客户端，发出文件、资 源和服务请求；又能充服务器，当接收到其他节点的网络请求时做出响应，提供 资源与服务；或是作为路由器，为其他节点传递信息。 p 2 p 网络最主要的目的是通过利用和集合每一个节点上的松散资源( 例如：存 储器、带宽和c p u ) 去构建一个大规模的分布式应用程序。随着p 2 p 技术的不断进 步与发展，p 2 p 技术的应用领域也得到了进一步的扩展，渗透到了科技的多个领域， 例如对等计算、搜索引擎、协同工作、共享文件等。 2 2 2p 2 p 网络结构 一般情况下，p 2 p 网络结构可以划分为以下四类： 1 ) 集中式p 2 p 网络 在集中式p 2 p 网络中，中央服务器用来维护被共享文件的信息索引、监视网络 中每个节点的运行状态、以及响应用户节点对这些共享信息的查询请求。每个节 点除了向其他对等点提供信息共享之外，还维护着与中央服务器的连接。采用集 中式p 2 p 网络的代表性软件之一是n a p s t e r 。 集中式p 2 p 网络结构见图2 2 所示： 图2 - 2 集中式p 2 p 网络结构 2 ) 完全分布式非结构化p 2 p 网络 完全分布式非结构化p 2 p 网络的拓扑结构可以被看作一个随机图，每个节点随 基丁二p 2 p 的数据库搜索引擎的体系结构上海师范人学硕士学位论文 机地选择其它节点作为自己的邻居节点，并且维护这些邻居节点的状态。每一个 节点既充当服务器又充当客户端，彼此具有相同的功能，所以又被称作对等点。 采用完全分布式非结构化p 2 p 网络的代表性软件之一是g n u t e ll a 。 集中式p 2 p 网络结构见图2 - 3 所示： 图2 3 完全分布式非结构化p 2 p 网络结构 3 ) 完全分布式结构化p 2 p 网络 完全分布式结构化p 2 p 网络是基于d h t ( d is t r i b u t e dh a s ht a b l e ，分布式散 列表) 的。该网络首先通过散列运算将查询关键字唯一地映射到网络中的某一节 点上，随后再通过不同的路由算法与该节点进行通信。在完全分布式结构化p 2 p 网络中，文件存储和检索的过程实质上是一个资源对象关键字k e y 和节点i d 的映 射过程。 4 ) 混合式p 2 p 网络 混合式p 2 p 网络借鉴了集中式p 2 p 网络与分布式p 2 p 网络结构各自的优点，在 搜索效率、可扩展性和抗攻击性上都得到了近一步的综合与提高。混合式p 2 p 网 络在分布式p 2 p 网络结构的基础上，根据节点的处理能力将其划分成三种类型： 用户节点、搜索节点、索引节点，并让这些特定类型的节点去完成某些特定的功 能。采用混合式p 2 p 网络的代表性软件之一是即时通信软件s k y p e 。 混合式p 2 p 网络结构见图2 4 所示： 6 上海师范人学硕士学位论文 基于p 2 p 的数据库搜索引擎的体系结构 图2 - 4 混合式p 2 p 网络结构 2 2 3p 2 p 网络与传统网络的对比 1 ) 由于传统的客户机服务器( c s ) 结构下的网络过分依赖于中央服务器，一旦 服务器出现故障或停机，整个网络也会随之受到影响。而对于p 2 p 网络而言， 每一个节点即是客户端，又可以被当作服务器，为其它节点提供服务，任何节 点的退出，不会对网络造成致命的影响，整个网络依然可以正常运行。 2 ) 传统的客户机n 务器( c s ) 结构下的网络一方面过度依赖于中央服务器，使 其始终处于超负荷运作的状态；另一方面客户端却存在着许多的闲散资源，并 没有得到充分有效地利用，必须等待服务器的响应，从而大大降低了的资源的 利用率。然而对于p 2 p 网络而言，每一个节点都充当着服务器的角色为其它节 点提供服务，充分发挥了各自的能力，大大提高了每一个节点的资源利用率。 3 ) 传统的客户机服务器( c s ) 结构下的网络过分依赖于中央服务器，因此，该 结构的网络较易于管理，只需对中央服务器进行维护即可；而对于淡化了“服 务器”概念的p 2 p 网络而言，与相比之下的不足之处便在于整个网络的管理不 方便，并且很难保证网络中的数据信息的可靠性与安全性。 传统c s 网络结构如图2 5 所示： 7 基于p 2 p 的数据库搜索引擎的体系结构 上海9 币范大学硕士学位论文 图2 - 5 传统c s 网络结构 p 2 p 网络结构如图2 - 6 所示： 图2 石p 2 p 网络结构 2 2 4j x t a 2 2 4 1 j x i a 定义 j x t a 是一套开放的、广义的点对点协议，允许任何网络设备( 例如传感器、 手机、p d a 、笔记本、工作站、服务器和超级计算机) 作为对等点相互通信、合作。 j x t a 协议独立于编程语言，可以绑定不同的语言环境，如j a v a 、c 、c + + 、n e t 等等。 2 2 4 2 j x i a 软件架构 j x t a 软件架构总共可以分为三层：核心层、服务层和应用层。 1 ) j x t a 核心层( j x t ac o r e ) j x t a 核心层封装了p 2 p 网络常用的、最小且必须的基本元素。它包括提供p 2 p 8 上海师范大学硕士学位论文 基下p 2 p 的数据库搜索引擎的体系结构 应用的关键机制的模块这些机制包括建立对等点和点组、发现，通讯传输、以 及相应的安全原语。 2 ) 服务层( s e r v i c e sl a y e r ) 服务层包括的网络服务不是p 2 p 网络运行所完全必需的，但却是在p 2 p 环境中 常用且极具吸引的。网络服务的例子包括文件分享、分布式文件系统、搜索和索 引、存储系统等。 3 ) 应用层( a p p l i c a t i o n sl a y e r ) 应用层包括完整应用程序的实现。例如：资源和文件其享、p 2 p 即时消息、p 2 p 电子邮件系统、娱乐内容管理和转发等。 j x t a 软件架构如图2 - 7 所示： 圆圆圈 嘲2 7j x t a 软件架构 基于p 2 p 的数据库检索方法研究上海师范人学硕十学位论文 第三章基于p 2 p 的数据库检索方法研究 数据库检索的主要任务是根据关键字k e y ，在整个数据库中检索出包含该关键 字的所有信息记录。 本章主要介绍了基于p 2 p 网络的数据库检索的基本方案，首先介绍了几种基本 的数据库检索方法：全文索引、页面搜索、以及按列扫描的数据库检索方法。随 后，又在按列扫描的基础上提出了基于副表的按行扫描和基于s q l 优化的按行扫 描。 3 1页面搜索 基于p 2 p 网络的数据库检索的一种简单方法是页面搜索，即将所有对于数据库 的搜索转化为对页面内容的搜索。 3 1 1基本步骤 该方法的原理较为简单，其基本步骤是： 1 ) 系统事先根据数据库中的各个用户表生成对应的页面； 2 ) 当系统接收到其他节点发出的关键字搜索请求后，便将请求包含的查询关键字 直接与步骤1 ) 中生成的页面中的内容进行匹配； 3 ) 如果匹配成功，则标记该页为需要返回的页面； 4 ) 如此循环步骤2 ) 、3 ) ，直至所有页面都完成遍历完为止，返回搜索结果给查 询用户。 具体流程如图3 1 所示： l o 上海师范人学硕士学位论文基t - p 2 p 的数据库检索方法研究 图3 1 页面搜索流程 3 1 2 优缺点 页面搜索的显著优势是该方法比较容易实现，只需考虑数据库表到页面的转换 和页面内容的搜索两个方面。然而另一方面，由于搜索结果返回的是所有包含查 询关键字的全部页面，但是用户所关心的仅仅是页面中的一两条记录，整个页面 信息常常含有大量的无关内容，必须由用户进行第二次筛选，可见该方法对用户 而言并不友好。 3 2全文索引 全文索引是如今比较流行的数据库检索技术之一。 3 2 1 基本原理 全文索引的基本原理是：首先确定一个关键字集合；随后依次统计出这些关键 字在被检索的文件中出现的位置与次数；接着把统计出来的信息以一定的顺序和 方式进行归纳整理，也就是为被检索的文件创建了一个关于关键字的索引。当用 户需要检索某个关键字的时候，便可以非常迅速的确定该关键字在文件中所在的 位置。 基于p 2 p 的数据库检索方法研究 上海师范大学硕士学位论文 3 2 2 基本步骤 以s q ls e r v e r 2 0 0 5 为例，创建全文索引的一般步骤为： 1 ) 启用该服务； 2 ) 初始化全文索引； 3 ) 创建全文目录； 4 ) 在目录中添加需要被全文索引的表； 5 ) 指定该表中需要被全文索引的列； 6 ) 填充全文目录。 该过程可以通过全文检索向导、存储过程、或者编程实现。创建结束后，便可 以用w h e r e 子句中含有c o n t a i n s 的s e l e c t 语句进行数据库查询了。 3 2 3 优缺点 全文索引的优点在于运用该技术的数据库检索效率高、速度快。然而，不足之 处在于，进行关键字检索之前必须先为数据库创建全文索引目录；其次，并不是 所有类型的数据库都支持全文索引的。 3 3 按列扫描 基于p 2 p 网络的数据库检索的第三种基本方法是按列扫描，该方法对数据库中 每个数据表的每一列属性进行一次s e l e c t 语句的查询扫描。 对于按列扫描可以作出如下定义： 定义l ：若表r ( a 1 ，a 2 ，a 3 ，a n ) ，按列扫描是指对表r 的a l 、a 2 、a 3 、 a n 列分别进行扫描，查找与搜索关键字匹配的内容。 3 3 1 基本原理 按列扫描的数据库检索的基本原理是，事先在数据库中创建一个列名词典，本 文称之为c o l u m n d i c t 表，该表的作用在于保存数据库中每一张用户表及其所含字 段的对应关系。当系统收到检索请求时，根据得到的关键字，以及c o l u m n d i c t 表 中的每一条信息记录，动态生成s e l e c t 语句，依次扫描该数据库中对应的用户表 及属性列。 3 3 2 列名词典 在按列扫描的数据库检索方法中引入了列名词典c o l u m n d i c t 这一概念，该表 存储了所有用户表以及用户表所包含的字段的对应关系。该数据表不仅在按列扫 描中使用，并且在接下来的几种方法中都会用到。 c o l u m n d ic t 表的表结构如下所示： c o l u m n d i c t ( c o l u m n n a m e ，t a b l e n a m e ) 表结构中c o l u m n n a m e 字段为数据列名，t a b l e n a m e 为该数据列所在的用户表 1 2 上海师范大学硕十学位论文基3 - p 2 p 的数据库检索方法研究 名称。 为此，定义如下关系模式( 其中r 代表用户表，a 代表该表所包含的字段) 。 r 1 ( a 1 1 ，a 1 2 ，a 1 3 ) r 2 ( a 2 l ，a 2 l ，a 2 3 ) 则列名词典c o l u m n d i c t 中的字段值应该如表3 1 所示： 表3 1 关系模式对应的c o l u m n d i c t 表 c o lu m n n a m et a b l e n a m e a l lr 1 a 1 2r 1 a 1 3 r 1 a 2 1r 2 a 2 1r 2 a 2 3 r 2 为了更形象的说明，假设有一个企业s p j 数据库，该数据库包括下列四个关系 模式： 供应商表：s ( s n o ，s n a m e ，s t a t u s ，s c i t y ) 零件表：p ( p n o ，p n a m e ，c o l o r ，w e i g h t ) 工程项目表：j ( j n o ，j n a m e ，j c i t y ) 供应情况表：s p j ( s n o ，p n o ，j n o ，0 t y ) 其中，s 表列出了供应商的代码( s n o ) 、名称( s n a m e ) 、状态( s t a t u s ) 及所 在城市( s c i t y ) ；p 表列出了零件的代码( p n o ) 、名称( p n a m e ) 、颜色( c o l o r ) 、 重量( w e i g h t ) ：j 表列出了工程项目的代码( j n o ) 、名称( j n a m e ) 及所在城市 ( j c i t y ) ；s p j 表列出了s 、p 、j 三表的对应关系，表示供应商s 提供了数量为 q t y 的零件p 给工程项目j 。 则对应的列名词典c o l u m n d i c t 中的字段值及其含义如表3 - 2 所示： 基t - p 2 p 的数据库检索方法研究上海师范大学硕十学位论文 表3 - 2c o l u m n d i c t 表中的记录及其含义 c 0 1u m n n a m et a b l e n a m e含义 s n os 在s 表中有s n o ( 供应商代码) 、s n a m e ( 供 s n a m es应商名称) 、s t a t u s ( 供应商状态) 、c i t y s t a t u ss ( 供应商所在城市) 四个属性列。 s c i t ys p n op 在p 表中有p n o ( 零件代码) 、p n a m e ( 零 p n a m ep 件名称) 、c o l o r ( 零什颜色) 、w e i g h t ( 零 c o l o rp 件重量) 四个属性列。 w e i g h tp j n oj在j 表中有j n o ( - 1 ：程项目代码) 、j n a m e j n a m ej ( 工程项目名称) 、c i t y ( 工程项目所在 j c i t yj 城市) 三个属性列。 s n o s p j在s p j 表中有s n o ( 供应商代码) 、p n o ( 零 p n o s p j 件代码) 、j n o ( 工程项目代码) 、q t y ( 零 j n os p j 件数量) 四个属性列。 q t ys p j 3 3 3 基本步骤 按列扫描的数据库检索方法的基本实现步骤如下： 1 ) 该方法在执行检索任务之前，必须事先在数据库中新增一张列名词典 c o l u m n d i c t 表。 2 ) 建立完c o l u m n d i c t 表之后，便可以执行检索任务了。当系统收到检索请求后， 根据得到的搜索关键字k e y 以及c o l u m n d i c t 表为依据，每次从c o l u m n d i c t 表 中读取c o l u m n n a m e 和t a b l e n a m e 的值，并对相应的用户表中相应的属性列执 行一次s e l e c t 语句的检索扫描。 3 ) 如此循环操作，直至c o l u m n d i c t 表中的每一条记录均被读取一遍，即表示数 据库中所有用户表的全部属性列均被搜索过。 具体流程如图3 2 所示： 1 4 上海师范大学硕士学位论文基于p 2 p 的数据库检索方法研究 图3 - 2 按列扫描流程 以s p j 数据库为例，首先按照步骤1 ) 得到该数据库的列名词典，该表已经在 上一小节给出，详见表3 - 2 。假设我们要搜索关键字“上海”，则按照步骤2 ) 得 到的关于供应商表s 的所有s e l e c t 检索语句如下： s e l e c t 木f r o msw h e r es n ol i k e上海 s e l e c t 术f r o msw h e r es n a v i el i k e上海 s e l e c t 水f r o msw h e r es t a t u sl i k e上海 s e l e c t 术f r o msw h e r es c i t yl i k e 上海 3 3 4 优缺点 假如一个数据库有a 张用户表，每一张用户表有b 列属性，则按列扫描的数据 库检索方法进行一次检索任务共需要进行a b 次扫描。由此可见，按列扫描的数 据库检索方法的扫描次数较多，如果将该方案运用于大型数据库，则会明显影响 执行效率。 3 4基于副表的按行扫描 按列扫描方案完成一次搜索任务所需执行的扫描次数较多、执行效率低下，为 此，本文在按列扫描的基础上，提出了基于副表的按行扫描的数据库检索方法， 基丁p 2 p 的数据库检索方法研究上海师范人学硕士学位论文 该方法在被扫描的表结构上做了修改，以达到减少扫描次数的目的。 对于按行扫描可以作出如下定义： 定义2 ：已知表r ( a 1 ，a 2 ，a 3 ，a n ) ，按行扫描是指对表r 的a 1 、a 2 、 a 3 、a n 列作为整体进行一次扫描，查找与搜索关键字匹配的内容。 对于基于副表的按行扫描可以作出如下定义： 定义3 ：已知表r ( a 1 ，a 2 ，a 3 ，a n ) ，基于副表的按行扫描是指对r 的副 表r ( a ) 的a 列进行一次扫描，查找与搜索关键字匹配的内容( 其中 a = a 1 + a 2 + a 3 + + a n ) 。 3 4 1 基本原理 基于副表的按行扫描的数据库检索方法的基本原理是：首先，为数据库中的所 有用户表创建对应的副表。然后，在数据库中创建一个表名词典t a b l e d i c t 表， 此表存储全部副表的表名。当系统收到检索请求后，根据得到的搜索关键字k e y ， 以及t a b l e d i c t 表中的每一条信息记录，动态生成s e l e c t 语句，依次搜索该数据 库中每张副表。 可见，基于副表的按行扫描的数据库检索方法与按列扫描的方法相似，所不同 的是酊者扫描的对象是只含有一个属性列的副表而不再是用户表。 3 4 2 副表 基于副表的按行扫描的数据库检索方法的关键在于引进了副表的概念，该副表 是完全基于用户表而生成的，却又不仅仅是用户表的副本，与用户表的区别在于 该副表只含有一个字段，且该字段是将用户表的所有属性列的值连接在一起而产 生的，即将用户表的全部属性列合并在一起形成唯一的一列属性。 为了更形象的说明副表的结构，定义如下关系模式( 其中r 代表用户表，a 代 表该表所包含的字段) ： r ( a 1 ，a 2 ，a 3 ) 则用户表r 的副表r 用关系模式表示即为： r ( a ) 可见，副表r 中仅有唯一一个字段a ，a 的值等于用户表r 中a 1 、a 2 、a 3 的 值以字符串形式连接起来得到的结果。 以零件表p 为例，假设该表含有记录如表3 3 所示： 1 6 上海师范人学硕十学位论文基于p 2 p 的数据库检索方法研究 表3 3 零件表p 中的记录 p n op n a m ec o l 。0 rw e i g h t p 1齿轮红3 0 p 2 凸轮橙 4 0 p 3 螺栓黄 1 7 p 4 螺母绿 1 2 p 5 螺丝刀蓝 1 4 p 6 螺丝刀紫 1 4 则零件表p 所对应的副表如表3 - 4 所示： 表3 _ 4 零件表p 所对应的副表p d a t a p 1 齿轮红3 0 p 2 凸轮橙4 0 p 3 螺栓黄1 7 p 4 螺母绿1 2 p 5 螺丝刀蓝1 4 p 6 螺丝刀紫1 4 3 4 3 表名词典 值得说明的是，该方法最初在数据库中所创建的表名词典t a b l e d i c t 表，其实 质是c o l u m n d i c t 表的特殊形式，当用户表仅拥有唯一一列字段时，简化了 c o l u m n d i c t 表的结构，去除了c o l u m n n a m e 列。 t a b l e d i c t 表的表结构如下所示： t a b l e d i c t ( t a b l e n a m e ) 其中字段t a b l e n a m e 即为数据库中所有副表的表名。 为此我们定义副表的关系模式如下： r 1 ( a 1 ) r 2 ( a 2 ) r 3 ( a 3 ) 则表名词典t a b l e d i c t 中的字段值应该如表3 5 所示： 1 7 基丁p 2 p 的数据库检索方法研究上海师范大学硕士学位论文 表3 - 5 关系模式对应的t a b l e d i c t 表 t a b l e n a m e r l r 2 r 3 以s p j 数据库为例，则t a b l e d i c t 表中的记录如表3 - 6 所示： 表3 - 6t a b l e d i c t 表中的记录 其中，s 、p 、j 、s p j 分别为供应商表s 、零件表p 、工程项目表j 以 及关系表s p j 的副表。 3 4 4 基本步骤 与按列扫描的数据库检索方法类似，基于副表的按行扫描的基本实现步骤如 下： 1 ) 该方法在执行检索任务之前，必须事先在数据库中新增一张表名词典 t a b l e d i c t 表。 2 ) 建立完t a b l e d i c t 表之后，便可以执行检索任务了。当系统收到检索请求后， 根据得到的搜索关键字k e y 以及t a b l e d i c t 表为依据，每次从t a b l e d i c t 表中 读取t a b l e n a m e 的值，并对相应的副表进行一次s e l e c t 语句的检索扫描。 3 ) 如此循环操作，直至t a b l e d i c t 表中的每一条记录均被读取一遍，即表示数据 库中所有副表均被搜索过。 3 4 5 优缺点 基于副表的按行扫描先将多列合并为一列，然后再进行扫描，其本质是按列扫 描的特殊情况。假如一个数据库有a 张用户表，每一张用户表有b 列属性，则基 于副表的按行扫描的数据库检索方法进行一次检索任务只需要执行a 次扫描，而 按列扫描的数据库检索方法则需要执行a b 次扫描，由此可见扫描次数得到了显 著的减少。 基于副表的按行扫描方法中由于引入了副表的概念，额外地创建了与用户表规 上海师范大学硕十学位论文基于p 2 p 的数据库检索方法研究 模相当的副表，以消耗系统存储空间为代价来减少扫描次数，对于大型数据库而 言，副表所占用的空间丌销是不可小视的。此外，还需要考虑副表的维护问题， 一旦数据库中的某个用户表被修改了，副表必须进行同步更新。解决这一问题的 可行方法之一是采用触发器机制，监控系统中每一个用户表的新增、修改、删除 等操作，使副表与用户表的数据保持一致。 3 5 基于s q l 语句优化的按行扫描 基于副表的按行扫描的数据库检索方案的显著不足在于需要额外占用与用户 表规模相当的磁盘空间。本节提出另一种基于s q l 语句优化的按行扫描的数据库 检索方案，该方法以s q l 语句优化为切入点，同样达到按行扫描的目的。 对于基于s q l 语句优化的按行扫描可以作出如下定义： 定义4 ：已知表r ( a i ，a 2 ，a 3 ，a n ) ，基于s q l 语句优化的按行扫描是指 利用s q l 语句对表r 的a 1 、a 2 、a 3 、a n 列作为整体进行一次扫描，查找与 搜索关键字匹配的内容( 其中a = a 1 + a 2 + a 3 + + a n ) 。 3 5 1 基本原理 基于s q l 语句优化的按行扫描方案的基本原理是，在执行搜索任务之前，事先 在数据库中创建列名词典c o l u m n d i c t 表( 参见3 3 2 小节) 。当系统收到检索请 求后，根据得到的关键字k e y ，以及c o l u m n d i c t 表为依据，从c o l u m n d i c t 表中读 取每一个用户表的所有属性列，动态生成s e l e c t 语句，并对相应的用户表进行一 次检索扫描。 与按列扫描所不同的是，该s e l e c t 语句一次扫描一整张用户表。而按列扫描 中的s e l e c t 语句一次仅扫描一张用户表的一个属性列。 3 5 2s o l 语句优化 3 5 2 1 采用按列扫描的s q l 语句 假设要在用户表中搜索关键字k e y ，则采用按列扫描的数据库检索方法，生成 的s q l 语句可以写成如下一般形式： s e l e c t 木 f r o m w h e r e l i k e k e y 为此，定义如下关系模式( 其中r 代表用户表，a 代表该表所包含的字段) 。 r ( a 1 ，a 2 ，a 3 ) 则根据关系模式r ，采用按列扫描的数据库检索方法生成的全部s o l 语句为： s e l e c t 木f r o mrw h e r ea 1l i k e k e y 1 9 基丁p 2 p 的数据库检索方法研究上海师范大学硕士学位论文 s e l e c t 术f r o mrw h e r ea 2l i k e k e y s e l e c t 木f r o mrw h e r ea 3l i k e k e y 3 5 2 2优化后的s o l 语句 基于s q l 语句优化的按行扫描的检索方法对按列扫描的s q l 语句进行了简化， 合并了查询相同数据表的多条s e l e c t 语句，去掉了部分冗余的重复语句，从而达 到了优化的目的。 同样，假设要在用户表中搜索关键字k e y ，则采用基于s q l 语句优化的按行扫 描的数据库检索方法，生成的s q l 语句可以写成如下一般形式： s e l e c t ：i c f r o m w h e r e l i k e k e y o r l i k e k e y 则根据关系模式r ，采用基于s o l 语句优化的按行扫描的数据库检索方法生成 的s q l 语句为： s e l e c t 木 f r o mr w h e r ea 1l i k e k e y o ra 2l i k e k e y o ra 3l i k e k e y 由此可见，经过s q l 语句优化后，对于同一关系模式r ，我们仅用一条s e l e c t 语句代替了按列扫描方法中的三句s e l e c t 语句。 3 5 2 3 实例分析 以供应商表s 为例( 详见表3 3 ) ，假设要在该表中搜索含有关键字“上海” 的全部记录。 则采用按列扫描生成的全部s q l 语句为： s e l e c t 术f r o msw h e r es n ol i k e上海 s e l e c t 半f r o msw h e r e