G-LOG - A GRAPH-BASED QUERY LANGUAGE

In this paper we introduce G-Log, a declarative query language based o n graphs, which combines the expressive power of logic, the modeling p ower of complex objects with identity and the representation power of graphs. G-Log is a nondeterministic complete query language, and thus allows the expression of a large variety of queries. We compare G-Log to well-known deductive database languages, and find that it is the on ly nondeterministic and computationally complete language that does no t suffer from the copy-elimination problem. G-Log may be used in a tot ally declarative way, as well as in a ''more procedural'' way. Thus, i t provides an intuitive, flexible graph-based formalism for nonexpert database users.