Начинающий велосипедистЕсть отдел и у него есть начальник(1 и только 1).
Где хранить информацию о начальнике отдела? Создать поле "Начальник" в таблице отделы или создать дополнительную сущность-связь "Начальник-отдел". Только вот смысл в ней, если начальник может быть только 1 и в будущем это не изменится (будем считать так).
Какую именно задачу или проблему вы хотите решить проектируя ваш "велосипед"?
О какой "информации" о начальнике отдела идет речь?
Для чего нужно в отделе указывать начальника?
Вы сознательно заложили ограничение, упростив модель вашей системы. Чем вызвано такое ограничение оно помогает вам решить вашу задачу проблему или вы через это упрощение пытаетесь ограничить границы задачи (проблемы).

Сегодня нужно указывать только начальника, завтра зама начальника, послезавтра зам-зама и т.д. В конце концов все сведется к тому что необходимо хранить список всех сотрудников подразделения (отдела).
А если один начальник (сотрудник) руководит несколькими отделами то с точки зрения вашей структуры это будут разные сотрудники.
Классически выделяют такие сущности:
Сотрудники
Роли (или должности) сотрудников
Подразделения
Сотрудники подразделений (перечень сотрудников в разрезе подразделения и роли, с учетом временной составляющей)

В рамках каждой из сущностей обеспечивается хранение необходимых атрибутов.

Начинающий велосипедистDinamo,

Возникли сомнения, что у отдела нет атрибута "Начальник" и быть не может (или может?). И поэтому его обязательно нужно хранить в другой таблице. А вот как обосновать или опровергнуть я не знаю.

Ну а по поводу всего Вами написанного я полностью согласен.
Да в моем варианте у отдела атрибут начальник не является обязательным, есть отдельная сущность (таблица) для представления списка сотрудников отдела по ролям.
Однако ничто вам не мешает такой атрибут добавить если на то есть явная необходимость или, например, требование заказчика.