面向PSTP查询的高效处理算法  

PSTP Query Oriented Efficient Algorithm

作　　者：周军锋[1] 李义国[1] 郭景峰[1] 

机构地区：[1]燕山大学信息科学与工程学院,河北秦皇岛066004

出　　处：《计算机科学与探索》2010年第11期1039-1048,共10页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金No.61073060;60673136~~

摘　　要：在使用"不完全结构的约束查询(PSTP查询)"从XML文档中获取信息时,用户可以根据自身对XML文档结构的熟悉程度,在查询表达式中灵活地嵌入结构约束条件,从而满足完全不了解、完全了解及了解部分结构信息的各种用户的查询需求。提出一种基于扩展Dewey编码的查询处理算法,可以在仅扫描一遍元素的情况下,处理任意形式的PSTP查询。不同数据集上的实验结果表明,EDPS算法在处理twig查询、不包含"*"结点的PSTP查询及包含"*"结点的PSTP查询时,综合性能明显优于已有方法。When extracting desired information from XML data using partially specified twig pattern（PSTP） queries,users can flexibly use any structural constraints to specify their query semantics,therefore different kinds of users,i.e.,users who fully understand or know nothing about or partially understand the underlying structure,can search desired information based on their familiarity with the structure of given XML data.This paper proposes an efficient algorithm,EDPS,based on extended Dewey labeling scheme to process a general PSTP query efficiently by just scanning the input elements only once.The experimental results on various datasets indicate that this method performs significantly better than existing ones when processing twig queries,PSTP queries without ＂＊＂ nodes and PSTP queries containing ＂＊＂ nodes.

关 键 词：可扩展标示语言 PSTP查询 扩展Dewey 

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