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.