Recursive query processing using graph traversal techniques
Estrella Pulido · 1996
This paper presents STARBASE, n new algorithm for recursive querypmcessittgondeductivedatabasesbaaedon the Chart Parsing algorithm.It is distinct from the other applicationsof parsing to deduction, namely Eartey Deduction and Ftoaenblueth's method, because it removes variabtes fmm literals snd extends the Chart Parsingengine to handte all possible variations in the pattern of arguments in the titerals of deduction rules.Like other tabling methods, STARBASE avoids redundant computation by storing and reusing partial results bu~in contrast with tbetw it does not depend on subsumption and uses syntactic equality checking, instead.Because STARBASE takes a skmgly graph-oriented view of both the database and the deduction tules, 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 tesults show that STARBASE, even in prototype fo~lies witbin the performance range of the most advanced existing systems.