J. Paredaens et al., MERGING GRAPH-BASED AND RULE-BASED COMPUTATION - THE LANGUAGE G-LOG, Data & knowledge engineering, 25(3), 1998, pp. 267-300
Citations number
26
Categorie Soggetti
Computer Science Artificial Intelligence","Computer Science Information Systems","Computer Science Artificial Intelligence","Computer Science Information Systems
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.