We demonstrate the power of object identities (oids) as a database query la
nguage primitive. We develop an object-based data model, whose structural p
art generalizes most of the known complex-object data models: cyclicity is
allowed in both its schemas and instances. Our main contribution is the ope
rational part of the data model, the query language IQL, which uses olds fo
r three critical purposes: (1) to represent data-structures with sharing an
d cycles, (2) to manipulate sets, and (3) to express any computable databas
e query. IQL can be type checked, can be evaluated bottom-up, and naturally
generalizes most popular rule-based languages. The model can also be exten
ded to incorporate type inheritance, without changes to IQL. Finally, we in
vestigate an analogous value-based data model, whose structural part is fou
nded on regular infinite trees and whose operational part is IQL.