An Optimal Graph Traversal Algorithm for Evaluating Linear Binary-Chain Programs.

Yangjun Chen, Theo Härder: An Optimal Graph Traversal Algorithm for Evaluating Linear Binary-Chain Programs. CIKM 1994: 34-41

@inproceedings{DBLP:conf/cikm/ChenH94,
  author    = {Yangjun Chen and
               Theo H{\"a}rder},
  title     = {An Optimal Graph Traversal Algorithm for Evaluating Linear Binary-Chain
               Programs},
  booktitle = {Proceedings of the Third International Conference on Information
               and Knowledge Management (CIKM'94), Gaithersburg, Maryland, November
               29 - December 2, 1994},
  publisher = {ACM},
  year      = {1994},
  pages     = {34-41},
  ee        = {db/conf/cikm/ChenH94.html, http://doi.acm.org/10.1145/191246.191257},
  crossref  = {DBLP:conf/cikm/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Grahne et al. have presented a graph algorithm for a subset of recursive queries. This method consists of two phases. In the first phase, the method transforms a linear binary-chain program into a set of equations over expressions containing predicate symbols. In the second phase, a graph is constructed from the equations and the answers are produced by traversing the relevant paths. Here we describe a new algorithm which requires less time than the algorithm of Grahne et al. The key idea of the improvement is to reduce the search space that will be traversed when a query is invoked. Further, we speed up the evaluation of cyclic data by generating most answers directly in terms of the answers already found and the associated "path information" instead of traversing the corresponding paths as usual. In this way, our algorithm achieves a linear time complexity for both cyclic and non-cyclic data.

Copyright © 1994 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 4, CIKM, DOLAP, GIS, SIGFIDET, ..." and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An2-4 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Proceedings of the Third International Conference on Information and Knowledge Management (CIKM'94), Gaithersburg, Maryland, November 29 - December 2, 1994. ACM 1994
Contents

Online Edition

Citation Page