基于知识的DeepWeb集成环境变化处理的研究

ISSN1000-9825,CODENRUXUEWE-mail:[e-mail],Vol.19,No.2,February2008,pp.257−266:[phone]©2008byJournalofSoftware.Allrightsreserved.基于知识的DeepWeb集成环境变化处理的研究∗徐和祥+,王鑫印,王述云,胡运发(复旦大学计算机科学与信息技术系,上海200433)StudyonEnvironmentalChangesProcessinginDeepWebIntegrationBasedonKnowledgeXUHe-Xiang+,WANGXin-Yin,WANGShu-Yun,HUYun-Fa(DepartmentofComputerScienceandInformationTechnology,FudanUniversity,Shanghai200433,China)+Correspondingauthor:Phn:[phone],E-mail:[e-mail],(2):257−266.:BasedontheresearchonthedependenceofthecomponentsinthedeepWebintegration(executivepartialorderandknowledgedependency),aknowledge-basedmethodisgiventoprocessthechangesinsuchintegration,whichincludesenvironmentalchangesprocessingmodel,aself-adaptivesoftwarearchitectureandalgorithm.Thismethodcanprovideareferencetothefurtherresearchortowardapplicationforthelarge-scaledeepWebintegration.Theexperimentalresultsshowthatthemethodcannotonlyprocessthechanges,butalsohighlyimprovetheperformanceoftheintegratedsystem.Keywords:knowledge;deepWebintegration;environmentalchange;softwarearchitecture摘要:研究了DeepWeb集成环境中构件的依赖关系(执行偏序依赖和知识依赖),并在此基础上提出了一种基于知识的环境变化的处理方法,包括DeepWeb集成环境变化处理模型以及适应DeepWeb环境变化的动态体系结构和处理算法,可以对大规模DeepWeb集成的进一步探索和走向应用提供参考.实验结果表明,该方法不仅可以处理DeepWeb环境的变化,还可以大幅度提高集成系统的性能.关键词:知识;deepWeb集成;环境变化;软件体系结构中图法分类号:TP393文献标识码:A当前Internet上的信息检索好比海上撒网捕鱼,可以搜索到很多信息,但同时也有很多信息因为隐藏得很深而漏掉.文献[1]表明,Google,Yahoo索引只覆盖了32%的DeepWeb信息,而MSN更少,只覆盖了11%的DeepWeb信息.DeepWeb的数据信息隐藏在Web查询界面的后面,查询界面是其唯一入口,用户只有通过查询界面,动态提交查询请求才能得到相应的查询结果.Bergman[2]的报告表明,2000年大约有96000个提供Web查询的站点,但到了2004年4月,这样的查询站点已经增长到大约450000个[3];另外,Google,Yahoo等常见搜索引擎由于采用针对文本和网页的“字”索引模式,因而无法保证搜索的准确性和检索的个性化需求.大量DeepWeb站点蕴藏着丰富的信息资源,拥有一个统一的查询平台,无缝连接这些数据源,实现集成查询非常有现实意义.目前对DeepWeb集成的研究主要集中在集成的各个环节的技术上,包括爬虫[3]、接口模式∗SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.60473070(国家自然科学基金)Received2007-08-31;Accepted2007-12-05258JournalofSoftware软件学报Vol.19,No.2,February2008抽取[4]、模式匹配[5−8]、分类[9]、统一查询接口界面生成[10]、DeepWeb源选择[11]、查询转换[12]、数据抽取[13,14].与本文的研究类似,文献[15,16]也是研究DeepWeb的集成,但是都缺少对DeepWeb集成环境变化处理的相关内容.本文研究DeepWeb集成环境变化处理,主要结果是:在研究大规模DeepWeb集成环境构件的依赖关系的基础上,给出一种基于知识的环境变化的处理方法,包括DeepWeb集成环境变化处理模型以及基于环境变化自适应的动态体系结构和处理算法.实验结果表明,该方法不仅可以处理DeepWeb集成环境的变化,还可以提高集成系统的性能.1相关概念定义1(DeepWeb源(DW)).DeepWeb源可以定义为一个三元组(D,I,R),其中:(1)D指的是运行在Web站点服务器端的后台数据库,可以是目前流行的各种数据库模式;(2)I=(url,V)为Web站点的查询接口模式,其中,url为查询接口对应的网络地址,V=(V1,…,Vn),Vi为查询接口的属性,i=1,...,n;(3)R为DeepWeb站点中通过查询接口I提交用户请求后返回的结果集.定义2(DeepWeb集成).DeepWeb集成可以定义为(DS,Iu,Ru),其中:(1)DS=(ds1,ds2,...,dsn),dsi=(Di,Ii,Ri)为一个DeepWeb源;(2)Iu为ds1,...,dsn集成后的统一查询界面,记为Iu=I1⊕I2⊕...⊕In;(3)Ru为经统一查询界面提交查询请求后返回的统一结果视图,记为Ru=R1R2...Rn.⊕表示在接口模式匹配[5−8]基础上的查询界面的集成,是基于逻辑和语义基础上的叠加,相关研究可参见Wise-integrator[10];而大规模DeepWeb集成环境下的问题到现在为止还缺乏研究成果.定义3(知识)[17].知识常采用逻辑方法表示,如Datalog.在现实世界中,知识一般有事实与规则两种.(1)事实给出了客体特性间的固有联系,它的一般表示形式是F(a1,a2,...,an).事实相当于(关系)数据库的关系元组,因此,可以认为数据库中的数据(元组)给出了事实性知识.(2)规则给出了客体间的因果关系或推理关系,规则可以用下面的形式表示:A1,...,An→B.当然,以上知识仅仅是客观世界中真正存在的知识的一个子集,鉴于这种知识目前在计算机中是较易于处理又为人们常用的一种知识,因此本文的研究建立在这种知识之上.定义4(动态软件体系结构(dynamicsoftwarearchitecture,简称DSA)).DSA=(P,N,L),其中:(1)P是系统逻辑功能的构件集合,如DeepWeb集成环境中的爬虫构件等.(2)N是实现系统调度和控制的构件集合.它们负责监控环境和构件的变化信息,并根据这些变化信息,按照一定的策略和方法,自适应调整系统的体系结构,使系统按目标继续稳定正确运行.N=(Core,Sensor),其中:①Core是自适应系统中动态体系结构的核心,包含一个自适应处理算法,该算法根据运行过程中的环境变化信息(知识),按照一定策略,实现系统状态的自动更新;②Sensor用于收集构件、环境在运行期间的变化信息,并将它们反馈给Core.(3)L表示构件的交互关系和规则.传统上的软件体系结构指的是静态体系结构,在运行过程中不会发生变化,但实际情况是,软件系统及其所处环境往往是不断变化的,这要求软件体系结构在运行时随之发生变化.软件体系结构的变化包括两类[18]:一类是软件内部执行所导致的体系结构改变,比如很多服务器端软件会在客户请求到达时创建新的构件来响应用户的需求;另一类变化是软件系统外部的请求对软件的构件进行重新组装.2DeepWeb集成环境和构件依赖2.1DeepWeb集成环境的特点DeepWeb集成环境的主要特点有:徐和祥等:基于知识的DeepWeb集成环境变化处理的研究2591)DeepWeb的数据信息隐藏在Web查询界面的后面,查询界面是其唯一入口,用户只有通过查询界面动态提交查询请求才能获得相应的查询结果.因此,DeepWeb集成环境返回给用户的查询结果是对各DeepWeb源返回结果的在线(online)动态合成.2)DeepWeb集成环境易变且不稳定.其原因主要是,用于集成的各DeepWeb源是完全自治的系统,其从生成到死亡的过程完全独立于集成环境.DeepWeb集成环境的主要变化包括:(a)集成的DeepWeb源的个数一直处于动态变化中,每天都有新的生成和死亡.(b)每个DeepWeb源的url、查询接口模式、查询返回结果的模式和语义等都在不断发生变化.Meng[19,20]等人研究了Internet中一般网页(静态)的变化规律,但研究者至今还没有发现关于DeepWeb各种变化的规律和频率的相关文献和研究资料.DeepWeb源的上述变化导致的后果包括:(1)DeepWeb源url的变化将引起集成系统到该DeepWeb源的不可达;(2)DeepWeb源的查询接口界面模式的变化将导致集成环境的统一查询接口模式到该DeepWeb源查询界面模式之间的错误映射,进而导致查询执行过程中查询条件转化的错误;(3)DeepWeb源的查询结果模式或语义的变化将导致集成过程中数据抽取及合成的错误.从而最终返回给DeepWeb集成系统的用户一个错误的结果集.2.2构件的依赖关系与MetaQuerier[15]对DeepWeb集成环境中构件的定义相同的是:爬虫(databasecrawler,简称DC),接口模式抽取(interfaceextraction,简称IE),数据源(DeepWeb源)分类(sourceclustering,简称SC),模式匹配(schemamatching,简称SM).另外,本文增加的是:统一接口查询模式生成(unifiedinterfacegeneration,简称UIG)和知识清理(knowledgecleaning,简称KC).1)爬虫:DeepWeb源查询接口地址的获取,详见文献[3];2)接口模式抽取:解析查询接口的语义,实现查询界面的模式抽取,获得对应DeepWeb源的查询能力,详见文献[4];3)数据源分类:通过查询接口模式,对DeepWeb源实现按领域分类,详见文献[9];4)模式匹配:实现领域内各DeepWeb源查询接口的语义匹配,是统一查询接口界面合成和查询转换的基础,详见文献[5−8];5)统一接口查询模式生成:实现领域DeepWeb源统一查询界面的生成,详见文献[10];6)知识清理:当删除某DeepWeb源时,清理知识库中与该DeepWeb源关联的知识.在大规模DeepWeb集成环境中,各构件按照一定的流程协作完