A Decorrelation Method Based on XQA Query Algebra
-
摘要: 介绍了一种用于支持复杂XML数据查询优化的XML查询代数XQA以及用于实现XQuery语言的中间语言FXQL,进而提出了一种基于XQA代数的去除相关性方法(de-correlation),通过查询重写引入连接运算的方法,使得人们有可能更多地利用高性能的连接算法来提高查询效率.在扩展了广义表结构的XDM数据模型的基础上,这种查询重写通过FXQL语言的程序变换方法来实现,易于与各种函数式语言编译优化技术相互结合.实验结果证明了该方法的有效性.Abstract: XQA(an XML Query Algebra), as well as a intermediate functional language named FXQL(a Functional XML Query Language) for implementation of XQuery language, is introduced to support optimizing for complex XML query.Furthermore, a decorrelation method base on XQA is put forward, which helps to use efficient Join algorithms to speed up query execution by rewriting the nested XML query with Join operator.Based on an extended XDM model with list structure, the query rewriting is implemented by a program transformation on FXQL program and easy to be combined with the various optimizations for functional language.Resultsof experiments demonstrate the effect of this optimization.
-
Keywords:
- XML /
- query language /
- auery algebra /
- decorrelation
-
-
[1] SCOTT B,DON C,FERN NDEZ M,et al.XQuery 1.0:An XML Query Language[EB/OL].MIT/CSAIL,USA:W3C,[2008-01-14].http:∥www.w3.org/TR/xquery/.
[2] 孟小峰,王宇,王小锋.XML查询优化研究[J].软件学报,2005,17(10):2069-2086.MENG Xiao-Feng,WANG Yu,WANG Xiao-Feng.Research on XML query optimization[J].Journal of Software,2005,17(10):2069-2086.(in Chinese) [3] ZHANG X,RUNDENSTEINER E.XAT:XML algebra for rainbow system[R/OL].Worcester,USA:WorcesterPolytechnic Institute,[2008-01-14].http:∥davis.wpi.edu/dsrg/Old/TECH-REPS/tech-wpi-cs-02-24-xat.ps.
[4] WANG S,RUNDENSTEINER E,MANI M.Optimization of nested xquery expressions with orderby clauses[C]∥Proceedings of the 21st international Conference on Data Engineering Workshops.Amsterdam,Netherlands:Elsevier SciencePublishers B.V.,2007:303-325.
[5] JAGADISH H,LAKSHMANAN L,SRIVASTAVA D,et al.TAX:a tree algebra for XML[C]∥Revised Papers From the8th international Workshop on Database Programming Languages,Lecture Notes In Computer Science.London,UK:Springer-Verlag,2001:149-164.
[6] FERN NDEZ M,SIM ON J,SUCIU Dan,et al.A data model and algebra for XML query[R/OL].NJ,USA:AT&TLabs,[2008-01-14].http:∥homepages.inf.ed.ac.uk/wadler/papers/xquery-algebra/xquery-algebra.html.
[7] BEERI C,TZABAN Y.SAL:an algebra for semistructured data and XML[C]∥Proceeding of the 2nd ACM SIGMODWorkshop on the Web and Databases.Philadelphia,Pennsylvania,USA:ACM Press,1999:37-42.
[8] GRINEV M,KUZNETSOV S.Towards an exhaustive set of rewriting rules for XQuery optimization:BizQuery experience[C]∥Proceedings of the 6th East European Conference on Advances in Databases and information Systems,Lecture Notes InComputer Science.London,UK:Springer-Verlag,2002:340-345.
[9] BRANTNER P,HELMER P,KANNE C,et al.Full-fledged algebraic XPath processing in natix[C]∥Proceedings of the21st International Conference on Data Engineering.Washington,DC,USA:IEEE Computer Society,2005:705-716.
[10] MAY N,HELMER S,MOERKOTTE G.Nested queries and quantifiers in an ordered context[C]∥Proceedings of the20th International Conference on Data Engineering.Washington,DC,USA:IEEE Computer Society,2004:239-250.
[11] 孟小峰,罗道锋,蒋瑜,等.OreintXA:一种有效的XQuery查询代数[J].软件学报,2004,15(10):1648-1660.MENG Xiao-feng,LUO Dao-feng,JIANG Yu,et al.OrientXA:an effective xquery algebra[J].Journal of Software,2004,15(10):1648-1660.(in Chinese)
计量
- 文章访问数: 10
- HTML全文浏览量: 0
- PDF下载量: 7
下载:
