面向移动计算环境的连接查询处理模式
- 格式:pdf
- 大小:250.19 KB
- 文档页数:5
收稿日期:2007-05-25;修回日期:2007-09-10。基金项目:国家自然科学基金资助项目(60572112);江苏省教育厅自然科学基金资助项目(06KJB120051)。作者简介:王敏(1980-),女,湖北襄樊人,硕士研究生,主要研究方向:移动计算、数据库系统;陈耿(1965-),男,江苏无锡人,教授,博士,主要研究方向:数据挖掘、数据库系统;朱玉全(1966-),男,江苏常州人,副教授,博士,主要研究方向:数据库系统、数据挖掘;张春芬(1982-),女,山东菏泽人,硕士研究生,主要研究方向:数据挖掘、医学图像。文章编号:1001-9081(2007)11-2756-04
面向移动计算环境的连接查询处理模式
王敏1,陈耿2,朱玉全1,张春芬1
(1.江苏大学计算机科学与通信工程学院,江苏镇江212013;2.南京审计学院信息管理系,南京210029)
(wang111min@163.com)
摘要:在移动计算环境下,基于准确的操作代价估算结果来选择合适的连接查询处理模式,可
以减少数据的传输量和移动设备的能量消耗。探讨了该环境下移动设备能量消耗的一个新的非对称
特征,提出了一种操作代价估算方法,并从数据传输量和能量消耗两个方面对连接查询处理模式进行
了代价估算和性能比较,提出了4个实用准则,以指导连接查询处理模式的选择。试验结果充分论证
了估算方法和准则的正确性,且比现有同类估算模型和结论具有更加广泛的应用范围。
关键词:移动计算;连接查询;数据传输;能量消耗
中图分类号:TP311.13文献标识码:A
Studyonjoinqueryprocessingschemesinamobilecomputingenvironment
WANGMin1,CHENGeng2,ZHUYuquan1,ZHANGChunfen1
(1.CollegeofComputerScienceandTelecommunicationEngineering,JiangsuUniversity,ZhenjiangJiangsu212013,China;2.DepartmentofInformationManagement,NanjingAuditUniversity,NanjingJiangsu210029,China)
Abstract:Underamobilecomputingenvironment,itcanreduceboththeamountsofdatatransmissionandenergy
consumptionofmobileunitstoselectasuitablejoinqueryprocessingschemebasedonaccuratecostestimateofoperations.Acostestimatemethodforjoinqueryprocessingwaspresentedafteranewasymmetricalfeatureofenergyconsumptionata
mobileunitwasexploited.Thecostsofjoinqueryprocessingschemeswereevaluatedfromdatatransmissionandenergyconsumption,andtheperformancesofthemwerecomparativelyanalyzed.Thenfourpracticalcriteriawereachievedtoguide
ustoselectthesuitableprocessingschemeandminimizethecostofjoinoperation.Theexperimentsfullydemonstratethattheestimatemethodandthecriteriaarereliable,andmoreapplicablecomparedwiththeexistingsimilarmodelsandresults.
Keywords:mobilecomputing;joinquery;datatransmission;energyconsumption
0引言
近年来,移动计算环境逐渐成为分布式数据库技术新的研究和应用环境[1]。由于该环境的特殊性,一些传统的分布式数据库技术不能直接加以应用[2],例如查询、事务处理、数据库安全等。查询处理是移动计算中最基本、最常用的一项技术,连接是查询处理中最常用的、最费时间和空间的操作[3],也是引起网络通信代价升高的主要原因。因此,在移
动设备倍受电池能量、通信带宽、存储容量和处理能力等限制的环境下,合理选择连接查询处理模式至关重要。考虑到该环境中连接查询可能仅涉及到一台服务器和一个移动设备上
的关系,也可能涉及到一台服务器和多个移动设备上的关系,为了便于区分,我们将前者称为单连接查询,后者称为多连接查询。前者的研究不仅是连接查询处理研究不可缺少的一部
分,也是对后者进行研究的必要基础,因此,本文先仅讨论单连接的处理模式。目前,传统数据库中连接查询处理的研究已相当广泛,而
面向移动计算环境中的连接查询处理研究却非常少,文献[4,5]中总结了移动计算环境的三个非对称特征,即服务器和移动设备在计算能力上的非对称、移动设备在发送和接收信息时能量消耗的非对称以及移动设备处于活动和空闲状态时能量消耗的非对称,并将这些特征应用到连接查询处理的操作代价估算模型中。提出了连接查询处理的多种模式,以
前述估算模型为基础进行了性能比较。连接操作结果关系的大小估算采用文献[6]所陈述的方法,该估算方法使用到连接属性域值 这个参数,结果关系的大小估算尽管相当简单,但在实际应用中受到了一定的限制,因为:1)在某些情况下,
该值是根本无法确定或无法计算的;2)一个属性的域值并不能完全反映某一特定时刻其所在关系的实际状态,从而影响估算的可信度,进而影响了文献[4,5]所提估算模型的可信
度,以及各种处理模式的性能比较。考虑到操作代价估算的准确与否会直接影响到处理模式的选择,为了弥补这些缺陷,在估算连接结果关系时,我们采用了关系型数据库理论中查
询操作的结果关系估算思想,其所使用到的各参数值都会随着关系的改变而改变,特定时刻具有特定的值,相对而言可信度更高。此外我们补充了一个新的非对称特征,即移动设备
在将接收到的数据是否插入数据库时能量消耗的非对称,因为不同的连接查询处理模式对于接收到的数据有不同的处理,需要插入数据库时自然要消耗更多的能量,尤其当数据量很大或传输距离较短时,这一开销将是不容忽视的,所以这一第27卷第11期
2007年11月计算机应用
ComputerApplicationsVo.l27No.11
Nov.2007特征对于研究连接查询处理模式的能量消耗估算非常重要。我们提出一种新的面向移动计算环境的连接操作代价估算方法,并基于此,从数据传输量和能量消耗两个方面对单连接操
作的三种处理模式进行评估分析,推导出了更加实用的准则,以指导在特定系统配置下处理模式的选择,进而减少移动设备的能量消耗和数据传输量,降低网络通信代价。
1预备知识
1.1相关定义及性质设|R|表示关系R中的记录数,V(R,A)表示R中属性A不同取值的个数,A(R)表示R在属性A上的投影,Ri!Rj表示关系Ri连接Rj。考虑到移动计算环境下可以采用半连接操作来辅助完成连接查询,下面先给出半连接操作的相关定义。为了简化讨论,我们以等值条件查询为例展开研究,并假定当且仅当两个关系之间存在一个连接谓词时,它们的连接属性具有相同的属性名。其他情况可以类推分析。
定义1半连接操作。设关系Ri和Rj在公共属性A上进行连接操作时,定义Ri半连接Rj为:Ri∀Rj=Ri!(A(Rj)),定义Rj半连接Ri为:Rj∀Ri=Rj!
(A(Ri))。
性质1Ri!Rj=(Ri∀Rj)!Rj=(Rj∀Ri)!Ri。证明由定义1可知,(Ri∀Rj)!Rj=(Ri!(A(Rj)))!Rj,又根据连接操作满足结合律,得(Ri!(A(Rj)))!Rj=Ri!((A(Rj))!Rj)=Ri!Rj同
理,(Rj∀Ri)!Ri=Rj!Ri。性质1得证。性质2令Rij=Ri∀Rj,则|Rij|=(|Ri|#V(Rj,A))/max(V(Ri,A),V(Rj,A))。证明由关系型数据库理论可知:|Ri!Rj|=(|Ri|#
|Rj|)/max(V(Ri,A),V(Rj,A)),|A(Rj)|=V(Rj,A)。根据定义1,Ri∀Rj=Ri!(A(Rj)),性质2得证。性质3若V(Rj,A)
证明根据性质2,以及V(Ri,A)∃|Ri|,性质3得证。定义2可缩减操作。如果在一个关系上执行某种操作后,使得该关系的记录个数有所减少,则称该操作为这个关系上的一个可缩减操作。性质4当且仅当V(Rj,A)
系Ri上的一个可缩减操作。根据性质2、性质3和定义2,易证之。定义3可选因子。对于具有属性A的关系Ri,定义i,A=V(Ri,A)/|Ri|为Ri关于属性A的可选因子,i,j=
V(Rj,A)/V(Ri,A)为半连接Ri∀Rj的可选因子。定义4有用半连接。移动计算环境下,设服务器具有关系Ri,移动设备具有关系Rj,Ri和Rj在公共属性A上进行连接,如果一个半连接操作能够降低移动设备上的能量消耗,则
称这个半连接为有用半连接。定义5移动启动或MI有用半连接。设服务器具有关系Ri,移动设备具有关系Rj,如果半连接Ri∀Rj为有用半连接,则称之为移动启动或MI有用半连接。定义6活动/空闲模式[7]。若移动设备Mk参加执行连
接操作,当它在进行某种相关操作时,称它处于活动模式,反之当它仅处于等待状态或未进行任何相关操作时,称它处于空闲模式。1.2操作代价估算的相关参数为了简化叙述,下面给出了代价估算中使用到的相关参数及其描述。其中除eRC(R)、eIN(R)和eSD(R)三个参数外,其他
参数都可以从移动设备的规范或使用经验中估计出来[4],并且
为了方便讨论,假设所有关系上每个记录具有相同的大小。er:移动设备接收一个记录,并且不插入数据库所消耗的
能量;rIE:移动设备接收单位数据插入数据库与不插入时所消耗能量的比值;
rE:移动设备发送与接收(不插入数据库)单位数据所消耗能量的比值;
eRC(R):移动设备接收关系R,且不插入数据库所消耗的能量,其值为er%|R|;
eIN(R):移动设备接收R,并且插入数据库所消耗的能
量,其值为er%rIE%|R|;
eSD(R):移动设备发送关系R所消耗的能量,其值为er%
rE%|R|;
ttuple:服务器处理单个记录所消耗的时间;rSM:服务器与移动设备处理能力的比值; :移动设备处于空闲模式时,单位时间内消耗的能量(即
空闲能量系数);
r :移动设备处于活动模式与空闲模式时,单位时间内消耗能量的比值;
dt:连接处理所引起的数据传输量;EC:连接处理所引起的能量消耗量;TS(Ri!Rj):服务器上执行连接操作Ri!Rj时所需要的