On instance-completeness for database query languages involving object creation

In 1978 Bancilhon and Paredaens introduced a notion of completeness for relational database languages on instance-level. Their criterion was subsequently calledBP-completeness. Since then, it was used frequently in the context of other database models. However, its application in the context of languages involving object creation appears to raise some serious problems. In this paper, we use the graph-oriented object database model GOOD as a framework to propose an alternative formulation of the BP-completeness criterion, adapted to the context of languages involving object creation.