Ограничение уникальности не действующее на записи с определённым значением колонки

Воспользуемся тем фактом, что индексы в Oracle не хранят значения если весь ключ NULL и с ключом NULL может быть сколько угодно значений. Создадим такой уникальный функциональный индекс который для deleted=0 даст сами значения для полей, а для 1 даст для всех NULL.

create unique index emp_uniq on emp(
  decode(deleted,0,dept,NULL),
  decode(deleted,0,theme,NULL),
  decode(deleted,0,date,NULL)
);

Можно сделать поле deleted целочисленного типа. Тогда процедура "удаления" может выглядеть где-то так

UPDATE emp e
  SET e.deleted =
    (SELECT max(deleted) + 1
     FROM emp i
     WHERE i.dept  = e.dept
       AND i.theme = e.theme
       AND i.date  = e.date)
WHERE e.empid = in_empid;

И можно делать unique constraint по четырём полям

---

Если приложение ждёт от базы данных только 0 или 1 в поле deleted, можно это решить используя представление или запрос в хранимой процедуре, возвращающей данные.

SELECT 
  e.empid, e.empname, e.dept,
  e.theme, e.date,
  case e.deleted when 0 then 0 else 1 end deleted
  FROM emp e;