Publication
Title
Merging graph-based and rule-based computation: the language G-log
Author
Abstract
In this paper we discuss the merging of two different computation paradigms: the fixpoint computation for deductive databases and the pattern-matching computation for graph-based languages. We show how these paradigms can be combined on the example of the declarative, graph-based, database query language G-Log. A naive algorithm to compute G-Log programs turns out to be very inefficient. However, we also present a backtracking fixpoint algorithm for Generative G-Log, a syntactical sublanguage 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 interesting 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.
Language
English
Source (journal)
Data & knowledge engineering. - Amsterdam
Publication
Amsterdam : 1998
ISSN
0169-023X
Volume/pages
25:3(1998), p. 267-300
ISI
000072788900002
Full text (Publisher's DOI)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
Affiliation
Publications with a UAntwerp address
External links
Web of Science
Record
Identification
Creation 01.03.2012
Last edited 14.06.2017
To cite this reference