MERGING GRAPH-BASED AND RULE-BASED COMPUTATION - THE LANGUAGE G-LOG

In this paper we discuss the merging of two different computation para digms: the fixpoint computation for deductive databases and the patter n-matching computation for graph-based languages. We show how these pa radigms can be combined on the example of the declarative, graph-based , database query language G-Log. A naive algorithm to compute G-Log pr ograms turns out to be very inefficient. However, we also present a ba cktracking fixpoint algorithm for Generative G-Log, a syntactical subl anguage of G-Log that, like G-Log, is non-deterministic complete. This algorithm is considerably more efficient, and reduces to the standard fixpoint computation for a sublanguage of Generative G-Log that is a graphical equivalent of Datalog. The paper also studies some interesti ng properties like satisfiability and triviality, that are undecidable for full G-Log and turn out to be decidable for sufficiently general classes of Generative G-Log programs.