数据流管理系统计算聚集查询结果保存在内存中形成流数据方（StreamCube），提供快速、精确的在线OLAP查询。有限的内存空间需要一种有效的存储方法来存储更大时间窗口的流数据方。提出一种基于QC-Tree结构的流数据方StreamQCTree生成、裁剪及查询方法。将QC-Tree结构中上界集划分为基本上界类和附加上界类;并分析附加上界类的成本计算模型;根据该模型在固定存储空间下，采用动态选择物化结点的方案选择物化部分附加上界类，使对StreamQCTree的平均查询响应时间最小。实验表明，StreamQCTree能够有效地访问数据方且获得较好的压缩效果。
142 2011,47(19) Computer Engineering and Applications计算机工程与应用 (3) StreamQCtree中每个节点包含一个附加值cost,表访存次数为Cm(UB)。物化上界UB的收益率为Bm 示检索节点的成本。对于物化节点,成本为1;非物化节点,表 B.=P×- (C(UB )-Cm(UB)) 示为在聚集查询时,访问其后续节点的时间。 (4)所有的非物化节点不存储其度量值 B是个对比值,可以评价UB,相对于其他上界的物化收 如性质2所述,部分上界类中的节点及其边或链接可从益,以评价并选择最佳的附加上界类物化,达到最低的平均查 StreamQCTree删除,并非像PMC中保留所有上界而只未物化淘响应时间 部分节点。如图2例所示,PMC结构中如果设后续节点链接32动态选择方案 数阈值为2,则节点I将不被物化;而 StreamQcTree将去除上 查询概率在用户未预先给定的情况下较难以确定。动态 畀C6,即节点11及其相连的边及链接(图中虚线部分)。这选择方案思想类似最近最少使用原则(LRU),收集用户对流 样,如果未物化上界C6,查询(*,M1,?)将扫描所有时间维子数据方查询集来推断最近将要执行查询的概率。静态历史数 树中节点。 据库的动态选择方案是全局物化节点(或视图)的调整,而流 如果查询附加上界类的值,需要在树中检索涉及的节点,数据方的动态选择方案是时间窗口内物化节点(或视图)的选 最差情况需要扫描整个树。如果某个节点成本cost很大,则需择。根据公式(2)可以计算出每个附加上界类的收益率,从而 花费较长时间来检索该节点的值。为了避免这种情况发生,选择物化最佳的上界集。 在物化过程屮尽量挑选这些节点物化。如何选择这些需要物 算法1 DynamicSelectUpper Bound( 化的节点,以获得最少的用户平均查询响应时间。下一章中 HHuA Current Query g, remained memory Mad, Query Set V 将阐述如何选择物化节点集的方案 StreamQCTree sqt(with only basic upper bound ) additional upper bound set vuh 3物化节点选择方案 输出 revised StreamQCTree syt Description: 3.1成本计算模型 定理1在 StreamQctre中未物化所有附加上界类也可得 V={}; 到正确的查洵结果。 Tor each a in v do 证叨根据基本上界类定义可知, StreamQCTree中基本上 P=count(q)/count( r) //Caculating each g's probability 界类概念层次最低DB,所有概念层次较高的查询都可在该概 End for ④念层次抽象。OLAP查询是各维的任意概念层次的组合,这些 For each v in do 都可以通过DB获得査询结果。所以,附加上界类未物化都可 Scarch sct I for qucrics q that v can answer 从基本上界类(DB)中所得正确的查询结果。 Prall gs probability; StreamQcTree中,完全物化所有上界类查询成本最低,存 B,hiv)=P,x(Cm(UB, )-Cn (UB. ))/Maud: End for 储成本最高。根据定理1,保留基本上界类,部分物化使用固 For cach y in l do 定的存储空间获得尽可能低的查询成本。 y′Max(Bm(v)) 设数据方有D个维,数据方存储分配m个存储单元,数据 =1a-p; 方时间窗口W,数据流滑动窗口s。每个数据方时间切片分配 if (S=S-M>0)then 内存空间M=m*s!W。设基本上界类总共占内存Ma。附加上 add v into sat 界类可使用空间为:Mm=M-Mbs End for 单个附加上界类存储成本。设指针存储占P,维标记存储 占La,度量值存储占Me,其后续节点数为coto如果增加一个4 StreamQCTree更新及查询 附加上界类,将増加存储空间为 41更新算法 Maua=cost×P+Me+x×a (1) 更新算法中,数据流不断到达,因为每个时间间隔△将生 其中x表示上界的维标记数,确定该值般为该上界的维标记成一个该数据方时间切片的QCef树。更新只需要将该T 序列中第一个*后维标记的个数,0<xm):例如,上界C4中第时刻的子树添加到 StreamQCtree的Ro节点。 个*后为E1,x=1,上界C1中第一个*后无维标记,x=0。 删除只有一种情况,出时刻T数据方时间切片在内存中过 查询成本为访问树中节点数。设完全物化访间成本期,将该子树从内在中删除。只要将该 QC-tree树内释放 Cm。在完全物化的树层次为D,因为直接可以在树中单个节并去掉Ro0指向子树的指针。 点检索到结果,所以1sCmD。附加上界类未物化的查询成42查询算法 本与第一个较高概念层次高(即维标记*)有关。节点如果第 杳询算法类似于QC-tre的杳询算法,因为部分节点未物 -个*在第层,会增加第-1层维标记的子树中基本上界类化,所以在查询涉及到未物化节点时会产生查询异常。在定 的节点访间数。例如,查询为(*,M,),C6上界类未物化(即位查询异常之后根据异常所处树的层次来确定第1-1层需 节点11及其相关链接),第一个*在第1层,需要扫描1-1-0层要访间的树中基本上界类节点,即函数 traverBUB() 的维标记Root的子树中所有基本上界类包含维标记M1的节 算法2 TravcISQT( 点,节点数为5;查询为(*,*,E1),删除上界类C4时,节点数为8 输入 Query y, StreanlQCTree syt 对丁任意附加上界UB,若在查洵集中访问UB在树中节 输出 result of quer 点概率为P,已物化UB的访存次数为Cn(UB),未物化UB的 Description: 廿亮,刘东红,贾焰,等: StreamQCTree:一种流数据方压缩结构 2011,47(19)143 ST=parse(q);//parse g, S[i] is ith dimensions label For each i in D dimension do StreamQCTree-ND StreamQCTree-D if traver(sqt, s[i])found then 801- QC-Trcc sqt=sgt->s[; /if the ith label found i/sqt replaced by his child tree with s[i If i equal to d then getresult(); 605044 Next i: /next i+lth label 35 eIse 30 traverBUB(sqt, i, s[); /if label not found, traver BUB break Number of dimension End for 图4查询响应时间对比 Rcturn result 分配固定大小存储空间,因此,维数越多节约空间越多, Function traverBUB(Sqt, i, s[) StreamQCTree相对QC-Tre进一步压缩了内存占用空间。 Description: For each BUB label at ith layer in sqt tree do 另外,如图4所示, StreamQCTree-D采用了动态选择方案 For计+ I to d do 选择部分物化树中节点,该方案物化查询频率最高的树中节 ver(sq,[+1]); ,尽量裁剪查询频率低或未查询到的树节点,相对QC-Tree If i equal to d then 的查询响应时间差距较小,降低较小查询性能。 StreamQC- esult’= getresult(); Tre丶ND采用静态选择部分物化的方案,未根据查询需求裁剪 End for 树节点,相比QC-Iree杳询响应时间差距较大,当流数据方维 result-fun(result); //fun is sum(), count(), or avg() 数增多时,查询的响应时间差距增大。 End for 因此,采用功态物化方案的 Stream octree相对QC-lre 5实验结果 在降低部分查询性能获得较高的数据压缩率。对于存储于内 实验中算法采用C++6.0实现,运行环境是安装Win- 存中的 Stream Cube是一种高效的压缩方法 dows XP Professional的PC,硬件配置为Core2Duo1.60GHz 处理器,160GB硬盘,2GB内存。假定数据流上的元组在时6结束语 间维上是均匀分布的,每个时刻T有 Delta size个元组到达,元 -Iree是一种有效压缩数据方的树形存储结构,但是对 组在其他维度上服从Zipf分布。 于保存于有限内存中的流数据,仍需进·步压缩存储空间。 数据共有6个维度(不包括时间维度),每个维度的基数 StreamQCTree是基于QC-Tree结构的多维数据流立方体 cardinality)均为100,数据方时间窗口W=10,Zjp/(acor=框架,采用查洵时间换空间的方法裁剪树中节点,将完全物化 1.2),每个时刻T有 Delta Size=100k个新元组到达,总共分配数据方树结构QC-Tree修改为部分物化的 StreamQCTree并 200MB内存空间,每个时刻片分配内存10MB。随机点查询通过分析建立成本计算模型,提出动态选择方案选择部分物 中有80%的查询访问其中20%的成员(80-20分布),统计化树中节点 000×10次所需查询响应时间。 实验结果表明, StreamQCTree通过减少大量树中节点,更 实验采用了三科流数据方存储结构的查询时间对比分别有效地压缩存储空间,并仍能快速、精确回答在线OLAP查询。 是:1 Stream QCTree-ND,未采用动态选择方案的 Stream OCTree (2) StreamQCTree-D.用动态选择方案的 Stream Octree:参考文献: (3)QC-Tree。如图3所示, StreamQCTree对比QC-Tree的内存 空间占有量。图4表示查询统计所有查询的响应时间总和的HanJ, Chen y, Dong G, et al. stream cube: An architecture for multi-dimensional analysis of data streams[J]. Distributed and 对比。 Parallel Databases, 2005,18(2): 173-197 [2 Harinarayan V, Rajaraman A, Ullman J D Implementing data StreamQCTree 60 QC-Tree cubes efficiently[C]pRoc of the 1990 ACM SIGMOD Interna tional Conference on Management of Data. Montreal, Canada 50 ACM,1996:205-216 [3 Lakshmanan L, Pei J, Zhao YQC-trees: An efficient summary 30 structure for semantic OL AP[C]//Proc of the 2003 ACM SIG 20 MOD International Confcrencc on Managcmcnt of Data. Califor nia:ACM,2003:64-75 Number of dimensio 图3内存空间占用对比 [4] Wang W, Lu H, Feng J,et al. Condensed cube: An effective ap- proach to reducing data cube size[C]/pRoc of the 2002 Interna 实验结果验证了 StreamQCTre的压缩方法的有效性。如 tional Conference on Data Engineering, San Fransisco, CA, 2002 图3所示,由于QC-Tre的存储空间随维数增加而增长 155-165 Stream octree采用时间片的存储模式,为每个时间片数据方 (下转185页