Username   Password       Forgot your password?  Forgot your username? 


An Optimization Method for XML Twig Query

Volume 14, Number 10, October 2018, pp. 2309-2319
DOI: 10.23940/ijpe.18.10.p8.23092319

Zhixue Hea, Huan Wangb, and Husheng Liaoc

aCollege of Computer Science and Technology, Civil Aviation University of China, Tianjin, 300300, China
bCollege of Computer and Remote Sensing Information Technology, North China Institute of Aerospace Engineering, Langfang, 065000, China
cCollege of Computer, Beijing University of Technology, Beijing, 100124, China

(Submitted on July 15, 2018; Revised on August 10, 2018; Accepted on September 12, 2018)


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%.


References: 16

                1. N. Bruno, D. Srivastava, and N. Koudas, “Holistic Twig Joins: Optimal XML Pattern Matching,” in Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, pp. 310-321, 2002
                2. L. Qin, J. X. Yu, and B. Ding, “Twiglist: Make Twig Pattern Matching Fast,” in Proceedings of International Conference on Database Systems for Advanced Applications, pp. 850-862, 2007
                3. J. Lu, T. W. Ling, Z. Bao, and C. Wang, “Extended XML Tree Pattern Matching: Theories and Algorithms,” IEEE Transactions on Knowledge and Data Engineering, Vol. 23, No. 3, pp. 402-416, March 2011
                4. N. D. Jones, “An Introduction to Partial Evaluation,” ACM Computing Surveys, Vol. 28, No. 3, pp. 480-503, September 1996
                5. H. Inoue, H. Hayashizaki, P. Wu, and T. Nakatani, “Adaptive Multi-Level Compilation in A Trace-based Java JIT Compiler,” ACM SIGPLAN Notices, Vol. 47, No. 10, pp. 179-194, October 2012
                6. A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, “Compilers: Principles, Techniques and Tools (Second Edition),” 2nd Edition, China Machine Press, pp. 338-339, 2014
                7. V. Bala, E. Duesterwald, and S. Banerjia, “Dynamo: A Transparent Dynamic Optimization System,” in Proceedings of the ACM SIGPLAN Notices, Vol. 46, No. 4, pp. 41-52, May 2011
                8. M. Bebenita, F. Brandner, M. Fahndrich, F. Logozzo, W. Schulte, N. Tillmann, et al., “SPUR: A Trace-based JIT Compiler for CIL,” ACM Sigplan Notices, Vol. 45, No. 10, pp. 708-725, October 2010
                9. A. Bondorf, “Improving Binding Times without Explicit CPS-conversion,” in Proceedings of the 1992 ACM Conference on Lisp and Functional Programming, pp. 1-10, January 1992
                10. M. A. Tahraoui, K. Pinel-Sauvagnat, C. Laitang, M. Boughanem, H. Kheddouci, and L. Ning, “A Survey on Tree Matching and XML Retrieval,” Computer Science Review, Vol. 8, pp. 1-23, May 2013
                11. H. Su and H. Liao, “The Research and Implementation of Partial Evaluation for XQuery,” Journal of Beijing University of Technology, Vol. 35, No. 12, pp. 1710-1717, December 2009
                12. C. F. Bolz, A. Cuni, M. FijaBkowski, M. Leuschel, S. Pedroni, and A. Rigo, “Allocation Removal by Partial Evaluation in A Tracing JIT,” in Proceedings of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, pp. 43-52, January 2011
                13. S. B. Scholz, “Partial Evaluation as Universal Compiler Tool: Experiences from the SAC Eco System,” in Proceedings of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program Manipulation, pp. 95-96, January 2014
                14. G. T. Sullivan, D. L. Bruening, I. Baron, T.Garnett, and S. Amarasinghe, “Dynamic Native Optimization of Interpreters,” in Proceedings of the 2003 Workshop on Interpreters, Virtual Machines and Emulators, pp. 50-57, June 2003
                15. A. Gal, C. W. Probst, and M. Franz, “HotpathVM: An Effective JIT Compiler for Resource-constrained Devices,” in Proceedings of the 2nd International Conference on Virtual Execution Environments, pp. 144-153, June 2006
                16. M. Vandercammen, J. Nicolay, S. Marr, J. de Koster, T. D’Hondt, and C. de Roover, “A Formal Foundation for Trace-based JIT Compilers,” in Proceedings of the 13th International Workshop on Dynamic Analysis, pp. 25-30, October 2015


                              Please note : You will need Adobe Acrobat viewer to view the full articles.Get Free Adobe Reader

                              Download this file (IJPE-2018-10-08.pdf)IJPE-2018-10-08.pdf[An Optimization Method for XML Twig Query]271 Kb
                              This site uses encryption for transmitting your passwords.