Efficient XML Query and Update Processing Using A Novel Prime-Based Middle Fraction Labeling Scheme  

作　　者：Zunyue Qin Yong Tang Feiyi Tang Jing Xiao Changqin Huang Hongzhi Xu 

机构地区：[1]Department of Computer Science, Sun Yat-sen University, Guangzhou 510006, China [2]School of Computer Science, South China Normal University, Guangzhou 510631, China [3]College of Engineering and Science, Victoria University, VIC, 3011, Australia [4]School of software, Jishou University, Zhangjiajie 427000, China

出　　处：《China Communications》2017年第3期145-157,共13页中国通信（英文版）

基　　金：supported by the National Science Foundation of China(Grant No.61272067,61370229);the National Key Technology R&D Program of China(Grant No.2012BAH27F05,2013BAH72B01);the National High Technology R&D Program of China(Grant No.2013AA01A212);the S&T Projects of Guangdong Province(Grant No.2016B010109008,2014B010117007,2015A030401087,2015B010109003,2015B010110002)

摘　　要：XML data can be represented by a tree or graph and the query processing for XML data requires the structural information among nodes. Designing an efficient labeling scheme for the nodes of Order-Sensitive XML trees is one of the important methods to obtain the excellent management of XML data. Previous labeling schemes such as region and prefix often sacrifice updating performance and suffer increasing labeling space when inserting new nodes. To overcome these limitations, in this paper we propose a new labeling idea of separating structure from order. According to the proposed idea, a novel Prime-based Middle Fraction Labeling Scheme(PMFLS) is designed accordingly, in which a series of algorithms are proposed to obtain the structural relationships among nodes and to support updates. PMFLS combines the advantages of both prefix and region schemes in which the structural information and sequential information are separately expressed. PMFLS also supports Order-Sensitive updates without relabeling or recalculation, and its labeling space is stable. Experiments and analysis on several benchmarks are conducted and the results show that PMFLS is efficient in handling updates and also significantly improves the performance of the query processing with good scalability.XML data can be represented by a tree or graph and the query processing for XML data requires the structural information among nodes. Designing an efficient labeling scheme for the nodes of Order-Sensitive XML trees is one of the important methods to obtain the excellent management of XML data. Previous labeling schemes such as region and prefix often sacrifice updating performance and suffer increasing labeling space when inserting new nodes. To overcome these limitations, in this paper we propose a new labeling idea of separating structure from order. According to the proposed idea, a novel Prime-based Middle Fraction Labeling Scheme（PMFLS） is designed accordingly, in which a series of algorithms are proposed to obtain the structural relationships among nodes and to support updates. PMFLS combines the advantages of both prefix and region schemes in which the structural information and sequential information are separately expressed. PMFLS also supports Order-Sensitive updates without relabeling or recalculation, and its labeling space is stable. Experiments and analysis on several benchmarks are conducted and the results show that PMFLS is efficient in handling updates and also significantly improves the performance of the query processing with good scalability.

关 键 词：XML data structure information order information information separation PMFLS labeling scheme 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]