An optimization method for XML twig query

被引：0
作者：
He Z. [1 ]
Wang H. [2 ]
Liao H. [3 ]
机构：
[1] College of Computer Science and Technology, Civil Aviation University of China, Tianjin
[2] College of Computer and Remote Sensing Information Technology, North China Institute of Aerospace Engineering, Langfang
[3] College of Computer, Beijing University of Technology, Beijing
来源：
International Journal of Performability Engineering | 2018年 / 14卷 / 10期
基金：
美国国家科学基金会;
关键词：
Hot-trace compilation; Partial evaluation; Twig query; XML data;
D O I：
10.23940/ijpe.18.10.p8.23092319
中图分类号：
学科分类号：
摘要：
XML tree pattern query, also known as Twig query, is the core operation in XML query processing. In the research of the Twig query algorithm, TreeMatch is considered to be one of the best algorithms because it reduces the generation of intermediate results. However, in the core operation getNext of the TreeMatch algorithm, there are many calculations that depend only on Twig mode. This redundant duplicate calculation affects the performance of the TreeMatch algorithm when there are many getNext calls. In order to further improve the algorithm, this paper proposes a Twig query optimization method based on partial evaluation and hot-trace compilation. This method takes Twig mode as an invariant to perform partial evaluation and translates query requests into a Twig query machine instruction sequence. The duplication calculation of the Twig pattern during the query process is avoided, and the process of interpretation of the instruction sequence of the query machine is optimized by using the hot trace compilation technique. The comparison experiment shows that the optimization method based on partial evaluation and hot-trace compilation can increase the efficiency of twig query by 20% to 60%. © 2018 Totem Publisher, Inc. All rights reserved.
引用
收藏
页码：2309 / 2319
页数：10
相关论文
共 16 条
  • [1] Bruno N., Srivastava D., Koudas N., Holistic twig joins: Optimal XML pattern matching, Proceedings of The 2002 ACM SIGMOD International Conference on Management of Data, pp. 310-321, (2002)
  • [2] Qin L., Yu J.X., Ding B., Twiglist: Make twig pattern matching fast, Proceedings of International Conference on Database Systems for Advanced Applications, pp. 850-862, (2007)
  • [3] Lu J., Ling T.W., Bao Z., Wang C., Extended XML tree pattern matching: Theories and algorithms, IEEE Transactions on Knowledge and Data Engineering, 23, 3, pp. 402-416, (2011)
  • [4] Jones N.D., An introduction to partial evaluation, ACM Computing Surveys, 28, 3, pp. 480-503, (1996)
  • [5] Inoue H., Hayashizaki H., Wu P., Nakatani T., Adaptive Multi-Level Compilation in A Trace-based Java JIT Compiler, ACM SIGPLAN Notices, 47, 10, pp. 179-194, (2012)
  • [6] Aho A.V., Lam M.S., Sethi R., Ullman J.D., Compilers: Principles, Techniques and Tools (Second Edition), pp. 338-339, (2014)
  • [7] Bala V., Duesterwald E., Banerjia S., Dynamo: A transparent dynamic optimization system, Proceedings of The ACM SIGPLAN Notices, 46, 4, pp. 41-52, (2011)
  • [8] Bebenita M., Brandner F., Fahndrich M., Logozzo F., Schulte W., Tillmann N., Et al., SPUR: A Trace-based JIT Compiler for CIL, ACM Sigplan Notices, 45, 10, pp. 708-725, (2010)
  • [9] Bondorf A., Improving Binding Times without Explicit CPS-conversion, Proceedings of The 1992 ACM Conference on Lisp and Functional Programming, pp. 1-10, (1992)
  • [10] Tahraoui M.A., Pinel-Sauvagnat K., Laitang C., Boughanem M., Kheddouci H., Ning L., A survey on tree matching and XML retrieval, Computer Science Review, 8, pp. 1-23, (2013)
12