G-Log: a deductive language for a graph-based data model
Peter Peelman · 1993
This Ph.D. thesis contains a study of G-Log, a new deductive database query language for a graph-based complex object data model. The aim for developing this database language was to examine the problems that arise when one tries to integrate the computation power of the logic programming paradigm, the modeling power of the object-oriented paradigm, and the representation capabilities of graphs. Before presenting G-Log, some languages and features on which this language is based are introduced: the Datalog language, the use of negation in Datalog, complex objects, classes, and object identifiers. G-Log has a fully graph-based data model. As well schemes as instances are directed labeled graphs. G-Log programs consists of G-Log rules, a graph-based type of logical implication rules. G-Log allows to express that rules have to operate together, by putting them in one G-Log set, and supports the sequencing of (sets of) rules. A construction is described to transform any first-order logic formula into an equivalent G-Log set. G-Log is a non-deterministic language with a minimal model semantics. We show that with this semantics, G-Log reaches the limit in expressive power: it can express every computable, generic database query. The language Generative G-Log, which is G-Log without negation in rule heads is very interesting, especially from a computational point of view. It is shown that any G-Log program can be transformed into an equivalent Generative G-Log program, and that the computation algorithm for Generative G-Log programs is a generalization of the standard fixpoint computation algorithm for Datalog programs. Finally, the decidability of a number of properties that have an impact on the computation of G-Log programs is investigated. It turns out that many properties are undecidable in G-Log but become decidable in Generative G-Log.