《XQuery语言的发展》PPT课件.ppt

XQuery语言的发展,“计算机科学与技术的发展”讲座廖湖声计算机学院软件系,什么是XQuery语言,标准的XML数据查询语言预备知识1、XML语言网络数据交换和数据共享的标准平台无关、XML数据库2、XPath语言支持XML数据查询3、XQuery语言支持XML数据查询、XML文档构造支持函数式程序设计、XML数据更新,一、XML语言,XML语言可扩展标记语言（eXtensibleMarkupLanguage）为数据交换和数据共享提供平台无关的数据格式简例信息安全专业的学生物理老师考试通知4月2日早8点在3教402室考试,文档声明,文档内容,为什么使用XML语言,网络应用系统的重要问题跨网络数据传输、数据共享跨平台不同的软件系统、硬件系统网络数据交换和数据共享的重要问题不同的数据格式和语义异构数据不同的开发平台和开发语言异构环境网络应用中需要统一的数据表示候选者HTML语言网页编制（仍不规范）XML语言简单、可扩展、事实上的标准重要性计算机网络和应用系统无处不在，都要使用XML数据,1.1XML语言结构,基本结构XML声明文档首行元素内容可嵌套属性name=“value”CDATA文本数据注释处理指令应用领域声明专用定义标记tag标记=命名空间:局部名namespace:localname命名空间：解决语义异构问题自描述性：以标记说明内容的语义,简例2：Books.xml,EverydayItalianGiadaDeLaurentiis200530.00HarryPotterJK.Rowling200529.99,XQueryKickStartJamesMcGovernPerBothnerKurtCagleJamesLinnVaidyanathanNagarajan200349.99LearningXMLErikT.Ray200339.95,XML文档树,文挡节点,bookstore,book,book,title,title,price,39.95,EverydayItalian,1.2XML数据类型,数据类型的描述工具DTD（DocumentTypeDefinition）XMLSchema正规式类型系统用途描述应用领域的数据组织检查XML数据的合法性（良构性）数据查询请求（查询语句）的优化数据查询和处理算法的优化,DTD的案例,在XML文档中引用DTD文件的方法,用正规式描述元素类型,元素属性名称、类型描述,必需属性,可选属性,必须是文本,XMLSchema的案例,类型的定义,命名空间定义,元素类型的说明,最多出现次数,正规式类型系统,案例：BookStoreType:=bookstore(BookType*)BookType:=book(title,author+,year,price)结构类型名:=正规式特点XML类型的抽象描述，形成理论模型支持合法性算法的分析与设计三种类型描述的比较：DTD：简单、实用、不灵活XMLSchema：功能强大、可扩展正规式类型系统：支持理论分析,1.3XML语言的应用扩展,扩展的用途专用领域内的通用数据格式基本方法规定应用领域的命名空间按照应用领域的专业词汇来设计专用的标记（Tag）按照应用领域的信息组织来设计专用的数据类型（DTD/XMLSchema）从而可以用XML语言描述应用领域的数据目标形成支持网络应用的领域专用语言支持跨网络的专用数据共享和数据交换借助XML合法性检查来检查应用数据的合法性,几个应用领域的扩展XML语言,WSDL：Web服务描述语言SMIL：同步多媒体集成语言SVG：可缩放矢量图像标记语言MathML：数学标记语言BSML：生物信息序列标记语言HRMML：人力资源管理标记语言MusicML：音乐标记语言AML：天文数据标记语言CML：化学标记语言。,XML相关技术,W3C中文教学网站相关技术XMLDOM-XML文档对象模型XPath-简易XML查询语言XSLT-XML数据变换语言XQuery-XML查询语言（编程语言）XLink-XML链接语言（支持超级连接）XPointer-XML指针语言（指向XML片段）XForm-下一代HTML表单语言。,二、XPath语言,XPath：XML数据查询语言查询XML文档中的数据元素、属性XPath表达式指定文档路径，获得节点集类似于文件系统的路径绝对路径例：/book选择根的所有book子孙节点相对路径例：（相对于当前节点）bookstore/book选择bookstore的所有book子节点bookstore/title选择bookstore中所有title子孙节点,XPath表达式,条件查询/bookstore/book1第一个book节点/bookstore/bookprice35.00价格大于35的book节点/title*有属性的title节点常用符号/父子关系/祖孙关系.当前节点.双亲节点属性*匹配所有元素查询步的计算四则运算、关系运算、逻辑运算following、preceding-sibling等13种轴操作last()、position()等100多个函数,查询步轴操作:节点测试谓词*,轴操作：Axis当前节点和所选节点的关系，如：attribute、ancestor节点测试：nodetest指定节点种类，如：tag、*、node()、text()谓词：predicate存在条件，如：title、*选择条件，如：price35、last()5简化条件，如：position()=2简写为2案例ancestor-or-self:bookcount(author)2child:*/child:price可简写为*/price,三、XQuery语言,XQuery语言：标准的XML查询语言SQL语言是标准的关系数据库查询语言XQuery语言是XML数据的“SQL”语言特点：包含XPath语言（数据模型、运算符和函数）支持XML文档的查询和构造可构造XHTML网页、XML文档提供选择结构、有限的循环结构、自定义函数支持函数式程序设计（无赋值语句）,查询例：XQuery简例,for$xindoc(books.xml)/bookstore/bookwhere$x/price30orderby$x/titlereturn$x/title结果LearningXMLXQueryKickStart针对XPath查询结果的选择、排序和重组核心：FLWOR表达式,HTML网页的构造例,书店for$xindoc(books.xml)/bookstore/bookorderby$x/titlereturnlet$t:=data($x/title),$c:=data($x/category)return$t.分类:$c说明let提供局部变量定义（改善可读性、避免重复计算）计算结果和字符串的隐式连接,基于自定义函数的程序设计例,declarefunctionlocal:sumPrice($sitem()*)asxs:decimalif(fn:empty($s)thenreturn0elsereturn$s1+local:sumPrice(fn:subsequence($s,2);(:函数的调用:)let$s:=for$bindoc(books.xml)/bookstore/bookreturndata($b/price)returnlocal:sumPrice($s),XQueryAPIforJava（XQJ）,为Java程序中使用XQuery语言提供统一的编程接口与XML数据源连接准备和提交XQuery查询将查询结果作为XML数据处理进行XML数据处理和数据集成处理XQuery语言的各种实现应符合XQJ规范基于不同数据源的查询引擎不同平台的XQuery引擎,XQJ使用例,XQDataSourcexqd=newDDXQDataSource();/创建数据源XQConnectionxqc=xqd.getConnection();/建立连接XQPreparedExpressionxqp=xqc.prepareExpression(/准备“declarevariable$idasxs:stringexternal;”+/外部变量声明“doc(orders.xml)/orderid=$id”);/XQuery查询表达式XQSequencexqs;xqp.bindString(newQName(“id”),“174”,null);/绑定变量XQSequencexqs=xqp.executeQuery();/执行首次查询xqs.writeSequence(System.out,null);。xqp.bindString(newQName(“id”),“267”,null);/绑定变量xqs=xqp.executeQuery();/执行再次查询xqs.writeSequence(System.out,null);xqc.close();,四、XQuery语言的发展,XML数据更新功能全文检索功能Web软件开发功能动态网页开发功能分布式软件开发目标：发挥XQuery语言简洁、描述能力强等说明型语言的特点，在更多的领域代替传统的Java/JavaScript语言,1、扩展XML数据更新功能,XQueryUpdateFacility1.0(W3C)数据更新表达式插入、删除、修改。程序例for$bindoc(“Library1.xml”)/booklet$c:=doc(“Library2.xml”)returninsert$binto$c/library将文件Library1.xml中的所有book元素作为孩子节点插入到文件Library2.xml的library元素中。,2、扩展全文检索功能,XQuery1.0andXPath2.0Full-Text在XML文本数据库中检索信息检索查询例for$bscore$s相关度in/books/bookcontentftcontains包含(“website”weight0.2)&权重（与）(“usability”weight0.8)权重where$s0.5orderby$sdescendingreturn$b/title$s,3、扩展Web软件开发功能,脚本语言过程化程序设计XQueryScriptingExtension1.0(W3C)XQueryP支持变量声明、赋值语句、控制结构支持Web网络软件的开发Web服务的开发（无状态/有状态）HTTP服务器软件的开发支持会话session、实体entity,4、扩展动态网页开发功能,客户端浏览器DOM的访问和操作事件响应机制和响应函数外部资源的访问代替JavaScript语言服务器端用XQuery开发Servlet程序支持会话的访问与更新Servlet转发和Servlet包含代替JSP语言,5、扩展分布式软件开发功能,支持分布式计算网络进程之间的消息传递工作流系统Web服务组合支持并行计算多线程并行计算线程之间的消息传递同步控制机制,XQuery语言实现技术的研究,“计算机科学与技术的发展”讲座廖湖声计算机学院软件系,为什么研究XQuery语言的实现技术,XML数据的广泛应用巨大的XQuery使用需求XML数据处理的特殊性半结构化数据：关系数据库技术不适用查询性能问题：执行速度、空间开销、跨网络处理方法问题：轴操作、树模式查询XQuery语言的特殊性XML查询语言、XML数据处理函数式语言、图灵完全网络应用开发的潜在应用价值,一、XQuery语言的实现方法,解释系统XQuery查询引擎支持XQuery程序的执行（XML数据查询）可嵌入到各种开发环境中（如：XQJ）编译系统将XQuery程序翻译成低级语言描述的目标程序如：XQuery程序Java字节码程序目标程序完成XML数据查询等计算特殊的优化问题XML数据查询、轴操作、函数式语言。,XQuery语言的各类实现需求,不同应用场景XML数据库XML数据集成（跨网络）XML流数据处理移动环境下的XML数据处理研究目标提高查询速度、减少空间开销、减少传输的开销约束条件数据密集型（数据量大）非结构化数据和特殊的查询模式动态生成查询请求内存有限,基本框架,翻译/类型检查,XQuery程序,中间代码,中间代码,查询结果,目标程序,程序优化,解释执行,目标代码生成,XML文档,编译后端,编译前端,解释引擎,中间语言,各种中间语言（研究对象）基本运算+复合运算结构+查询原语语法简洁、便于实现、便于优化如：XQuery核心语言、FXQLXQuery程序例for$itemindoc(items.xml)return$item/news_itemXQuery核心语言程序例for$iteminfn:doc(items.xml)return$item/descendant-or-self:node()/child:element(news_item),编译系统,翻译/类型检查,XQuery程序,中间代码,中间代码,目标程序,程序优化,目标代码生成,编译后端,编译前端,目标程序+标准函数库,查询结果,XML文档,XQuery编译实现的特殊性,动态编译的需求在网络应用中，查询请求跨网络传输，是动态生成的编译本身必须有较高的执行效率Hotspot编译技术选择经常使用、且效率低的子查询（Hotspot）解释执行过程中，编译Hotspot部分后执行研究课题Hotspot选择策略（静态分析、动态分析、代价）解释/编译支撑框架、运行环境,二、XML查询代数,提供数据模型序列广义表元组的集合提供一组算子通过算子的组合运算来表示查询请求将复杂的查询请求分解为独立的算子支持查询的逻辑优化进行查询重写（等价变换）改变算子的组合关系,XQA查询代数,数据模型（基于广义表）Node|Atom|*主要代数算子foreach(a1,a2,a3,f)f(a1),f(a2),f(a3)flat(a1,b1,b2,c1)a1,b1,b2,c1filter(1,2,3,4,f)wheref(a)=eq(a%2,1)1,3some(2,4,6,f)wheref(a)=gt(a,5)true,将XQuery程序翻译为查询代数,将XQuery请求for$xindoc(“order.xml”)/itemwheredata($x/title)=“computer”return$x/price翻译为查询代数flat(foreach(filter(child(doc(“order.xml”),”item”),f1)f2)wheref1($x)=eq(data(child($x,“title”),“computer”)f2($x)=child($x,“price”),基于查询代数的优化案例,消除不必要的计算flat(foreach(1,2,3,f)wheref(a)=add(a,a)优化为foreach(1,2,3,f)wheref(a)=add(a,a)减少中间数据（谓词下移）filter(foreach(1,2,3,f1),f2)优化为foreach(filter(1,2,3),f3),f1)wheref3(a)=f2(f1(a)常见的优化（类似于数据库查询优化）投影上移、排序上移消除相关性、用连接代替笛卡儿积计算,XML查询代数的研究课题,查询代数的设计需求针对不同的应用场景支持XML查询的特殊操作查询计划的实现需求中间语言表示便于查询计划的生成逻辑优化的实现需求XML数据查询的逻辑优化方法程序设计语言的编译优化方法基于类型的优化方法,三、XML数据编码和索引,使用需求高性能的数据访问（避免遍历树）结构关系的判断（祖孙、父子、兄弟）数据化方式（NumberSchemas）Dietz编码、Dewey编码、PRiTree编码。索引图方式（IndexGraphSchemas）DataGuide索引、A(k)-index、T-index。,Dietz编码案例,（1，8）,（3，1）,（2，2）,（4，5）,（5，3）,（6，4）,（8，6）,（7，7）,节点编码（pre,post）祖孙关系的判定方法如果pre(x)pre(y)并且post(y)post(x)，则x是y的祖先,Dewey编码案例,祖先关系的判定：如果c(x)是c(y)的前缀，则x是y的祖先,1,1.1.1,1.1,1.2,1.2.1,1.2.2,1.3.1,1.3,DataGuide索引,文挡节点,bookstore,book,book,auther,title,price,39.95,EverydayItalian,bookstore,title,price,title,auther,book,四、树模式查询,树型的XML数据查询即：Twig查询、小枝查询、树模式匹配嵌套在各种XML查询语句如：XPath查询、XQuery查询Twig查询例XPath查询:/A/BC/DTwig查询的表示节点：标记双线：祖先单线：父子兄弟次序无关,A,C,B,D,Twig查询例,查询结果a2,b2,d2,c3,a2,b2,d3,c3,a3,b1,d1,c1,a4,b3,d2,c2,a4,b3,d3,c2,c1,d1,b3,d2,c3,a4,b2,b1,b4,d4,a3,a2,a1,d3,c2,XML文档例,A,C,B,D,XQuery程序中的树模式,for$iindoc(“order.xml”)/item$dindoc(“catalog.xml”)/product$rindoc(“prices”)/prices/pricelist/prodwhere$i/num=$d/numberand$d/number=$r/numreturn,name,product,number,树模式查询的算法（1）,基于标记流的结构连接算法标记流：相同标记的节点有序排列避免遍历整个XML树采用Dietz、Dewey等编码判断结构关系MPMGKN、StackTree等算法采用归并连接方法，完成树中每个边的二元结构连接采用适当的连接次序，逐步选出符合条件的匹配结果优缺点查询效率高、但保存过多的中间结果,树模式查询的算法（2）,整体树模式匹配PathStack、TwigStack采用Dietz等区域码Twig2Stack、TwigList采用不同的中间结构VisualJ、TJStack采用Dewey基本策略按照路径查询，将查询结果组织在特定的中间结构中完成所有路径查询后，连接中间结构中的数据，形成最终的结果各种算法采用不同的路径查询方法和中间结构优缺点效率高，已经成为主流方法不支持流数据处理，中间结构有改进的余地,树模式查询的算法（3）,顺序模式匹配方法（Sequence）ViST、PRIX等基本方法对数据和查询进行编码，形成序列通过子序列的模式匹配来完成查询整理匹配结果，构造查询结果优缺点不需要连接中间结构中的数据仅支持有序树模式查询、索引开销大,树模式查询的算法（4）,导航式模式匹配（Navigation）适用流数据处理YFilter、XPush、SXSI等基本方法基于XPath的自动机或基于类型的树自动机深度优先、顺序处理XML节点判断能否为自动机接收优缺点无需编码和索引、支持流数据处理会遍历过多的XML节点,基于NFA自动机的XPath查询处理（YFilter）,针对多个XPath查询Q1:/a/bQ2:/a/cQ3:/a/b/cQ4:/a/cQ5:/a/*/*/c,a,b,Q1,c,Q3,c,Q2,*,c,Q4,c,Q5,Twig查询模式的扩展研究,扩展功能允许节点的弱绑定（可有可无）支持返回节点的指定（部分节点）支持有序树模式支持兄弟关系、前驱后续关系的描述支持图模式查询查询条件谓词求值（存在、条件、下标）算法研究XML查询专用算法研究热点,不同应用场景的Twig查询研究,XML数据库专用编码方法、专用查询索引整体查询算法：Twig2Stack、TwigList。关系库支撑的XML数据库专用编码方法、专用查询索引专用查询算法XML流数据处理自动机方法面向海量数据、有限内存空间移动环境中间结果的空间分析,五、XML物化视图,XML视图建立在若干XML文档数据上的虚拟XML文档采用XML查询语言来定义常见：XPath视图、XQuery视图物化视图（缓存）按照视图的定义，获得查询结果，并保存。语义缓存：视图定义+物化视图用途直接用于响应查询请求，提高查询效率。,XQuery查询例,for$iindoc(“order.xml”)/item$dindoc(“catalog.xml”)/product$rindoc(“prices”)/prices/pricelist/prodwhere$i/num=$d/numberand$d/number=$r/numreturn选择物化视图V1=doc(“catalog.xml”)/product,重写后的XQuery查询,for$iindoc(“order.xml”)/item$dinV1$rindoc(“prices”)/prices/pricelist/prodwhere$i/num=$d/numberand$d