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}
}
BibTeX
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.
CDROM Version: Load the CDROM "Volume 2 Issue 4, CIKM, DOLAP, GIS, SIGFIDET, ..." and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
BibTeX
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 BibTeX
Online Edition
Citation Page
BibTeX
Referenced by
- Yangjun Chen:
Speeding up the Counting Method by Computing Heritage Functions in Topological Order.
ADBIS 1997: 108-116
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
CIKM 1994 Proceedings, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:01:44 2009