Недавно я вышла из отпуска по уходу за ребенком. Получилось так, что я попала на одно собеседование, на должность программиста. Заранее оформила резюме и отправила по почте. К моему удивлению, собеседование превратилось в университетский экзамен. Мне дали тест, потом 2 задачи, а, после разговора, еще одно задание. Хотелось еще сказать, что когда я пришла, человека, с которым была назначена встреча, почему-то не оказалось на месте. Собственно, про последнее задание я и хотела рассказать.

Задание: Представить нагруженный направленный граф в виде реляционной базы данных

Мое решение простое, и, как мне на тот момент показалось, самое очевидное. В ориентированном графе две сущности: вершины и ребра. Следовательно в нашей базе будет две таблицы, которые будут связанны между собой связями один-ко-много.

Честно говоря, когда мой собеседник предложил мне представить ориентированный граф в виде одной таблицы, которая будет содержать в себе матрицу инцидентности, я была немного удивлена. Его база-таблица должна была содержать в себе четыре поля: id — ключевое поле, номер начальной вершины, номер конечной вершины и вес ребра. Записать, конечно, все можно, и отправить в табличку, однако реляционной базой данных это не будет. Так как «Реляционная база данных — база данных, основанная на реляционной модели данных.» А реляционная модель данных в свою очередь включает несколько компонентов, в том числе и теорию  нормализации, о которой обязательно рассказывают всем в университете. Предложенный вариант ни коим образом не удовлетворяет даже первой нормальной форме. В предложенной базе (таблице) будет не атомарный атрибут — вершина графа, так как у вершины графа есть вес и характеристика (начальная или конечная). Я уж не буду говорить о том, что реализация алгоритмов удаления, добавления и изменения вершины достаточно проблематична.

Придя домой, я подтвердила свой вариант решения данной задачи несколькими источниками, с которыми вы можете ознакомится (1,2).

Данная задача очень проста для IT-специалиста со стажем. Очень жаль, что в наших IT-компаниях ведут собеседования такие «высококвалифицированные специалисты». Не удивительно, что мало хороших программных  продуктов пишется в России…