|
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
| |
|
DOI
|
|
|
|
10.1016/S0169-023X(97)00020-7
| |
|
Volume/pages
|
|
|
|
25
:3
(1998)
, p. 267-300
| |
|
ISI
|
|
|
|
000072788900002
| |
|
Full text (Publisher's DOI)
|
|
|
|
| |
|