Secondo me il problema è un altro: mettendo data come attributo della relazione, non forzi il constraint richiesto dalle specifiche.
Quello che devi fare, ispirandoti a quanto scritto, ad esempio, qui:
http://cisnet.baruch.cuny.edu/holowczak/classes/4300/week3.html#relationship_construct, è spezzare la relazione molti a molti tra medici e reparti in due relazioni 1:N con un entità intermedia.
In particolare, devi avere un'entità che possiamo chiamare slot con identificatore data e identificatore esterno preso da reparto tramite una relazione 1:N (uno slot contiene 1 e 1 solo reparto, ma un reparto può essere in più slot); in questo modo hai degli slot identificati univocamente dalla coppia data reparto, che puoi collegare con una relazione 1:1 o 1:N a medico, a seconda che un reparto possa avere 1 solo o più medici nello stesso giorno.