Methods, apparatus, and articles of manufacture to encode auxiliary data into relational database keys and methods, apparatus, and articles of manufacture to obtain encoded data from relational database keys are disclosed. An example method to encode auxiliary data into relational data includes generating a code comprising a plurality of groups and representative of auxiliary data, determining incremental values for the plurality of groups, generating a first key based on the code, and generating a subsequent key by modifying the first key based on the value of the first key and the incremental values.