基于星型模式的一个多路top-k join算法

top-kjoin查询返回用户最感兴趣的k个连接结果.近来top-kjoin已经成为一个重要的研究课题,且在Web数据库、信息抽取和数据挖掘中均有应用.星型模式的数据仓库在实际应用中也存在top-kjoin查询,如有时决策者只想查询星型连接结果中他最感兴趣的k个.然而,现有top-kjoin算法不适合星型模式.为了在星型模式上有效地支持top-kjoin查询,文中提出两类索引并基于这两类索引提出一个适用于星型模式的多路top-kjoin算法.该算法通过采用一个比现有算法更优的上界和一个剪枝策略获得了更高的效率.此外,实验也表明文中的算法比现有算法效率更高.

一种基于向量索引的内存OLAP星型连接加速新技术

星型连接是OLAP中重要的操作,事实表与维表基于星型连接执行多维分析处理.星型连接的性能取决于连接性能.当前研究主要集中在如何在不同的处理器平台上优化哈希连接性能,然而如何获得最优的哈希连接参数或实现是一个复杂的问题.哈希连接不依赖于模式的语义信息,然而却可以在事实表与维表之间通过维映射特征进一步优化连接性能.该文提出了一种新颖的面向OLAP负载的向量索引以提高事实表与维表之间的连接性能.从模式的角度来看,维表可以映射为向量索引,每一个事实表记录可以直接映射到向量索引上的相应位置,无须执行基于值匹配的哈希连接操作.从实现技术的角度看,向量索引是一种位图索引、字典表压缩、主外键参照完整性约束和连接索引相结合的技术.系统化的设计使向量索引可以扮演多种角色:(1)向量索引与位图索引类似起到过滤作用;(2)向量索引相对于只存储0或1的位图索引使用更多的位来表示更多的信息;(3)映射或创建自动增长的主键作为向量索引地址并且更新相应的外键,将主外键参照完整性约束转换为向量参照约束;(4)外键连接操作简化为通过外键值引用向量单元.基于向量索引,OLAP中代价大的星形连接可以抽象为向量索引计算,OLAP查询可以简化为基于向量索引的单表扫描处理.向量索引简化的设计不仅可以提升性能,而且降低了在GPU平台实现的复杂度.本文首先讨论了向量索引机制和如何在数据库中应用向量索引;然后设计向量索引更新机制,以保证在更新时向量参照约束;最后提出基于向量索引的OLAP框架来提高内存数据库OLAP性能.基于向量索引的星型连接可以用作GPU上的OLAP加速器,使CPU可以将计算密集型负载转移到高性能GPU平台来加速OLAP处理.实验结果表明向量索引更新代价较低,而向量引用性能收益较大.更重要的是,向量索引支持OLAP中的星形连接操作在内存数据库引擎之外进行加速,降低了内存数据库的CPU负载,或者将星形连接负载通过硬件级加速器,如GPU进行加速.基于向量索引的星型连接可以显著提升CPU和GPU平台上的星型连接性能,相对于内存数据库Vector,在SSB Q4.1查询可以获得最大3倍的性能提升,平均性能提升了1.2倍.

内存OLAP多核并行查询优化技术研究

随着以大内存和多核为代表的计算机硬件技术的发展,以cache-conscious算法为中心的查询优化技术逐渐转向以multicore-conscious为中心的查询优化技术,来提高多核处理器的并行处理性能.该文的研究目标是具备复杂星型连接特点的联机分析处理OLAP技术,以查询执行代价最大的星型连接为研究对象,提出同时满足cache-conscious和multicore-conscious的多核并行连接算法DDTA-MPJ.该算法包括基于事实表水平分片和维属性列共享访问模式的查询内多核并行算法IntraDDTA-MPJ、基于QuerySlots的查询间多核并行算法InterDDTAMPJ以及中位数多核并行算法Median-MPJ.实验结果表明该算法具有良好且稳定的并行查询处理性能,线性查询处理模型能够更好地利用多核处理器的先进性能.

