Object Identifiers, Keys, and Surrogates: Object Identifiers Revisited

Sound naming schemes for objects are crucial in many parts of computer science, such as database modeling, database implementation, distributed and federated databases, and networked and distributed operating systems. Over the past 20 years, physical pointers, keys, surrogates and object identifiers have been used as naming schemes in database systems and elsewhere. However, there are some persistent confusions about the nature, applicability and limits of these schemes. In this paper we give a detailed comparison of three naming schemes, viz. object identifiers, internal identifiers (often called surrogates) and keys. We discuss several ways in which identification schemes can be implemented, and show what the theoretical and practical limits of applicability of identification schemes are, independently from how they are implemented. In particular, we discuss problems with the recognition and authentication of identifiers. If the identified objects are persons, an additional problem is that object identification may conflict with privacy demands; for this case, we indicate a way in which identification can be combined with privacy protection.