查询算法（精选八篇）
查询算法 篇1
不确定数据通常采用概率数据模型的方式进行描述, 这种模型对每个元组附加一个概率值来表示该元组的可靠程度。概率数据模型[1]不仅可以对关系数据模型无法描述的不确定数据进行描述, 而且可以描述关系数据模型所能描述的确定的数据。对概率数据库进行的查询称为概率查询。
如图所示, 下图中有两个关系表, 每一个关系表中都有一个概率属性, 说明了该元祖发生的概率。
本文尝试利用概率统计的知识, 利用足够精确的代价计算方法探讨这种信息转换过程, 并利用正确抽取数据元素特征方法减少代价计算成本, 希望能有效降低这种转换代价和由此产生的误差。
1 算法概述
现在假设一个聚类代表一个实体, 当这个聚类中的实体的概率为1的时候, 该聚类的元组发生是相互独立的, 该元组发生的几率就是必然发生了;反之若元组的概率为0的话, 该元组就是必然不发生。这两种情况先不研究。
首先, 在这里, 我们把一个元组的属性分成这四种属性:主属性, 特征属性, 动作属性, 概率属性。其中, 主属性就是区分关系表中不同对象的属性, 比如账号, 代号;特征属性就是伴随主属性而唯一确定的属性, 如姓名, 表2中的行为属性, 这种属性由主属性唯一确定, 如11002001对应的唯一姓名属性就是张三。动作属性就是该元组对象的不同动态行为, 如存款, 取款等, 相同的主属性可以有不同的动态属性;概率属性就是描述该动态对象在某一时刻、地点的动态行为。
使用了这种动态属性之后, 该关系表就不是传统关系意义上的简单对象, 而是动态对象 (包括动态对象本身和动态的对象属性) 的一个事件连同其发生的概率了。该关系表描述的是一个事件的发生概率, 不同的行为描述的是不同的概率, 同一事件不允许出现在同一关系中。
其中, 数据库的概率查询可以分为两个方面: (1) 数据库操作的概率化, 根据相应条件, 计算每个元组发生的概率; (2) 查询语句的概率化, 通常需要在数据库查询过程前增加相应的语义分析, 这里主要包含两类情况, 一类是直接含有概率条件的查询语句, 如列出“行为=′存钱′”且选择概率大于等于0.7的账号, 其SQL语句如下。
账号行为=′存钱′∧ (概率) =0.7) (Π (账号, 行为, 概率) (表1) )
那么综合表1和表2的数据, 我们可以得知账号为的张三存款金额为11002001元的概率是0.8×0.6=0.48。
这是一个简单的例子, 但是给了我们一个很好的启发, 对于一些简单的概率查询有了一个一般性的思路。
2 算法实现
根据概率学上的全概率公式。
P (B) =P (B|A0) P (A0) +P (B|A1) P (A1) +…+P (B|AN) P (AN) , 其中P (B|AN) 是B在AN下的影响的概率, P (AN) 是AN发生的概率。
我们可以对照前面两个表进行类似的分析, 比如我们要求账号为11002001, 存款金额为5000的元组信息。我们可以从第一个表中得知账号为11002001存款的概率为0.8。我们记事件A1为“11002001存款”, 那么事件B“存款金额为5000”, 从而可以得到了11002001存款金额为5000元得概率是0.8×0.6=0.4 8.
由此, 我们可以写出一个查询式子。
Select distance账号, 金额, sum (a..概率*b.概率) f rom表1a, 表2b, w here a..账号=b.账号。
简单来说, 这种算法的思路就在于把符合要求的元组进行简单连接, 然后将相应的概率相乘, 然后将符合相同条件的元组相加。
3 结语
传统的关系模式已经不能很好的适用于对不确定性信息的处理了。本文通过对概率论的基础知识进行处理, 给出了对多表的一种简单的查询处理。这种新型的数据库能够对确定性数据和不确定性数据进行同时处理。
参考文献
[1]刘波, 雷刚跃, 杨路明, 等.非一致性数据概率查询策略与算法分析[J].
[2]袁鼎荣, 严小卫, 陈宏朝.一个新的概率数据模型[J].计算机应用研究.
[3]李石君, 谭成予, 刘海青, 等.一种概率关系数据库系统[J].
[4]李俊丽.概率算法及其算法研究[J].
[5]Barbara D, Garcla-Molina H, Porter D.The Management of Probabilistic Data[J].
[6]P.Barcelo, L.Bertossi.Logic programsfor querying inconsistent databases[J].
XML查询的结构连接算法 篇2
关键词：XML； 结构连接； B+树； 查询优化
中图分类号：TP311.131
文献标志码：A
Structural join algorithm in XML query
HUANG Yuan, YANG Weiwei
(College of Computer & Tech., Huazhong Univ. of Sci. & Tech., Wuhan 430074, China)
Abstract： With the defects in most XML structural joint methods that the temporary sorting for input data and creating index costs decrease the performance too much if the input element set does not have indexes, or is out-of-order, the classical Stack-Tree-Desc algorithm and B+ tree index optimization algorithm are analyzed. A novel strategy that isn’t limited to any external index is proposed and implemented. The experiment results indicate that it outperforms Stack-Tree-Desc algorithm.
Key words： XML; structural join; B+ Tree; query optimization
0 引 言
XML已成为Web上信息表示和数据交换的国际标准.由于XML数据自身的特点，XML文档一般用树结构表示.而为了方便查找，还要对树中每个节点进行编码.最为普遍的编码方案为基于四元组的区间编码方案[1]，即(DocId，Start，End和Level)，其中：DocId为XML文档的标志符，对于同一文档中的节点而言，DocId是一样的；Start和End是文档节点的开始和结束位置；Level是文档节点的嵌套深度(层号).采用这种标注方法易于判定两节点之间的结构化关系.
(1) 祖先—后代关系：给定两个节点N1=(DocId1，Start1，End1，Level1)和N2=(DocId2，Start2，End2，Level2)，当且仅当DocId1=DocId2，Start1 (2) 父—子关系：当且仅当N1和N2都满足祖先—后代关系，且L1+1=L2时，N1是N2的父亲节点. 为了方便文档的插入删除操作，一般编码标注的Start和End值并非连续，而是留出一定的空间以便更新文档.[2]图1即为一个采用此编码方案的XML文档(省去了DocId和Level). 1 结构连接算法分析 1.1 结构连接的概念与基本算法思想 文献[3]提出结构连接的概念：对于从查询语句表达式中分解的一个二元关系(a,d)(祖先—后代关系)，文档中与a匹配的点集A={a1,a2，…，an}为潜在的祖先节点集，与d匹配的点集D={d1,d2,…，dm}为潜在的后代节点集，A和D均按其中节点Start值的增序排列.以A(潜在的祖先节点集)与D(潜在的后代节点集)为输入进行匹配而得出的结果集为Out={(ai,dj)|ai∈A&dj∈D&(ai,dj)满足祖先—后代关系}. 文献[3]同时也提出基于栈的结构连接算法Stack-Tree-Desc，其基本思想为：若ai∈A为dj∈D的祖先，则将ai压入一个栈中并将其与dj匹配输出到结果集，如果不是，则将其出栈，这样顺序遍历A和D，直到得出所有的匹配结果为止.Stack-Tree-Desc算法只需遍历A和D各一次，且利用一个栈来减少联接次数，中间结果减少，效率较高. 1.2 B+树索引的结构连接算法 由于Stack-Tree-Desc算法需要遍历A和D中每一个元素，有一些多余的操作，文献[4]对XML文档采用B+树索引来优化算法. 图2是对应图1元素的B+树. 图 2 B+树 利用B+树自身的特点而得出的基于B+树索引的结构连接算法. 算法1： (1) a,d分别指向队列A和D的第一个元素； (2) while(a<>Endof(A) and d<>Endof(D)) do； (3) if (a是d的祖先) then； (4) 在列表A中找出所有d的祖先并压入栈中； (5) 让a指向压入栈中的最后一个元素； (6) 将d与栈中的元素依次成对输出成祖先—后代对，但不引发退栈操作； (7) d指向列表D的下一个元素； (8) else if (a.End (9) 弹出栈中所有在d之前的祖先元素； (10) 令l指向最后弹出的祖先元素； (11) 让a指向列表A中Start值大于l.End且其值最小的那个元素； (12) else /*a在d的后面或a是d的后代*/ (13) 将d与栈中元素依次成对输出成祖先—后代对，但不引发退栈操作； (14) if (栈为空) then； (15) d指向列表D中Start值大于a.Start且其值为最小的那个元素； (16) else； (17) d指向队列D中下一个元素； (18) end if； (19) end if； (20) end while. 算法1开始时，变量a和d被赋予两个列表的第一个元素(具有最小Start值)，然后算法将a和d向前推进即置为列表的下一个元素,并执行连接直到某一个列表为空.算法的(11)和(15)步利用B+树索引跳过列表A和D中不必要的元素. 2 优化策略及算法 算法1利用索引跳过A和D中不必要参与连接的元素，从而达到效率优化.就A列表来分析，其实质是从A中快速找到下一个是dj∈D的具有最小Start值的祖先节点而避免对列表中元素的一一遍历，而算法1借用B+树索引完成这一过程.由于对B+树索引进行维护需要额外的时间和空间开销，受算法1启发，提出一种不依赖于特定索引结构的优化算法. 算法2： (1) a,d分别指向队列A和D的第一个元素； (2) while(A和D非空或者栈非空) do； (3) if ((a.Start>Stack→Top.End))&&(d.Start>Stack→Top.End)) then； (4) 元素出栈； (5) else if (a.Start (6) 将a所指元素压入栈中； (7) 将a指向后面的某一元素，此元素是d或者d的下一个元素的祖先元素； (8) else； (9) 将栈中所有元素与d进行匹配，并输出到结果集； (10) if (栈为空) then； (11) d指向后面的某一元素，此元素是a或者a的下一个元素的后代元素； (12) else； (13) d指向D中的下一个元素； (14) end if； (15) end if； (16) end while. 在算法2中，第(7)步和第(11)步为优化的关键步骤，即通过这两步跳过不必要的节点，快速定位达到优化效果.下面要解决具体的定位策略问题.由于A和D中的元素均按其Start值的增序排列，即A和D都是静态有序表；这样，问题实质上就可以转化为静态有序表的查找.基于此，提出一种分块查找策略，即对列表中元素按间隔分块，每比较一次后向后跳过δ个元素(即块长)再进行比较，若查找出元素在某一个块中，则在此块中进行顺序查找，δ为跳跃因子，可根据队列大小进行定义.以算法2中第(7)步查找A中下一个进行连接的元素为例，列出其算法。 算法3：FindNextA() /*输入为当前的a和d，输出为符合条件的anext*/ (1) pre=a+1; post =pre (2) while (post (3) if (post.End (4) pre= post ; post = post +δ (5) else (6) for(anext=pre+1; anext<= post; anext++) (7) if ((anext→pre.End (8) return anext (9) end if (10) end if (11) end while 在列表长度比较大时，可以适当将跳跃因子的值设大，即将块的大小设大.若块大到一定程度，在块中使用顺序查找势必不够优化，此时可将大块再分成小块，将算法3嵌套使用，此处不再列出具体算法.而算法2中第(11)步查找D中下一个进行连接的元素的算法FindNextD()与FindNextA()相似，限于篇幅，也一并省略. 3 试验设计及结果分析 试验平台：Intel P4c 1.7 G，256 M RAM，Win 2000+sp 4，Java程序，Jdk1.5 试验数据来源于在前人工作中被广泛用于实验的IBM XML数据生成器(IBM XML data generator).分别测试3种情况下Stack-Tree-Desc算法以及算法2结合算法3的时耗.3种情况分别为： (1) A.length=50 000，D.length=100 000 (2) A.length=100 000， D.length=100 000 (3) A.length=200 000， D.length=10 000 3种情况下跳跃因子δ均设为10.为便于表示，将Stack-Tree-Desc算法简写为STD，将算法2结合算法3称为结合算法. 图 4 试验结果 从图4中可以看出，改进后的结合算法比起Stack-Tree-Desc算法总体上有较大的性能提高，当A与D的长度差距增大时，性能的提高幅度也在增加，特别是在情况(3)所示的A的长度远大于D时，性能提高尤为明显. 4 结束语 结构连接是XML查询处理的核心操作，已受到关注和研究.[5]高效的算法是高效查询处理的关键，目前已经提出许多结构连接的算法，包括各种计算祖先／后裔关系(含双亲／孩子关系)结构连接的直接归并结构连接算法、基于缓存的归并结构连接算法和twig模式结构连接算法，以及计算文档位置关系的结构连接算法等.它们中的大多数都基于如下的前提条件之一：输入元素集合存在索引或者有序，当这些条件不成立时，由于对输入数据临时排序或建索引的代价，这些算法的性能会大大下降. 本文在研究、分析经典的Stack-Tree-Desc算法思想和使用B+树索引的优化算法基础上，提出一种改进的不局限于索引结构的查询优化策略，并给出算法实现.试验结果表明改进后的算法较Stack-Tree-Desc算法具有更高的查询效率. 参考文献： [1] LI Q, MOON B. Indexing and querying XML data for regular path expression [C]//Proc 27th International Conference on Very Large Database, 2001. [2] SHASHA D, WANG J T L, GIUGNO R. Algorithmics and applications of tree and graph searching [C]//Proc ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database System. Madison, Wisconsin, 2002: 39-52. [3] KHALIFA S A L, GADISH H V, KOUDAS N, et al. Structural joins: a primitive for efficient XML query pattern matching [C]//Proc 18th International Conference on Data Eng. Los Alamitos: IEEE Computer Society Press, 2002: 141-152. [4] CHIEN S Y, VAGENA Z, ZHANG D, et al. Efficient structural joins on indexed XML documents [C]//Proc 28th International Conference on Very Large Database, 2002. [5] WU Y, PATEL J M, JAGADISH H V. Structural join order selection for XML query optimization[C]//Proc IEEE Data Engineering, 2003. “本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文” 方便快捷的公交查询服务, 是一个城市现代化程度的标志.目前的公交查询系统存在三方面的不足:其一是在公交查询设计时没有充分考虑乘客的各种需求[1,2,3,4,5,6,7];其二是没有考虑地铁和步行出行方式[1,2,3,4,5,6,7];其三是计算换乘次数的效率低, 无论是广度优先还是深度优先, 都是基于穷举搜索法[1,2,3,4,5], 一般只能提供换乘两次以内的查询, 这样不能适应城市快速发展的趋势和各种查询需求。特别是, 如果要与现代通信相结合, 让人们在任何时间、任何地点都能及时地获得可视化的最佳公交信息, 更是需要查询的高效性。 本文首先对乘客的查询需求进行了全面分析, 然后利用最优直达矩阵对初始公交线路信息进行预处理, 并利用直达矩阵是一个典型的稀疏矩阵的特点, 将大型直达矩阵转化为用十字链表表示, 将矩阵的换乘运算转化为链表的交集运算, 设计了实用高效的城市公交查询快速算法。 1 城市公交查询需求分析 在设计城市公交查询时, 必须了解公交乘客出行时所考虑的因素, 通过对公交乘客的出行心理和行为的研究来设计高效的公交查询系统。根据在南京市做的一个公交乘客出行心理调查统计结果显示, 公交乘客主要考虑以下几个因素: (1) 换乘次数最少, 是指乘客在完成一次出行过程中所换乘公交的次数 (含公汽和地铁) ; (2) 出行时间最短, 是指乘客在完成一次出行过程中所用的总时间 (包括乘车时间、等车时间、换乘时间、步行时间等) ; (3) 出行费用最少, 是指乘客在完成一次出行过程中所花的总车费。 除此之外, 为了满足乘客的不同需求, 还应该考虑以下因素: (1) 是否步行距离最短优先; (2) 是否地铁优先; (3) 是否景观道路优先; (4) 是否空调车优先等。乘客可根据自己的情况进行选择和自主定义优先级, 这样可以满足不同乘客的查询需求。不同的乘客由于自身情况的不同, 因而对各个目标的要求也不一样, 有的优先考虑换乘次数, 有的优先考虑出行时间, 而有的优先考虑步行距离, 有时还要根据乘客实际综合考虑几个因素, 因而查询系统应提供给乘客各种选择的方便, 给出几种最优查询结果供乘客选择。 2 数据预处理 目前查询效率低, 主要是所有查询都在原始的公交线路信息表上, 虽然有的方法对公交线路信息表进行了索引, 但不能从本质上提高查询效率。下面利用构造最优直达矩阵来对原始的公交线路信息表进行预处理, 这样所有的查询都在这个矩阵上进行, 查询效率只与公交站点数有关, 与公交线路的条数和一路公交车经过的站点数都无关。 2.1 直达方式 (1) 公汽直达 两站点能够公汽直达是指至少存在一条公汽线路从一个站点到达另一个站点。 (2) 地铁直达 两站点能够地铁直达是指一个站点可以只通过地铁到达另一个站点, 涉及站点包含所有地铁站点以及与地铁站点相邻的公汽换乘站点。 (3) 步行直达 两站点能够步行直达是指在地理位置上相邻的邻近站点, 通过“捷径”或原公交路径在合理的时间范围内可步行相互到达。 在理论上任意两个站点都可以步行直达, 但没有实际意义。在实际计算中可确定一个邻近站点的合理范围, 在此范围之内的站点叫作此站点的邻近站点。不考虑适当的步行在实际应用中也是不合理的, 因为不考虑步行只有当不同线路之间有公共站点时才能进行转车。这样就忽略了现实生活中人们可步行小段距离再转车的情况。具体地讲, 人们在转车时, 并不是下车后直接在下车的站点处转车, 往往需要步行一小段距离到附近的站点转车, 这样不仅可以减少换乘次数, 往往还能减少出行费用甚至时间。 2.2 最优直达矩阵 2.2.1 仅考虑公汽 首先建立最优代价直达矩阵: 式中, 其中n为公汽站点总数, aij为由i站点直达j站点所需的最优代价, 当代价为时间即为最优时间直达矩阵, 当代价为费用即为最优费用直达矩阵。因为直达往往不止是一种情况, 所以求最优。T (0) 一般不是对称矩阵。 2.2.2 考虑公汽和地铁 n为公汽站点数+地铁站点数, 此时将最优代价aij换记为bij。记wij为从i站点到j站点的最优步行代价, 代价为时间时wij为步行时间, 为费用时wij=0;dij为从i地铁站点到j地铁站点的地铁直达最优代价 (将地铁系统看成整体) ;L (m) 为地铁站点m的公汽换乘站点集合;D (m) 为公汽站点m的地铁换乘站点集合。任两站点都有两种直达可能, 并在两种直达中求最优, 于是有下面4种情况: (1) 当i, j都为公汽站点时: (2) 当i, j都为地铁站点时: (3) 当i为公汽站点, j为地铁站点时: (4) 当i为地铁站点, j为公汽站点时: 2.2.3 同时考虑公汽、地铁和步行 n为公汽站点数+地铁站点数, 此时将最优代价bij换为cij, 记s (i) 为站点i的步行直达邻近站点集合 (含自己) 。故对任意站点i, j有: 3 最优查询标准分析 公交查询不同于其它多目标规划问题, 所有目标的实现都是基于换乘运算, 下面首先定义换乘算子。 3.1 换乘算子“⊕”的定义 对于直达矩阵T (0) = (tij (0) ) n×n, 令T (k) =T (k-1) ⊕T (0) , k=1, 2, …, n, 其中换乘算子“⊕”定义为: tij (k) =Min{til (k-1) +δi, l, j + tlj (0) |l = 1, 2, …, n} 当考虑费用时, δi, l, j=0;当考虑时间时, δi, l, j为i经l到达j的换乘时间。则T (k) = (tij (k) ) n×n为换乘k次对应的矩阵, tij (k) 为站点i到达站点j最多换乘k次所需要的最小代价。 3.2 最优查询标准判断 理论上, 对最优直达矩阵T (0) 最多进行n次⊕运算均可以得到相应最优目标, 实际上⊕运算次数远小于n。下面给出任两站点i, j三种主要目标的判断方法。 (1) 对最优直达矩阵T (0) , 当⊕运算适当次数后若tij (k-1) =∞, tij (k) ≠∞, 则表示从i站点到j站点最少换乘k次能够到达; (2) 对最优时间直达矩阵T (0) , 当⊕运算适当次数后若T (k) =T (k-1) , 则tij (k) 即表示从i站点到j站点所需的最短时间; (3) 对最优费用直达矩阵T (0) , 当⊕运算适当次数后若T (k) =T (k-1) , 则tij (k) 即表示从i站点到j站点所需的最少费用。 4 城市公交查询快速算法 通过上述分析, 公交查询过程就是根据乘客提供的最优目标顺序和条件, 首先根据第一目标进行查询, 然后根据第二目标、第三目标等分层筛选得到最佳查询结果, 所有的运算都是以换乘算法为基础。下面首先讨论如何提高换乘算法的效率。 4.1 数据结构 通过调查可得到公交线路信息表、地铁线路信息表、公汽地铁换乘信息表、步行信息表等原始信息, 这些原始信息表不能够有效支持多需求快速查询。上面介绍了如何通过这些原始信息建立最优直达矩阵, 可以支持快速查询, 但随着城市化发展加速, 站点数越来越多, 直达矩阵就越来越大, 会给查询效率带来一定影响。 通过实例分析发现, 直达矩阵每行每列的非零元素 (即表示直达) 远远小于站点总数, 也即任一站点可直达的站点数远小于站点总数。显然直达矩阵是一个典型的稀疏矩阵, 于是可以用十字链表来存储直达矩阵中的非零元素的所有信息, 同时记下在矩阵中的行列位置便于计算, 在实现时可用结构体数组表示, 如图1所示;为了方便计算, 再用一个一维数组来顺序存储所有行头指针, 用一个一维数组来顺序存储所有列头指针。这样不仅减少了存储空间, 而且提高了查询效率, 而且当站点数和信息表发生变化, 十字链表也容易修改。 4.2 一次换乘快速算法 一个乘客只关心两个站点之间的最佳出行方案, 不会关心任两站点的情况。根据换乘算子“⊕”定义, i站点到j站点换乘一次即相当于直达矩阵中第i行与第j列作一次⊕运算, 即若第i行第k列与第k行第j列都是非零元素, 则表明i站点可通过k站点转乘到达j站点。以十字链表为存储结构, 即为第i行顺序表与第j列顺序表根据行表中列号与列表中行号是否相同求交集, 并求最小目标值。 算法1 一次换乘快速算法 输入:最优直达矩阵T (0) (十字链表存储结构) , 起止站点i, j。 输出:i站点换乘1次到达j站点的最小代价tij (1) 。 该算法时间复杂度为O (m) , 其中m为所有行表、列表的平均表长。令Row (T (0) , i) 表示T (0) 的第i行, Col (T (0) , j) 表示T (0) 第j列, 把该算法记为Row (T (0) , i) ⊕Col (T (0) , j) 。 4.3 k次换乘快速算法 i站点到j站点换乘两次可以先用一次换乘算法求出T (1) 中第i行所有元素, 然后再用一次换乘算法求tij (2) , 即: 依此类推, 在此基础上可得到k次换乘快速算法。 算法2k次换乘快速算法 输入:最优直达矩阵T (0) (十字链表存储结构) , 起止站点i, j, 换乘次数k。 输出:i站点换乘k次到达j站点的最小代价tij (k) 。 4.4 城市公交查询算法 前面给出了三种主要查询标准的判断方法, 显然时间最少和费用最少都依赖于换乘次数, 理论上可以用给出的判断标准进行判断, 但对于实际问题, 如果换乘次数太多就没有实际意义。因此, 可以由乘客给定一个换乘上限或系统默认, 然后根据乘客给定的目标及其优先级进行查询, 不同的目标、不同的优先级查询方法不一样, 具体算法如下: 算法3 公交查询算法 输入:最优直达矩阵T (0) (十字链表存储结构) , 起止站点i, j, 目标及其优先级。 输出:最佳查询结果。 情况1 如果以换乘次数为第一目标 Begin Step1 首先直接判断是否直达, 然后调用k次换乘算法, 并用换乘次数最少判断标准进行判断, 在计算过程中记录相关信息; Step2 根据第二目标、第三目标以及乘客的其它要求从若干可行的情况中分级进行最佳筛选; Step3 最后给出满足乘客要求的最佳乘车方案。 End 情况2 如果以出行时间 (或出行费用) 为第一目标 Begin Step1 根据乘客提供或系统默认的最多换乘次数, 调用k次换乘算法, 记录下每种换乘次数下的第一目标的最优结果, 并在计算过程中记录相关信息; Step2 对每种换乘次数下的查询结果 (含直达) , 根据第二目标、第三目标以及乘客的其它要求从若干可行的情况中分级进行最佳筛选; Step3 最后给出不同换乘次数下的最佳乘车方案供乘客选择。 End 4.5 复杂度分析与比较 显然该算法优于广度优先搜索和深度优先搜索法, 同时由于采用十字链表存储直达稀疏矩阵, 不仅节省了存储空间, 而且进一步提高了查询效率, 具体比较如表1所示。 表中l为公交线路总条数, n为站点总数, k为换乘次数 (k≼m) , m为平均表长 (m≼n) , 所以采用链表方式可在线性时间复杂度得到查询结果。 5 实例计算与比较 利用文献[8]提供的数据进行计算和比较, 该数据共有520条公交线路, 共3957个公交站点, 两条地铁线路, 共39个地铁站点, 以及相关的换乘数据信息, 求以下6对起始站→终到站之间的最佳路线: (1) S3359→S1828; (2) S1557→S0481; (3) S0971→S0485; (4) S0008→S0073; (5) S0148→S0485; (6) S0087→S3676。 实验环境:CPU1GHz, 内存512MB, XP系统;用C++进行编程。从下面三个方面进行计算比较, 暂时不考虑地铁和步行情况。三种情况都明显得到:利用直达矩阵优于广度优先和深度优先, 而用链表优于矩阵。 (1) 以站点S3359→S1828为例, 在不同换乘次数下四种计算方式的运行时间比较如表2所示。*表示运行时间远远超过5小时。括号内为在相应转乘次数下乘客的出行时间。 单位:秒 (s) (2) 以换乘次数最少为第一目标, 6对站点运行时间对照表见表3;括号内为最少换乘次数。 单位:秒 (s) (3) 以出行时间最少为第一目标, 理论上要搜索所有情况, 广度优先后深度优先运行时间太长, 于是我们在最多转乘2次的条件下进行比较。6对站点运行时间对照表见表4;括号内为在最多转乘2次的条件下乘客的最佳出行时间。 单位:秒 (s) 6 结束语 本文研究了如何提高城市公交查询的高效性问题, 利用最优直达矩阵对数据进行预处理, 并利用十字链表作为存储结构, 改进了换乘算法的时间复杂度, 为实现城市公交查询的方便、快捷和人性化提供了条件。但要做到真正人性化, 还要作以下努力:其一, 除准确了解公汽线路信息表、地铁线路信息表、换乘信息表、步行信息表外, 还要调查了解乘客的各种需求, 比如换乘时的步行距离长短以及每路车的拥挤情况、服务态度等;其二, 要与GSM移动通信系统、城市电子地图、短信业务联合。本方法不仅可用于城市公交查询, 稍作修改便可用于各种交通系统查询, 因而具有较大实用价值和市场前景。 参考文献 [1]廖楚江, 蔡忠亮, 杜清运, 等.基于最少换乘的公交最优路径算法的设计与实现[J].武汉大学学报:信息科学版, 2006, 31 (10) :904-907. [2]苏啸, 曾子维.基于关联的城市公交换乘查询算法[J].计算机工程与设计, 2006, 27 (3) :519-521. [3]何胜学, 范炳全.公交网络最优路径求解算法[J].交通运输工程与信息学报, 2007, 5 (1) :22-27. [4]李玉芝, 方潭敏.城市公交查询系统的设计与实现[J].地矿测绘, 2006, 22 (1) :3-5. [5]扈震, 张发勇, 刘书良.城市公交换乘数据模型研究及算法实现[J].电信网技术, 2007 (4) :71-74. [6]徐多勇, 李志蜀, 梅林.基于GSM短消息的公交查询系统的最优转乘方案研究与设计[J].计算机应用, 2007, 27 (6) :397-399. [7]艾菊梅, 蒋年德.基于WebGIS公交查询平台的MMS技术及实现[J].微计算机信息, 2007, 23 (6) :264-266. 本课题受广东省科技计划项目(NO.2006B11301001)和广州市科技计划项目(NO.2006Z3-D3081)资助。 1基本概念 设有基本表T(D1,D2,……Dn , M),其中Di为维属性,0<=i<=n,M为度量属性。用CT表示T的数据立方体,CCT表示T的封闭立方体。用“*”表示特殊维值All。c∈CT,其上界元组用UBc表示。 定义1:封闭掩码 建立一个长度为n的全‘0’二进制位串bstr,设有格c∈CCT,对所有j,若c[Dj]不为*,1<=j<=n,则修改bstr从左至右的第j个位为‘1’,由此得到的bstr所表示的十进制整数,称为格c的封闭掩码,记为MSK(c) 。 例如,对表1所示的基本表sale,采用SUM()函数进行聚集,所得封闭立方体CCsale如表2所示[4]。在CCsale中,格(van,*,*,6)对应的bstr为‘100’,该格的封闭掩码为4。 定义2:封闭掩码集 定义CCT的封闭掩码集为SMSKT={i|i=MSK(c), c∈CCT}。 例如,对基本表sale,SMSKsale={0,1,2,4,7}。 定义3:子掩码 对于SMSKT中的元素i1和i2,分别用长度为n的二进制位串bstr1和bstr2表示其二进制形式,若对bstr1中的所有‘1’,在bstr2中的相同数位均为‘1’,则称i2为i1的子掩码。 例如,3对应‘011’,7对应‘111’,所以3和7均为3的子掩码。 定义4:封闭子集 SMSKT中的每一个封闭掩码i对应的封闭子集为Si={c|c∈CCT,MSK(c)=i}。 例如,CCsale被划分成5个互不相交的封闭子集,分别对应SMSKsale中的5个封闭掩码。如表3所示。 引理1:MSK(UBq)必为MSK(q)的子掩码。 证明:因为q覆盖UBq,所以对q中所有非*的维,UBq中相应维上的值均为非*。由子掩码的定义可知命题成立。得证。 引理2:对一个针对CCT的点查询q=(……, vx ,……,vy ,……),x,y∈N,1<=x<=y<=n,i∈SMSKT ,若i不是MSK(q)的子掩码,则UBq∈Si 。 证明:反证法。若UBq∈Si ,由定义4可知MSK(UBq)=i,根据引理1可知i必为MSK(q)的子掩码,与已知条件相矛盾。得证。 2查询算法 由引理2可知,若SMSKT中某个元素i不是MSK(q)的子掩码,则为了查找UBq,无需搜索Si 。据此,我们设计了MSKQRY算法,用来回答点查询。 在MSKQRY算法的第2步中,只有当i是h的子掩码时才在Si中查找q,否则不再搜索相应的封闭子集,这就缩小了回答查询所需搜索的范围。例如,设q=(*,*,d1)为一个针对CCsale的点查询,MSK(q)为1,SMSKT={0,1,2,4,7},其中1,7是1的子掩码,这样就只需要在S1和S7两个封闭子集中搜索UBq。 算法MSKQRY 输入:q=(……, vx ,……,vy ,……) 输出:格q中的聚集值 (1)int h =MSK(q); (2)for each i∈SMSKT //按i从小到大的顺序 if(i是h的子掩码) {if(UBq∈Si) 返回UBq的聚集值;} (3)return false HQ算法的各个分层分别包含了CCT的一个或多个封闭子集,较小编号分层对应的封闭子集将在MSKQRY算法的第2步中被先搜索,由此找到的第一个被q覆盖的格就是UBq 。这样,MSKQRY算法的平均查找代价与HQ算法相当,但是因为MSKQRY算法的搜索范围较小,所以其查询效率较高。 若将CCT的各个封闭子集按照对应HQ算法的分层来顺序存放,将可以减少磁头来回移动的次数,从而进一步缩短查询所需的响应时间。 对于范围查询,我们将其分解为多个点查询进行运算,在大多数情况下,一个范围查询在某一个维属性上指定的范围为从一个非*的维值到另一个非*的维值,从而使得这些点查询中指定的格具有相同的封闭掩码。在这些情况下,所有点查询可以在同一次的顺序搜索中得到查询结果。 3封闭掩码集的生成 封闭掩码集可以在生成封闭立方体的同时被生成。我们修改了原有的ClosedCube算法,使之在生成封闭立方体的同时生成相应的封闭掩码集。限于篇幅,仅给出其中部分代码,这部分代码用于替代原算法中的第9至12行。 4实验结果与分析 我们采用数据集weather[5]进行了实验,该数据集包含了美国能源部二氧化碳信息分析中心关于天气和云图数据的记录。我们采用SEP85L数据文件中的solar-altitude, longitude和presentweather三个维属性生成了封闭立方体。 我们分析了实验结果,发现较之HQ算法,MSKQRY 算法需搜索的记录范围较小。例如对点查询q=(*, v2 ,v3 ),采用HQ算法时需搜索level2和level3的所有记录,数量为116886;而采用MSKQRY算法时只需搜索S3和S7的所有记录,数量仅为104161。按照其中为*的维的数量和位置,可以将点查询分为8种类型,其分别需搜索的记录数量如表4所示,对于其中的6种类型的点查询(即75%的情况),采用MSKQRY算法需搜索范围包含的记录数降低到采用HQ算法时相应记录数的92%左右,对于通常十分庞大的数据仓库而言,这能节省可观的查询时间。这说明MSKQRY算法是有效的。 5结论及进一步的工作 MSKQRY算法缩小了在数据立方体中需搜索的记录范围,提高了查询效率。 在进一步的工作中,我们将重点研究对封闭立方体的排序方法。这里的排序是指将一个新生成的数据立方体按HQ算法要求的分层次序进行排序,以及按MSKQRY算法要求的封闭子集次序进行排序。 参考文献 [1]Gray J,Bosworth A,Layman A,Pirahesh H.Data Cube:Arelational aggregation operator generalizing group-by,cross-tab,and sub-totals.In:Su SYW,ed.Proc.ofthe12th Int l Conf.on Data Engineering.NewOrleans:IEEE Computer Society,1996,152~159 [2]Lakshmanan LVS,Pei J,HANJW.Quotient Cube:Howto summarize the semantics ofa data cube.In:Proceedings of28th Inter-national Conference on Very Large Data Bases,Hong Kong,2002,Morgan Kaufmann,2002,778~789 [3]李盛恩,王姗.封闭数据立方体技术研究.软件学报,2004,15(8):1165~1171 [4]Zhao Y,Quotient Cube and QC-Tree:Efficient Summarizations for Semantic OLAP.The UniversityofBritish Columbia,Thesis for Master ofScience,2003. XML已经成为代表网络数据的标准。因此,如何有效地查询XML数据已经成为一个日益重要的问题。传统的结构化查询语言,如xpath的[1]和xquery的[2],是用来搜索XML数据,它可以表示复杂的语义。因此,能够获得预期的准确数据。不过,在Web应用系统中普遍存在着一些特殊情况:(1)用户可能不知道数据模式,或者模式是非常复杂的,不能轻易地公式化为一个查询;(2)用户根本不会使用结构化查询语言。对于这些情况,对XML文件进行基于关键字的查询是非常需要的。然而与关系型数据库中的查询相比,XML数据的查询缺乏表述性,结果是模糊、不确定的。 (1)结构化查询语言能够(xquery中或者sql中)是通过where结合and/or的语句匹配到数据节点,而基于关键字的查询也需要以一种关联的方式自动连接匹配节点。 (2)结构化查询语言的返回节点通过"return"的语句(xquery中)或"select"语句(sql)指定,而基于关键字的查询应该有效地确定想要得到的返回信息 经过一些研究(XRank,XSearch,XKeyword),前一个问题已得到解决。但是对于第二个问题,这些方法都没有进行研究。即当我们确定匹配的联系后,应该返回何种数据。返回信息的格式有两种,一种是返回基于VLCA节点的子树(SubtreeReturn),另一种是查询VLCA节点的后裔节点,找出与关键字相匹配的节点,返回该节点的路径(PathReturn),这两种方法对于返回节点都不能有效地定义。 本文定义了关键字查询中的两个问题,并提出算法分析。 (1)通过匹配的联系确定查询的谓语。并且推断希望得到的返回节点。根据文献[3]中的方法,计算VLCA节点。如果一个XML节点包含至少一个关键字的匹配,并且它的子节点都没有包含关键字的匹配,则称该节点为一个VLCA节点。对于XML数据的关键字查询来说,基本操作就是找到包含给定关键字的XML片段的根节点:VLCA节点针对VLCA问题的求解方法与Dewey编码有着紧密的联系,主要原因就是因为Dewey编码包含了该节点所在节点路径上所有节点的Dewey码信息,而这些信息对于建立节点与路径的关联关系,也就是关键字所在节点间的结构关系,有着实际的便利。 (2)推断希望得到的返回节点。节点返回形式有两种,一种是根据关键字匹配后找出明确的返回节点;另一种是综合考虑关键字匹配和数据相关实体后模糊形式的返回。除了输出匹配后的节点外,满足查询期望的节点也需要进行输出以满足用户实际的要求。 1关键字查询中的语义推断 1.1 Dewey编码 我们把XML数据看作是树模型,树中节点根据Dewey编码标注(图1),每个树中节点具有节点名,每个叶节点有一个数值等于1,我们将属性节点看作是关联元素节点。与元素节点并没有加以区分,每个节点赋予Dewey标签作为唯一的ID,我们记录节点相对于兄弟节点的位置,利用符号`.'进行连接,从根节点开始为每个节点编排Dewey标签,例如:DeweyID为0.2.3的节点是节点0.2.的第四个子节点。DeweyID能够用于顺序的发现,以及发现兄弟、继承的关系。 (1)u节点的开始标签在v节点之前出现,只有Dewey(u)的每一部分都比Dewey(v)小时。 (2)u是v的父节点的充要条件是Dewey(u)是Dewey(v)的前缀。 (3)u是v的兄弟节点的充要条件是Dewey(u)与Dewey(v)的最后一部分不相同。 我们还可以推断出两个节点的最近相同继承节点LCA(lowest common Ancestor), LCA的Dewey ID等于Dewey(u) 与 Dewey(v)的最长相等部分。 1.2分析XML数据结构 根据关系数据库中的实体关联概念,一个XML文档可被视为一组现实世界的实体,每个实体具有属性,并与其他实体相关联。例如图1中,根据概念我们可以识别两种实体:team和player,每种实体具有一些属性:team具有name, division,arena和founded属性。Player具有name,position和nationality属性。实体之间的关系通过路径相关联。例如:一个team包含一个或者多个player节点。 我们相信用户希望通过查询在XML文档中找到与实体相关的信息,因此,必须将实体与关键字联系起来,确定查询的结果。例如,问题1查询Rockets,用户希望获得现实世界中Rockets的资料。于是,我们首先确定team节点中ID为0.2的为Rockets的实体,然后输出这个team实体的信息。我们认为Team实体的相关属性是重要的,必须最先输出。Team和player的关系是第二位重要的,我们将生成player相关关系的链接,使用户能够点击浏览实体的关系图。 查询系统的首要方针是区分代表实体的节点和代表属性的节点,并且产生基于实体和关键字匹配的节点输出。但是,XML数据可能是由自治源产生的,我们也许不能直接知道代表实体的节点和代表属性的节点。我们在两种环境下提供启发式的推断,一种是XML的schema是可用的,另一种是在schema是缺少的情况下。 当XML的schema是可用时,我们将根据节点之间的关系将节点归纳为实体和属性。如果一个节点n1与n2具有1对多的关系,则n2代表实体,n1代表属性。另一方面,1对1的关系接近于属性。鉴于上,我们得出有关节点分类推论: (1)DTD中如果一个节点与多个节点关联,则为实体节点。 (2)如果一个节点没有与多个节点关联,并且只有一个子节点,则该节点为常数。 (3)如果一个节点既不是实体,也不是属性节点。那么它是一个关系(connection)节点,一个关系节点可以含有一个多种类型的节点。 例如,图3是关于图1的DTD片段,因为与父节点league的关系是多对1,所以team为一个*-节点,也就代表是实体节点;相反,league.name, division, arena, 和founded是team实体的属性节点。另一方面,players不是*-节点,也没有作为常量的子节点,因此,它是一个关系节点。尽管这些推论不是常规成立的,但是它们在缺乏E-R模型图的情况下提供了一种启发式的推断方法。当缺少了XML文档的schema时,我们根据数据摘要推断schema,然后根据推断的schema确定实体和属性节点。 1.3关键字匹配方法的分析 关键字查询系统第二个方针是定义关键字匹配的模式。当产生返回结果时,将关键字分为两类:查询谓词和返回节点。 (1)一些关键字象征着查询的限制,类似于XQuery或者SQL语句中的where语句。 (2)一些关键字为文档中的节点定义输出类型,类似于 XQuery 中的return或者是SQL 中的select语句。 一个关键的问题是我们该如何推断谓词,返回节点。为达成这个目的,我们首先需要区分数据类型和数据值。如果XML的schema是存在的,则我们可以直接获取类型信息;否则,我们定义节点名作为数据类型,套用结构化查询语言XQuery或者是SQL。注意到,一个谓词包含一对类型和数值,但是返回语句仅仅定义返回数据类型,而没有具体数值。基于此,我们作出如下推论: (1)如果一个输入关键字k1与节点名字(类型)为u的节点相匹配,而又不存在另一个关键字k2与节点v的值相匹配,这样u是v的祖先节点,则k1定义了返回节点。 (2)一个关键字没有定义返回节点则被当作谓词说明,换句话,如果一个关键字与一个节点的值相关联,或者与节点的名字(类型),而该节点的具有一个子孙节点,它的值与另一个关键字相关联,则该关键字是谓词的说明。 例如,对问题2而言,因为center与值(0.2.4.0.1.0)相匹配,所以可视为谓词;在问题2和问题3中,Yao被视为谓词;问题4中的team也可被视为谓词,因为它与(0.2)匹配,存在值节点(0.2.0.0)作为(0.2)的后裔节点与另一个关键字Rockets相匹配。另一方面,问题3中的position因为与两个节点(0.2.4.0.1, 0.2.4.1.1)匹配,并且这两个节点都没有后裔的值节点与问题3中的关键字相匹配,因此,问题3中position被视为返回节点。同理,问题4中的players也被视为返回节点。 2基于节点分类的节点返回方式 关键字查找和结构化查找的的主要区别在于,除了需要将与返回节点与数据匹配进行输出外,还需要将数据与谓词匹配。尽管面对着不明确的关键字查询,用户希望检查谓词匹配,以得到满足意义的谓词。因此,所有VLCA节点与本身子节点的联系路径都必须作为输出的一部分,标志关键字的匹配以及匹配之间的关系。例如问题3中,尽管用户只关心position的信息,我们还是将VLCA节点player(0.2.4.0)到谓词Yao(0.2.4.0.0.0)节点的路径输出。基于此目的,我们定义明确和含糊的返回节点,并采用适当的方法表现它们。总结如下结论: (1)节点返回形式有两种,一种是根据关键字匹配后找出明确的返回节点;另一种是综合考虑关键字匹配和数据相关实体后模糊形式的返回。 (2)满足返回要求的数据节点的返回方法是基于分类的:属性、实体还是连接节点。 (3)除了输出匹配后的节点外,满足查询期望的节点也需要进行输出以满足用户实际的要求。 与返回节点相匹配的数据节点必须根据分类来表现:属性、节点和关联节点。为了输出一个属性,我们表现它们的名字和具体值。但是,以实体为根节点的子树可能会很大,从用户友好性角度看,应该输出其中最重要的信息。而用户可以根据其中的扩展链接浏览细节信息。 3实验与结论 我们利用JAVA语言实现了上述算法,使用关键字作为输入参数,输出符合查询期望的XML文档片段。对比其他查询方法(图4),该方法在查询结果质量上超过了其他基于节点返回和路径返回的方法,查询耗时也令人满意。 参考文献 [1] Clark J, DeRose S. XML path language (XPath) 1.0. http://www.w3.org/TR/xpath.November 1999 [2] XQuery 1.0: An XML Query Language, http://www.w3.org/XML/Query.June 2001 关键词：查询优化,粒子群算法,执行代价估计,树形编码 1 概述 数据库查询优化技术致力于研究如何高效、迅速的从大型数据库中检索出需要的信息。大型数据库中数据分别被存在不同的表中,查询时经常需要进行多表连接查询,当表的数量很多的时候查询的代价会呈指数增长 [1]。因此研究如何降低多表连接查询时的执行代价,是提高系统性能及查询效率的关键。 目前对查询优化技术的改进主要有两个方向:第一,使用确定算法改进,如:动态规划 [2]、贪心算法 [3]等。第二,使用随机算法,该算法是在解空间内通过随机方法求得近似最优解,如:遗传算法[4,5]、粒子群算法[6]等。当数据库表文件较少时,使用确定性算法是较好的选择,而针对大型数据库,表文件非常多时,随机算法效率更高更有优势。 为提高多表连接查询的效率,该文使用粒子群算法对数据库的查询策略进行优化。使用树形编码的方法对多连接查询问题进行编码,种群中一个粒子表示一种表的连接顺序,设计了多表查询的执行代价模型作为适应度函数,然后进行迭代计算得到优化后的解。实验表明优化后的查询执行代价有显著下降。 2 查询优化技术概述 查询优化(Query Optimization)是指在数据库执行查询操作的过程中使系统执行代价及时间消耗尽可能小,从而提高查询操作的执行效率[7,8,9]。一个复杂的查询一般包含多种可行的查询策略,通常用户无法直接准确的写出最优的查询语句,使用查询优化方法在多种可行的查询策略中选取出最优的策略,对提高查询效率有重要的意义。 多连接查询(Multi-Join Query,MJQ)是将数据库中多张表按一定的规则连接而成的关系表达式。多表连接查询因关系数据库的广泛应用而成为查询优化技术研究的重点。 3 查询执行代价计算 查询优化首先需要生成一个和给定查询语句查询结果相同的解空间,使用语法树可以方便的表示出数据库中表的连接顺序,该文使用左线性语法树来生成解空间,当有n个连接操作时,所生成的解空间有(n+1) !种可行解。 解空间确定好后,需准确的计算出解空间中每个可行解的执行代价,该文提出的代价估计如下: 假设多连接查询中共有n个关系,其语法树的内部结点个数为t i,则查询的执行代价即为语法树内部结点个数的总和。 对于一个多连接查询语句,S为所有与用户提供的查询语句有相同结果的查询策略的集合,则集合中执行代价最小的查询语句则是最优策略: 对于任意结点t,若l、r分别为t的左右子结点,即t = lr ,而c表示公共属性,v(a,t) 表示t中a的不同取值的个数。则代价估计公式可以如下表示。 若各个关系间没有公共属性,则执行代价计算公式为cos t(t) = n l×n r。 4改进的查询优化算法 4.1 粒子编码方法 多连接查询问题因其特殊性,普通的二进制编码方式无法进行表示[10],故本文对粒子群中的粒子使用树形编码。对于一个语法树,令连接节点的值为0表示连接操作,令叶子节点的值为i表示数据库中的表的编号,如图1所示: 图1中语法树的编码为 (0,0,0,0,1,2,3,4,5) ,编码长度为9。其中,编码的前n-1位表示连接操作,对编码无实际意义,故可以进行简化表示为 (1,2,3,4,5 )。树形编码简单直观,根据编码即可直接得到语法树的连接情况。 4.2适应度函数设计 适应度函数直接影响粒子群算法的收敛情况。多连接查询需要在解空间中找到执行代价最小的查询语句,其适应度函数设计如下: 即首先计算每个粒子的执行代价,再对所求得的值取倒数即为适应度函数值。当粒子的执行代价越小时,适应度越高。 4.3 改进的查询优化算法的实现步骤 1) 对原始查询语句进行编码。 2) 初始化种群,即在问题的解空间中,随机给粒子赋予初始值。 3) 取执行代价的倒数作为适应度函数。 4) 使用粒子群算法进行迭代寻优。 5) 终止条件。当迭代达到设定的代数,或者达到设置的精度要求则结束算法。 5实验结果及分析 5.1 实验数据库概述 本文从一个大型的工程数据库中获取部分数据进行实验,该数据库中,为了查询包含不同信息的报表,而这最多需要对5个关系表进行连接查询。这5个关系表为h_beian(合同备案表)、h_gaikuang(工程概况表)、h_tezheng(工程特征表)、h_shouche(《手册》表)、h_jiancha(履约检查表)。 假设一个查询语句如下: 所涉及到的数据库中表的部分统计信息如表1所示。 对于原始查询语句未使用粒子群算法优化前计算出的执行代价为975。 5.2实验结果及分析 1) 对于原始查询语句Q,解空间中的可行解个数为120。所以,种群数量不用设置得过大,该文对种群规模设置为5,10,20,30,实验结果如表2所示。 由实验可看出当种群数目为15和20时,所得的执行代价较小,优化效果理想。 2) 根据表2中的结果,种群大小为20。最大迭代次数取10、20、30、40、60,实验结果如表3所示: 将表3中的结果换算成适应度值后,适应度变化曲线如图3所示。 由图3可以看出,适应度值随着迭代次数的增加呈现上升趋势且变化趋于平缓,说明基于粒子群算法的查询优化算法收敛。经过优化后执行代价为868的粒子所表示的查询语句,即为所得的解。 由实验可看出经过粒子群算法优化后的查询语句比原始查询语句的执行代价有了显著的下降,随着表的数目及表内数据的增加,经过优化后的效果会更加明显。 6 总结 流动数据处理长期以来没有受到足够重视, 目前并不存在像数据库管理系统一样的成熟的、通用的数据流处理平台。但随着互联网技术的发展和广泛应用, 国际、国内对数据流的研究已逐步得到重视。 1. 选择多查询处理及其分类 数据流管理系统和传统的数据库管理系统最重要的区别之一是持续查询在数据流管理系统中的重要地位, 而选择查询是数据流持续查询中最基本、也是最重要和使用得最广泛的一类查询。 直观的说, 一个选择查询就是一个过滤条件, 当流数据到达时, 数据流管理系统查询处理引擎在选择查询上进行条件测试, 如果条件测试的结果为真, 我们说这个选择查询得到满足 (或者说这个选择查询得到匹配) 。 数据流管理系统中一般都注册有大量的选择查询。数据流S上的选择多查询处理是指:给定S上的选择查询集合Q s e t{Q1, Q2, …, Qn}, 当S的一个数据元组t到达时, 返回查询集合中所有取值为真的查询的编号。 Qset也可用表1直观地表示, 其中谓词P[i, j]是查询Qi在属性aj上的谓词。 一个流数据元组到达后, 按照多查询处理算法在表1中的处理顺序, 已有的多查询处理算法可分为3类: 1.1 行顺序处理方法: 当一个数据流元组到达后, 多查询处理引擎逐行 (逐查询) 处理表1中各查询; 1.2 列顺序处理方法: 当一个数据流元组到达后, 多查询处理引擎逐列 (逐属性) 处理表1中的查询; 1.3 行列交错处理方法: 当一个数据流元组到达后, 多查询处理引擎按照行 (查询) 、列 (属性) 交错的顺序处理表1中的查询。 2. 基于决策树的选择查询算法 本文提出一种新的数据流选择多查询的处理算法, 这种多查询的索引具有决策树形式的结构, 笔者称之为数据流多查询的决策树索引算法。多查询的决策树索引同时利用了单个属性上的谓词索引和单个查询内各属性谓词间的合取关系, 因而能更大程度减少冗余计算。各种单属性上的谓词索引能很容易集成到多查询的决策树索引中。这种多查询的决策树处理算法被归入到行列交错处理算法类别。 2.1 查询决策树的构造 设数据流S用模式R (a1:Ω1, a2:Ω2, …, am:Ωm) 描述, Qse t{Q1, Q2, …, Qn}是在S上定义的查询集合, 下面讨论如何在Qset上建立基于决策树的查询索引。 查询决策树是以自上向下的方式构造的, 在构造的过程当中, 每个结点关联一个查询集合和一个属性集合, 查询集合是以当前结点为根结点的子树所索引的查询子集, 属性集合是当前结点可选的划分属性集合。构造从决策树的根结点开始, 根结点关联的查询集合包含了原始查询集合Qset中的所有查询, 根结点关联的属性集合包含了数据流模式S的所有属性。利用一个先进后出的栈 (stack) 来保存将要被扩展的结点, 及其关联的查询集合和属性集合。初始化栈时, 把根结点及其关联的查询集合和属性集合压入栈, 然后每次从栈的头部弹出一个待扩展结点, 将这个结点扩展, 再将扩展得到的新结点压入栈, 重复这个过程直到栈变为空为止。使用栈来保存待扩展结点, 按照先进后出的顺序依次扩展每个结点, 是一种深度优先的树构造策略。 假设当前从栈顶弹出的待扩展结点关联的查询集合为Qset{Q1, Q2, …, Qn}, 属性集合为Aset{a1, a2, …, am}。从Aset中选择一个属性做为划分属性。预先对数据流的各属性赋以一个序号, 结点扩展时总是选择Aset中序号最小的属性做为划分属性。 假设已经选择属性aj做为当前结点的划分属性, 查询Qi在属性aj上的谓词为P[i, j], 设aj的值域为Ω, 由数据流选择查询的定义得知, 谓词P[i, j]确定了Ω的一个子集ωi (即P[i, j] (aj) 为真当且仅当aj∈ωi) , 那么我们用ω1, ω2, ……, ωn将aj的值域Ω划分成s个不相交的值域子集σ1, σ2, ……, σs, 满足: 条件 (I) 和 (II) 保证了, aj的任何一个可能取值落入且仅仅落入某一个值域子集σk (1≤k≤s) 。条件 (III) 保证了, 对于任意值域子集σk, 任意查 询在划分属性上的谓词P[i, j]确定的值域子集ωi要么完全包含σk, 要么σk和不相交。等价的描述是, 对于σk (1≤k≤s) 中的任意两个不同值x和y, P[i, j] (x) =P[i, j] (y) ("1≤i≤n, 1≤j≤m) 。在满足上面三个条件的前提下, 应使s尽量的小。 在给定属性aj的值域Ω上, 定义关系R:对于任意的x, y, x Ry当切仅当对所有的1≤i≤n有P[i, j] (x) =P[i, j] (y) 。容易证明R是Ω上的一个等价关系, 而σ1, σ2, ……, σs则是由这个等价关系划分出的一族等价类。 接下来, 为当前结点创建s个子结点, 每个子结点分别对应于一个值域子集。每个子结点都和属性集合Aset{aj}关联, 其中aj是当前结点的划分属性。每个子结点初始时都和一个空的查询集合关联, 然后对于Qset中的每个查询Qi和每个值域子集σk, 如果P[i, j]完全包含了σk, 则将Qi插入到第k个子结点关联的查询集合中。后面用Qset’[k]表示当前结点第k个子结点关联的查询集合。注意, 一个查询可能被插入到多个子结点所关联的查询集合中。然后, 这新建立的s个子结点及其关联的属性集合和查询集合被压入栈顶。每个子结点关联的属性集合为Aset{aj}, 也就是说, 每个子结点所关联的属性集合大小至少比其父结点关联的属性集合少1, 因此, 构造的查询决策树的最大深度为M, 这里M是数据流属性的个数。 最后, 为当前结点关联的查询集合Q s e t在划分属性a j的谓词上建立匹配器matcher, matcher是划分属性上的谓词索引。利用matcher, 对于给定的划分属性值, 能快速计算它落入了哪个值域子集。各种单属性上的谓词索引都可以用来建立matcher。 给一个查询决策树结点扩展的简单例子。假设当前结点关联的查询集合为:Q1: (5 0<a 1<1 2 0) ∧…;Q2: (a 1<8 0) ∧…;Q3: (a1≥80) ∧…, 属性a1被选为划分属性, a1的值域为[0, 65535]。那么, a1的值域可以被划分为4个不相交的值域子集:[0, 50], [51, 79], [80, 119], [120, 65535], 为当前结点创建4个子结点, 每个子结点对应于一个值域子集。接下来, 为每个子结点关联一个空的查询集合, 将每个查询插入到各子结点关联的查询集合中。例如, Q1覆盖了[51, 79]和[80, 119], 我们把Q1插入到第二个和第三个子结点关联的查询集合中。扩展后的子树图见图1。图中结点内的字母表示这个结点的划分属性, 结点右边的花括弧里为结点关联的查询集合, 边上标示了值域子集。 2.2 查询决策树的匹配算法 利用查询决策树, 搜索给定的数据流元组T满足了哪些查询的匹配算法, 是一个从树的根结点往下遍历直到某个叶结点的过程。初始化时将匹配结果查询ID集合Rset置为空, 结点指针P指向查询决策树的根结点, 那么递归的匹配算法可以描述如下: mat ch (P, Rse t, T) //P为指向当前访问结点的指针, Rset为存放匹配结果查询ID的集合, T为待匹配的数据流元组 匹配算法中, 访问每个非叶结点时, 用数据元组的划分属性值搜索当前结点的谓词索引, 如果元组的划分属性值落入了第k个值域子集, 那么将搜索以第k个子结点为根的子树, 而直接跳过了其它的子结点及其子树。因此, 查询内各属性谓词间的合取关系得到了充分利用。 匹配算法最多需要搜索M个结点的谓词索引, 这里M是查询决策树的最大深度, 即数据流属性的个数。如果每个结点中的谓词索引的搜索时间不大于O (f (N) ) , 其中N是查询的个数, f (N) 为单属性谓词索引的搜索时间复杂度上界, 那么上述匹配算法的最坏情况时间复杂度为O (M f (N) ) 。一般情况下, 常用的单属性上的谓词索引能满足f (N) =O (log (N) ) 。多查询行顺序处理算法、列顺序处理算法和行列交错处理算法最坏情况下的时间复杂度都为O (MN) , 而查询决策树O (Mlog (N) ) 的最坏情况时间复杂度显然更适合实时数据流应用。 3. 结语 查询决策树不仅使用了单个属性上的谓词索引, 各种单属性上的谓词很容易集成到查询决策树结构中, 而且还充分利用了查询内各谓词间的合取关系, 相对于以前的各种多查询处理算法, 能更有效减少冗余计算。 最后在一个模拟的网络入侵检测环境下测试了查询决策树的匹配时间效率和存储使用量, 并将其和改进的行顺序处理算法及列顺序处理算法进行对比, 验证了查询决策树在匹配时间效率上的巨大优势。 摘要：本文提出了一种基于决策树的查询索引结构, 笔者称之为查询决策树。查询决策树不仅利用了查询内各个谓词间的合取关系, 还充分利用了单个属性上的谓词索引。 关键词：数据流管理系统,查询决策树 参考文献 [1]徐恪, 徐明伟, 吴建平, 吴剑.路由查找算法研究综述.软件学报, Vol.13 (1) , pp42～50 [2]陈有祺.形式语言与自动机.南开大学出版社, 1999, pp.45～78 Skyline计算 Skyline计算应用于很多不同领域的数据集, 比如集中式数据库、时空数据库、数据流、分布式数据库和属性数据分类数据中。Skyline算法主要偏向于个人偏好查询, 在数据库中搜索不被支配的点。一个点所以支配另外一个点是因为第一个点至少肯定有一项要比另外一个点要好, 该算法主要根据用户的选择和喜好找到适合的语义。Skyline计算在数据领域的定义:在一个数据集中D={s1, s2, s3, …sn}, 其中各数据点可表示为Si={p1, p2, …, pn}, i=1, 2, 3, …n - 1, n。对于任何一个pi ∈ D, pi ∈ (0, 1) , 对于pi来说, 数据的属性值越小越好。查询对象数据集合中所有不被其他点支配的点组成的集合谓Skyline查询;其中每个点称之为SP。本文中的Skyline查询优化算法采用索引技术, 减少Skyline计算中SP点和点之间的比较次数, 然后尽可能的找到最合适的SP点。 最近邻的Skyline查询算法 基于索引的Skyline算法是指在输出用户自己要查询的SP点前, 首先建立分布式数据结构, 通过利用用户建立的索引, 尽量减少Skyline计算过程中点和点比较的次数, 优先找出最可能得SP点。一般的Skyline查询算法比较次数的最好情形为O (kn) , 最坏复杂度为O (kn2) 。最近邻算法 (Nearest Neighbor, 简称NN) 是对数据对象构建R -树索引, 求出距离最近的点, 对该点进行数据分区, 构建矩形区, 同时递归调用算法来计算, 直到分区中不含有任何Skyline查询结果为止。NN算法的是在数据集中找到的k个最近的邻居, 根据分类属性统计, 统计出的结构按照分类属性来赋值。因此在类别决策时, 只与极少量的相邻样本有关。NN算法主要靠极少的邻居样本进行分类, 它更应用于类别比较多的数据。 Hadoop平台上NN算法查询优化研究 改进NN查询算法 Skyline查询改进后使用分枝界定法。首先采取R -树遍历, 然后再访问MBR分配到各层。从根结点N开始, 对所有的结点离根节点N的距离进行计算, 分片采用升序方式存储在内存堆栈中, 如果结点不被SP中的点支配, 继续遍历其孩子结点, 若孩子结点被SP支配, 那么放弃这个结点, 否则继续存储在内存堆栈中, 如此循环下去直到找到叶子结点并且不被SP支配, 那么这个点一定是Skyline点。把这个点存储在表中。循环如此, 直到堆栈为空。在每次查询过程中需要执行多次Skyline查询, 多次遍历R -树。 改进后的算法采用一种相互Skyline查询, 在查询过程中利用局部查询得到Skyline集合来尽量减少SP点, 提高搜索效率, 减少I/O开销。当数据量非常大的时候, 可能出现错误不能保证查询正常进行, 运行故障监测和任务迁移, 在查询过程中找到发生的故障, 将故障中的任务迁移到副本, 尽量保证查询的正常执行。图1 是M=2 阶R -树, 图2 是M=2 阶R -树在二维空间上的表现形式。 具体步骤如下。 (1) 将根所包含的结点n1 升序放入堆D1 中, 同时将根所包含的结点n2 升序置入堆栈D2 中。 (2) 首先对最近距离节点n1 操作:移出栈中的n1, 将n1 的2 个孩子 (n3, n4) 插入堆栈D1 中, 然后在对n3 节点进行扩展, 由于n3 的两个孩子结点 (1、2) 结点不被S1 支配, 将 (1、2) 插入堆栈D1 里, 移出最小距离的1, 2, 因为1 和2 是叶子的结点并且同时不被S所能支配, 于是1、2 就被放入Skyline点的固定列表S中。这样我们就得到了局部的skyline点。通过用S1中的点与后面堆D1中的结点比较要被扩展后的结点n4, 如果n4被S中的已经插入的点支配, 所以n4移除, 当堆栈D1为null时, S1中的点确认为全局的Skyline点。 (3) 同样的道理, 对于 (2) 中的可以操作:将 (5、6) 插入堆D2 中, 这样我们就得到了局部的Skyline点。通过用S2 中的点与后面堆D2 中的结点比较要扩展的是结点, 当堆D2为空时, S2中的点就是局部所有的Skyline点。 (4) 我们将S1 中的全局Skyline点 (1, 2) 与S2中的局部Skyline点 (5, 6) 进行比较交集, 得出S= (1, 2) 。 (5) 局部Skyline查询找到点的时候不断的更新这个查询点, 全局Skyline查询则不需要。 当数据量非常大的时候, 容易出现局部Skyline集合发生故障, 比如堆过大, 线路中断等情况。在算法执行过程中协调者一直在监测整个查询过程, 局部Skyline计算过程中周期性地保存中间结果和计算状态至可靠节点。 (1) 协调者接收查询请求后, 将查询请求运行; (2) 协调者把发送查询后接收所有返回局部Skyline集合放入Sn中; (3) 如果有未返回的局部Skyline集合, 协调者发送消息探测等待看是否发生故障, 如果未发生故障, 则合并所有局部Skyline数据集;把所有的局部合并成全局Skyline集合; (4) 协调者将全局Skyline集合返回给用户, 查询成功, 退出; (5) 否则记录故障, 找到故障写入访问记录文件Record File; (6) 检查Record File的status是否完成;若是完成则继续查询执行 (2) , 否则取出SP (dn) , 通过比较数据副本的负载平衡, 用state记录副本节点的忙闲, 堆D (n) 中等待该副本节点的运行者, Time记录副本节点最近一次更新的时间; (7) 查找空闲副本, 重新发送请求, 找到合适数据副本的节点继续执行 (3) 。 算法分析 通过分支界定法, 局部查询算法, 查询次数算法执行访问结点的数目 (N) 小于s*h (h为R -树的高度) , 减少了SP点的访问次数。算法所需的堆中结点的数目应小于 (s - 1) *N。不符合的SP点直接支配剪掉, 不影响后续查询。 算法实验评估 本文实验环境在百兆局域网中的5 台PC机中运行, 配置为:处理器:Intel Corei3 - 3210M (2.5GHz/L33M) , 内存容量:2GB, 硬盘容量:80GB, 操作系统为Windows XP。准备多台服务器, 虚拟机VMware的安装, 下载安装软件并分别在5 台机器上安装。由于5 台机器的D盘剩余空间都较大, 统一在D盘安装VMware Workstation软件, 分配空间10G。 设置1 台Master机, 4 台Slave机。 安装Linux系统中的Ubuntu的iso文件。Jdk采用Jdk1.6.0 版本和Hadoop采用版本hadoop - 0.20.2。 第一组实验R -树采用页面尺寸设置为512B, 768B, 1024B, 3072B, 本实验在二维和三维数据上进行测试。采用JAVA语言来进行编译。图3 是二维数据的查询比较, 图4 是三维数据上的数据查询比较。改进的NN算法在查询成本上原有的NN算法开销和时间比较低。 第二组实验对比访问次数, 经过比对如下表1, 改进的NN算法比NN算法索引维护少, 并且高的访问次数并不一定有高的查询成本, 因为查询成本除了I/O成本还包括CPU计算成本。 通过改进NN算法, 我们通过三组实验验证了改进的NN算法的有效性, 不仅可以减少I/O的访问次数, 而且减少内存占用, 减少CPU运行时间。R -树对数据集进行索引, 利用全局和局部查询算法来尽可能减少SP点, 保证算法的渐进性。达到了预期的查询效果。 观点建议 大数据时代信息暴涨, 在教育领域将掀起一阵狂潮。教师和学生已经成为互动的两个角色。 大数据推进了数据和实证进行决策的文化, 使所收集的教育数据在广度和深度上不断延伸, 有助于更好的撂跤学生的个人行为。提高数据分析结果的时效性、可视性及可读性。 【查询算法】相关文章： 住房公积金查询查询09-07 申请(行贿查询) 招标行贿受贿查询函申请05-29 福建省养老保险查询个人账户查询05-03 查询04-28 查询使用05-01 移动查询06-07 网络查询06-11 语义查询06-20一种城市公交查询快速算法 篇3
一种新的封闭立方体查询算法 篇4
基于VLCA的关键字查询匹配算法 篇5
一种改进的数据库查询优化算法 篇6
一种基于决策树的选择查询算法 篇7
查询算法 篇8