I know in the one database we have is that we have a product ID that is sequential.
Then we also have calculation fields that is based on the product ID and other factors. (that would just be a concatenation: category & productID) If there isn't a category chosen yet the product ID would still be calculated, and it would look the same as the product ID until the category is chosen.
You can keep the primary product ID, but mainly use the new calculation field for relationships.
And if the calculation field is to slow there is another field that is static (a text or number field) which is updated whenever the field is needed. Also, it is updated in a server script that runs in the middle of the night.