S_m∨P_n的邻强边染色

为了解决图的邻强边染色问题中一个图的色数算法问题,通过特别的方法来记图的染色过程,同时分4种情况讨论了星和路联图的邻强边染色问题,指出在染色过程中给定的4种情况的染色方法各不相同,并通过对图的着色得到了星和路联图的邻强边色数.

关于W_m∨S_n的均匀全染色

对一个正常的全染色满足各种颜色所染元素数(点或边)相差不超过1时,称为均匀全染色,其所用最少染色数称为均匀全色数.就轮Wm与星Sn的联图Wm∨Sn,得到了在m,n不同取值情况下的均匀全色数.

数据仓库查询处理中的一种多表连接算法

在进行数据仓库的 OLAP( online analytical processing,联机分析处理 )查询处理时 ,经常会涉及到多表连接操作 ,因此 ,提高多表连接的性能就成了数据仓库领域的关键性问题 .基于数据仓库的星型模式 ,给出了一种新的多表连接算法 ( M- Join) .与传统关系数据库管理系统的多表连接查询处理相比 ,该算法充分考虑了数据仓库中的数据本身和多表连接的特点 ,采用对多个表进行一次性连接的方法 ,使得查询的性能有明显的改善 .同时 ,还给出了算法的实验结果和分析 .

关于C_m·S_n和C_mΔS_n的全染色

设m≥3,n≥2V(Cm.Sn)={ui|i=1,2,…,m}∪{vij|i=1,2,…,m;j=1,2,…,n},E(Cm.Sn)={u1u2,u2u3,…,u(m-1)um,umu1}∪{uivij|i=1,2,…,m;j=1,2,…,n}则称Cm.Sn为m个Sn(星)的心联图.V(CmΔSn)={ui|i=1,2,…,m}∪{vij|i=1,2,…,m;j=1,2,…,n},E(CmΔSn)={v11v21,v21v31,…,v(m-1)1vm1,vm1v11}∪{uivij|i=1,2,…,m;j=1,2,…,n}则称CmΔSn为m个Sn(星)的沿联图.本文给出Cm·Sn和CmΔSn全染色以及全色数.

P_m∨S_n的邻点可区别全染色

把星{u0,u1,u2…,un}中的每一个点与路{v1,v2,v3,…,vm}中的每一个点相连,得到路和星的联图,记为Pm∨Sn.本文给出了PmVSn的邻点可区别全色数.

圈与星的联图的邻点可区别全色数

对于一个正常的全染色,相邻点满足顶点及其关联边染色色集不同的条件时,称为邻点可区别全染色,其所用最少染色数称为邻点可区别全色数。就圈Cm与星Sn的联图Cm∨Sn,得到m,n任意取值下的邻点可区别全色数。

关于C_m∨S_n的均匀全染色

对一个正常的全染色满足各种颜色所染元素数(点或边)相差不超过1时,称为均匀全染色,其所用最少染色数称为均匀全色数.就圈Cm与星Sm的联图Cm∨Sn,得到了在m,n不同取值情况下的均匀全色数.

两类非连通图(P_2∨■)(0,0,r_1,0,…,0,r_n)∪St(m)及(P_2∨■)(r_1+a,r_2,0,…,0)∪G_r的优美性

对自然数n,m,i∈N,设Ki表示i个顶点的完全图,■表示Kn的补图,St(m)表示m+1个顶点的星形树,Gr为有r条边的优美图,Pn为n个节点的路,P2∨■是P2与Kn联图。给出了非连通图(P2∨■)(r1,r2,0,…,0)∪St(m)及(P2∨■)(r1+a,r2,0,…,0)∪Gr的定义,并论证了当n≥2时,这两类图都是优美图。

关于C_m∨C_n和C_m∨S_n的点可区别边色数

