When I had to do this, I did it by fetching everything that was not in the new incoming data set, and deleting everything in the fetch result. This only works if you have a unique ID of some kind-- if your A, B, and C are unique IDs that don't have duplicates.
The code would be something like
First get all unique IDs found in the new incoming data. If the incoming objects are in an array called restResults, this would be something like
NSArray *incomingUniqueIDs = [restResults valueForKey:@"uniqueID"];
Do a fetch request with a predicate that finds everything with a unique ID that not in the new list. Something like
NSPredicate *predicate = [NSPredicate predicateWithFormat:@"uniqueID not in %@", incomingUniqueIDs];
Then perform the fetch and delete everything it finds. In your case, on the second time around, incomingUniqueIDs would contain A and C. The predicate would fetch only B. You'd delete that entry, and you'd be done.