Title
Merging graph-based and rule-based computation: the language G-log Merging graph-based and rule-based computation: the language G-log
Author
Faculty/Department
Faculty of Sciences. Mathematics and Computer Science
Publication type
article
Publication
Amsterdam ,
Subject
Computer. Automation
Source (journal)
Data & knowledge engineering. - Amsterdam
Volume/pages
25(1998) :3 , p. 267-300
ISSN
0169-023X
ISI
000072788900002
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Affiliation
University of Antwerp
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.
E-info
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000072788900002&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000072788900002&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000072788900002&DestLinkType=CitingArticles&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
Handle