Hi Mark, also chiming in, because I am very surprised by what you are stating.
As said above, the needed operation could be performed in a single call in a standard SQL database. Is there not a way for you to arrange it so that it is a single API call, and then a batch update behind that ?
Relationships are set in a different way than regular column properties. As a result, a single query to update relationships for multiple primordial objects is not possible.