|
|
|
@inproceedings{DBLP:conf/cikm/Pulido96,
author = {Estrella Pulido},
title = {Recursive Query Processing Using Graph Traversal Techniques},
booktitle = {CIKM '96, Proceedings of the Fifth International Conference on
Information and Knowledge Management, November 12 - 16, 1996,
Rockville, Maryland, USA},
publisher = {ACM},
year = {1996},
pages = {37-44},
ee = {db/conf/cikm/Pulido96.html, http://doi.acm.org/10.1145/238355.238371},
crossref = {DBLP:conf/cikm/96},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
This paper presents STARBASE, a new algorithm for recursive query processing on deductive databases based on the Chart Parsing algorithm. It is distinct from the other applications of parsing to deduction, namely Earley Deduction and Rosenblueth's method, because it removes variables from literals and extends the Chart Parsing engine to handle all possible variations in the pattern of arguments in the literals of deduction rules.
Like other tabling methods, STARBASE avoids redundant computation by storing and reusing partial results but, in contrast with them, it does not depend on subsumption and uses syntactic equality checking, instead.
Because STARBASE takes a strongly graph-oriented view of both the database and the deduction rules, the evaluation of a query on a database can be viewed as a process of traversing paths in the graph representing the database.
A prototype of the STARBASE system has been implemented in the C language. Performance results show that STARBASE, even in prototype form, lies within the performance range of the most advanced existing systems.
Copyright © 1996 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.