Object identity as a query language primitive

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.