高效查询范文（精选4篇）
高效查询 第1篇
Top-k查询大量运用在数据库领域, 可以从大量数据库中提取到K个数据集或者数据点。目前面临两方面的挑战, 许多研究通过数据融合来完成数据查询处理, 来减少传送能耗、增长传感器生命期。数据融合技术中, 传感器网络最基础的应用为top-k。Silberstein.et.al[1,2]提出了一种线性top-k查询方法, 设计了数据查询器。Zeinalipont et.al[3]提出了一种阀值数据查询算法, 需查询的各个属性区域设置了一些不同的阀值来减小对基站所传送的无用数据。Wu et.al[4,5]在节点中设置了滤波器来滤除无用的数据。上面的几种算法一定程度上改善了传感器网络数据查询的效率, 降低了能耗, 关注的却是传感器一维数据集。而传感器网络高维数据的查询在理论研究及实际应用中, 同样有着非常重要的意义, 如海洋的检测研究, 生物学家关注的是光照度、水温等, 地质学家却关注水流速度、酸碱度等。需要设计的系统可根据用户的需求及偏好采用多属性的查询方式。而无线传感器网络多维数据查询研究较少。设计传感器的节点能量高效及多用户需求与偏好的连续高维数据的top-k查询为当前要解决的首要问题。
1 问题描述
无线传感器网络中, 假设数据集为D={d1, d2.....dn}, di则为m-维数据点即表示为 (m+2) 个数据元组:di= (di.x1, di.x2, ......., di.xm, di.id, di.t) , di xi表示为数据, di.id表示为数据类ID号, di.t表示所需要的时间。用户需求的查询函数则可以定义[4]为:F (di) =∑mj=1wj·di.xj, wj表示数据在j维的权重。用户需求top-k查询指的是在数据D中来查询F的函数值最大K个点。同多数研究相同, 只需要去考虑典型线性凸函数。该单调函数要满足以下条件:若xj≤xj′, 则F (x1, x2, ......, xm) ≤F (x1′, x2′, ......, xm′) 。如数据维度是2, 对应di四元组表示为<di.x1, di.x2, di.id, di.t>, di.x1, di.x2则为采样值。无线传感器的sink节点需依据用户的每个wj权重来返回查询结果, 表示为URS, 用户偏好不同, 则wj不同, 传感器sink节点可能不只返回K个结果。
2 用户高维处理框架
为了高维数据查询扩展的方便、提高数据的查询精度以及减少数据通信量, 提出一种用户的高维数据查询处理架构。高维数据查询处理框架如图1, 在传统的框架上进行改进, 具体的改进有以下几点:
(1) 根据用户的偏好不同, 来赋值权重K值, 优先来响应较大K值的查询请求;
(2) 通过增加可选单元, 用来进行模糊查询或处理数据老化, 与其它设备相连;
(3) 支配图接收的数据查询结果同Sink节点查询结果相融合, 再传送到节点;
(4) 从图1得出, 改进的处理框架将不会依赖传感器网络路由, 各路由结构都可以采用。
图1中用户数据流先通过无线传感器网络传送, 如果Sink节点接收的数据查询结果为RS, 则节点通过检测支配图, 再与RS相融合, 最终传送给数据流目的节点以及与Sink节点的汇合。基站传送数据同时, 还会回传TOP-K全局的数据信息给无线传感器网络, 也可以在当经过滤波器信息时, 传送给全局网络接收, 但可能会影响到数据查询的精度以及查询的结果重复, 造成数据受限。要进行更好的高维数据查询, 需在已有的TOP-K基本数据查询方法上, 提出一种新的改进的用户高维数据查询算法。
3 改进的用户高维数据TOP-K查询算法
由于传感器网络不能进行大规模的通信, 通过sink节点的连续分发进行滤波器更新难以实现。同时滤波器在过滤数据需要来设置其数据过期时间, 如果数据过期时间不设置, 则需要设置区域的节点数设为counts, FLsink设为节点更新滤波器, 设为节点数据传送到sink平均路径的长度。则为更新滤波器所引起的额外开销。如果数据过期需要更新一个滤波器, 更新算法如下所示:
输入表示为sink节点有效支配图 (DG) , 输出表示为非top-k的结果节点集合 (NS) 以及counts
(1) loop:If Sink所接收的新数据data或者支配图 (DG) 的数据过期then
(2) 更新区域中Sink的数据DG
(3) 计算更新后支配图 (DG) 的FLsink
(4) If FLsink配的新数据data then
(8) Sink给集合 (NS) 各个节点发布FLsink
改进后的数据节点处理模块, 当数据节点接收到滤波器的数据集FLsink以后, 会进行当地滤波器的更新, 再从滤波器中去掉过期数据, 最后寻找需发送的点 (不属于TOP-K的查询结果) 。如果FLi为非支配的新数据datai, 需将数据传送到父节点, 同时在循环中去掉过期的数据。TSi设为节点所发送数据集。
4 总结
在传统的数据查询基础上, 设计出一种用户偏好函数无线传感器数据处理框架。通过支配图维护top-k数据查询信息。通过数据支配信息来设定偏好函数, 使用户的数据查询更易实现, 而非top-k数据查询结果可以通过滤波器来进行数据的过滤处理。本架构还有较好的扩展性, 通过在框架的可选单元加入模糊数据查询, 用来解决数据的老化。下一步研究异构传感器数据通信的内容。
参考文献
[1]Silberstein A, Braynard R, Ellis C, et a1.A SamPling-based Approach to Optimizing Top-k Queries in Sensor Networks[J].Proceedings of IEEE ICDE, 2010.
[2]曾利军, 刘卉, 彭广.动态传感器网络区域受限的移动sink路径选择研究[J].计算机应用研究, 2013, 30 (6) :1652-1655.
[3]Zeinalipont D, Vagena Z, Gunopulos D, et al.The Threshold Join Algorithm for Top-k Queries in Distributed Sensor Networks[J].Proceedings of workshop data Management for Sensor Networks (DMSN) , 2009.
[4]刘卉, 李泽军.基于投影矢量的双组播树高效路由数据收集[J].传感技术学报, 2013, 26 (4) :570-576.
高效查询 第2篇
关键词：XML查询,XML多分支路径查询,XML编码
0 引 言
XML数据查询尤其是结构复杂的XML数据查询是一项重要的研究课题。XML数据查询主要分为单路径查询和分支路径查询。单路径查询语句形如a//b/c, 目前针对单路径的查询方法有A (K) [1]、D (k) [2]、APEX[3]、1-index[4]、XISS[5]、DataGuide[6]等, 其基本思路是对XML文档树建立路径索引, 有效地减少查询单路径的时间。XML分支路径查询研究较少, 国内尚无相关文献报道。目前解决分支路径查询的一般方法可分为两种: (1) 首先将分支路径查询拆分成由根结点到叶子结点的单路径, 并通过结构连接算法[7,8]得到单路径的查询结果, 然后将所得到的单路径查询结果进行连接操作得到分支路径查询结果。例如, 查询分支路径a[b=‘c’]//[d=‘e’], 首先将该分支路径进行拆分得到两个单路径a//b/c和a//d/e, 然后利用结构连接算法分别得到这两个单路径的查询结果, 最后将两个单路径的连接结果进行连接操作, 得到最终满足条件的分支路径查询。 (2) 将分支路径拆分成结点对, 分别对结点对进行查询, 最终将结点对连接成分支查询结果。例如, 查询分支路径a[b=‘c’]//[d=‘e’], 首先将其拆分成a//b, b/c, a//d, d/e然后分别对这些结点对进行查询, 最后将查询的结果进行连接操作。方法 (1) 由于拆分操作产生了多条单路径, 在将单路径连接成多分支路径的算法中采用循环比较方法, 效率低。方法 (2) 将多分支路径拆分成结点对, 将会得到大量的中间结果, 在对这些中间结果进行连接操作时, 效率同样低。为了避免XML多分支路径查询过程中多条单路径的连接操作而带来的查询效率低的问题, 本文提出了一种高效的XML多分支路径查询算法MBPQ, 该算法同样是将多分支路径查询转化为单路径查询, 但是它与现有的XML多分支查询的处理过程不同。它首先对XML文档和被查询的多分支路径结点分别按照各自不同的方式进行编码, 然后将被查询的多分支路径拆分成单路径, 并进行单路径查询, 利用栈匹配具有共同祖先结点的单路径查询结果, 最后得到多分支路径查询结果。实验表明, 与现有的XML多分支查询一般算法相比, 算法MBPQ的查询效率高。
1 XML结点编码与结点索引
算法MBPQ首先对XML文档进行编码 , 本文提出的编码方法是:将XML文档看作是流文件, XML文档树中的每一个结点在解析文档时根据每个标签在文档中出现的先后次序赋予两个序号begin和end。其中begin代表文档标签的开始位置, end代表文档标签的结束位置。以图1中的XML文档为例, <PLAY>标签记为1, <PGROUP>标签记为2, <PERSONA>标签记为3, 直至文档最后一个标签</PLAY>为105, 所以, PLAY标签的编码为 (1, 105) , PGROUP标签的编码为 (2, 12) 等等。对于图1所示的XML文档, 其对应的文档树及其编码如图2所示。显然, 祖先结点u的编码区间[begin (u) , end (u) ]包含后裔结点v的编码区间[begin (v) , end (v) ]。
根据XML文档树中每个结点的编码, 建立XML结点索引。在进行单路径查询时, 利用该索引就可以快速得到结构连接算法所需要的结点集合。
推论 设文档树中的任意两个结点u和v是祖先/后裔关系, 当且仅当begin (u) <begin (v) <end (v) <end (u) 。特别地, 若两个结点u和v是父子关系, 当且仅当begin (u) <begin (v) <end (v) <end (u) 且u.level=v.level-1, 其中level表示结点位于文档树中的层次。
2 多分支路径查询一般算法
本文将多分支查询一般算法称为算法pathjoins, 其基本思想是:首先对查询树进行编码, 将其拆分成由根结点到叶子结点的单路径, 并用pathstack算法[9]得到单路径查询结果, 然后将单路径查询结果利用结构连接算法进行匹配得到多分支查询结果。
为了在查询匹配算法中进行高效的路径连接, 我们对查询树各个结点采用了特别的编号方法。设查询树根结点的编号为“0”, 其孩子结点的编号由其父结点的编号和其属于其父结点的第几个孩子结点组成。如图3中“ACT”结点, 其父结点“PLAY”的编号为0, 且属于“PLAY”结点的第一个孩子结点, 因此结点“ACT”的编号为01。结点“PGROUP”属于PLAY的第二个孩子结点, 所以其结点编号为02。
下面以查询语句PLAY[/ACT[//SCENE[/SPEECH][/STAGEDIR]][//SPEECH[/SPEAKER][/LINE]]][//PGROUP[/PERSONA][/GRPDESCR]]为例, 说明算法pathjoins的执行过程。
(1) 将查询语句用查询树 (图3) 表示, 并对查询树进行编码, 同时按照查询树从左到右的顺序将多分支查询语句拆分成单路径查询条件, 如表1所示。
(2) 使用pathstack算法[9]得到所有单路径的查询结果。
(3) 利用结构连接算法进行单路径匹配得到分支路径的查询结果。
3 多分支路径查询算法MBPQ
3.1 算法思想
算法MBPQ同样是将多分支路径查询转化为单路径查询, 但是它与上述XML多分支查询算法的单路径匹配方法不同。其基本思想是:
(1) 将查询语句用查询树表示, 并对查询树进行编码, 同时按照查询树从左到右的顺序将多分支查询语句拆分成单路径查询条件。
(2) 执行pathstack算法[9]得到单路径的查询结果。
(3) 利用栈控制匹配过程, 按照查询树从左到右、自底向上的顺序匹配具有共同祖先结点的单路径查询结果, 从而得到多分支路经查询结果。
3.2 执行过程及举例说明
下面以查询语句PLAY[/ACT[//SCENE[/SPEECH][/STAGEDIR]][//SPEECH[/SPEAKER][/LINE]]][//PGROUP[/PERSONA][/GRPDESCR]]为例。说明算法MBPQ的执行过程。
(1) 将查询语句表示成查询树, 并进行编码, 如图3所示, 同时将多分支路径查询条件拆分得到单路径P1、P2、…、P6, 如表2所示。
(2) 执行pathstack算法[9]得到各个单路径的查询结果, 其单路径条数如表2所示。例如, P1在XML文档树中的查询结果有2条。
(3) 匹配具有共同祖先结点的单路径查询结果, 获得多分支路经查询结果。为了减少不必要的匹配, 我们利用栈控制匹配顺序, 按照查询树从左到右、自底向上的顺序进行匹配。匹配过程如下:若栈为空, 则第一条单路径入栈。在第i条单路径入栈之前, 首先比较其分支编号是否与栈中单路径的分支编号相同, 若相同则单路径继续入栈, 若不同, 则表明栈中的若干单路径具有共同祖先, 栈中单路径可以进行匹配。
栈中单路径匹配完毕后将分支结点编号的最后一个分支结点编号删除, 并记录下子树查询结果, 其余单路径出栈, 继续判定将要入栈单路径和栈顶单路径的分支结点编号, 步骤和上述步骤相同。所有单路径处理完毕后栈中保存着最后将要匹配的子树。
将栈中子树匹配得到多分支路径查询结果。以表2所示单路径为例, 首先PLAY (0) /ACT (01) //SCENE (011) /SPEECH (0111) , PLAY (0) /ACT (01) //SCENE (011) /STAGEDIR (0112) 入栈, 当第三条路径PLAY (0) /ACT (01) //SPEECH (012) /SPEAKER (0121) 将要入栈时, 其单路径中分支结点编号和栈顶单路径的单路径中分支结点编号不相同, 此时处理栈中的单路径, 处理完毕后可知有3个匹配子树, 记录下匹配子树, 栈中单路径除第一个入栈单路径以外其余单路径出栈, 将栈中单路径的分支结点编码中的最后一个分支结点编码删除, 即栈中单路径为PLAY (0) /ACT (01) //SCENE (011) /SPEECH (0111) , 分支结点编码为0, 01, 重复执行上述步骤直到单路径处理完毕, 栈中只留下PLAY (0) /ACT (01) //SCENE (011) /SPEECH (0111) , 分支结点编码为0, PLAY (0) //PGROUP (02) /PERSONA (021) 分支结点编码为0, 此时表明图3所示查询树的左子树和右子树已经查询完毕, 下面只要将左子树和右子树进行匹配得到最终的多分支查询结果, 匹配完毕可知图2的XML文档树中共有22个图3所示的查询子树。
3.3 算法MBPQ描述输入:查询树root;
输出:多分支查询结果。
算法描述:
4 实验及结果分析
为了验证算法MBPQ的效率, 我们利用VC++实现了算法MBPQ。实验环境为:Pentium Ⅳ1.60G CPU, 256MB内存, Windows 2000。实验数据为莎士比亚XML数据集[10]。
在实验中, 我们测试了莎士比亚XML数据集的10个分支查询语句, 查询语句如表3所示。对于多分支路径查询, 分别使用算法MBPQ和算法pathjoins进行查询。它们的查询效率如图4所示, 结果表明算法MBPQ的性能明显优于算法pathjoins。
由图4可以看出, 当由查询树拆分得到的单路径大于两条时, 算法MBPQ的执行效率要优于算法pathjoins, 如查询语句p3, p4, p5, p6, p7, p8, p9, p10;当查询树仅有一个分支结点, 即拆分得到两条单路径时, 如查询语句p1、p2, 算法MBPQ的执行效率和算法pathjoins差不多。
5 结束语
对XML文档实现多分支路径查询, 一般方法是将多分支路径拆分成若干个单路径, 对单路径分别进行查询, 然后再对单路径查询结果进行连接操作, 这样的算法效率低。而本文算法MBPQ为实现XML多分支路径快速查询提供了一种对单路径查询结果进行匹配的有效方法, 即利用栈匹配具有共同祖先结点的单路径查询结果, 从而大大提高了查询效率。
参考文献
[1]Kaushik R, Shenoy P, Bohannon P, et al.Exploiting Local Similarity forEfficient Indexing of Paths in Graph Structured Data[C]//10thInter-national Conference on Database Theory, San Jose, California, USA, 2002:129-140.
[2]Chen Q, Lim A, Ong KW.D (k) -index:An adaptive structural summa-ry for graph-structured data[C]//Proc.of the 2003 ACMSIGMOD In-tl.Conf.on Management of Data, San Diego, California, USA, 2003:134-144.
[3]Chung C, Min J, Shim K.APEX:An adaptive path index for XML data[C]//Proc.of the 2002 ACM SIGMOD Intl.Conf.on Management ofData, Madison, Wisconsin, 2002:121-132.
[4]Milo T, Suciu D.Index structures for path expressions[C]//7thInter-national Conference on Database Theory, Jerusalem, Israel, 1999:277-255.
[5]Quanzhong Li, Bongki Moon.Indexing and Querying XML Data forRegular Path Expressions[C]//Proceedings of the 27thVLDB Confer-ence, Roma, Italy, 2001:361-370.
[6]Roy Goldman, Jennifer Widom.DataGuide:enabling query formulationand optimization in semistructured databases[C]//23th InternationalConference on Very Large Data Bases, pages, Athens, Greece, 1997:436-445.
[7]Al-khalifa Bruno N, Koudas N, Srivastava D.Holistic Twig Joins:Opti-mal XML Pattern Matching[C]//Franklin M J et al Eds.Proceedingsof the 21thACM SIGMOD International Conference on Management ofData.Madison, Wisconsin, USA, 2002:310-321.S, Jagadish HV, Koudas N.Structural Joins:A Primitive for Efficient XML Query Pat-tern Matching.In:Hiong Ngu A H et al Eds.Proceedings of the 18thIEEE ICDE International Conference on Data Engineering.California, USA, 2002:141-152.
[8]Chien S Y, Vagena Z, Zhang Donghui, et al.Efficient Structural Joinson Indexed XML Document[C]//Papadias D et al Eds.Proceedings ofthe 28thVLDB International Conference on Very Large Database.HongKong, China, 2002:263-274.
[9]Bruno N, Koudas N, Srivastava D.Holistic Twig Joins:Optimal XMLPattern Matching[C]//Franklin MJ et al Eds.Proceedings of the 21thACM SIGMOD International Conference on Management of Data.Madi-son, Wisconsin, USA, 2002:310-321.
高效查询 第3篇
当愈来愈多的数据资料以XML为标准格式进行存储时,由于其格式的不同而导致传统的数据库及查询语法无法适用,如何以高效快捷的方式实现文件资料的转换与提取,成为XML发展的又一个重要方面。从2000年1月起W3C开始着手拟订一种XML数据库查询语言XQuery,该语言可实现条件查询、排序、连结、筛选、分类汇总等数据操作,具有条件表达式、分支语句、循环语句及排序子句等,还提供了一系列可用于求和、求平均数等运算的内置函数,这种语言利用了XPath的路径表达式实现对XML中的节点定位,无疑,这一标准一旦形成W3C正式建议,则将会对XML的进一步发展带来深远的影响。本文将就此查询语言作一分析探讨。
1 XML及其相关标准的概述
XML包含有三个要素:文档类型定义DTD(Document Type Definition)或XML大纲(XML Schema)、可扩展样式语言XSL(eX-tensible Stylesheet Language)和可扩展链接语言XLL(e Xtensible Link Language)。其中DTD及XML Schema定义了XML文件中的元素、元素的属性及元素与元素属性之间的关系并规定了XML文件的逻辑结构;XSL使数据与其表现形式相互独立;XLL描述了资源之间如何链接,可以从不同的方向进行遍历,并可将链接存储在独立于引用文档的数据库中。
W3C为XML制定了三个技术规范[1]:XSLT(XSL Transformations)、DOM(Document Object Model)和XPath(XML Path Language),其中XSLT的作用是将某种结构的XML文件转换为另一种结构的XML文档(含HTML文档);DOM则提供了一种功能强大的编程接口,使应用程序能够访问和更新XML文档的样式、结构及内容,这由支持DOM的解释器来实现,将可得到一个包含XML文档中所有元素的树状结构;XPath定义了一些可对XML文档中的数据进行“寻址”的表达式,其操作对象是XML树状结构中的节点,其中最重要的表达式称为“定位路径”(Location Path),在微软的msxml及IBM的xalan这两个支持XPath的软件系统中其运算对象是DOM的文档(Document)或节点(Node)。
这三者的典型应用关系可简述如下:利用XPath检索存放数据的XML DOM,得到需要查询的数据子集,进而利用DOM提供的接口控制XSLT中的模板,将检索出来的数据按照适当的方式显示在用户浏览器窗口内,另外,可以利用XPath寻址XML和XSLT DOM中的节点,然后通过DOM提供的编程接口对XML中的数据和XSLT模板中的参数进行动态修改[2]。
2 XQuery查询语言发展状况
XML的发展趋势将成为互联网上的通用数据库,实现平台无关化,且不依赖于机器类型,其数据结构的开放性使得数据的查询检索成为一个极其重要的领域。上述以XPath及DOM等为基础的应用还仅是一种初步的方法,尤其是DOM节点与XPath节点之间的一些不一致问题还有待解决。随着用XML存储、交换和表述信息的应用日益增多,人们对其研究也越来越深入,如何从XML数据源中准确有效地获取所需信息,也就变得越来越重要。目前已有的查询语言如XQL、XML QL、QUILT、XML GL、XPath、QOL、YATL、Lorel等一般具有较强的针对性,往往只适用于某种或少数几种数据类型的查询,为了适应XML的发展需求,XML通用查询语言的制定工作显得关键而重要。
W3C于2000年1月公布了第一版XML查询语言需求草案文件(XML Query Requirements W3C Working Draft),对XML的查询语言本身及XML查询数据模板、表示法的发展方向及使用环境等进行了规范,其制定原则是构建于W3C发展中的另一个标准规范XML Infoset之上并支持命名空间(Namespaces)的应用。它规定了查询的应用范围不应只限于单一的XML文档内,且应可基于文件的内容及结构对查询条件作出定义,从而实现在整个文件或部分内容中进行检索的目的,最终要求查询的结果可根据用户需求自动构造成新的XML文档[3]。目前该语言的最新版本是2002年11月15日发布的Xquery草案。
国际标准组织W3C的XML Query工作小组及XSL工作小组最近于2003年2月14日为XML的全文检索工作发布了两份草案文件,分别为XQuery and XPath Full-Text Requirements和XQuery and XPath Full-Text Use Cases。前者明确提出全文检索需能够处理XQuery/XPath文档模型中的示例且无须设计成类客户端的界面语言,若Xquery/Xpath Full-Text支持查询元素与属性名时,应能对元素内容、属性值等进行区分[4];后者则阐述了全文检索的实际应用,以范例形式说明了全文检索的各个功能。这一切牵涉到以全文标记化(tokenized)方法对XQuery和Xpath语言的扩充,基本机理是将一段文字逐字、逐标点地分成若干个标记(token),从而使相关位置上的单字能够参与检索运算,这样不仅能实现邻近单字的查找,而且还能对其它字元及字根的使用进行处理[5]。
3 XQuery分析及应用比较
3.1 XQuery描述
XQuery由Quilt所衍生而来,同时又从XPath和XQL中吸收了路径表示语法以适应层次结构文档的需要,融入了SQL中基于关键字系列子句的思想,为数据重建提供了类SQL的Select From Where模式,并吸取了OQL中由几种不同表达式全嵌套组成的功能语言概念。XQuery作为一种将查询表示成表达式的功能语言,可以完全嵌套,故而沿用了子查询的功能与用法。
XQuery语言的组成单位可称为查询模块(query modules),模块之间相互独立但多个模块可以用分号隔开同时使用并被合法解析,以下是XQuery中的表达式组成体系:
1)主要表达式(Primary Expressions):这是XQuery的基本单元,包括有字符、变量、函数调用及决定优先级的括弧使用,其中一个URL字符在定义上等价于一个字符串。
2)路径表达式(Path Expressions):其语法基于Xpath 1.0,这是一种以路径方式浏览XML文件的标记法,在路径表达式的开始处可指定文件中的一个特定节点或一个包含有其他子节点的父节点,再按照文件结构配合以XPath的语法以寻找出符合检索路径的数据。例如:document(“myxml.xml”)//chapter[2]//figure[caption=“SearchThisData”]。
首先是找到myxml.xml文件中的根结点,然后查找根节点内的第二个chapter子结点,最后检索出此chapter子结点中包含有caption元素且其值为SearchThisData的figure子结点。
3)序列表达式(Sequence Expressions):XQuery支持结构化运算及组合序列,序列指零或其他项目的有序集合,其中一个项目允许是一个单位值或一个节点。例如以下表达式构造了一个序列10、(1,2)、空序列()及(3,4):
序列表达式中的项目可以进行插入及移除操作。
4)算术表达式(Arithmetic Expressions):包括常见的加、减、乘、除及取模运算等。
5)比较表达式(Comparison Expressions):Xquery提供了4种比较表达式如数值比较、节点比较等,下例为一个返回结果为“假”的表达式,原因是每个结构化结点均具有自己的标识:
6)逻辑表达式(Logical Expressions):该表达式的组成形态为“AND”及“OR”中的两者之一,其运算结果总为TRUE或FALSE(除非出现错误例程)。
7)构造式(Constructors):Xquery提供该方法的用途在于利用查询结果生成一个XML结构的文件,以便于存储和调用。其中它提供了在数据模型[XQuery 1.0 and XPath 2.0 Data Model]中列出除命名空间(namespace)节点以外的每一种结构,另外,它还具有一种称为计算结构(computed constructor)的特殊形式,可以创建出一个文档节点或其中的某个元素及其属性。作为构造式中的重要类别———元素构造表达式(Element constructors),通常可实现查询时除对现有数据进行检索外,并可利用查询结果产生新的数据的功能,这种方法允许使用XML的标记法直接将元素包含于查询之中,也即允许以XML元素本身作为查询的表达式。在早期的Xquery草案版本中,它曾作为与上述逻辑表达式等相并列的一类表达式出现,新的版本将其归纳于Constructors构造式之中。
8)FLWOR表达式(FLWOR expressions):它由FOR、LET、WHERE、ORDER BY及RETURN等子句以特定顺序组合而成。早期版本中含有排序表达式(Sorting)这一类别,是指查询时有时需要控制输出数据的排列顺序,该子句可设定多个排序条件,并可附加升幂(Ascending)或降幂(Descending)两个关键字设定排序的方向。当时FLWOR表达式只是称为FLWR表达式,即不含有ORDER BY子句。该表达式第一部分中包含了FOR或LET子句,其值由一到多个变量组成,且变量的组成是其他表达式如路径表达式等。一个FLWOR表达式可能包括多个FOR或LET子句,并将由WHERE子句进行条件筛选并可通过ORDER BY子句进行排序,最终满足检索条件的结点数据才会包含于RETURN子句中。如下例所示,表示可列出设备(Equ)中制造商(Fac)为“沈阳某机械厂”并且于2001年购买的设备名称(Name):
9)无序表达式(Unordered Expressions):这一表达式在传统的数据查询语言中较少出现,而在定义XML查询规范时却有着极其重要的意义,这一表达式未列入早期版本,草案制定的过程中讨论增加了这一功能。WEB化下的检索对实现效率要求极高,故对于一些对排序根本无要求的返回结果若按照常规排序后输出将会增加服务器运算及响应方面的负担,以下是一个无序函数使用的示例(查询返回教师及所对应授课的课程代码):
10)条件表达式(Conditional Expressions):其基本语法为“if”“(“Expression1“)”“then”Expression2“else”Expression3,含义为首先判断Expression1条件式是否满足,为true则返回Expression2,否则返回Expression3。
11)限定表达式(Quantified expressions):在某些查询需求下,需测试是否全部或只有部份元素符合某个条件,Xquery为此专门提供了“some”及“every”表达式用來分別表示“部份”及“全部”的选择。下例使用“some”表示取得book中段落只要有包含sailing及windsurfing的Name元素:
同样,下例使用“every”表示取得book中每个段落均含有sailing的Name元素:
12)用于序列类型的表达式(Expressions on SequenceTypes):它通常作为一种附加的函数参数出现,用于instance of、typeswitch、cast、castable和treat表达式中。
13)确认型表达式(Validate Expressions):该表达式在早期版本中不列为主要类型,以下为用法示例:
W3C关于该表达式的说明中指出目前“{”及“}”括号的应用在嵌入式表达式的环境中还存在着一些问题。
3.2 应用示例
制定XQuery标准前W3C提出了针对XML查询的相关需求,其中一项提及XML查询语言应可实现在多个文档中实现关联性连结查询。以下以教师授课为例说明其实现过程,要求根据目录关联表产生课时安排文档,将教师与其授课信息以姓名、课程名为序排列输出。
首先建立三份XML文档:teachers.xml(教师信息表)、lessons.xml(课程信息表)、catalog.xml(课时安排目录表)。
teachers.xml中包含若干个
lessons.xml中包含若干个
catalog.xml中含有上述文档的关联属性,由若干个
以上示例显示了一个内部关联的数据表连结过程,实际上XQuery中与传统SQL语言相类似,同样也提供了外部关联的操作,如左关联、右关联等。
3.3 XSLT与XQuery的比较
XSLT于1999年成为一个W3C建议标准,具有根据相关模板中指定的数据转换方式对XML结构的文档进行输出样式处理的功能,但是,由于XSLT在表达式和模式方面运用了Xpath,而XPath是XQuery的一个子集,因此它一直与XQuery标准化进程一起被不断地修订完善。
XSLT与XQuery之间最显著的差别在于一个XSLT样式表(stylesheet)实际上是一个XML文档,通常与Xquery相比其缺陷是不易阅读且文档不够简洁。
XSLT和XQuery之间更重要的差异是执行模型,特别是指控制流方面。如果不去考虑Xquery中与众不同的数据类型,则它可认为是一种相对普通且含有显式控制流的程序语言。相反,一个XSLT样式表的执行受一个模板处理器控制,每个节点均与一套模板相匹配对应,并在当前节点的子节点上进行模板的递归调用。使用模式匹配方式执行应用通常是较为高效便捷的,但当运用其进行更为复杂的编程时,则会变得很不灵活而且代码冗长。
4 目前应用状况
尽管Xquery目前尚处于草案阶段,但因其有着良好的应用前景,故而传统大型数据库开发公司均在加紧制定各自的标准及规范以期实现对Xquery的支持。2002年3月Oracle发表了Java XQuery的原型标准,其中包含一个XQuery的Java API(称为JXQI)及一个使用命令行操作的界面。它参照了W3C的Xquery标准并加上Oracle的自定义功能,并致力于文档关联及XQuery用例(XQuery use cases)方面的支持。另外它还包含一个实验性质的JDBC式的Java API供XQuery使用,并可在SQL的查询结果上使用XQuery。Oracle最终希望能提供XQuery-based兼具SQL风格的查询语言,以供用户在Oracle数据库中对XML文档内容进行准确查询。
目前已商业化的软件产品有X-Hive公司发布的X-Hive/DB 3.0版本,其内置了XQuery引擎,并提供了转换或格式化XML文档的功能,可实现XHTML或PDF格式的转换。为符合用户需求,X-Hive/DB支持的XML公开标准包含XML 1.0、XQuery、XPath、XSL、XPointer、XLink、Xupdate及DOM.等。此外Ipedo Inc.公司研制的可以运行于Sun Solaris 7&8、Red Hat Linux(version 6&7)、Windows 2000或Windows NT平台上的Ipedo XML Database(目前版本2.0)是一套专门用以存储XML文档的数据库系统,其存储方式有別于传统关联式数据库,适合作为XML的內容管理平台。它以XML Schema、DTD来组织与分类文件以实现集中式的XML管理,使用W3C XQuery查询语言,并可由XML Schema或DTD建立用户自订的索引,同时还具有易于整合的特性。
5 结束语
随着XML技术的发展,各种数据格式之间的差异已逐渐地减少直至可能在未来实现统一化的数据平台。Xquery的标准制定就是为了解决各类广泛数据源的数据查询检索问题,这种全新的查询语言将会促进重要的数据技术变革,并将成为统一的数据交换媒介。
摘要：当愈来愈多的数据资料以XML为标准格式进行存储时,由于其格式的不同而导致传统的数据库及查询语法无法适用,该文分析了一种全新的XML查询语言XQuery,并对其在相关领域的应用作了介绍和比较。最后,对XQuery的发展前景作出展望。
关键词：XQuery,XML,XML查询语言
参考文献
[1]陈奇.XSLT、Xpath和DOM的应用研究[J].计算机工程,2003,29(3):14-15.
[2]World Wide Web Consortium.XML Path Language(XPath)Version1.0.http://www.w3.org/TR/1999/REC-xpath-19991116.W3C Rec-ommendation1999-11-16.
[3]World Wide Web Consortium.XQuery1.0:An XML Query Language.http://www.w3.org/TR/2002/WD-xquery-20021115/.W3C Working Draft2002-11-15.
[4]World Wide Web Consortium.XQuery and XPath Full-Text Requirements.http://www.w3.org/TR/xmlquery-full-text-requirements/.W3C Working Draft2003-02-14.
高效查询 第4篇
Dremel系统是谷歌开发的查询半结构化数据列存储数据库, 并公开了Dremel系统的基本工作原理。同时也是Google的“交互式”数据分析系统。可以组建成规模上千的集群, 处理PB级别的数据。Map Reduce处理一个数据, 需要分钟级的时间。作为Map Reduce的发起人, Google开发了Dremel将处理时间缩短到秒级, 作为Map Reduce的有力补充。Dremel作为Google Big Query的Report引擎, 获得了很大的成功。
海量数据存储是一个必然的趋势。然而数据如何的存储和查询, 尤其是当今非结构化数据的快速增长, 对其数据的存储, 处理, 查询。使得如今的关系数据库存储带来了巨大的挑战。分布存储技术是云计算的基础, 主要研究如何存储、组织和管理数据中心上的大规模海量数据.由于面临的数据规模和用户规模更加庞大, 在可扩展性、容错性以及成本控制方面面临着更加严峻的挑战。
针对这种情况, 如何快速的查询数据的问题, 本文提出了一种解决方案, 并对其进行实现验证。
1 HBase及相关简介
1.1 HBase数据库系统概述
HBase (Hadoop Database) , 是一个高可靠性、高性能、面向列、可伸缩的分布式存储系统, 利用HBase数据库技术可在廉价PC Server上搭建起大规模结构化存储集群。是Google Bigtable的开源实现, 类似Google Bigtable利用GFS作为其文件存储系统, HBase利用Hadoop HDFS作为其文件存储系统;Google运行Map Reduce来处理Bigtable中的海量数据, HBase同样利用Hadoop Map Reduce来处理HBase中的海量数据。Google Bigtable利用Chubby作为协同服务, HBase利用Zookeeper作为对应[1,5]。
1.2 HBase数据存储格式简介
HBase的数据模型可以定义为一种稀疏的、长期存储的、分布式的、多维排序的映射表。映射表中通过Row Key、Column Key以及时间戳来三维索引一个Cell, 每个Cell中存放着一个任意长度的字符串。HBase以行记录的形式将数据存放在表中, 每行由一个Row Key唯一标识并可以包含任意多个列。通常情况下, 一张表根据存放的数据量的大小被分割成一个或者多个称为Region的子表。一个HBase集群通常由一个Master和多个Region Server组成。每个Region Server管理一个或者多个由Master分配的Region, 而Master则负责维护每个Region的元信息以及Region和Region Server之间的映射关系。Region中的数据最终将被存放在Hadoop的多副本分布式文件系统HDFS中[6]。当访问某一行数据时, Client首先查询Master找出含有该行数据的Region对应的Region Server, 然后向该Server发送数据访问请求以访问指定的数据。
在物理上, 一个列簇成员 (列) 在文件系统上都是存储在一起。因为存储优化都是针对列簇级别的, 这就意味着, 一个列簇的所有成员都是用相同的方式访问的。通过Row Key和列名为唯一条件进行检索数据[7]。HBase的数据查询方式主要是Get和Scan两种方式, 具体的数据检索方法就不是这篇文章的范围, 因此就不再这里赘述了。
1.3 半结构化数据定义及特点
半结构化数据是数据的结构不规则或不完整。这类数据介于模式固定的结构化数据 (如关系库中的表元组和对象库中的类型对象) 和完全没有模式的无序数据 (如正文、声音、图像) 之间。是指那些既不是完全无结构的, 也不是传统数据库系统中那样有严格结构的数据。这一定义给出了半结构化数据的特点, 但是很不精确, 因为定义中“结构”的含义是非常模糊的。为确立一个明确的范围, 给出了数据以及半结构化数据的定义, 并提出了一种用待确定文法分析半结构化数据的方法[8]。
定义1 (数据) :数据可以看作是一个有序的流a1a2...an, 对数据的一个有序划分是指对a1a2...an的一个划分σ1, σ2, ..., σm, 它满足σ1, σ2, ..., σm, →a1a2...an。
定义2 (半结构化数据) :如果数据的结构所对应的语言无法用全局一致的上下文无关文法描述, 但是存在数据的一个有序划分, 对分割出来的每个分划, 利用前n个分划的语义信息, 可以得到第n+1个分划的局部一致的上下文无关文法, 则称之为半结构化数据[9]。
各个数据源上的格式和类型千差万别, 目前尚无统一的模型。
以硬盘监控信息记录格式为例即为半结构化的数据, 如图1所示 (required表示必须字段, optional为可选字段) 。
1.4 Dremel系统
Dremel系统是一个稳定的、可交互查询只读半结构化数据的查询分析系统。采用树状分层查询方式和列存储数据结构Big Table, 可以在一秒钟查询10多亿行数据。该系统可扩展到几千块CPU和支持PB级的数据查询分析, 在谷歌有成千上万的用户在使用。Dremel系统的基本原理是将记录进行拆分, 将属性相同的数据存储到独立的表中, 然后在查询的时候重新将记录根据所查询的条件所涉及到的表记录使用进行重新装载成一个新的半结构化数据记录。从而将不相关的列进行过滤掉, 减少查询的数据量。目的就是为了在查找的时候只查找条件相关的列, 即列对应得表。在数据结构变化频繁的半结构化数据, 使用此种方法将无关列数据过滤, 从而加快数据查找的速度[10]。
2 半结构化数据HBase数据存储以及查找方案
如何在最大化的保留数据之间的关联关系的前提下保存数据条件方便进行查找。因此我们这里就需要牺牲一定空间的条件来表示半结构化数据之间的关联性。需要一定的数据冗余。如图1所示我们将记录Rd1, Rd2进行拆分将属性相同的记录值使用同一张表进行保存, 然后将该节点的所有的父节点的信息保存在同一列簇的其他列中, 从而保持Rd1, Rd2记录之间的关系。
2.1 使用HBase数据库无损表示记录结构
数据存储的时候, 我们可以将每一列的值直接排列下来, 不用引入其他的概念, 也不会丢失数据。对于嵌套的结构, Key表示所属外, value表示其对应的值。由于可以我们可以看出来在数据存储的时候由于大量的关系使用Key来建立关系, 可以看到数据在很大程度的冗余。我们简称该类表为结构表。图2是数据在HBase数据库中实际的存储的格式。
表名的命名规则格式为record@各级节点名称。例如:IP地址数据的表示格式为record@ip。
伪代码如下:
初始化:将recorddata中数据读入到decoder中
2.2 数据查找
在Dremel系统中是对数据进行重新拼装后, 然后在对数据进行查找。造成了大量的中间数据, 还需要在查找结束后进行收回。而HBase使用图2的设计的表格式是做的一个物化视图, 可以根据查询条件多次查询, 并不需要再查询后销毁数据。由于HBase数据库不支持半结构化数据的查询, 因此在数据查询的时候还需要使用关系型数据的一些方法, 使用结果集的逻辑运算求出计算结果。在数据的分装原理上同Dremel系统类似。将半结构化数据的记录拆分, 将属性相同的数据进行集中存储。
2.2.1 直接查找数据
如果检索数据的条件只有一列的话, 那么直接查询单个表就可以实现。比如查询Avg Disk Bytes PerTransfer=1536的数量, 那么查询record@driver@avgdiskbytespertransfer表, 查询值等于1536的列的数量就可以实现了。
2.2.2 多条件的分步查找
如果检索数据的条件有多列而且条件之间通过and或者or进行连接。那么通过建立彼此条件间结果集之间的交、并、差之间的集合计算, 那么就可以计算出需要返回的数据。由于HBase是列存储数据库对复杂的条件查询暂不支持。我们举例如下:
例1:我们查询Avg Disk Bytes Per Transfer=1536且drivername=C的记录数。
那么我们就先从record@driver@Avg Disk BytesPer Write中查询出满足条件Avg Disk Bytes Per Write=1536的结果集R1, 然后再查询record@driver@drivername出满足条件drivername=C的结果集R2。然后进行交叉查询出满足条件的记录, 返回结果即使满足例1的结果集R5, 得到记录数。如图3所示。
如果查询条件之间用或条件, 那么就是使用公式R5= (R3∩ (R1∪R2) ) 。同理非条件的使用也同样遵循集合运算。我们从查询步骤上可以看出随着查询条件的增多查询的程序随之繁琐。
伪代码如下:
假设查找条件R1, R2…Rn, 那么各个条件查找的记录数为n (R1) , n (R2) …n (Rn) .那么查找的时间复杂度为:O (Min (n (R1) , n (R2) …n (Rn) ) * (∑ (n (R1) , n (R2) …n (Rn) ) -Min (n (R1) , n (R2) …n (Rn) ) ) 。其中Min (n (R1) , n (R2) …n (Rn) ) 表示所有的条件查找记录中记录数最小的记录, ∑ (n (R1) , n (R2) …n (Rn) ) -Min (n (R1) , n (R2) …n (Rn) ) 表示剩余记录数减去最小记录数的差。
如果查询条件位于半结构化数据节点的树结构节点的深度较深, 那么需要比较的Key比较多, 从而需要花费更多的查询时间。
2.2.2 查询系统的设计
在实际的查询中, 需要开发一个查询系统, 可以供所有的人员使用而不是仅仅通过上面的方式查询。那样的话就需要有一定的专业基础和逻辑思维能力。因此很有必要开发一个类似于以Big Table为列存储数据库为基础的Dremel系统。开发一个以HBase为基础的查询系统, 需要实现两个功能。
1.将类似的半结构化查询语言的语句转化成可以实现基础查询的语句, 然后对HBase数据库数据库查询。
2.将步骤1中的数据根据查询语句中的逻辑条件进行逻辑计算, 将逻辑运算的查找还是基于HBas的分布式查找性能。
大数据查找的数据挖掘擅长的是大数据量的数据查找而不是进行复杂的数据运算, 因此该查询系统的设计不需要设计复杂的数学计算而是分布式的大数据查找的优势。
3 实验结果与分析
本节将通过一系列的实验来验证上述提出的半结构化数据的列存储的应用方案以及可行性。从而证明提出的半结构化数据查询的可行性和高效性。
3.1 实验环境
使用HBase 0.95.1和Hadoop 1.1.2来进行实验, 并将其部署在4个物理节点上, 其中一个节点作为Master节点, 其余3个作为Slave节点, 每个节点含有3.40GHz CPU, 4GB内存以及500GB磁盘空间, 操作系统为64bit Red Hat Enterprise Linux 6, 网络带宽为1Gbps, 四个节点的机器部署在同一个局域网内。实验中主要参数的取值情况如表3所示默认情况下, 每个查询含有4个查询条件。
3.2 实验结果
实验1:在1个Master机器、1个Slave机器和1个Master机器、3个Slave机器的硬件条件下, 记录数为250万, 500万, 1000万的相同条件下, 加载1、2、4列的时间对比与性能对比
实验结果如图4所示:
这个实验得出结论:
结论1:当查询一列数据的时候, 查询消耗时间少。随着列的增多, 还需要做集合逻辑运算, 性能迅速的就落后了。
结论2:4节点的平均处理时间比2节点平均处理时间明显的减少。因此可以得出猜测随着扩展的计算机的规模增大也会减少时间。但随着规模的扩大性能可能随之下降, 还需要进行详细的性能测试。
结论3:记录的集合计算是昂贵的, 每个都可能导致执行耗时的增多。在其他数据集合的实验中看到的趋势大致相同。软件层 (在查询处理层之上) 最好被优化。互联网级别的海量数据集合可以做到很快速的扫描, 但想要花费更少的时间则很困难。
实验总结:由于HBase数据库并不支持树状结构的分层查询服务器, 而是采用Master-Slave体系结构。因此在处理数据的能力上远达不到Dremel系统。查询数据的能力达到PB级别还有很大的性能提升空间。
4 总结与展望
在大数据中很多的数据都是半结构化数据, 因此半结构化数据的处理和查询的提高能进一步发展大数据的应用价值。本方法在查询条件的结果集之间做做交、并、差之间的集合计算需要耗费时间比重比较大, 这个还需要进一步提高性能。如何能减少无关数据的查找, 之查找相关的数据、如何在数据的关联性和数据的查找的便捷性找到结合点是解决半结构化数据查找的关键。
目前大数据仅仅是发展的初步阶段, 作为大数据的处理功能HBase虽在存在着一定的弊端, 比如不能支持条件查询、不能支持Master Server的故障切换、不支持Slave节点的层次划等问题, 随着HBase数据库系统的日益完善, 功能会变得更加丰富, 这些比较高级的正被官方社区慢慢地添加进来。但是HBase作为主流的开源列存储数据的发展趋势锐不可当, 进一步发展现在有数据挖掘技术。
摘要：本文用以Dremel系统为基础解决在HBase系统下如何查询大量的半结构化数据。基本原理是进行先进行数据预处理将半结构化数据进行拆分, 将记录拆分成列使用表存储, 拆分之后保持原有之间的半结构化数据的树之间的上下层关系, 然后再查询的时候只查询条件相关的列, 然后做集合计算, 即可得到数据需要查询的结果, 从而节省了很多时间。