【作者】 李国良； 冯建华； 塔娜； 周立柱；

【Author】 Li Guoliang,Feng Jianhua,Ta Na,and Zhou Lizhu (Department of Computer Science and Technology,Tsinghua University,Beijing 100084)

【机构】 清华大学计算机科学与技术系；

【摘要】 XML Twig查询可以表示为一棵带标签结点的查询树,它支持对XML文档进行带有复杂谓词的结构或内容查询.整体(holistic)Twig查询算法已经被公认为XML查询处理的核心算法.很多学者提出了大量基于整体处理的XML Twig查询算法.但是目前已有的算法都只适合于Twig查询中不包含通配符*的情况.而当Twig查询中包含通配符*时,一种简单而直接处理的方法就是,把被查询文档中的所有结点元素都读到内存,把这些元素都看做通配符*所对应的元素,然后按照已有的算法进行查询处理.显然这种方法是不合理的,它会增加大量I/O开销.因此提出了一种有效地支持通配符*的查询处理算法.通过建立索引,它可以很好地处理含通配符*的查询,从而可以避免不必要的I/O开销.最后通过实验证明,算法要明显好于已有的算法.更多还原

【Abstract】 An XML twig query,represented as a labeled tree,is essentially a complex selection predicate on both structure and content of an XML document.Twig query matching has been identified as a core operation in querying tree structured XML data.A number of algorithms have been proposed recently to process a twig query holistically.Those algorithms,however,only deal with twig queries without starwildcard. A naive approach that first loads all elements of the queried XML document into memory and then gets the result using the existing algorithms is obviously not optimal in most cases.In this paper,a novel holistic-processing algorithm for twig queries with star-wildcard is studied without loading all elements into memory.In particular,to avoid involving too much I/O,efficient indices are introduced for the method.it is shown that using indexes can significantly improve the performance for matching twig queries with star-wildcards,and the method is much more efficient than the niave ones.更多还原