《语义缓存查询处理优化技术及实现》由会员分享，可在线阅读，更多相关《语义缓存查询处理优化技术及实现（4页珍藏版）》请在金锄头文库上搜索。
1、计算机科学2004V013110(增刊)语义缓存查询处理优化技术及实现SemanticCachi“gQueryProcessl“gOptimizationTechniqueandImpIementatlon郝小卫1万海2章陶1李磊1(中山大学软件研究所广州510275)1(中山大学信息科学与技术学院广州510275)2Abstr扯tSenlanticcachingi3partlcularlyefficientIoruseinmobileenvironrnentsduetothereducedcommunlcatlontr8fficandtheimprovedresponsetimebutthe
2、reexistsdmicultyand1蛆itationinapplyingthistechniqueThispaperputsforwardthemodelofapplyi“gembeddeddatabaseinsemanticcache：SCE1)B，presentstheco廿cept，architectureandhlghperfor眦ncesolutionofoptimi让tlontechlliqueinsemantKcachi“gqueryuationbasedonenlbeddeddatabase，particuIarlyanalysesthesemanticcachingmod
3、亡l，queryuationandoptimizationB“thenpropedatwoleveloptimizationapproachanditsrealizationtechnique，final睁，thePeranceofthese-manticcac地modeIisexaminedthroughasimulatIonstudyKeywordsSemanticcachi“g，QueryprocessingEmbeddeddatabase1引言2scEDB体系结构与数据存储模型语义缓存技术是缓存技术的一种，它通过既缓存数据本身，也缓存对数据的语义描述比只缓存数据本身可以更好地节省网络开
4、销1，客户端可以利用本地缓存的语义信息进行推理，从而确定客户查询是否可在本地被完全解答或部分解答，无需与服务器通信，因此语义缓存技术得到广泛应用。目前，人们对语义缓存技术进行了大量的研究，文1给出了语义缓存的明确定义，并描述了语义缓存技术解决策略的较完整思路；文2，3对如何从语义缓存中导出当前查询(部分)结果的问题，研究了查询从缓存导出的充分条件和相应的算法；文4专门讨论了语义缓存技术中的替代问题，并给出解决策略。实用性对语义缓存技术来说是至关重要的，主要表现在：(1)客户端需对缓存的数据和语义进行组织和管理，而现有工作没有提供一个实用的语义缓存模型；(2)现有研究往往把内存作为语义缓存的存储
5、介质，这会影响客户端处理其它事务的效率，降低速度；(3)语义缓存存储数据的粒度通常为“段(或块)”，这种存储模型比较粗糙，查询修剪、替代和客户端与服务器一致性维护等操作也很难进行。本文提出了基于嵌入式数据库实现语义缓存的技术方案(scEDB：SemanticcacheBasedonEmbeddedDatabase)，由于采用嵌入式数据库在客户端缓存的查询与结果可与服务器的数据库管理系统在数据存储和运算上实现统一，也便于实现客户端的查询修剪，替代策略。ScEDB的设计采用独立部件化设计方法，能最大限度节省客户端开销。sCEDB的体系结构如图1所示。scEDB作为客户端与服务器的中间件寄生于客户端
6、，核心是一个嵌入式数据库引擎，用来存储客户端的查询结果和语义信息。它的工作方式，每当客户端发出一个请求Q，它首先在本地进行查询，如果满足查询要求，则直接返回给客户端，否则就向服务器发出查询请求Q，；并由Q，代替Q完成查询并将结果返回给客户端。若系统处于网络断接状态，也只能在本地执行本地查询；如果在断接期间更新数据，则当网络重新连接时，应用一致性维护算法保证数据的一致性。一t目斛“广量业I怒II慧燃11位LJLL；订蓠匾霉lH矗Itp欺1!一图l定义1(嵌入式语义缓存模型scEDB)sCEDB使用嵌入式数据库存储查询结果和语义。scEDB=R。，R：，R。，其中R中(1in)是scEDB中的关系
7、。Am表示由关系Rt结构定义的属性集合，A代)本文得到中山大学学科建设规划基金项目(35000-3253201)资助都小卫博士生工程师。主要研究颁域为数据库人工智能知识库65表整个数据库的属性集，有AUAm，(1in)。定义2(结果记录集Dc)结果记录集Dc是针对客户端的一次查询结果的集合。每一个Dc都有唯一的查询语义Q。相对应；Dc具有如下的表达式：(DcR，DcP，Dc，。)。其中DC。一dDcp(DcR)，DcREDB。定义5(结果集sc)结果集sc表示服务器上一个表或视图的查询结果存储在SCEDB的一个关系；sc形如(ScR，SCP，sc。)，其中scRDC州scP=VDC，(1in)
8、；Sc。=oscp(ScR)；sc是由具有相同关系的DG组成的集合，集合中相同元组只出现一次。5查询处理scEDB同时保存语义描述和查询结果，客户端发出的查询Q先在sCEDB进行推理，确定能否被完全解答；如能完全解答，就无须再与服务器通信；如果只能得到部分解答，则修剪查询Q将修剪后的部分发往服务器进行处理。51相关定义定义4(查询修剪)当查询Q(形如(Qt，Qr，Q，。)在ScEDB的sc表中只能部分解答，将Q分解为两部分：一部分可从sC回答P。(ProbeQuery)，另一部分不能从SC得到回答R。(RemainderQuery)，这个分解过程称作查询修剪，且满足：P妒VRqP=Q，且PqP
9、RqP=日。定义5Pq(probeQuery)ProbeQuery简称pq，是在sC中得到的部分或全部解答的查询，其解空间为Q。nSC。定义6K(RemainderQuery)RemainderQuery简称Rq，是查询Q不能从sC中得到解答，而是需发往服务器端才能得到结果的查询，其解空间为Q，。一sC。定义7假设存在sc形如(scn，scP，sc。)和一个查询Q形如Qn，Q，Q。)，我们称：1)Q能从Dc得到解答，如果scn=Qn，且QrScP在SCt上是可满足的；2)Q能从Dc得到全部的解答，如果scR=Qt，且QP，SCP。52Q与sc之间的关系用谓词Q表示用户想进行的查询用sc表示数据
10、存储表存在如下关系：设sC中存在n个属性，与此对应有n维空间DD。，D2，Dn，其中D“=l，2，n)表示第i维向量Vi(1，2，n)，有DiDL。，DUi(DLi，Du，是DL。nDu。)闭区间的表示)，语义表达式为m维向量PPt，R，P。，且mn，Vj(1，662，m)，有p，PL，PU门。对于sc与R(Q)之间的包含(相等)、相交和无关等关系分两种情形讨论：1)m=n包含(相等)：Vi，j(1，2，n)，有PL，Pu，SDL。，Du。；相关：Vi，j(1，2，n)，PL，PujDL，Du，是可满足的，且PL，PUJ一DL。，Du非空；无关：i，j(1，2，n)，PL，Pu，DL、，DU是
11、不可满足的。2)m。其中E，p=(q_7sC)日q，EnQn，E。为空。由Ec，SC。一垂，那么Ecp一SCpECpsCp=EcpECpSC=ECp队丽E”一(Qp_7so)Ec，就可以简化为E一岛Ec，。那么在Q经sc修剪后，再直接经Ec修剪，而不要将q_7Sq经正c修剪，减少运算的复杂程度。由此可知。增加了空结果集Ec，对查询Q进行修剪时，探头查询Pq是不会受彰响的，只是需要对剩余查询进行适当的调整就可以了。在原来剩余查询的基础上再减去一个空查询就可以得到优化后的剩余查询了。对于剩余查询R=(，孙，R，)-将其中的R矿=Qp_7scp调整为R”一(锡1sq)一Ea，其余部分保持不变。我们得
12、到优化后的修剪算法QueryTrim2tQuerytrim2(QueryQ，sCscECec)IfQr8SCrsthen(p尊QR”；母；lsTrimEc皇false；)Else讧QrsnSC碍o且Qrsn-7SCrB西thenp”巷Q，SCF。R叮兰QP_，SCp，IsTrimEC=truei)ElseQrsflSCrs需oP=垂；R毒QPIsTrimEC=tru8；)ifistrhrIECthenIfQpECpthenE=Q，R驴=壬IElseifQpnECp西且QpnEcp圣thenE=QPECP，R砷=R蟑，ECp；ElseQrsnSCrs=垂-&，盎垂；)修剪后会得到R、Eq和R。三
13、种子查询，其中R。发往服务器端进行查询，其余部分在本地完成。R。查询成功后，将其结果和R的结果合并，就是查询Q所要得到的查询结果。如果此次R。查询失败，那么原来sc中的记录集和相应的语义子句不用改变，但需要将此次的R。存储到Ec中。5实验与分析51模拟仿真实验环境介绍我们设计了模拟仿真实验环境来对本文所讨论ScEDB模型的性能进行测试。1)sCEDB模型介绍sCEDB模型的嵌入式数据库采用中山大学软件所研制的EBase数据库系统，由服务器、客户端、sCEDB服务器端组件、(下转第74页)67性。本文的体系结构是我们ERTDBs系统实现的第一步，还需要进一步细化和验证。以后的工作还包括利用此体系
14、结构建立系统原型，进一步探讨其适用性。参考文献】熊光泽，古幼鹏，桑楠嵌入式软件设计方法学研魁综述计算机应用，2004，24(4)：142Tksanov【cA，NystrjmDHanssonJ，Norst而mCEmbeddedIhtabascsforEmbeddedRea卜TimeSystem：ACompo僻ntBa5edApprch：tech印DePan巾衄t。fc湘putefscjenceLiIlkpingunlversLty柚dDepart眦ntofcomputefEngii“gMiIardalcnUnLvergnyt20023王彤王良嵌入式移动数据库的综述及评价计算机工程，200l，27
15、(12)：1551574stanko啊cJA，sonS蛐gHyuk，HonJMisco啦eptb蚰about弛altimedatabasesComputer，199932(6)；z9365何新贵唐常杰-李霖-刘云生特种数据库技术M北京：科学出版社z0002042366MemrTDN”rstras=oBeyondobEcts：Compo啪ts1n：MPPapaglouGschl89etef，edsCooperatlveInatlonSyst洲；CurrentTfendsandDirectlonsJ99749787RashidA，SawyerPAspectorlentatindd缸abasesystems!ffectlvecustomkat如napproachSoftwareIEEProc，2001148(5)，lS6164BEkadT，AkshsMKkzalesGHa1DlscusngaspectsofAOPCommunicationBoftheACM2001，44(10)：33389RashidAAHyb划Approachtoseparaclonofconcerns：TheStoryofSADESIn：3rdIntlConfonMetaLev毹Archlt
