用后缀树构造XML路径字典加快路径查询评价速度

Constructing Path Dictionary with Suffix Trees to Speed up XML Query Evaluation

后缀树的重要性可以为多年来学术界对它总是有新的发现而印证 .它的结构简单 ,但可以在线性的时间里解决许多复杂的问题 ,被大量的使用在字符串及树的模式匹配中 .对于 XML标准 ,有很多基于关系库和对象库的索引技术和查询方案被提出来 ,我们试图给出一种基于后缀树进行路径导航的查询机制 :用后缀树构造 XML 路径字典加速路径查询评价速度 .我们提出可以在线地建立一个 trie树的后缀树 .讨论了 XML路径字典中的后缀树建树算法 ,阐述了整个索引方案和查询机制 ,并探讨了包括 RPE在内的它所支持的各种查询操作 .XML

The importance of suffix trees is underlined by the fact that new discoveries about them are made repeatedly in the past years. Despite their simple data structure, many complicated problems can be solved in linear time with suffix trees. So they are intensively employed in pattern matching on string and trees. A lot of indexing and query schemes for XML data have been proposed, but the problem of efficiency still remain as an open research issue. We construct a suffix tree of a trie which encodes all path patterns exists in the XML database. We call this suffix tree the XML path dictionary. We can see that the XML path dictionary can be construct on line. The algorithm to construct such an XML path dictionary is given. The whole indexing method and query processing scheme are presented as well as the discussion for processing RPE. The XML path dictionary is used to speed up path query.