对图G的正常边染色,若满足不同点的点所关联边色集合不同,则称此染色法为点可区别的边染色法,其所用最少染色数称为该图的点可区别边色数.本文得到了Cm∨Cn和Cm∨Sn的点可区别边色数.

联机分析查询处理中的一种聚集算法

联机分析处理(online analytical processing,简称OLAP)查询是涉及大量数据的即席复杂查询,从SQL(structured query language)角度来看,这些查询通常都包含多表连接和分组聚集操作.从OLAP查询处理角度出发,提出一种新的基于排序的聚集查询算法MuSA(sort-based aggregation with multi-table join).该方法充分考虑到数据仓库星型模式的特点,将聚集操作和新的多表连接算法MJoin相结合,排序时采用关键字映射技术对排序关键字进行压缩,从而可以显著地提高排序速度.此外,通过预先估计聚集分组的数目,优化选择不同的排序方法,使得算法对不同的分组聚集查询都进行优化.算法实验数据表明,这种聚集查询算法与传统的聚集查询处理方法相比,其性能有显著的提高.

图Pm∨Sn的邻强边色数

对一个正常边染色满足相邻点的色集不同,称为邻强边染色,其所用最少染色数称为邻强边色数。就路Pm与星Sn的联图Pm∨Sn,本文得到了在m,n不同取值情况下的邻强边色数。

图S_m∨S_n的均匀全色数

一个全染色满足||Ti|-|Tj||≤1时称为均匀的,其中|Ti|为染第i种颜色的元素数,所需最少染色数称为均匀全色数,记为χet(G)。文中得到了Sm∨Sn的均匀全色数。

K_(1,m)∨P_n的均匀全染色

对一个正常的全染色满足各种颜色所染元素数(点或边)相关不超过1时,称为均匀全染色,其所用最少染色数称为均匀全色数.就星K1,m与路Pn的联图K1,m∨Pn,得到了在m,n不同取值情况下的均匀全色数.

图S_m∨W_n的点可区别边色数

对图G的正常边染色,若满足不同点的点所关联边色集合不同,则称此染色法为点可区别的边染色法,其所用最少染色数称为该图的点可区别边色数。研究得到了Sm∨Wn的点可区别边色数。

一类多重联图的邻点可区别E-全染色

设G(V,E)是一个简单图,k是一个正整数,f是一个V(G)UE(G)到{1,2,…,k}的映射.如果(?)u,υ∈E(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),其中C(u)={f(u)}U{f(uv)|uv∈E(G)}.称f是图G的邻点可区别E-全染色,称最小的数κ为图G的邻点可E-全色数.本文给出了星、路、圈间的多重联图的邻点可区别E-全色数.

基于列存储机制下多维数据仓库模型的优化与研究

通过对分布式列存储机制下多维数据仓库模型的研究,考虑到多维数据仓库模型上的关联和聚集操作常常会引入大量的数据迁移,提出一种有效的列存储机制下多维数据仓库模型的优化方法即结合层次编码技术。采用维表层次全局域编码和维表层次局部域编码相结合的方式对传统星型模型维表中的层次信息进行二进制编码整合,将维表的层次信息压缩进事实表形成无连接星型模型,并针对新模型下的数据特征提出一种复合压缩策略,以期减少分布式列存储机制下的OLAP操作引入的数据迁移并降低数据存储空间,提升系统的查询性能。实验结果表明,该优化方法是可行且有效的。

W_6×S_n的交叉数

早在20世纪50年代,Zarankiewicz猜想完全2-部图K_(m,n)(m≤n)的交叉数为[m/2]×[(m-1)/2]×[n/2]×[(n-1)/2](对任意实数x,[x]表示不超过x的最大整数).目前这一猜想的正确性只证明了当m≤6时成立.假定著名的Zarankiewicz的猜想对m=7的情形成立,确定了6-轮W_6与星S_n的笛卡尔积图的交叉是cr(W_6×S_n)=9[n/2]×[(n-1)/2]+2n+5[n/2].