I would like to get notification whenever something is deleted or upserted in semarchy. UPSERT is working nicely since notification's payload has attribute EntityNames which tells us where the data has changed its status. But when DDJ-job finishes it does not return any value for EntityNames. What would be suggested way to get notification of deleted records?

You are correct that the default Delete jobs do not fill in the parameter EntityName with a value. Typically this is because each delete job is specific to only the entity that triggered the Delete. In the Job Notification Policy, you could use the JobName parameter, which will include the entity name.