文章基本信息

标题：Fast Reachability Test on DAGs for XML
本地全文：下载
作者：Yusaku Nakamura ; Tetsuya Maita ; Hiroshi Sakamoto 等
期刊名称：人工知能学会論文誌
印刷版ISSN：1346-0714
电子版ISSN：1346-8030
出版年度：2007
卷号：22
期号：2
页码：191-199
DOI：10.1527/tjsai.22.191
出版社：The Japanese Society for Artificial Intelligence
摘要：We propose an efficient algorithm for deciding the reachability between any nodes on XML data represented by connected directed graphs. We develop a technique to reduce the size of the reference table for the reachability test. Using the small table and the standard range labeling method for rooted ordered trees, we show that our algorithm answers almost queries in a constant time preserving the space efficiency and a reasonable preprocessing time.
关键词：XML ; range labeling ; ancestor-descendant relationship ; directed acyclic graph