通信学报
通信學報
통신학보
JOURNAL OF CHINA INSTITUTE OF COMMUNICATIONS
2014年
7期
46-55
,共10页
可扩展标记语言%子树构建%ELCA%相关关键字节点
可擴展標記語言%子樹構建%ELCA%相關關鍵字節點
가확전표기어언%자수구건%ELCA%상관관건자절점
XML%subtree results construction%ELCA%RKN
构建结果子树是XML关键字查询处理的核心问题,其中求解与每个子树根节点相关的关键字节点是影响结果子树构建效率的重要步骤.针对已有方法不能正确求解基于ELCA(exclusive lowest common ancestor)语义的相关关键字节点(RKN,relevant keyword node)的问题,提出RKN的形式化定义及相应的RKN-Base算法.该算法通过顺序扫描每个关键字节点一次即可正确判断其是否为某个ELCA节点的RKN.针对RKN-Base不能避免处理无用节点的问题,提出一种优化算法RKN-Optimized,该算法基于每个ELCA节点求其RKN集合,从而避免了对无用节点的处理,降低了时间复杂度.最后,通过实验验证了所提算法的高效性.
構建結果子樹是XML關鍵字查詢處理的覈心問題,其中求解與每箇子樹根節點相關的關鍵字節點是影響結果子樹構建效率的重要步驟.針對已有方法不能正確求解基于ELCA(exclusive lowest common ancestor)語義的相關關鍵字節點(RKN,relevant keyword node)的問題,提齣RKN的形式化定義及相應的RKN-Base算法.該算法通過順序掃描每箇關鍵字節點一次即可正確判斷其是否為某箇ELCA節點的RKN.針對RKN-Base不能避免處理無用節點的問題,提齣一種優化算法RKN-Optimized,該算法基于每箇ELCA節點求其RKN集閤,從而避免瞭對無用節點的處理,降低瞭時間複雜度.最後,通過實驗驗證瞭所提算法的高效性.
구건결과자수시XML관건자사순처리적핵심문제,기중구해여매개자수근절점상관적관건자절점시영향결과자수구건효솔적중요보취.침대이유방법불능정학구해기우ELCA(exclusive lowest common ancestor)어의적상관관건자절점(RKN,relevant keyword node)적문제,제출RKN적형식화정의급상응적RKN-Base산법.해산법통과순서소묘매개관건자절점일차즉가정학판단기시부위모개ELCA절점적RKN.침대RKN-Base불능피면처리무용절점적문제,제출일충우화산법RKN-Optimized,해산법기우매개ELCA절점구기RKN집합,종이피면료대무용절점적처리,강저료시간복잡도.최후,통과실험험증료소제산법적고효성.